[cfe-dev] Patch for IdentifierResolver

[Chris Lattner]

On Apr 9, 2008, at 9:59 PM, Argiris Kirtzidis wrote:

> Chris Lattner wrote:
>> Some thoughts:
>>
>> +  /// IdDeclInfoMap - Associates IdDeclInfos with Identifiers.
>> +  class IdDeclInfoMap {
>> +    std::list<IdDeclInfo*> IDIArrPtrs;
>>
>>
>> std::list<pointer> is very inefficient, maybe llvm::ilist would  
>> work?  This puts the prev/next pointers in the IdDeclInfo object  
>> itself.  This can be a follow-on patch of course.
>> http://llvm.org/docs/ProgrammersManual.html#dss_ilist
>
> I didn't make it clear; "std::list<IdDeclInfo*> IDIArrPtrs;" doesn't  
> contain all the allocated IdDeclInfos, just pointers to arrays of  
> IdDeclInfos that serve as a kind of 'pools'
> to avoid allocating each individual IdDeclInfo on the heap. With  
> array size of 512 and needing only 1092 IdDeclInfos for carbon.h,  
> you only get 3 pools (just 3 elements to store in
> IDIArrPtrs), thus the std::list doesn't make much of an impact on  
> efficiency.

Ah, gotcha.  That makes a lot of sense.

>>
>> +    static const unsigned int ARRAY_SIZE = 512;
>> +    IdDeclInfo OrigArr[ARRAY_SIZE];
>>
>> This is sort of gross: 512 is a magic number, where did you get  
>> it?  Is this really needed? Maybe the ilist is enough?  The bad  
>> part about this is that it adds a couple kilobytes into the middle  
>> of the sema object, which seems suboptimal.
>
> 512 serves the same purpose as 32 in
>
> typedef llvm::SmallPtrSet<Action::DeclTy*, 32> DeclSetTy;
>
> of Scope class, it only affects memory allocated.
>
> OrigArr is supposed to be the initial pool of IdDeclInfos. Shall I  
> allocate it to the heap instead ?
> As it is now, pools of ARRAY_SIZE size are allocated on a need to  
> have basis (to map identifiers to IdDeclInfos). Another idea would  
> be to start from a small initial size and double the size of
> the next pool when the initial pool is filled, or expand it by 1.5  
> etc.

Yeah, I think it would be appropriate to just let the first shadowed  
identifier allocate an entry in the std::list.  What about  
"std::list<IdDeclInfo[512]>" (using a struct to hold the array?)?   
This saves an extra allocation of the list node, which is not a big  
perf/memory win, but is tidier because you don't have to delete[] the  
nodes.

-Chris