rev-list --use-bitmap-index

The documentation for --use-bitmap-index notes that if used with --objects trees and blobs they won't have their paths printed, but it appears to change a whole lot more than that. In my testing, it appears to mean --date-order, --format. --parents, and maybe more are effectively ignored.

It appears this changed in 2.26.0. The release notes for that version
include this blurb, which seems like it might be relevant, but I'm not
sure:
* The object reachability bitmap machinery and the partial cloning
  machinery were not prepared to work well together, because some
  object-filtering criteria that partial clones use inherently rely
  on object traversal, but the bitmap machinery is an optimization
  to bypass that object traversal. There however are some cases
  where they can work together, and they were taught about them.

I have a repository with a bitmap: $ git repack -abdfln --keep-unreachable Marked 2 islands, done. Enumerating objects: 3603142, done. Propagating island marks: 100% (2576295/2576295), done. Counting objects: 100% (3603142/3603142), done. Delta compression using up to 20 threads Compressing objects: 100% (2898179/2898179), done. Writing objects: 100% (3603142/3603142), done. Reusing bitmaps: 291, done. Selecting bitmap commits: 293052, done. Building bitmaps: 100% (363/363), done.

Here's some output from Git 2.25.1: $ /opt/git/2.25.1/bin/git rev-list --boundary --ignore-missing --date-order --parents --use-bitmap-index c6abb83d2798415fa9fe0ebd683623620076b412 1c55e675a66cb98955232e1bd230119fd97a5467 634396036782682e7cd8c955070dfb30546ed58c -- | head c6abb83d2798415fa9fe0ebd683623620076b412 2c7281b151d0079acc3f9b2c67d4667e1c9bf6d9 634396036782682e7cd8c955070dfb30546ed58c 1c55e675a66cb98955232e1bd230119fd97a5467 2c7281b151d0079acc3f9b2c67d4667e1c9bf6d9 d672894d3b2413b62034cb3cdb3470e5dee0001c 76250ec85aadff2ff451ec13efdadb8ccfd6b239 d672894d3b2413b62034cb3cdb3470e5dee0001c 013343e1900330429bcd1e31bb2ae7261fc1e3af 3e1e27621aa5f1d49286e23d77199004a835699e 3e1e27621aa5f1d49286e23d77199004a835699e b944291d204cb7f3d5eb7678360b16435c53b2f3 b745a7b9bd9434eefb411d5f2a80a7187e3e8b93 1c55e675a66cb98955232e1bd230119fd97a5467 7f2c871e0d239e87bef7a1505ae928ae3a09a402 76250ec85aadff2ff451ec13efdadb8ccfd6b239 04f561866a9c015c14c69a0294b753ced5e084f2 013343e1900330429bcd1e31bb2ae7261fc1e3af d907528818d010a360113790e227ebbcd8a61395 b745a7b9bd9434eefb411d5f2a80a7187e3e8b93 b944291d204cb7f3d5eb7678360b16435c53b2f3 7f2c871e0d239e87bef7a1505ae928ae3a09a402 c2ec4d3d76d865a9b701eb8be822d31252278a76

Changing to Git 2.26.0, I see this: $ /opt/git/2.26.0/bin/git rev-list --boundary --ignore-missing --date-order --parents --use-bitmap-index c6abb83d2798415fa9fe0ebd683623620076b412 1c55e675a66cb98955232e1bd230119fd97a5467 634396036782682e7cd8c955070dfb30546ed58c -- | head 634396036782682e7cd8c955070dfb30546ed58c 1c55e675a66cb98955232e1bd230119fd97a5467 7f2c871e0d239e87bef7a1505ae928ae3a09a402 c2ec4d3d76d865a9b701eb8be822d31252278a76 899053a9043045fcfeb7f9254f2700d286c60a63 f1adcf64a8c06cb12f4e3e876040ee596fb3c0ca 16792db59ffdbbefe4a27a11a9831eac39be69a0 b844c3d11d09c2aec3428ce61bef02fdd097b9f9 802918fb139ef96cae5259822d22a36478c5e7b1 3a6105686ab302093648733dbf5fada3b44db72b

