Re: [Caml-list] map implementation question

[j h woodyatt <jhw@conjury.org>]

On Aug 17, 2006, at 4:37 AM, Xavier Leroy wrote:
>
> This said, red-black trees would probably work faster anyway, but I'll
> let the algorithm experts on this list comment.

My experience trying to tweak the red-black trees in the Cf library  
of OCaml NAE so they perform globally better than the height-balanced  
trees in the standard library has been mixed.  Some functions perform  
marginally better, but others are worse-- sometimes substantially  
worse, and I don't think there's any way around it.  (It doesn't help  
that a lot of my exercises reveal that my binary set operations need  
improvement, but there are other places where there's simply nothing  
to do.  I'll get around to fixing the binary set operators someday,  
before my next release.)

By the way, Xavier is very correct: that "imbalance <= 2" thing is  
utterly brilliant.  I'm pretty sure my red-black trees would smoke  
the standard library if it weren't for that.

The result is that I recommend using my red-black trees only when you  
are either 1) using the other facilities in the Cf library that are  
integrated well with them, e.g. Cf_seq and such, or 2) using them in  
a [currently hypothetical] case where you have compared the  
performance with the standard library and it makes a valuable  
difference to get 15% more CPU (or one less field per tree node) out  
of your tree algorithm.


—
j h woodyatt <jhw@conjury.org>
san francisco, ca