Tracking down superlinear reductions

[Ulf Wiger (AL/EAB)]

> It looks like orddict:store() is an O(n) function as it seems 
> to be doing a linear scan.  That explains why its about 
> 1000*1000/2.  A linear scan should be O(n)/2.
> 
> I'll go look at the gb_trees module.

The simplest way to check how much the complexity of orddict adds to the equation is of course to switch to dict - since orddict and dict have exactly the same API.

According to the manual, orddict mimics dict, but uses an ordered list. The manual for dict doesn't specify what it uses, but the code does:

%% We use the dynamic hashing techniques by Per-Åke Larsson as
%% described in "The Design and Implementation of Dynamic Hashing for
%% Sets and Tables in Icon" by Griswold and Townsend.  Much of the
%% terminology comes from that paper as well.


BR,
Ulf W