more heap sort benchmark info

Stephen Weeks MLton@sourcelight.com
Thu, 21 Jun 2001 08:50:16 -0700


> Using this I can determine how long each  part  takes.   The  timings,  using
> 80000 elements, the biggest size he uses, are
> 
>     create initial array:   C       .020385 seconds
>                             MLton   .012050 seconds
> 
>     copy and sort:          C       .136650 seconds
>                             MLton   .191040 seconds
> 
> Note,  we  are  faster than C in the creating of the array, even though the C
> code doesn't do multiple allocations, it allocates the array  once  and  then
> fills it in a bunch of times.  I believe that the reason is that MLton, being
> no fool, has inlined the gen_random function, while gcc did not.  This causes
> 80,000  extra  function calls, and if each takes about .5 mics (longer than I
> would expect) then it would explain things.

I see .1 mics, not .5, which hopefully makes more sense to you.

> The real point to notice is that in the actual sorting, we are only about 40%
> slower  than  gcc.   This isn't good, but if you look at his graphs, it seems
> that MLton is 5 times slower.  Even given that the new  MLton  is  faster,  I
> have no explanation.

The only explanation I have at this point is double alignment, and that MLton
was lucky on Doug's machine and unlucky on yours.