From: Jeff King <firstname.lastname@example.org> To: Derrick Stolee <email@example.com> Cc: "SZEDER Gábor" <firstname.lastname@example.org>, "Ævar Arnfjörð Bjarmason" <email@example.com>, "Stefan Beller" <firstname.lastname@example.org>, git <email@example.com>, "Duy Nguyen" <firstname.lastname@example.org> Subject: Re: We should add a "git gc --auto" after "git clone" due to commit graph Date: Mon, 8 Oct 2018 23:08:03 -0400 [thread overview] Message-ID: <20181009030803.GA6250@sigill.intra.peff.net> (raw) In-Reply-To: <email@example.com> On Mon, Oct 08, 2018 at 02:29:47PM -0400, Derrick Stolee wrote: > > > > But I'm afraid it will take a while until I get around to turn it into > > > > something presentable... > > > Do you have the code pushed somewhere public where one could take a look? I > > > Do you have the code pushed somewhere public where one could take a > > > look? I could provide some early feedback. > > Nah, definitely not... I know full well how embarassingly broken this > > implementation is, I don't need others to tell me that ;) > There are two questions that I was hoping to answer by looking at your code: > > 1. How do you store your Bloom filter? Is it connected to the commit-graph > and split on a commit-by-commit basis (storing "$path" as a key), or is it > one huge Bloom filter (storing "$commitid:$path" as key)? I guess you've probably thought all of this through for your implementation, but let me pontificate. I'd have done it as one fixed-size filter per commit. Then you should be able to hash the path keys once, and apply the result as a bitwise query to each individual commit (I'm assuming that it's constant-time to access the filter for each, as an index into an mmap'd array, with the offset coming from a commit-graph entry we'd be able to look up anyway). I think it would also be easier to deal with maintenance, since each filter is independent (IIRC, you cannot delete from a bloom filter without re-adding all of the other keys). The obvious downside is that it's O(commits) storage instead of O(1). Now let me ponder a bit further afield. A bloom filter lets us answer the question "did this commit (probably) touch these paths?". But it does not let us answer "which paths did this commit touch?". That second one is less useful than you might think, because we almost always care about not just the names of the paths, but their actual object ids. Think about a --raw diff, or even traversing for reachability (where if we knew the tree-diff cheaply, we could avoid asking "have we seen this yet?" on most of the tree entries). The names alone can make that a bit faster, but in the worst case you still have to walk the whole tree to find their entries. But there's also a related question: how do we match pathspec patterns? For a changed path like "foo/bar/baz", I imagine a bloom filter would mark all of "foo", "foo/bar", and "foo/bar/baz". But what about "*.c"? I don't think a bloom filter can answer that. At least not by itself. If we imagine that the commit-graph also had an alphabetized list of every path in every tree, then it's easy: apply the glob to that list once to get a set of concrete paths, and then query the bloom filters for those. And that list actually isn't too big. The complete set of paths in linux.git is only about 300k gzipped (I think that's the most relevant measure, since it's an obvious win to avoid repeating shared prefixes of long paths). Imagine we have that list. Is a bloom filter still the best data structure for each commit? At the point that we have the complete universe of paths, we could give each commit a bitmap of changed paths. That lets us ask "did this commit touch these paths" (collect the bits from the list of paths, then check for 1's), as well as "what paths did we touch" (collect the 1 bits, and then index the path list). Those bitmaps should compress very well via EWAH or similar (most of them would be huge stretches of 0's punctuated by short runs of 1's). So that seems promising to me (or at least not an obvious dead-end). I do think maintenance gets to be a headache, though. Adding new paths potentially means reordering the bitmaps, which means O(commits) work to "incrementally" update the structure. (Unless you always add the new paths at the end, but then you lose fast lookups in the list; that might be an acceptable tradeoff). And finally, there's one more radical option: could we actually store a real per-commit tree-diff cache? I.e., imagine that each commit had the equivalent of a --raw diff easily accessible, including object ids. That would allow: - fast pathspec matches, including globs - fast --raw output (and faster -p output, since we can skip the tree entirely) - fast reachability traversals (we only need to bother to look at the objects for changed entries) where "fast" is basically O(size of commit's changes), rather than O(size of whole tree). This was one of the big ideas of packv4 that never materialized. You can _almost_ do it with packv2, since after all, we end up storing many trees as deltas. But those deltas are byte-wise so it's hard for a reader to convert them directly into a pure-tree diff (they also don't mention the "deleted" data, so it's really only half a diff). So let's imagine we'd store such a cache external to the regular object data (i.e., as a commit-graph entry). The "log --raw" diff of linux.git has 1.7M entries. The paths should easily compress to a single 32-bit integer (e.g., as an index into a big path list). The oids are 20 bytes. Add a few bytes for modes. That's about 80MB. Big, but not impossibly so. Maybe pushing it for true gigantic repos, though. Those numbers are ignoring merges, too. The meaning of "did this commit touch that path" is a lot trickier for a merge commit, and I think may depend on context. I'm not sure how even a bloom filter solution would handle that (I was assuming we'd mostly punt and let merges fall back to opening up the trees). Phew. That was a lot. I don't want to derail any useful work either of you is doing. These are just things I've been thinking over (or even in some cases experimenting with), and I think it's worth laying all the options on the table. I won't be surprised if you'd considered and rejected any of these alternate approaches, but I'd be curious to hear the counter-arguments. :) -Peff
next prev parent reply other threads:[~2018-10-09 3:08 UTC|newest] Thread overview: 78+ messages / expand[flat|nested] mbox.gz Atom feed top 2018-10-03 13:23 Ævar Arnfjörð Bjarmason 2018-10-03 13:36 ` SZEDER Gábor 2018-10-03 13:42 ` Derrick Stolee 2018-10-03 14:18 ` Ævar Arnfjörð Bjarmason 2018-10-03 14:01 ` Ævar Arnfjörð Bjarmason 2018-10-03 14:17 ` SZEDER Gábor 2018-10-03 14:22 ` Ævar Arnfjörð Bjarmason 2018-10-03 14:53 ` SZEDER Gábor 2018-10-03 15:19 ` Ævar Arnfjörð Bjarmason 2018-10-03 16:59 ` SZEDER Gábor 2018-10-05 6:09 ` Junio C Hamano 2018-10-10 22:07 ` SZEDER Gábor 2018-10-10 23:01 ` Ævar Arnfjörð Bjarmason 2018-10-03 19:08 ` Stefan Beller 2018-10-03 19:21 ` Jeff King 2018-10-03 20:35 ` Ævar Arnfjörð Bjarmason 2018-10-03 17:47 ` Stefan Beller 2018-10-03 18:47 ` Ævar Arnfjörð Bjarmason 2018-10-03 18:51 ` Jeff King 2018-10-03 18:59 ` Derrick Stolee 2018-10-03 19:18 ` Jeff King 2018-10-08 16:41 ` SZEDER Gábor 2018-10-08 16:57 ` Derrick Stolee 2018-10-08 18:10 ` SZEDER Gábor 2018-10-08 18:29 ` Derrick Stolee 2018-10-09 3:08 ` Jeff King [this message] 2018-10-09 13:48 ` Bloom Filters (was Re: We should add a "git gc --auto" after "git clone" due to commit graph) Derrick Stolee 2018-10-09 18:45 ` Ævar Arnfjörð Bjarmason 2018-10-09 18:46 ` Jeff King 2018-10-09 19:03 ` Derrick Stolee 2018-10-09 21:14 ` Jeff King 2018-10-09 23:12 ` Bloom Filters Jeff King 2018-10-09 23:13 ` [PoC -- do not apply 1/3] initial tree-bitmap proof of concept Jeff King 2018-10-09 23:14 ` [PoC -- do not apply 2/3] test-tree-bitmap: add "dump" mode Jeff King 2018-10-10 0:48 ` Junio C Hamano 2018-10-11 3:13 ` Jeff King 2018-10-09 23:14 ` [PoC -- do not apply 3/3] test-tree-bitmap: replace ewah with custom rle encoding Jeff King 2018-10-10 0:58 ` Junio C Hamano 2018-10-11 3:20 ` Jeff King 2018-10-11 12:33 ` Bloom Filters Derrick Stolee 2018-10-11 13:43 ` Jeff King 2018-10-09 21:30 ` We should add a "git gc --auto" after "git clone" due to commit graph SZEDER Gábor 2018-10-09 19:34 ` [PATCH 0/4] Bloom filter experiment SZEDER Gábor 2018-10-09 19:34 ` [PATCH 1/4] Add a (very) barebones Bloom filter implementation SZEDER Gábor 2018-10-09 19:34 ` [PATCH 2/4] commit-graph: write a Bloom filter containing changed paths for each commit SZEDER Gábor 2018-10-09 21:06 ` Jeff King 2018-10-09 21:37 ` SZEDER Gábor 2018-10-09 19:34 ` [PATCH 3/4] revision.c: use the Bloom filter to speed up path-limited revision walks SZEDER Gábor 2018-10-09 19:34 ` [PATCH 4/4] revision.c: add GIT_TRACE_BLOOM_FILTER for a bit of statistics SZEDER Gábor 2018-10-09 19:47 ` [PATCH 0/4] Bloom filter experiment Derrick Stolee 2018-10-11 1:21 ` [PATCH 0/2] Per-commit filter proof of concept Jonathan Tan 2018-10-11 1:21 ` [PATCH 1/2] One filter per commit Jonathan Tan 2018-10-11 12:49 ` Derrick Stolee 2018-10-11 19:11 ` [PATCH] Per-commit and per-parent filters for 2 parents Jonathan Tan 2018-10-11 1:21 ` [PATCH 2/2] Only make bloom filter for first parent Jonathan Tan 2018-10-11 7:37 ` [PATCH 0/2] Per-commit filter proof of concept Ævar Arnfjörð Bjarmason 2018-10-15 14:39 ` [PATCH 0/4] Bloom filter experiment Derrick Stolee 2018-10-16 4:45 ` Junio C Hamano 2018-10-16 11:13 ` Derrick Stolee 2018-10-16 12:57 ` Ævar Arnfjörð Bjarmason 2018-10-16 13:03 ` Derrick Stolee 2018-10-18 2:00 ` Junio C Hamano 2018-10-16 23:41 ` Jonathan Tan 2018-10-08 23:02 ` We should add a "git gc --auto" after "git clone" due to commit graph Junio C Hamano 2018-10-03 14:32 ` Duy Nguyen 2018-10-03 16:45 ` Duy Nguyen 2018-10-04 21:42 ` [RFC PATCH] " Ævar Arnfjörð Bjarmason 2018-10-05 12:05 ` Derrick Stolee 2018-10-05 13:05 ` Ævar Arnfjörð Bjarmason 2018-10-05 13:45 ` Derrick Stolee 2018-10-05 14:04 ` Ævar Arnfjörð Bjarmason 2018-10-05 19:21 ` Jeff King 2018-10-05 19:41 ` Derrick Stolee 2018-10-05 19:47 ` Jeff King 2018-10-05 20:00 ` Derrick Stolee 2018-10-05 20:02 ` Jeff King 2018-10-05 20:01 ` Ævar Arnfjörð Bjarmason 2018-10-05 20:09 ` Jeff King
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20181009030803.GA6250@sigill.intra.peff.net \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --subject='Re: We should add a "git gc --auto" after "git clone" due to commit graph' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).