[m-dev.] Sorting results

[Ralph Becket]

>From Zoltan Somogyi on 08/02/2001 02:50:14
> On 07-Feb-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> > HEAPSORT
> > starting sorting benchmark on 1000 items over 5 iterations
> > [...]
> 
> At this size, much of what you are measuring is pure chance. The times
above,
> 20ms to 50ms, are 2 to 5 quanta. That's why one of your other experiments
> got zero quanta. It is no coincidence that all the ratios look
suspiciously
> like round numbers.

The timings were collected using benchmarking__benchmark_det, so I suspect
the round numbers are an artifact of either that code or the underlying
timing mechanism.

I agree that with data sets this small the S/N ratio is too low; here are
the results for sorting 1000 items 1000 times:

starting sorting benchmark on 1000 items over 1000 iterations
1000 x list__sort/1 on ascending sequence: 6269ms
1000 x list__sort/1 on descending sequence: 5750ms
1000 x list__sort/1 on randomized sequence: 9120ms
1000 x array__sort/1 on ascending sequence: 1520ms
list/array time = 412.43%
1000 x array__sort/1 on descending sequence: 1370ms
list/array time = 419.71%
1000 x array__sort/1 on randomized sequence: 2400ms
list/array time = 380.00%

> Those three groups of numbers look to be derived from the same executable.
> Are they using the same list__sort/1 or not? If yes, why did you measure
> it three separate times?

Er, there were three distinct executables (shame...) each with a single
LOC difference specifying which array sort to use; the list tests were there
partly as a sanity check that nothing weird was going on, like getting
wall clock times as opposed to CPU times.

> > hlc really does the trick!  And a clear victory for mergesort
> > over quicksort, which rather flies in the face of the recieved
> > wisdom.
> 
> It flies in the face of received wisdom only if you received your wisdom
> from someone other than Richard O'Keefe, although the context differs
slightly
> from the one in which he made his point.

I'd understood Richard's advice to apply to list sorting, but either I got
it wrong or his advice is more widely applicable.

It would be interesting to code up SAMsort, but I ought to be getting on
with some work.  Next time I have a few minutes...

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------