No parents now, and the commits aren't in the same order. I've tested with 2.30.1 and it produces the same output as 2.26.0. If I remove the bitmap, all versions produce the same output as 2.25.1 does, with parents and in the expected order. (I should note, the bitmap is perfectly up-to-date; I did the repack right before running these rev-list commands. I've also tried the rev-list without several of the options in place, like --boundary, and it behaves the same. This command line is assembled automatically, so I'm just including it here how the system produced it.)

Is this expected? If so, perhaps the --use-bitmap-index documentation should be updated to indicate that it has unexpected interactions with a whole lot more than just --objects? Or perhaps I'm doing something wrong/unexpected here? What sorts of traversals are --use-bitmap-index expected to be used for?

Best regards, Bryan Turner

On Fri, Mar 5, 2021 at 12:18 AM Bryan Turner <bturner@atlassian.com> wrote:

Apologies, it looks like Gmail helpfully jumped in and ruined my output for me. Let me try this with shorter hashes: c6abb83 2c7281b 6343960 1c55e67 2c7281b d672894 76250ec d672894 013343e 3e1e276 3e1e276 b944291 b745a7b 1c55e67 7f2c871 76250ec 04f5618 013343e d907528 b745a7b b944291 7f2c871 c2ec4d3d

All of these are on their own lines, as shown.

On Fri, Mar 05, 2021 at 12:18:15AM -0800, Bryan Turner wrote:

Yes, quite a few options won't work with bitmaps. The order you get is not a traversal order at all, but mostly just the order of objects within the pack (and then with any extra traversal we had to do tacked onto the end!). Likewise something like "--boundary", as that implies that we actually walked the graph. We probably _could_ support --format and --parents, but don't.

Probably the documentation should be strengthened to say that --use-bitmap-index implies thinking about the resulting objects as a set result, rather than a traversal. Or maybe that's getting too into the weeds.

It has always been the case that those options wouldn't work with bitmaps. But v2.26 did let us use bitmaps in more cases.

The blurb you mentioned is a bit of a red herring; it only applies when --filter is used. The interesting commit for your example below is 4eb707ebd6 (rev-list: allow commit-only bitmap traversals, 2020-02-14).

The "--use-bitmap-index" option is really "if you can use bitmaps to speed things up, do so". So prior to v2.26 it was simply being ignored in your example (and you got no speedup benefit from specifying it).

That "use it if you can" behavior should probably likewise be documented. Callers need to be prepared to receive either result (and hence asking for stuff like --boundary does not make any sense at all).

The interesting traversals IMHO are:

  - with --objects, quickly getting the result set (but without paths,
    and without any ordering)

  - with --count (with or without --objects), because we avoid quite a
    bit of work by counting bits rather than walking the graph

  - with the new --disk-usage, which likewise avoids a bunch of work

Asking about just commits via bitmaps isn't that big a speed improvement these days, because commit graphs make the cost to actually traverse each commit way cheaper (see the numbers in the commit I mentioned above).

So the behavior you're seeing is expected, but probably not all that useful (and you should likely just drop --use-bitmap-index).

-Peff

On Fri, Mar 5, 2021 at 12:47 AM Jeff King <peff@peff.net> wrote:

I can't speak for anyone else, but to me that actually feels a lot
less "in the weeds" than the current documentation.
- The existing documentation talks about "speeding up the traversal",
but your comment here suggests what it actually does is _eliminate_
the traversal--producing output that's totally different (in terms of
ordering and content) to what a traversal would have produced
- The existing documentation talks about one specific flag, --objects,
where the output can change dramatically depending on whether
--use-bitmap-index is applied, but it doesn't hint at all that there
are other flags that are also affected, or may just be outright
ignored

Documenting that --use-bitmap-index produces a set, rather than a traversal, might be more clear.

Thanks for all the details, Jeff, and for taking the time to provide such a thorough answer. I had figured there must be some potential downsides to --use-bitmap-index--otherwise, if it was just a simple "go faster" knob I'd expect it would have long ago been enabled by default--but trying to figure out what they are is tricky. And as they start to materialize, the next challenge is to figure out, given those downsides, where the upsides are useful.

Based on your list here, there are a couple places where I think I could see some benefits, in other commands that I run, but it's clear it's not a general-use option.

-b