[Haskell-cafe] Can Haskell outperform C++?

[Richard O'Keefe]

On 19/05/2012, at 5:51 AM, Isaac Gouy wrote:
>> In the 'tsort' case, it turns out that the Java and Smalltalk
>> versions are I/O bound with over 90% of the time spent just
>> reading the data. 
> 
> My guess is that they could be written to do better than that - but it's 
> idiotic of me to say so without understanding the specifics, please 
> forgive me ;-)

Actually, I/O bound is *good*.

Here's the times from the C version, which has been hacked hard in order
to be as fast as I could make it.

 N     total      input      process    output
 1000; 0.004618 = 0.004107 + 0.000438 + 0.000073
 2000; 0.014467 = 0.012722 + 0.001609 + 0.000136
 5000; 0.059810 = 0.051308 + 0.008199 + 0.000303
10000; 0.204111 = 0.150638 + 0.052800 + 0.000673
20000; 0.717362 = 0.518343 + 0.197655 + 0.001364
50000; 3.517340 = 2.628550 + 0.885456 + 0.003331

N here is the number of nodes in the graph;
the number of edges is floor(N**1.5 * 0.75).
Input is the read-word + look up in hash table time.
Process is the compute-the-transitive-closure time.
Output is the time to write the node names in order.
All node names had the form x## with ## being 1..10000.
This is with my own low level code; using scanf(%...s)
pushed the input time up by 40%.

The Mac OS X version of the tsort command took
31.65 CPU seconds for N=10,000, of which
28.74 CPU seconds was 'system'.

Like I said, the languages I used in this test
>> ... have I/O libraries with very different
>> structures, so what does "identical algorithms" mean?  If you
>> are using dictionaries/hashmaps, and the two languages have
>> implementations that compute different hash functions for strings,
>> is _that_ using the same implementation? 
> 
> Of course, to some degree, user defined hash functions remedy that specific problem.

While creating other, and perhaps worse, ones.

For example, in the Smalltalk code, if you use a Dictionary of Strings,
you're getting Robert Jenkin's hash function in optimised C.  If you
supply your own, you're getting a very probably worse hash function
and it's going to run rather slower.  And above all, the stuff you are
benchmarking is no longer code that people are actually likely to write.

> But we're still going to ask - Will my program be faster if I write it in language X? - and we're 
> still going to wish for a simpler answer than - It depends how you write it!

Here's another little example.  I had a use for the Singular Value Decomposition
in a Java program.  Should I use pure Java or native C?

Pure Java taken straight off the CD-ROM that came with a large
book of numerical algorithms in Java:   T seconds.

After noticing that the code was just warmed over Fortran, and was
varying the leftmost subscript fastest (which is good for Fortran,
bad for most other languages) and swapping all the matrix dimensions: T/2 seconds.

After rewriting in C:  T/4 seconds.

After rewriting the C code to call the appropriate BLAS
and thereby using tuned code for the hardware, T/7 seconds.

Since this was going to take hundreds of seconds per run, the answer was easy.

A simple little thing like using a[i][j] vs a[j][i] made a
factor of 2 difference to the overall speed.

"It depends" is the second best answer we can get.
The best answer is one that says _what_ it depends on.