Re: suggestion for dictionary representation

["Paul N. Hilfinger" <hilfingr at otisco dot mckusick dot com>]

A random piece of empirical data, for what it's worth: 

Out of curiosity, I slapped together a little skip-list implementation
and ran all the stabs symbols in a large (67MByte) executable through
it---adding all of them.  There were a total of about 670000 adds, of
which about 150000 were distinct.  This required about 3 seconds
(including the time to allocate new list nodes, allocate copies of the
keys, and insert the new items) running on an 800MHz Athlon processor.
For comparison, the time to first prompt for a version of GDB (version
5.1.1 or so) on this same file was 4 seconds, or 47 seconds if started
with -r.  

Interpretation, I admit, is difficult, but I think this establishes
some sort of rough bound on possible performance hits from this
representation (the skip-list implementation, being hasty, was not
particularly optimized).

Paul Hilfinger