[erlang-questions] dict, orddict and gb_tree

[Robert Virding]

I will try some more scan patterns to see what types of figures I get. I 
don't really envision calculating random permutations of 500k element 
lists. :-)

Richard Carlsson wrote:
> 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
> 
>