Supercharging the Git Commit Graph IV: Bloom Filters

Re:Supercharging the Git Commit Graph IV: Bloom Filters by stolee on Tuesday July 17, 2018 @06:33AM (#17548644)

It does! The Bloom filter stores every path that changed, including paths to trees (except the root tree, which is expected to be changed by default). When you change a file, you also change every tree above it.

[ Parent | on HN ]

Re:Supercharging the Git Commit Graph IV: Bloom Filters by kingosticks on Tuesday July 17, 2018 @03:40PM (#17552550)

So presumably that eats into the 512 item limit. If I had quite a deep directory structure (10 levels doesn't sound that unreasonable) I'd only get this speedup for commits changing 51 files or less. Right?

[ Parent | on HN ]

Re:Supercharging the Git Commit Graph IV: Bloom Filters by stolee on Wednesday July 18, 2018 @06:33AM (#17557004)

In your calculation, you are assuming that all of those files are in independent parts of the folder hierarchy. In practice, deep directory structures mean that single commits are likely focused in a few very deep folders. We ran the statistics on a number of repos with different shapes to come up with this number, and it covers 99% of commits that we measured.

[ Parent | on HN ]

Re:Supercharging the Git Commit Graph IV: Bloom Filters by kingosticks on Wednesday July 18, 2018 @08:46AM (#17557834)

That is true and I do agree. Thanks for clarifying and for the informative write-up, it's a great use of bloom filters.

[ Parent | on HN ]