DMD internal: appendToModuleMember performance

[Johan Engelen via Digitalmars-d]

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.