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

[Bryan Turner <bturner@atlassian.com>]

On Fri, Mar 5, 2021 at 12:47 AM Jeff King <peff@peff.net> wrote:
>
> 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.

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.

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

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