OT (partially): about promotion of integers

[Timon Gehr]

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.