Re: rev-list --use-bitmap-index

On Fri, Mar 5, 2021 at 12:47 AM Jeff King [off-list ref] wrote:

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

quoted

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.

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.

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.

quoted

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:

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).

quoted

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?

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).

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

-Peff