[Haskell-beginners] Red-black tree performance

[Lorenzo Bolla]

Your scripts stack-overflows on my box.

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 at 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 at haskell.org
> http://www.haskell.org/**mailman/listinfo/beginners<http://www.haskell.org/mailman/listinfo/beginners>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120320/aac10451/attachment.htm>