Re: RFC: partial symbol table address range generalization

[Daniel Berlin <dan at cgsoftware dot com>]

On 7 Nov 2001, Jim Blandy wrote:

>
> Daniel Jacobowitz <drow@mvista.com> writes:
> > I've got a question.  What we really want to represent here are not
> > just sets of addresses, but a single address space and the symtabs
> > known to correspond to different sections of it.  Would it be more
> > useful to represent them that way, so that the code to search the
> > address space would only happen once for all psymtabs/symtabs?
>
> Right, I've been thinking the same thing.  You want an "address map"
> ADT --- something that maps CORE_ADDR's to void * values.  We could
> use it everywhere.
>
> For example, here's a better way to represent line number info: have
> one addrmap mapping CORE_ADDR's to integers (line numbers); have
> another that maps CORE_ADDR's to symtabs / null pointers.  That would
> be tons simpler, and tons faster, than what we have now.  Assuming the
> address map had a low per-address-range overhead, it wouldn't use much
> more memory.  All the fancy logic could get handled once, when the
> tables are created.
>
> The question is, how can you represent this in an obstack-friendly
> way?  The obvious representation of an addrmap is a sorted array, with
> a gap for insertion, but obstacks don't like arrays that expand
> occasionally.  A doubling algorithm can guarantee that the waste is
> merely proportional to the final size, but that's kind of crummy.  A
> binary tree works better, but you spend a lot of memory on child
> links; we wouldn't want to use an addrmap to store line number info if
> it took twenty bytes per line (currently it takes only twelve) (both
> assuming a 64-bit CORE_ADDR and 32-bit pointers and ints).
Errr, why should it be obstack friendly?
An interval tree without obstacks will be more efficient in terms of speed
and memory than something else with obstacks.

If it's really necessary, You could also use a interval stabbing skiplist,
which would be obstack friendly. At least, moreso than the tree.
You can just throw elements on a free list, and reuse them.

If you don't want an interval structure, a skiplist with probability .25
will give you 1.33 pointers average per element, rather than 2 for a tree.
They are also much easier to maintain.

--Dan