dict/orddict (was: HIPE'd stdlib modules rule !!!)

[Richard Carlsson]

On Sun, 25 May 2003, Chris Pressey wrote:

> On Fri, 23 May 2003 14:16:41 -0500
> Eric Newhuis <enewhuis@REDACTED> wrote:
>
> > I HIPE'd the orddict.beam file (erlc +native orddict.beam) and now the
> > same app is fast, relatively speaking ~ 5% CPU on that same arbitrary
> > peice of iron.
>
> You might be able to get it to go even faster if you can use 'dict'
> instead of 'orddict' :)

Not necessarily. It depends quite a lot on the application.

The data structures used by the 'dict' module have higher overhead, both
space-wise (if there are relatively few elements in the dictionary)
and time-wise. Where the break-even point is exactly can vary a bit (in
particular, it can vary with whether you insert often, or just look up),
but when I have checked, it has been somewhere between 20 and 100
elements.

So, if you *know* that your dictionaries will contain at most than a
couple of dozen elements, the 'orddict' module is your choice (but be
warned that you could run into complexity problems if you start using
the app for larger problems). If you could easily have 50-100 elements
or more, you should use the 'dict' module. If in doubt, use the latter,
unless it is actually important to you that the representation uses
ordered lists.

The same reasoning applies to the modules 'sets' and 'ordsets', of
course. One example where ordsets can pay off is when you both do
insertion and union/intersection. To take the union of two 'sets'
actually requires more work than taking the union of two 'ordsets'. It
could also be a good idea to separate the data representation into
phases, using 'sets' when you do a lot of insertion and/or lookup, and
using 'ordsets' when you mostly do union, intersection or subtraction.

Needless to say (or is it?), the usual "premature optimization is the
root of all evil" applies. Only use ordsets/orddict if you need to.

My own programs often contain code like this:

	%% ----------------------------
	%% Dictionary implementation

	dict__new() ->
		orddict:new().
	%	dict:new().

	dict__store(Val, Dict) ->
		orddict:store(Val, Dict).
	%	dict:store(Val, Dict).

	...etc.

to make it easy to switch implementation.

	/Richard


Richard Carlsson (richardc@REDACTED)   (This space intentionally left blank.)
E-mail: Richard.Carlsson@REDACTED	WWW: http://user.it.uu.se/~richardc/
 "Having users is like optimization: the wise course is to delay it."
   -- Paul Graham