On Fri, Jul 02, 2021 at 01:44:12PM -0400, Taylor Blau wrote: > I would add that these effects change with the size of the bitmap. > Let's just consider the "count the number of objects in a bitmapped > commit". On my local copy of the kernel, I see a relatively modest > improvement: > > $ tip=2ab38c17aac10bf55ab3efde4c4db3893d8691d2 > $ hyperfine \ > 'GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $tip' \ > 'GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $tip' \ > --warmup=3 > Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $tip > Time (mean ± σ): 21.5 ms ± 5.6 ms [User: 8.7 ms, System: 12.7 ms] > Range (min … max): 12.4 ms … 34.2 ms 170 runs > > Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $tip > Time (mean ± σ): 10.6 ms ± 1.6 ms [User: 7.1 ms, System: 3.5 ms] > Range (min … max): 4.5 ms … 11.9 ms 258 runs > > but on my copy of the kernel's fork network repo (that containing all of > torvalds/linux's objects, as well as all of its fork's objects, too), > the magnitude of the effect is much bigger: > > Benchmark #1: GIT_READ_COMMIT_TABLE=0 git.compile rev-list --count --objects --use-bitmap-index $tip > Time (mean ± σ): 332.3 ms ± 12.6 ms [User: 210.4 ms, System: 121.8 ms] > Range (min … max): 322.7 ms … 362.4 ms 10 runs > > Benchmark #2: GIT_READ_COMMIT_TABLE=1 git.compile rev-list --count --objects --use-bitmap-index $tip > Time (mean ± σ): 260.0 ms ± 9.3 ms [User: 191.0 ms, System: 69.0 ms] > Range (min … max): 250.4 ms … 272.8 ms 11 runs > > That's a more modest 1.28x improvement (versus 2.03x in just linux.git), > but the overall magnitude is much bigger. Thanks, this is much more compelling. 70ms is a lot of startup time to save. I am a little surprised that a no-traversal bitmap query like this would still take 300ms. I wonder if 2ab38c17aac actually got a bitmap in your second example (and if not, then there are probably cases where the relative speedup would be even more impressive). > This clouded up some of my timings in p5310, which made me think that it > would be a good idea to `git config pack.writeReverseIndex true` in the > setup for those tests, but an even better direction would be to change > the default of pack.writeReverseIndex to true everywhere. Yes, I'd be in favor of that. IMHO the reason to make it configurable at all was not because it's ever a bad idea, but just to phase it in and get experience with it (and to give an escape hatch for debugging it). It's probably _less_ useful for local clones that are not serving fetches. But every push is already generating the same thing in-memory, so it seems like a good tradeoff to just use it everywhere. > > - there's some extra complexity in the file format and code to read > > and write these (and still fall back to the old system when they're > > absent). I don't think it's a deal-breaker, as it's really not that > > complicated a feature. > > I agree with both of these. The complexity is manageable, I think, > especially since I dropped support for the extended offset table (having > a bitmap file that is >2GiB seems extremely unlikely to me, and it's > possible to add support for it in the future) and > fanout table (there are usually less than <1k commits with bitmaps, so > a 256-entry fanout table doesn't seem to help much in benchmarking). > > So what's left of the format is really just: > > - a table of object id's > - a table of (uint32_t, uint32_t) tuples describing the (short) offset > of the bitmap, and an index position of the xor'd bitmap (if one > exists). Yeah, that really seems quite simple. I'd have to judge after seeing the cleaned up code, but I suspect it's not going to be a burden. > I'll be offline for the next ~week and a half for my wedding, but I'll > post some patches to the list shortly after I get back. Yep, no rush. Thanks for looking into this. -Peff
