Go rant

[Andrei Alexandrescu]

bearophile wrote:
> Walter Bright:
>> Ain't that cool? But look closer. The advantage of quicksort is
>> that it is an *in-place* sort. The Haskell one creates new arrays
>> for every state in the sort. The other fundamental problem with the
>> Haskell version is that it selects the first array element as the
>> "pivot". This is the worst choice, since arrays to be sorted tend
>> to already be mostly sorted, and quicksort gives quadratic
>> performance to sort an already sorted array with the first element
>> as the pivot.
> 
> You are missing two big things, Walter:
> 
> 1) The first one is big: that was not an example of a general-purpose
> sort routine to be used to sort items. If you go look at how normal
> system sort is done in Haskell you will see a much longer and much
> more efficient implementation. The point of that example was to show
> how you can compactly express a computational idea in Haskell, in a
> safe, very compact and readable enough way. In a normal program a
> significant percentage of the code doesn't need to be top
> performance, in both runtime performance and memory used, because
> it's used rarely and/or on small data sets. So for this code it's not
> good to write an extremely efficient implementation, it's better to
> use a safe, very compact and readable implementation. Haskell gives
> you both safety and compact code. Note that for real sorting purposes
> you don't use that onliner, you use some kind of system sort. So what
> I am says applies to new code, absent in the standard library.

It's a piece of crap. A crappy example is a crappy example is a crappy
example. It consistently does more harm than good.

> 2) The second point you are missing is even bigger. Today languages
> as Clojure (and F# and a bit less Scala) are using more and more
> immutabe data structures. They reduce bugs, allow a quite simpler
> multi-processing (so they are multicore-friendly) and they allow a
> more functional-style coding (that in the hands of a modern
> compiler/VM allows gives enough semantic constraints to allow a good
> compilation. See pure functions). This of course puts more pressure
> on the garbage collector, but the GC of Haskell is designed for this
> purpose, and the compile is able to optimize away some of this work.
> The resulting code is not as efficient as C code on a single CPU but
> on many CPUs it may lead to efficient code.

Quicksort is parallellizable although it uses mutation so you chose the 
wrong example to make an otherwise generally valid point.

> Please ask if you have missed my two points, because they must be
> understood if you want to design a modern language.

I'd say that's a tad assuming :o).


Andrei