[m-dev.] Sorting results

[Ralph Becket]

>From Adrian Pellas-Rice on 07/02/2001 14:45:52
> > n       | sort  | fwds bwds rand
> > --------+-------+---------------
> > 1000    | merge |  200  200  200
> > 10000   | merge |  213  157  204
> > 100000  | merge |  242  272  294
>                                ^^^	
> A sudden-ish increase from 204 to 294?
> 
> > --------+-------+---------------
> > 1000    | heap  |   33  100   66
> > 10000   | heap  |   77  114  150
> > 100000  | heap  |  104  165  226
> > --------+-------+---------------
> > 1000    | quick |   50  100  100
> > 10000   | quick |  106  100  175
> > 100000  | quick |  145  152  255
> 
> At this 3-result stage, the heap and quick sorts seem to be enjoying
> logarithmic improvement (relative to list-merge-sort).  
> 
> On the other hand, the relative improvement of the merge sort would appear
> to be better than linear.  If put on the spot, I would explain the sudden
> improvement for the merge sort as a consequence of the n = 100 000 data
> set stressing the L1 cache while the n = 10 000 data set does not (as
> much).

What strikes me as most odd is that mergesort should be largely 
insensitive to the order of the input data, yet there's quite a
bit of variance.  I used time__clock//1 and converted the results
to milliseconds before computing the ratios (this was under linux).
I thought time__clock returned elapsed processor time for the process
(this is what the docs say), but that fails to explain the difference
in results on differently ordered data.

Ralph

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