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

[Jeff King <peff@peff.net>]

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

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

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

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

-Peff