Re: suggestion for dictionary representation

[Daniel Jacobowitz <drow@mvista.com>]

On Sun, Sep 22, 2002 at 09:44:40PM -0500, Jim Blandy wrote:
> 
> It seems to me that the `skip list' data structure simultaneously
> meets a lot of the criteria that we're currently meeting by having
> multiple representations.  Skip lists:
> - provide (probabalistic) log n access time
> - are low overhead ("They can easily be configured to require an
>   average of 1 1/3 pointers per element (or even less).")
> - are easy to build incrementally, and stay "balanced" automatically
> - are obstack-friendly, since they don't involve realloc (as hash
>   tables do)
> - are an ordered structure, which would support completion nicely (and,
>   by the way, make the `_Z' test for the C++ V3 ABI faster too)
> - have a trivial iterator (walking the finest level of links)
> - are pretty easy to understand
> 
> http://www.cs.umd.edu/~pugh points to a paper describing and analyzing
> them.
> 
> Using skip lists, there'd be no need to distinguish `expandable' from
> non-expandable blocks.  This one structure would scale to handle both
> local blocks and the global environment (depending on how we handle
> lazy symbol reading --- I'd like a more generic and descriptive term
> than "partial symbol tables").

Hmm.  Lots of simplicity/cleanliness benefits, but the real question as
far as I'm concerned is whether the benefit to completion (the _Z thing
is done as we read in symbols right now, so it's a complete non-issue)
outweights going from O(1) to O(probabalistic log n) for symbol lookup.

I suspect it would; having faster completion [I can't really see how to
beat O(n) with the current hash tables, can anyone else?  But I think
it's slower than O(n) right now; I recall it being quadratic...] would
be nice.  O(~ log N) ought to be plenty fast, right?

> The only remaining special case would be function blocks, in which
> parameter symbols must to appear in the order they appear in the
> source.  I think it's pretty ugly to abuse the name array this way; it
> introduces special cases in dumb places.  This kludge could be removed
> by changing the `function' member of `struct block' to a pointer to
> something like this:
> 
>    struct function_info {
>        struct symbol *sym;
>        int num_params;
>        struct symbol **params;
>    };
> 
> This would require extra space only for function blocks; non-function
> blocks would remain the same size.  And this info would only be
> consulted when we actually wanted to iterate over the parameters.
> This would clean up a bunch of loops in GDB that currently have to
> iterate over all the symbols in a function's block and do a switch on
> each symbol's address class to find the arguments.  (And would this
> also allow us to remove the arg/other distinction in enum
> address_class?  Dunno.)
> 
> But if we were to remove function blocks as a special case, there
> would only need to be a single structure for representing levels of
> the namespace.

I'm tempted to whack the block special case for function arguments.  It
may make name lookup a little more complicated but I think it will make
everything clearer.  We could, of course, try this on the branch and
see if we like the results :)

David, what do you think?

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer