[Haskell-cafe] (flawed?) benchmark : sort

[Chaddaï Fouché]

2008/3/4, Krzysztof Skrzętnicki <gtener at gmail.com>:
> Thanks for improved code. My point was to measure which programming patterns
> are faster than the others so I can learn which ones I should use. However,
> the thing that is really bad is the fact, that even oneliner qsort_i is
> faster than library sort. Which is very different from what I've expected.
> My intuition is only best and fastest code goes to library, to the point
> that people can learn from it. It seems I was mislead.

I think you did not correctly got the point of my and Neil Mitchell's
message : you benchmarked those function on a completely random
sequences so qsort was at his best, but in the real world, most
sequences would have bias, and it is not infrequent at all to sort a
partially sorted (or reverse sorted) list... In this case the
performance of all your qsort are abysmal... Which is the reason the
old sort was replaced by the actual mergesort in the library. Try my
code (with 10000 elements for example), you'll see that sort is the
best on a sorted list, and that qsort is at least 60 times slower (on
10000, in fact it is degenerating in O(n^2)).

In the real world, the library maintainers decided it was ok to pay a
slight overhead in the case where the list to sort is really randomly
distributed since mergesort won so hugely over qsort in the pretty
frequent case (in programs) of lists which present regularities.

There is no sort which is ideal in all situations, but we can try to
get a sort that works well in all situations, and don't trash in
situations not so infrequent.

(On the other hand, don't expect libraries functions to always be the
best to use in your particular situation, they tend to be all-purpose
as we just saw and the maintainers prefer simple generic
implementations rather than complicated ones who could be slightly (or
even significantly) faster in some case)

-- 
Jedaï