[Haskell-beginners] Red-black tree performance

[Heinrich Apfelmus]

Adrien Haxaire wrote:
> I tried with foldl'. I modified the code at several places to match
> the argument pattern, and now I see why flip is so useful :) The
> conclusion is also interesting: the productivity climbs up to 92%,
> while the calculation time raises to 6.3s. I guess that the choice is
> space or time, as often.

92% productivity seems right for me. In contrast, 20% garbage collection 
may be a sign that something went wrong.

> Another interesting point. By using foldr' and removing the
> exclamation marks in the Tree data type, I even get better results:
> 3.76s. Which means a ratio of 5.87. I tried adding some bang patterns
> and inline pragmas but it didn't help.

I think that this is likely due to laziness: in the very end, you only 
query the rightmost element. After a while, the program simply won't 
evaluate the balancing on the left side of the tree, as you're not 
asking it to evaluate anything there.

So, you're not necessarily comparing apples and apples here. But on the 
other hand, maybe that's a performance disadvantage of the C++ version. 
In Haskell, performance depends a lot on usage patterns.


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com