[RFC] type safe trees

[Mark Mitchell]

Geoff Keating wrote:

> On 24/06/2004, at 9:43 PM, Mark Mitchell wrote:
>
>> Also, I understand what you're saying about CONST_DECLs living only 
>> in PCH memory which is never read -- but what about things like 
>> TREE_LISTs or VAR_DECLs that get built a lot even after the PCH has 
>> been read in as the remaining code is processed.  Do you have any 
>> ideas about how profitable it might or might not be to shrink them?  
>> (We can get lots of these nodes as templates are instantiated and as 
>> code is processed.)
>
>
> I think it would help.  We have some evidence that a small percentage 
> reduction in memory size gives about half that percentage reduction in 
> compile time.  (I'm anxiously awaiting someone trying a large 
> percentage reduction.)

Interesting data point.

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

Yes, probably.  I was thinking about the fact that we rebuild lookup 
tables as we enter/exit class scope.  We cache the most recently used 
one, but in my experiments that doesn't seem to help too much.  I 
suspect we should either cache them all, or at least cache the most 
recently used N for N maybe 5 or 10.

I've also got some measurements from Qt showing that lookup_base is an 
expensive function; that's another thing that we could memoize and/or 
improve on our current data structures.  For example, a global hash 
table of pairs <derived, base> mapped to a binfo?  I've not thought 
aobut this enough to see whether that would actually be a win; the hash 
overhead might overcome the win.  It's also not clear to me why we're 
calling this function so often, and it may be more profitable to attack 
it at that level.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com