[Haskell-beginners] Red-black tree performance

[Adrien Haxaire]

On Wed, Mar 21, 2012 at 10:08:06AM +0000, Lorenzo Bolla wrote:
> toInsert :: [Int]
> --  toInsert = [1..1000000]
> toInsert = map (`mod` 100) [1..10000000]

Hello,

Sorry for replying so late.

Using mod 100 will just give me entries from 0 to 99, right? so this can explain the performance improvement :)

Concerning the GC. Foldl' gives me a better productivity but takes more time, when foldr' uses more GC but results in faster code. In general, what are the best practices here: tolerate a use of the GC up to 20% but with good performance, or strive for the minimum GC use? Apart from the RBTree case, in the Haskell code I am writing, performance is not the primary goal, so I would go for latter. But maybe there are some common rules to measure the right tradeoff?

I chose to use this worst cas scenario of inserting a sorted ascending list to require many rebalancing; it is the same list I use to compare with the C++ implementation. I ask for the maximum to see if it yields the right result. Thanks for the reminder about the pattern used in the program, and the pattern order in functions. Reorganizing them led to some improvement. I'll keep that in mind. 

Best regards,
Adrien



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