Re: [PATCH 09/11] pack-bitmap: enable cross-pack delta reuse

[Taylor Blau <me@ttaylorr.com>]

On Fri, Oct 11, 2024 at 04:31:34AM -0400, Jeff King wrote:
> On Wed, Oct 09, 2024 at 04:31:28PM -0400, Taylor Blau wrote:
>
> > In order to do this, the pack-reuse code within pack-bitmap.c marks
> > bits in a separate bitmap called 'reuse_as_ref_delta'. Objects whose
> > bits are marked in that bitmap must be converted from OFS_DELTAs to
> > REF_DELTAs.
> >
> > To mark bits in that bitmap, we adjust find_base_bitmap_pos() to
> > return the bitmap position of any delta object's base regardless of
> > whether or not it came from the same pack. This is done by:
> >
> >   1. First converting the base object's into a pack position (via
> >      `offset_to_pack_pos()`).
> >
> >   2. Then converting from pack position into into lexical order (via
> >      `pack_pos_to_index()`).
> >
> >   3. Then into an object ID (via `nth_packed_object_id()`).
> >
> >   4. Then into a position in the MIDX's lexical order of object IDs
> >      (via `bsearch_midx()`).
> >
> >   5. And finally into a position in the MIDX's pseudo-pack order (via
> >      `midx_pair_to_pack_pos()`).
> >
> > If we can find that base object in the MIDX, then we use its position
> > in the MIDX's pseudo-pack order to determine whether or not it was
> > selected from the same pack. If it is, no adjustment is necessary.
> > Otherwise, we mark the delta object's position in the new
> > `reuse_as_ref_delta` bitmap, and convert accordingly from within
> > `write_reused_pack_one()`.
>
> OK, that makes sense. It does feel like a non-trivial amount of work to
> do for each delta we're going to (potentially) reuse from a midx'd pack.
> Can we recognize the common case that the base is in the same pack and
> also being sent/reused without doing the full conversion to oid and the
> resulting bsearch?

I don't think it ends up saving you anything if you don't find anything
matching the pack/offset pair in the MIDX. If you perform that lookup
with bsearch_midx() and get nothing back, then you have to take the
slower path above anyway.

My figuring here was that it would be better to uniformly take a
slightly slower path instead of taking a hopefully-faster path which
might fail, only to then go back to the slower path on top.

Of course, you could do both, or apply some heuristics like avoiding the
cross-pack lookup if you know you're in the preferred pack, etc. I'm not
sure how much it is worth doing so, TBH.

> > @@ -1182,10 +1188,24 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,
> >  	if (pos >= end)
> >  		return reuse_packfile->bitmap_pos / BITS_IN_EWORD;
> >
> > -	while (pos < end &&
> > -	       reuse_packfile_bitmap->words[pos / BITS_IN_EWORD] == (eword_t)~0)
> > +	while (pos < end) {
> > +		size_t wpos = pos / BITS_IN_EWORD;
> > +		eword_t reuse;
> > +
> > +		reuse = reuse_packfile_bitmap->words[wpos];
> > +		if (reuse_as_ref_delta_packfile_bitmap) {
> > +			/*
> > +			 * Can't reuse verbatim any objects which need
> > +			 * to be first rewritten as REF_DELTAs.
> > +			 */
> > +			reuse &= ~reuse_as_ref_delta_packfile_bitmap->words[wpos];
> > +		}
> > +
> > +		if (reuse != (eword_t)~0)
> > +			break;
> > +
> >  		pos += BITS_IN_EWORD;
> > -
> > +	}
>
> This is accessing reuse_as_ref_delta_packfile_bitmap->words directly
> using pos/end as limits. But those come from reuse_packfile_bitmap. Are
> we guaranteed to have zero-extended the reuse_as_ref_delta bitmap as far
> as the original went?

Yeah, we know this is OK because both are allocated with the same size
in reuse_partial_packfile_from_bitmap(), where the relevant portion is:

    word_alloc = objects_nr / BITS_IN_EWORD;
    if (objects_nr % BITS_IN_EWORD)
            word_alloc++;

    reuse = bitmap_word_alloc(word_alloc);
    reuse_as_ref_delta = bitmap_word_alloc(word_alloc);

all of the bitmap_set() operations on the former are bounded in
try_partial_reuse(), but adding a length check can be done here as an
extra safety measure.

> Could we just be calling bitmap_get() here, which would do the length
> check for us? Though I guess we would miss out on some whole-word magic
> it is doing. So maybe we need to just do that length check ourselves.

Yeah, we don't use bitmap_get() because we want to access the whole word
at a time.

Thanks,
Taylor