[erlang-questions] dict, orddict and gb_tree

[Richard Carlsson]

Robert Virding wrote:
> 3. gb_trees is very slow on adding new values, but rather fast on 
> fetching and updating them. I don't know why this is so.

There were several posts to this list years ago with similar
measurements, and I've never seen such strange numbers for add/enter
before. In particular, the difference between enter and add (when the
key does in fact not exist in the tree) should be precisely the time
it takes to do a lookup. Your numbers show a much greater difference
between enter and add, so something seems to be fishy here.

> 4. It is a big win for gb_trees if you know whether you have an existing 
> key or not when modifying the table.

Yes, that is because if the key is known to be present, there will
be no need to do any rebalancing (or even check for rebalancing), so
the update can be made much faster. Hence, for algorithms that do a
lot of updates, it can definitely be better to fully populate the tree
in advance, so that update can be used throughout instead of enter.
(However, the functional-array implementation that Dan G. and I posted
to the list a while back is much faster still, if you have a range of
integer keys.)

> 5. I was a bit surprised that red-black trees could match gb_trees in 
> fetching as red-black allows some inbalance in the tree. Perhaps the 
> order of insertion was right for it?

Try a random set of keys and let us know.

     /Richard