Re: [RFC] Symbol table improvements

[Daniel Berlin <dan at www dot cgsoftware dot com>]

On 21 Jun 2001, J.T. Conklin wrote:

> >>>>> "Daniel" == Daniel Berlin <dan@cgsoftware.com> writes:
> Daniel> Problems right now:
>
> Daniel> Worst case is currently symbol not existing. We search *everything*.
> Daniel> Search isn't particularly fast. It actually depends on where the
> Daniel> symbol will be found.  We repeatedly search the same blocks.
>
> Yes.  This is exacerbated by the expresion parser looking up
> everything that might be a identifier as a global symbol.  I have
> number of command scripts used for groveling data structures that
> run much slower than they should because of this.
>
> I toyed around a bit.  I got halfway through storying the block symbol
> array in a tree (using libavl), but I never had time to follow through.
> Perhaps if I understood what I was doing I'd be less intimidated by the
> magnitude of the task.

It's very tricky, until you realize a lot of the comments aren't telling
the whole truth anymore.
:)

The motivating example in this case was the simple python script to
backtrace the python stack.

>
> Daniel> Current attempt:
> [...]
>
> Daniel> Thoughts, comments?
>
> Sounds like a giant step in the right direction.

I'm eventually going to be divorcing the block structures from the symbol
arrays, at least, hopefully, anyway. In fact, the secondary purpose of
this patch is to do just start doing that.  It goes about 90% of
the way to removing the blocks being needed for symbol lookups (we
already know whether we'll find the symbol before we search a given
block now).

It's the best way to do namespaces properly.
Otherwise, you have to copy things into other blocks, etc.  It's just a
mess.  To do the effect of important namespace std right now, would
require copying every single symbol into the right blocks (yes, i'd have
to copy it multiple times).
Or doing a hacked lookup.

In reality, what we should have is a large array of symbols, each with
some unique id number, and whatever wants to track something about the
symbols (blocks, for instance), just keeps a bitmap of the id's or
whatever.
Or something of the sort.

>
> Daniel> I've got the global splay tree stuff done, and it's noticeably
> Daniel> faster.  The only thing not done is the not searching of
> Daniel> duplicate blocks.
>
> Do you have a patch that I can test?  I'd like to toy with it with a
> GDB that understands our crash dump format and our scripts that walk
> task lists, message queues, etc.

Didn't I send it?  I thought I did.

I actually have a tree with just that patch in it, that I was using for
performance testing.

I won't be able to get to it until monday night if i haven't, i'm not at
home.


>
>         --jtc
>
> --
> J.T. Conklin
> RedBack Networks
>