I've made 2 little changes, to ensure strictness. I believe your "insertList" is building up a huge list of thunks.
import Data.Foldable (foldr')
<snip>
main :: IO ()
main = putStrLn $ show $ maxTree $ foldr' insert Empty toInsert
Better?
L.
On Tue, Mar 20, 2012 at 2:37 PM, Adrien Haxaire
<adrien@haxaire.org> wrote:
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
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners