[m-dev.] Sorting results

[Zoltan Somogyi]

On 07-Feb-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> HEAPSORT
> starting sorting benchmark on 1000 items over 5 iterations
> 5 x list__sort/1 on ascending sequence: 29ms
> 5 x list__sort/1 on descending sequence: 40ms
> 5 x list__sort/1 on randomized sequence: 50ms
> 5 x array__sort/1 on ascending sequence: 20ms
> list/array time = 145.00%
> 5 x array__sort/1 on descending sequence: 20ms
> list/array time = 200.00%
> 5 x array__sort/1 on randomized sequence: 20ms
> list/array time = 250.00%

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.

To ret trustworthy numbers, you have to repeat the experiments many more times.

> HEAPSORT
...
> starting sorting benchmark on 100000 items over 5 iterations
> 5 x list__sort/1 on ascending sequence: 10440ms
> 5 x list__sort/1 on descending sequence: 10250ms
> 5 x list__sort/1 on randomized sequence: 14880ms
...
> QUICKSORT
...
> starting sorting benchmark on 100000 items over 5 iterations
> 5 x list__sort/1 on ascending sequence: 10350ms
> 5 x list__sort/1 on descending sequence: 10050ms
> 5 x list__sort/1 on randomized sequence: 14950ms
...
> MERGESORT
...
> starting sorting benchmark on 100000 items over 5 iterations
> 5 x list__sort/1 on ascending sequence: 10210ms
> 5 x list__sort/1 on descending sequence: 10090ms
> 5 x list__sort/1 on randomized sequence: 15050ms

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?

> 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.

Zoltan.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------