Data.List.sort, not so good?

[Adrian Neumann]

Hello Haskell-Cafe,

lately I've been playing around with sorting. I discovered that  
Data.List.sort is not as optimized I thought. At least not for random  
lists. I think we should consider adding a Data.List.Sort package to  
hackage (Similar to Data.List.Split) that offers a wide variety of  
sorting algorithms.

I don't consider myself to be a very advanced Haskell programmer, but  
I could come up with a Mergesort that beats List.sort, time- and  
spacewise.

 > http://hpaste.org/13403

On my machine List.sort takes ~10 sec, mergeSort 7, qs 4 (compiled  
with -O2). List.sort eats too much ram to sort 20.000.000 ints, my  
algorithms don't.
QuickCheck says my implementations are correct.

I suppose List.sort does clever things for nonrandom lists, that I  
didn't consider? I had a look at the source, but I couldn't find  
anything obvious.


Adrian


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bayley, Alistair-3]

> From: haskell-cafe-bounces@...
> [mailto:haskell-cafe-bounces@...] On Behalf Of Adrian Neumann
>
> I don't consider myself to be a very advanced Haskell
> programmer, but  
> I could come up with a Mergesort that beats List.sort, time- and  
> spacewise.
>
>  > http://hpaste.org/13403
>
> On my machine List.sort takes ~10 sec, mergeSort 7, qs 4 (compiled  
> with -O2). List.sort eats too much ram to sort 20.000.000 ints, my  
> algorithms don't.
> QuickCheck says my implementations are correct.

Your single module might be benefiting from optimisation; specifically,
specialisation to Ints, which would allow the dictionary lookup to be
removed. Can you get the same performance if you move your mergeSort &
qs functions into a separate module, and only export mergeSort & qs?

Alistair
*****************************************************************
Confidentiality Note: The information contained in this message,
and any attachments, may contain confidential and/or privileged
material. It is intended solely for the person(s) or entity to
which it is addressed. Any review, retransmission, dissemination,
or taking of any action in reliance upon this information by
persons or entities other than the intended recipient(s) is
prohibited. If you received this in error, please contact the
sender and delete the material from any computer.
*****************************************************************

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Adrian Neumann]

Ah that's interesting. Now my Mergesort is exactly as fast as  
List.sort. I thought GHC was smart enough to do that kind of inter-
module optimisation.

Still, Quicksort is twice as fast, so at least one argument for a  
Data.List.Sort package on hackage remains.


Am 29.12.2008 um 16:43 schrieb Bayley, Alistair:

>> From: haskell-cafe-bounces@...
>> [mailto:haskell-cafe-bounces@...] On Behalf Of Adrian Neumann
>>
>> I don't consider myself to be a very advanced Haskell
>> programmer, but
>> I could come up with a Mergesort that beats List.sort, time- and
>> spacewise.
>>
>>> http://hpaste.org/13403
>>
>> On my machine List.sort takes ~10 sec, mergeSort 7, qs 4 (compiled
>> with -O2). List.sort eats too much ram to sort 20.000.000 ints, my
>> algorithms don't.
>> QuickCheck says my implementations are correct.
>
>
> Your single module might be benefiting from optimisation;  
> specifically,
> specialisation to Ints, which would allow the dictionary lookup to be
> removed. Can you get the same performance if you move your mergeSort &
> qs functions into a separate module, and only export mergeSort & qs?
>
> Alistair
> *****************************************************************
> Confidentiality Note: The information contained in this message,
> and any attachments, may contain confidential and/or privileged
> material. It is intended solely for the person(s) or entity to
> which it is addressed. Any review, retransmission, dissemination,
> or taking of any action in reliance upon this information by
> persons or entities other than the intended recipient(s) is
> prohibited. If you received this in error, please contact the
> sender and delete the material from any computer.
> *****************************************************************
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Krzysztof Skrzętnicki]

I think you are repeating my steps :-) On sorted data (like [1..n])
quicksort is O(n^2).

Please read this thread:
http://www.nabble.com/(flawed-)-benchmark-:-sort-td15817832.html

All best

Christopher Skrzętnicki


2008/12/29 Adrian Neumann <aneumann@...>:

> Ah that's interesting. Now my Mergesort is exactly as fast as List.sort. I
> thought GHC was smart enough to do that kind of inter-module optimisation.
>
> Still, Quicksort is twice as fast, so at least one argument for a
> Data.List.Sort package on hackage remains.
>
>
> Am 29.12.2008 um 16:43 schrieb Bayley, Alistair:
>
>>> From: haskell-cafe-bounces@...
>>> [mailto:haskell-cafe-bounces@...] On Behalf Of Adrian Neumann
>>>
>>> I don't consider myself to be a very advanced Haskell
>>> programmer, but
>>> I could come up with a Mergesort that beats List.sort, time- and
>>> spacewise.
>>>
>>>> http://hpaste.org/13403
>>>
>>> On my machine List.sort takes ~10 sec, mergeSort 7, qs 4 (compiled
>>> with -O2). List.sort eats too much ram to sort 20.000.000 ints, my
>>> algorithms don't.
>>> QuickCheck says my implementations are correct.
>>
>>
>> Your single module might be benefiting from optimisation; specifically,
>> specialisation to Ints, which would allow the dictionary lookup to be
>> removed. Can you get the same performance if you move your mergeSort &
>> qs functions into a separate module, and only export mergeSort & qs?
>>
>> Alistair
>> *****************************************************************
>> Confidentiality Note: The information contained in this message,
>> and any attachments, may contain confidential and/or privileged
>> material. It is intended solely for the person(s) or entity to
>> which it is addressed. Any review, retransmission, dissemination,
>> or taking of any action in reliance upon this information by
>> persons or entities other than the intended recipient(s) is
>> prohibited. If you received this in error, please contact the
>> sender and delete the material from any computer.
>> *****************************************************************
>>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe