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 <ndmitchell@gmail.com> wrote:
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.