Supercharging the Git Commit Graph IV: Bloom Filters • Hacker News Board

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#41

Post by stolee » Wed, Jul 18, 2018, 10:33 AM UTC

kingosticks wrote: post #38

stolee wrote: post #17

Earlier quoted context omitted.

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.

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?

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.

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#42

Post by stolee » Wed, Jul 18, 2018, 10:50 AM UTC

kanox wrote: post #39

stolee wrote: post #24

Earlier quoted context omitted.

Do you mean `git branch --contains` or `git branch -vv`? There are many options to `git branch` that cause Git to be very slow. The commit-graph feature in general will make these faster by reducing time spent parsing commits. You can compute a commit-graph right now if you have Git 2.18 installed: https://blogs.msdn.microsoft.com/devops/2018/06/25/superchar... Generation numbers will make these operations much faste…

A long time ago I made an alias always passes -v to git branch and this is the problem: on large repos it can take a long time to compute the "ahead X, behind Y" information. It can be fixed by aliasing to some git branch --format without %(upstream:track) Those numbers not really useful interactively when very large, for example it doesn't help to print that one of my branches is "behind 132132". Maybe git could pri…

Earlier this year, we considered similar changes to the ahead/behind calculation in 'git status'. We concluded that there is no good way to provide partial information. Specifically, you can't say "10 ahead" without walking everything you are behind to find all merge-bases. That "10" you found could become smaller by walking more of the other set. We instead opted to not calculate that information as often.

Here is my reply to the thread on-list that summarizes why I think this direction is futile: https://public-inbox.org/git/20180108154822.54829-1-git@jeff...

This ahead/behind calculation is in a lot of places, including 'git fetch' where it checks if each ref update was a forced update (checks if the new ref value has the old ref value in its history). For our version of Git that ships with GVFS, we added an option to skip this check, providing a significant speedup to users fetch times: https://github.com/Microsoft/git/commit/9616c7da3141f539a425...

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#43

Post by avar » Wed, Jul 18, 2018, 12:40 PM UTC

influx wrote: post #25

avar wrote: post #13

Earlier quoted context omitted.

[Source: I contribute to Git and talked to Twitter's "git guys" at the time at Git Merge, am not affiliated with Twitter in any way] My understanding is that they didn't cargo-cult anything. They made a conscious choice at Twitter to pursue the monorepo model. One reason they mentioned is that while they have a lot of services running all over the place, those services tend to heavily use the same underlying base lib…

Sure, that was the justification, but when you literally can’t switch branches without waiting for a minute, I fail to see the benefit. As I recall the developers authoring the custom git patches left the company around that time. I don’t know what happened after that. There was talk of moving to mercurial with facebooks patches, but I had already left.

It would be interesting to get some background info on that branch switching.

Switching branches per-se is really cheap in git, on linux.git it takes 200ms, around the time it takes to run a cold "git status". This is because just creating a new branch doesn't need to touch the tree at all.

I know "status" was a bottleneck at Twitter. They had the first inotify patches to git, but it never made it in. Eventually the patches Microsoft wrote to do the same thing made it in.

What can get expensive is if the tree you're switching to has drastically different content. On the latest linux.git (~60k files) switching to the 2.6.* era takes around 10 seconds or me (~10k files).

I'd expect with a monorepo model like what Twitter had (has?) that most working branches are relatively up-to-date with the master branch, so switching should be cheap.

Was it spending most of its time in the "Checking out files" phase, or before that?

Was this on e.g. OSX with some corporate virus scanner running where each I/O syscall was wrapped? That can drastically slow things down.

Or was it just that the repository truly had a ridiculous amount of files in the checkout (around 1 million?).

Edit: I remember now that I have an old copy of 2015-04-03-1M-git.git which David Turner of Twitter publicly shared a while back, it was meant to emulate the size and shape of Twitter's monorepo. It has around 230k files.

Re: Supercharging the Git Commit Graph IV: Bloom Filters

#44

Post by kingosticks » Wed, Jul 18, 2018, 12:46 PM UTC

stolee wrote: post #41

kingosticks wrote: post #38

Earlier quoted context omitted.

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?

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.

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