[Haskell-beginners] Red-black tree performance

[Adrien Haxaire]

 Dear list,

 I had to implement a red-black tree in C++. So I took Okasaki's 
 functional pearl and ported the algorithm to C++, where the rebalancing 
 is done by following parent pointers. I shew the Haskell algorithm to 
 colleagues, and after admitting it is impressive, they told me whatever 
 the beauty as long as we have performance. So I benchmarked it and the 
 C++ implementation, insertion of one million elements, and the C++ 
 version is 15 times faster. Mainly because in C++ it is just moving 
 pointers around I guess. I have to mention that the space usage is 
 outrageous with Haskell.

 The Tree is strict in its subtrees, but I think the problem comes from 
 the laziness of the balance function, which needs to hold the whole 
 tree.

 This reduces to my main question: how can I decompose balance in a 
 stricter version? Or maybe I'm completely wrong and there is something 
 obvious I am missing?

 If you want to take a look, the code is here: http://hpaste.org/65611


 Adrien


 PS: compiler options and profiling stderr output

> ghc -Wall -O2 -prof -auto-all -rtsopts rbt.hs

> rbt.exe +RTS -K20M -p -sstderr -RTS
 1000000
      964,079,612 bytes allocated in the heap
      230,842,072 bytes copied during GC
       58,442,812 bytes maximum residency (7 sample(s))
          327,812 bytes maximum slop
              105 MB total memory in use (0 MB lost due to 
 fragmentation)

                                     Tot time (elapsed)  Avg pause  Max 
 pause
   Gen  0      1810 colls,     0 par    0.30s    0.27s     0.0001s    
 0.0034s
   Gen  1         7 colls,     0 par    0.19s    0.19s     0.0278s    
 0.0938s

   INIT    time    0.00s  (  0.00s elapsed)
   MUT     time    1.78s  (  1.82s elapsed)
   GC      time    0.48s  (  0.46s elapsed)
   RP      time    0.00s  (  0.00s elapsed)
   PROF    time    0.00s  (  0.00s elapsed)
   EXIT    time    0.00s  (  0.00s elapsed)
   Total   time    2.28s  (  2.28s elapsed)

   %GC     time      21.2%  (20.3% elapsed)

   Alloc rate    537,387,643 bytes per MUT second

   Productivity  78.8% of total user, 78.5% of total elapsed




-- 
 Adrien Haxaire
 www.adrienhaxaire.org | @adrienhaxaire