Supercharging the Git Commit Graph IV: Bloom Filters – Microsoft DevOps Blog

SRANK

We’ve been discussing the commit-graph feature in Git 2.18 and how we can use generation numbers to accelerate commit walks. One area where we can get significant speedup is when presenting output in topological order. This allows us to walk a much smaller list of commits than before. One place where this breaks down is when we apply a filter to our results.For instance, if we filter by a path, then we are asking for a set of commits that modified that path. The following Git command returns the commits that changed “The/Path/To/My/File.txt” in the master branch:git log master -- The/Path/To/My/File.txtIf the path is not modified very often, then we need to walk more of the commit graph in order to return the results. What’s more, we need to walk a number of trees to determine if the path was modified. In the example above, we need to walk five trees: the root tree and four nested trees for the directories above “File.txt”.These behaviors combine to make some history calls slow.…