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

On Friday, 15 April 2016 at 18:33:44 UTC, Johan Engelen wrote:
> 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.

Yep, see also: https://issues.dlang.org/show_bug.cgi?id=15323. When I tried to get rid of the ordered array, I ran into several interesting issues, but I don't remember many details.

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

Another "quick fix" if we have to keep the order would be to add a Bloom filter/… on the side to eliminate most array searches.

 — David

On Friday, 15 April 2016 at 19:32:46 UTC, David Nadlinger wrote:
> 
> Another "quick fix" if we have to keep the order would be to add a Bloom filter/… on the side to eliminate most array searches.

In rare cases, symbols are removed from the members list, so the shadow data structure needs the ability to delete elements.

On Saturday, 16 April 2016 at 13:58:28 UTC, Johan Engelen wrote:
> On Friday, 15 April 2016 at 19:32:46 UTC, David Nadlinger wrote:
>> Another "quick fix" if we have to keep the order would be to add a Bloom filter/… on the side to eliminate most array searches.
>
> In rare cases, symbols are removed from the members list, so the shadow data structure needs the ability to delete elements.

Bloom filters can have false positives anyway. As long as elements are not removed too frequently (what do your numbers say?), the performance impact of doing a full linear search in those cases shouldn't be too bad.

 — David

On Friday, 22 April 2016 at 18:51:57 UTC, David Nadlinger wrote:
> As long as elements are not removed too frequently (what do your numbers say?), the performance impact of doing a full linear search in those cases shouldn't be too bad.

Note that a (properly tuned) probabilistic data structure like a Bloom filter allows you to avoid having to keep a full second copy of the list around, hopefully making it possible to keep the optimisation on by default without regrets. (For tiny modules with only a small number of members, you can still do the linear search to skip the hash lookup.)

 — David

On Friday, 15 April 2016 at 18:33:44 UTC, Johan Engelen wrote:
> 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...).

Did you have a closer look at where this is done? One place where order matters is for `object` in `importAll`, but that's trivially rewritten a different way.

 — David

On Friday, 22 April 2016 at 18:51:57 UTC, David Nadlinger wrote:
> On Saturday, 16 April 2016 at 13:58:28 UTC, Johan Engelen wrote:
>>
>> In rare cases, symbols are removed from the members list, so the shadow data structure needs the ability to delete elements.
>
> Bloom filters can have false positives anyway. As long as elements are not removed too frequently (what do your numbers say?), the performance impact of doing a full linear search in those cases shouldn't be too bad.

The false-positive nature of Bloom filters makes them unsuited, I think, unless we can make the chance of a false-positive very low for lists that are very big, my testcase has a list size of 140k elements. It needs something scalable, otherwise there is no size-benefit. Wikipedia leads me to this: http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf

I don't understand exactly what you mean; do you propose to resort to linear search after a removal happened? Or only do a linear search when the shadow data structure says the item is present?
I don't know how often removals happen, but for the 140k elements list removals happens _very_ often. While compiling phobos, removals happen not for all modules, but for quite a few of them.

In any case, I wrote the code such that it is easy to change the underlying data structure and test the impact.

On 4/22/2016 11:55 AM, David Nadlinger wrote:
> On Friday, 22 April 2016 at 18:51:57 UTC, David Nadlinger wrote:
>> As long as elements are not removed too frequently (what do your numbers
>> say?), the performance impact of doing a full linear search in those cases
>> shouldn't be too bad.
>
> Note that a (properly tuned) probabilistic data structure like a Bloom filter
> allows you to avoid having to keep a full second copy of the list around,
> hopefully making it possible to keep the optimisation on by default without
> regrets. (For tiny modules with only a small number of members, you can still do
> the linear search to skip the hash lookup.)
>
>   — David

Why not just use a hash table? D's builtin one?

On Friday, 22 April 2016 at 21:48:09 UTC, Walter Bright wrote:
> Why not just use a hash table? D's builtin one?

Apparently, some parts rely on the insertion order, although I'm not convinced they should. Module::importAll is one of them, but in a way that's trivial to avoid. I didn't check any other locations.

If order is not important, a hash set should be fine.

 — David

On 4/22/2016 2:38 PM, Johan Engelen wrote:
> I don't understand exactly what you mean; do you propose to resort to linear
> search after a removal happened? Or only do a linear search when the shadow data
> structure says the item is present?
> I don't know how often removals happen, but for the 140k elements list removals
> happens _very_ often. While compiling phobos, removals happen not for all
> modules, but for quite a few of them.

I did a grep for "members.remove" and got no hits. Where are the removes happening?