GHC Data.List.sort performance question

[Judah Jacobson]

On Jan 15, 2008 8:16 AM, Bertram Felgenhauer
<bertram.felgenhauer at googlemail.com> wrote:
> Marcus D. Gabriel wrote:
> > By a rather indirect route, I discovered that I obtain an almost
> > factor of two improvement in performance in Data.List.sort if I make
> > one small change in the implementation of the function merge which
> > supports mergesort and hence sortBy and sort.  Admittedly, the
> > improvement was only noticeable to me when sorting for example one
> > million random Int.  The current code in libraries/base/Data/List.hs
> > for merge is
> >
> > merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
> > merge cmp xs [] = xs
> > merge cmp [] ys = ys
> [snip]
> >
> > and all that I did was
> >
> > merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
> > merge cmp [] ys = ys
> > merge cmp xs [] = xs
> [snip]
> >
> > that is, I swapped the order of the first two lines.  By the way, the
> > second version is much less likely to overflow the stack than the
> > first version.
> >
> > Can some confirm this?  If you confirm it, can someone explain to me
> > why one obtains this performance improvement?  I currently just do not
> > grasp the point.
>
> I'm not sure why there is a performance difference, but there is
> one major difference in the behaviour of these two implementations:
>
> The library version evaluates the list from right to left (i.e. it
> compares the last two elements of the list first), because the third
> argument of 'merge' is forced before the second one.
>
> Swapping those two lines of 'merge' results in a version which compares
> the first two elements of the list first.
>
> This means that the library version produces a stack overflow on
> lists generated in an iterate like fashion (say, take 1000000 [0..]).
> The modified version produces a stack overflow on the reverse of
> that list, but I believe such lists are much rarer in practice.
>

Bertram, are you sure that's right?  There's already a stack overflow
in "take 1000000 [0..]" itself (try just "last $ take 1000000 [0..]").
 See the bug http://hackage.haskell.org/trac/ghc/ticket/1997

By using [0..1000000] (which doesn't trigger that bug), I can compute both of
last $ sort [0..1000000]
last $ sort $ reverse [0..1000000]
without any stack overflows. (Using ghc-6.8.2)

Best,
-Judah