I've written little framework to work on. See sortbench.hs and
sortbench.pyattachments.
Furthermore, I checked Yhc's implementation of sort: it is indeed very fast:
[Tener@laptener sorting]$ python sortbench.py
Benchmark type: OnSorted
[1 of 1] Compiling Main ( sortbench.hs, sortbench.o )
Linking sortbenchOnSorted.bin ...
1/10
(...)
10/10
Total time: 171.392577887
Scaled vs best.:
('yhcSort', 1.0)
('sort', 4.1826933506099904)
('treeSort', 4.2466878529708207)
Benchmark type: OnRevsorted
[1 of 1] Compiling Main ( sortbench.hs, sortbench.o )
Linking sortbenchOnRevsorted.bin ...
1/10
(...)
10/10
Total time: 187.789487839
Scaled vs best.:
('yhcSort', 1.0)
('treeSort', 1.2973727012306746)
('sort', 1.3028663057478311)
Benchmark type: OnRandom
[1 of 1] Compiling Main ( sortbench.hs, sortbench.o )
Linking sortbenchOnRandom.bin ...
1/10
(...)
10/10
Total time: 289.231264114
Scaled vs best.:
('yhcSort', 1.0)
('treeSort', 1.1167200854190948)
('sort', 1.2050043053111394)
The above results are for 1000000 Ints x 10 runs, but I don't expect any
drastic changes in longer run. I leave the interpretation up to you.
I must also admit there are not quickCheck properties in the code. Maybe
someone will want to write some.
Christopher Skrzętnicki
On Mon, Mar 10, 2008 at 9:36 AM, Neil Mitchell
Hi
Can whoever picks this up please try the sort code from Yhc in their comparisons. In my benchmarks it ran up to twice as fast as the GHC code. http://darcs.haskell.org/yhc/src/packages/yhc-base-1.0/Data/List.hs
I think what we really need is first quickCheck and timing framework for measuring sorts. After we have decided what makes one sort faster/better than another, then is the time to start deciding what sort is the best one. Ian did some initial work on this:
http://www.haskell.org/pipermail/glasgow-haskell-users/2002-May/003376.html
Until the sort-check package is uploaded to hackage I think most people will find it hard to be convinced of one sort over another.