On 12/13/2012 12:47 AM, Walter Bright wrote:
On 12/12/2012 3:23 PM, Timon Gehr wrote:
On 12/12/2012 10:35 PM, Walter Bright wrote:
some algorithms are doomed to be slower.

Here's a (real) quicksort:
http://stackoverflow.com/questions/5268156/how-do-you-do-an-in-place-quicksort-in-haskell


Ok, I'll bite.

Here's a program in Haskell and D that reads from standard in, splits
into lines, sorts the lines, and writes the result the standard out:

==============================
import Data.List
import qualified Data.ByteString.Lazy.Char8 as L
main = L.interact $ L.unlines . sort . L.lines
==============================
import std.stdio;
import std.array;
import std.algorithm;
void main() {
   stdin.byLine(KeepTerminator.yes)
   map!(a => a.idup).
   array.
   sort.
   copy(
     stdout.lockingTextWriter());
}
===============================

The D version runs twice as fast as the Haskell one.

You are testing some standard library functions that are implemented in wildly different ways in both languages. They are not the same algorithms. For example, looking at just the first element of the sorted list will run in O(length.) in Haskell. If you build a sort function with that property in D, it will be slower as well. (if a rather Haskell-inspired implementation strategy is chosen, it will be a lot slower.) The key difference is that the D version operates in a strict fashion on arrays, while the Haskell version operates in a lazy fashion on lazy lists.

This just means that Data.List.sort is inadequate for high-performance code in case the entire contents of the list get looked at.

This is a good treatment of the matter:
http://stackoverflow.com/questions/11481675/using-vectors-for-performance-improvement-in-haskell/11485331#11485331

You are using Data.List.sort. The best implementations shown there seem to be around 5 times faster. I do not know how large the I/O overhead is.

Certainly, you can argue that the faster version should be in a prominent place in the standard library, but the fact that it is not does not indicate a fundamental performance problem in the Haskell language. Also, note that I am completely ignoring what kind of code is idiomatic in both languages. Fast Haskell code often looks similar to C code.

Note that there's
nothing heroic going on with the D version - it's straightforward dumb
code.

A significant part of the D code is spent arranging data into the right layout, while the Haskell code does nothing like that.

Reply via email to