DMD internal: appendToModuleMember performance

Johan Engelen via Digitalmars-d digitalmars-d at puremagic.com
Fri Apr 15 11:33:44 PDT 2016


Hi all,
   When building a unittest case in Weka.io's codebase, I measure 
that appendToModuleMember takes about 10% of the total compile 
time, and about 25% of total semantic analysis time. 
"appendToModuleMember" is the only function that pops up in 
profiling with such a large time fraction spent in it.

The culprit is the linear search at the end of 
appendToModuleMember, because the members list with Dsymbols gets 
pretty large (50k+ members).
https://github.com/D-Programming-Language/dmd/blob/master/src/dtemplate.d#L8012-L8026

I've modified the code to also store the list of members as an 
rbtree, and voila, much faster compiles: from 26sec to 20sec 
(semantic only). The old data structure is still there and the 
only change is to do a lookup into the tree instead of the linear 
search.
The hack is here: 
https://github.com/ldc-developers/ldc/compare/master...JohanEngelen:speed_up

I couldn't use symtab as it isn't populated with all symbols and 
I wasn't sure if it would break things.

I'm thinking about removing the old array all-together.
My question is: is it essential to keep an ordered list? (I see a 
`.shift(...)` call on the array, to put something in first 
position. If so, could that be solved by having *two* trees, 
where "in-order" iteration first iterates over the first one and 
then the second. The "high priority" symbols can then be put in 
the first tree, normal ones in the second tree (if that is how 
order matters...).

Thanks,
   Johan



More information about the Digitalmars-d mailing list