This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC] type safe trees

Geoff Keating <> 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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]