Re: [RFC] type safe trees

[Zack Weinberg <zack at codesourcery dot com>]

Geoff Keating <geoffk@geoffk.org> writes:

>> Also, on the identifier table issues you mention, I was actually
>> thinking about how to reorganize that stuff today.  We should avoid
>> stepping on each other in that area.  I think there are some data
>> structure improvements we should make and also some ways in which we
>> can seriously improve the case of entering/exiting class scopes,
>> which happens a ton.
>
> My thinking in that area had to do with the identifier hash table
> itself, and possibly making it something not a hash table (I was
> thinking of B-trees).  But I think there are better things to try
> first.

While I was on vacation I mocked up a new identifier-lookup algorithm
that uses a hybrid ternary/red-black search tree.  In Python, which
means I don't have performance numbers that can be compared to
anything for GCC itself.  However, it can hold forty thousand
identifiers with a worst-case tree depth of only 20, and it can do
lookup in parallel with identifier scanning.  I think this is a
promising approach, but I also agree there are lower fruit.

zw