Re: [Doxygen-develop] Doxygen taking longer to run?

[Dimitri v. H. <di...@st...>]

On Mon, Aug 11, 2003 at 12:52:53PM +0100, Edmund Green wrote:
> Attached is my suggested patch for eliminating a few redundant calls to 
> resolveTypeDef

Thanks for looking into this. As you have noticed, the resolution of
typedefs and classes has evolved into something quite complex, and as you
demonstrated that it is/can be a bottleneck, I agree it is time to 
rethink the design.

> I've also been thinking a little more about the speed problem, and if 
> I've understood it correctly then changing getResolveClassRecursive from 
> iterating through all the visible namespaces searching for matching 
> names, to doing a global lookup of all matching local names (i.e. RHS of 
> the name, against RHS of all full names) and then searching within the 
> list of matching names for the best matching namespace could be a lot 
> faster in the typical case where there is only one instance of the local 
> name. It would also remove the need for recursion.
> 
> This would involve adding a global map of lists of fully qualified names 
> indexed by local-name - e.g. some pseodo code for getting a matching 
> class name with this mechanism (ignoring typedefs, and other technicalities)
> 
> ClassDef *getResolvedClass(
>                            Definition *scope,
>                            QCString name,
>                            ...
>                           )
> {
>   String localName = name with any namespace prefix stripped off;
>   String explicitNs = any namespace prefix from the name;
> 
>   List<ClassDef*> *possibleMatches = globalMapOfNames.find(localName);
> 
>   ClassDef* bestMatch = 0;
>   for possibleName in possibleMatches
>   {
>     if possibleName is better match than bestMatch for name from scope
>     {
>       bestMatch = possibleName;
>     }
>   }
>   return bestMatch;
> }
> 
> Admittedely the test inside the loop is slightly awkard when taking in 
> to account "using" namespaces, but it would seem to mostly be a case of 
> matching the left hand side of the possible name against the left-most 
> portion of the scope, and the right hand side against the name, and 
> seeing if any remaining unaccounted for bits in possibleName can be made 
> up from the available imported namespaces.
> 
> I'd expect this to be a lot faster as possibleMatches would typically 
> only have a single entry for most C++ and Java code - though there are a 
> few cases, such as defining call-back interfaces as 
> inner-classes/structs all with the same local name, which would then 
> give longer lists to linearly search through which would also be 
> expected to grow in length approximately linearly with the size of the 
> project (Looking at one of our projects I only found a couple of 
> duplicated class names out of several hundred classes - with the worst 
> case being used in 13 different scopes)

I do something like this for members now. I have two maps, one 
for file/namespace members and one for class members. What you suggest sounds
like a generalization of this, making it one map for all symbols, which could indeed
make a lot of things simpler in doxygen. The downside is that it is a lot of work,
so we should find a way to introduce this gradually.

Regards,
  Dimitri