Re: [PATCH 0/4] Bloom filter experiment
- From
- Jonathan Tan <jonathantanmy@google.com>
- Date
- Oct 16, 2018, 23:41 UTC
- Message-ID
- <20181016234129.194138-1-jonathantanmy@google.com>
- In-Reply-To
- <61559c5b-546e-d61b-d2e1-68de692f5972@gmail.com>
Show 8 quoted lines
> | Implementation | Queries | Maybe | FP # | FP % | > |----------------|---------|-------|------|-------| > | Szeder | 66095 | 1142 | 256 | 0.38% | > | Jonathan | 66459 | 107 | 89 | 0.16% | > | Stolee | 53025 | 492 | 479 | 0.90% | > > (Note that we must have used different starting points, which is why my > "Queries" is so much smaller.)
I suspect it's because your bloom filter implementation covers only the first parent (if I'm understanding get_bloom_filter() correctly). When I only covered the first parent in my initial test (see patch 2 of [1]), I got (following the columns in the table above):
53096 107 89 0.001676
Also, I think that the rejecting power (Queries - Maybe)/(Total tree comparisons if no bloom filters were used) needs to be in the evaluation criteria somewhere, as that indicates how many tree comparisons we managed to avoid.
Also, we probably should also test on a file that changes more frequently :-)
[1] https://public-inbox.org/git/cover.1539219248.git.jonathantanmy@google.com/
Show 8 quoted lines
> The increase in false-positive percentage is expected in my > implementation. I'm using the correct filter sizes to hit a <1% FP > ratio. This could be lowered by changing the settings, and the size > would dynamically grow. For my Git repo (which contains > git-for-windows/git and microsoft/git) this implementation grows the > commmit-graph file from 5.8 MB to 7.3 MB (1.5 MB total, compared to > Szeder's 8MB filter). For 105,260 commits, that rounds out to less than > 20 bytes per commit (compared to Jonathan's 256 bytes per commit).
Mine has 256 bits per commit, which is 32 bytes per commit (still more than yours).
Having said all that, thanks for writing up your version - in particular, variable sized filters (like in yours) seem to be the way to go.
> We'll see how much time I have to do this polish, but I think the > benefit is proven.
Agreed.