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.
