[m-dev.] Sorting results

[Fergus Henderson]

On 08-Feb-2001, Adrian Pellas-Rice <apell at students.cs.mu.oz.au> wrote:
> 
> Hi, All.
> 
> > Tests were run on data sets of 1000, 10000 and 100000 elements comprising
> > of the numbers 1..N in (a) ascending order, (b) descending order and (c)
> > a random permutation.
> 
> [snip]
> 
> > 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?

That doesn't seem suprising to me.  The array version is doing
in-place update, whereas the list version probably does a lot of
dynamic memory allocation.  As `n' increases, the cost of garbage
collection becomes more significant.

Ralph, could you try this one in grade hlc.gc?
It would be interesting to see the difference.

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

Well, locality is the basic issue, I think.  It might be the L1 cache.
Or it might just be that for N=10000, the number of real garbage
collections for both the list and array versions is similar (perhaps
zero), but for N=100000, number of GCs for the list version is greater
than for the array version.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------