pack-bitmap: convert offset to ref deltas where possible
cover pack-bitmap: convert offset to ref deltas where possible
This patch series enables more objects to be candidates for verbatim reuse when generating a pack with the aide of reachability bitmaps.
By the end of this series, two new classes of objects are now reuse candidates which were not before. They are:
- Cross-pack deltas. In multi-pack bitmaps, if the delta and base were selected from different packs, the delta was not reusable.
- Thin deltas. In both single- and multi-pack bitmaps, we did not consider reusing deltas whose base object appears in the 'haves' bitmap.
This series teaches the pack-objects machinery to convert cross-pack and thin deltas to reference deltas so that they may be reused.
The series started off as a couple of patches, each addressing one of the two classes from the above. But as I started refining these patches, the series grew longer, as there were a handful of opportunities to clean up some of the existing pack-reuse bitmap code.
The series is organized as follows:
- The first seven patches are various cleanups that make the pack-reuse code more readable and prepare us to enable delta reuse in more situation as above.
pack-bitmap.c: do not pass pack_pos to try_partial_reuse() pack-bitmap.c: avoid unnecessary offset_to_pack_pos() pack-bitmap.c: delay calling 'offset_to_pack_pos()' pack-bitmap.c: compare base_offset to delta_obj_offset pack-bitmap.c: extract find_base_bitmap_pos()
pack-bitmap: drop from_midx field from bitmapped_pack write_reused_pack_one(): translate bit positions directly
- The next patch is a test fixup:
t5332: enable OFS_DELTAs via test_pack_objects_reused
- The next patch after that enables us to reuse deltas whose base appears in another pack:
pack-bitmap: enable cross-pack delta reuse
- The final two patches enable the "thin deltas" optimization above:
pack-bitmap.c: record whether the result was filtered
pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap
I think that the first seven patches are worthwhile on their own. I considered splitting those out into their own series, but decided against it to so that we could realize their benefit more readily.
The first optimization (cross-pack deltas) should help clones and fetches, but the second optimization (thin deltas) will only help fetches, since the 'haves' bitmap will necessarily be empty for clones.
Of course, REF_DELTAs have a less compact representation than OFS_DELTAs, so the resulting packs will trade off some CPU time for a slightly larger pack. But we're only talking about a handful of extra bytes, and network bandwidth is pretty cheap, so I think the optimization is worthwhile here too.
Thanks in advance for your review!
Taylor Blau (11):
pack-bitmap.c: do not pass pack_pos to try_partial_reuse() pack-bitmap.c: avoid unnecessary offset_to_pack_pos() pack-bitmap.c: delay calling 'offset_to_pack_pos()' pack-bitmap.c: compare base_offset to delta_obj_offset pack-bitmap.c: extract find_base_bitmap_pos()
pack-bitmap: drop from_midx field from bitmapped_pack write_reused_pack_one(): translate bit positions directly
t5332: enable OFS_DELTAs via test_pack_objects_reused
pack-bitmap: enable cross-pack delta reuse
pack-bitmap.c: record whether the result was filtered
pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap
builtin/pack-objects.c | 110 ++++++++++++-------- midx.c | 1 - pack-bitmap.c | 198 ++++++++++++++++++++++++------------ pack-bitmap.h | 6 +- t/t5332-multi-pack-reuse.sh | 72 ++++++++++++- 5 files changed, 275 insertions(+), 112 deletions(-)
base-commit: 777489f9e09c8d0dd6b12f9d90de6376330577a2
Signature · 1 line
2.47.0.11.g487258bca34
PATCH 1/11 pack-bitmap.c: do not pass `pack_pos` to `try_partial_reuse()`
The function try_partial_reuse() uses its pack_pos parameter to determine if:
- the object specified by that position is in bounds of the pack it's operating on, and
- in the case that the specified object is an OFS_DELTA (and we're operating on a single-pack reachability bitmap) to ensure that the position of the base object occurs earlier than the delta
But neither of these checks are necessary. The bounds-check is redundant because we are operating on bit positions which we know correspond to objects in some pack, and the caller in reuse_partial_packfile_from_bitmap_1() is smart enough to know to stop processing bits when it is at the end of some pack.
Likewise, the delta dependency check is also unnecessary, because we can use the object offsets within a single pack as a proxy for bit positions in that pack's bitmap.
So let's avoid passing in this redundant piece of information, and save one call to offset_to_pack_pos(), which is O(log N) in the number of objects in the pack we're currently processing.
(This all comes from a discussion on a semi-related series from [1]).
[1]: https://lore.kernel.org/git/[email protected]/
--- pack-bitmap.c | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-)
pack-bitmap.c +9 -12
@@ -2054,7 +2054,6 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,static int try_partial_reuse (struct bitmap_index *bitmap_git,struct bitmapped_pack *pack,size_t bitmap_pos, -uint32_t pack_pos,off_t offset,struct bitmap *reuse,struct pack_window **w_curs)
@@ -2063,9 +2062,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,enum object_type type;unsigned long size; -if (pack_pos >= pack->p->num_objects) -return -1 ;/* not actually in the pack */ - delta_obj_offset = offset; type =unpack_object_header (pack->p, w_curs, &offset, &size);if (type <0 )
@@ -2121,8 +2117,13 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,* OFS_DELTA is the default). But let's double check to * make sure the pack wasn't written with odd * parameters. +* +* Since we're working on a single-pack bitmap, we can +* use the object offset as a proxy for the bit +* position, since the bits are ordered by their +* positions within the pack. */ -if (base_pos >= pack_pos) +if (base_offset >= offset)return 0 ; base_bitmap_pos = pack->bitmap_pos + base_pos; }
@@ -2184,7 +2185,6 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_gitfor (offset =0 ; offset <BITS_IN_EWORD ; offset++) {size_t bit_pos; -uint32_t pack_pos;off_t ofs;if (word >> offset ==0 )
@@ -2203,12 +2203,9 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git midx_pos =pack_pos_to_midx (bitmap_git->midx, bit_pos); ofs =nth_midxed_offset (bitmap_git->midx, midx_pos); - -if (offset_to_pack_pos (pack->p, ofs, &pack_pos) <0 ) -BUG ("could not find object in pack %s " -"at offset %" PRIuMAX" in MIDX" , -pack_basename (pack->p), (uintmax_t )ofs); }else { +uint32_t pack_pos; + pack_pos =cast_size_t_to_uint32_t (st_sub (bit_pos, pack->bitmap_pos));if (pack_pos >= pack->p->num_objects) BUG("advanced beyond the end of pack %s (%"PRIuMAX" > %"PRIu32")",
@@ -2219,7 +2216,7 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git }if (try_partial_reuse (bitmap_git, pack, bit_pos, - pack_pos, ofs, reuse, &w_curs) <0 ) { + ofs, reuse, &w_curs) <0 ) {/* * try_partial_reuse indicated we couldn't reuse * any bits, so there is no point in trying more
Signature · 1 line
2.47.0.11.g487258bca34
PATCH 2/11 pack-bitmap.c: avoid unnecessary `offset_to_pack_pos()`
In reply to Taylor BlauIn try_partial_reuse(), for any object which is either an OFS_DELTA or REF_DELTA, we need to determine the bitmap position for its base.
We handle the case of single- and multi-pack bitmaps separately:
- For multi-pack bitmaps, we look to see if the MIDX selected the base we're looking at to represent that object. If the base object was selected from a different pack in the MIDX, we won't reuse the delta.
- For single-pack bitmaps, we convert the base object's offset into a pack-relative position (identified here as 'base_pos') by calling offset_to_pack_pos().
But we also call offset_to_pack_pos() before handling each case above separately. For the MIDX case, this is unnecessary, since we don't need to lookup the base object's pack-relative position; instead, we just care whether the selected copy of that base is from the same pack we're currently operating on.
For the non-MIDX case, we end up calling offset_to_pack_pos() again, yielding the same result, making the earlier call wasteful. This behavior dates back to 519e17ff75 (pack-bitmap: prepare to mark objects from multiple packs for reuse, 2023-12-14).
Let's correct that by avoiding the unconditional call to 'offset_to_pack_pos()'.
--- pack-bitmap.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-)
pack-bitmap.c +2 -3
@@ -2069,7 +2069,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,if (type ==OBJ_REF_DELTA || type ==OBJ_OFS_DELTA ) {off_t base_offset; -uint32_t base_pos;uint32_t base_bitmap_pos;/*
@@ -2085,8 +2084,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,if (!base_offset)return 0 ; -offset_to_pack_pos (pack->p, base_offset, &base_pos); -if (bitmap_is_midx (bitmap_git)) {/* * Cross-pack deltas are rejected for now, but could
@@ -2105,6 +2102,8 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,return 0 ; } }else { +uint32_t base_pos; +if (offset_to_pack_pos (pack->p, base_offset, &base_pos) <0 )return 0 ;
Signature · 1 line
2.47.0.11.g487258bca34
PATCH 3/11 pack-bitmap.c: delay calling 'offset_to_pack_pos()'
In reply to Taylor BlauWhen handling single object reuse from a single-pack bitmap, we first convert the base object's offset into a pack-relative position. Then, we check if the base object's offset occurs after the delta object's offset. If that's the case, then we kick the delta'd object back to the slow path.
But there are a couple of oddities here:
- However unlikely it is that we'll find a delta/base pair with base_offset >= offset, it doesn't make sense to convert the base's offset to a pack-relative position if we're going to throw out the reuse opportunity anyway.
- We "convert" the base object's position into bitmap order by offsetting it by 'pack->bitmap_pos'. But this makes no sense, since single-pack bitmaps have only one pack (by definition), and that pack's first object occurs at bit position 0.
Let's clean up this part of 'try_partial_reuse()' by (a) first seeing if we can reuse the delta before converting its base object's offset into a pack position, and (b) avoid an unnecessary conversion with 'pack->bitmap_pos'.
(b) allows us to avoid the intermediate 'base_pos' variable, and instead write directly into 'base_bitmap_pos', which we also change here for further clarity.
--- pack-bitmap.c | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-)
pack-bitmap.c +3 -6
@@ -2102,11 +2102,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,return 0 ; } }else { -uint32_t base_pos; - -if (offset_to_pack_pos (pack->p, base_offset, - &base_pos) <0 ) -return 0 ;/* * We assume delta dependencies always point backwards. * This lets us do a single pass, and is basically
@@ -2124,7 +2119,9 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,*/ if (base_offset >= offset)return 0 ; - base_bitmap_pos = pack->bitmap_pos + base_pos; +if (offset_to_pack_pos (pack->p, base_offset, + &base_bitmap_pos) <0 ) +return 0 ; }/*
Signature · 1 line
2.47.0.11.g487258bca34
PATCH 4/11 pack-bitmap.c: compare `base_offset` to `delta_obj_offset`
In reply to Taylor BlauWhen comparing the offsets of either half of a delta/base-pair, we compare base_offset to offset.
There is nothing functionally wrong with that comparison, but it is slightly confusing, since offset points to just after the delta object's type header in the pack, whereas base_offset points to the beginning of the header.
In practice, that distinction does not matter, and it is perfectly fine to compare base_offset to offset.
But we already make a copy of offset before it is moved forward by calling the function unpack_object_header(). So let's use that copy (which points at the beginning of the delta object's header) in the comparison so that we are comparing like quantities.
--- pack-bitmap.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
pack-bitmap.c +1 -1
@@ -2117,7 +2117,7 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,* position, since the bits are ordered by their * positions within the pack. */ -if (base_offset >= offset) +if (base_offset >= delta_obj_offset)return 0 ;if (offset_to_pack_pos (pack->p, base_offset, &base_bitmap_pos) <0 )
Signature · 1 line
2.47.0.11.g487258bca34
PATCH 5/11 pack-bitmap.c: extract `find_base_bitmap_pos()`
In reply to Taylor BlauInside of try_partial_reuse() is a block of code that handles specially the case where the object we are attempting reuse on is either an OFS_DELTA or a REF_DELTA.
Extract that part of the routine out to a separate function, named find_base_bitmap_pos(). This will allow us to make that routine slightly more complex in order to implement cross-pack and thin-delta conversion (which we'll describe in detail in subsequent patches) without compromising the readability of its caller, try_partial_reuse().
--- pack-bitmap.c | 90 ++++++++++++++++++++++++++++----------------------- 1 file changed, 49 insertions(+), 41 deletions(-)
pack-bitmap.c +49 -41
@@ -2047,6 +2047,52 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,return NULL ; } +static int find_base_bitmap_pos (struct bitmap_index *bitmap_git, +struct bitmapped_pack *pack, +off_t base_offset, +off_t delta_obj_offset, +uint32_t *base_bitmap_pos) +{ +if (bitmap_is_midx (bitmap_git)) { +/* +* Cross-pack deltas are rejected for now, but could +* theoretically be supported in the future. +* +* We would need to ensure that we're sending both +* halves of the delta/base pair, regardless of whether +* or not the two cross a pack boundary. If they do, +* then we must convert the delta to an REF_DELTA to +* refer back to the base in the other pack. +* */ +if (midx_pair_to_pack_pos (bitmap_git->midx, pack->pack_int_id, + base_offset, base_bitmap_pos) <0 ) +return -1 ; + }else { +/* +* We assume delta dependencies always point backwards. +* This lets us do a single pass, and is basically +* always true due to the way OFS_DELTAs work. You would +* not typically find REF_DELTA in a bitmapped pack, +* since we only bitmap packs we write fresh, and +* OFS_DELTA is the default). But let's double check to +* make sure the pack wasn't written with odd +* parameters. +* +* Since we're working on a single-pack bitmap, we can +* use the object offset as a proxy for the bit +* position, since the bits are ordered by their +* positions within the pack. +*/ +if (base_offset >= delta_obj_offset) +return -1 ; +if (offset_to_pack_pos (pack->p, base_offset, + base_bitmap_pos) <0 ) +return -1 ; + } + +return 0 ; +} +/* * -1 means "stop trying further objects"; 0 means we may or may not have * reused, but you can keep feeding bits.
@@ -2081,49 +2127,11 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,*/ base_offset =get_delta_base (pack->p, w_curs, &offset, type, delta_obj_offset); -if (!base_offset) +if (!base_offset || +find_base_bitmap_pos (bitmap_git, pack, base_offset, + delta_obj_offset, &base_bitmap_pos) <0 )return 0 ; -if (bitmap_is_midx (bitmap_git)) { -/* -* Cross-pack deltas are rejected for now, but could -* theoretically be supported in the future. -* -* We would need to ensure that we're sending both -* halves of the delta/base pair, regardless of whether -* or not the two cross a pack boundary. If they do, -* then we must convert the delta to an REF_DELTA to -* refer back to the base in the other pack. -* */ -if (midx_pair_to_pack_pos (bitmap_git->midx, - pack->pack_int_id, - base_offset, - &base_bitmap_pos) <0 ) { -return 0 ; - } - }else { -/* -* We assume delta dependencies always point backwards. -* This lets us do a single pass, and is basically -* always true due to the way OFS_DELTAs work. You would -* not typically find REF_DELTA in a bitmapped pack, -* since we only bitmap packs we write fresh, and -* OFS_DELTA is the default). But let's double check to -* make sure the pack wasn't written with odd -* parameters. -* -* Since we're working on a single-pack bitmap, we can -* use the object offset as a proxy for the bit -* position, since the bits are ordered by their -* positions within the pack. -*/ -if (base_offset >= delta_obj_offset) -return 0 ; -if (offset_to_pack_pos (pack->p, base_offset, - &base_bitmap_pos) <0 ) -return 0 ; - } -/* * And finally, if we're not sending the base as part of our * reuse chunk, then don't send this object either. The base
Signature · 1 line
2.47.0.11.g487258bca34
PATCH 6/11 pack-bitmap: drop `from_midx` field from `bitmapped_pack`
In reply to Taylor BlauThis field was added in 41cd4b478f7 (pack-bitmap: tag bitmapped packs with their corresponding MIDX, 2024-08-27) in order to expose the bitmap's MIDX in order to translate bit positions correctly from within 'pack-objects' during pack-reuse (c.f., 125c32605ab (builtin/pack-objects.c: translate bit positions during pack-reuse, 2024-08-27) for more details).
But another approach would have been to use the ->midx field of the struct bitmap_index * directly, which feels clearer and avoids duplicating information.
Unfortunately, we can't access that field directly since it is part of the bitmap_index structure which is static within the pack-bitmap.c compilation unit.
So let's instead introduce a new function which returns that pointer to us, and replace the from_midx field with uses of that new function (which we call bitmap_midx() here).
--- builtin/pack-objects.c | 4 ++-- midx.c | 1 - pack-bitmap.c | 6 +++++- pack-bitmap.h | 2 +- 4 files changed, 8 insertions(+), 5 deletions(-)
builtin/pack-objects.c +2 -2
@@ -1201,7 +1201,7 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,if (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr) goto done; -if (reuse_packfile->bitmap_pos) { +if (bitmap_is_midx (bitmap_git)) {/* * When doing multi-pack reuse on a * non-preferred pack, translate bit positions
@@ -1209,7 +1209,7 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,* pack-relative positions before attempting * reuse. */ -struct multi_pack_index *m = reuse_packfile->from_midx; +struct multi_pack_index *m =bitmap_midx (bitmap_git);uint32_t midx_pos;off_t pack_ofs;
midx.c +0 -1
@@ -496,7 +496,6 @@ int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id + sizeof(uint32_t)); bp->pack_int_id = pack_int_id; - bp->from_midx = m;return 0 ; }
pack-bitmap.c +5 -1
@@ -2326,7 +2326,6 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git, packs[packs_nr].pack_int_id = pack_int_id; packs[packs_nr].bitmap_nr = pack->num_objects; packs[packs_nr].bitmap_pos =0 ; - packs[packs_nr].from_midx = bitmap_git->midx; objects_nr = packs[packs_nr++].bitmap_nr; }
@@ -2981,6 +2980,11 @@ int bitmap_is_midx(struct bitmap_index *bitmap_git)return !!bitmap_git->midx; } +struct multi_pack_index *bitmap_midx (struct bitmap_index *bitmap_git) +{ +return bitmap_git->midx; +} +const struct string_list *bitmap_preferred_tips (struct repository *r) {const struct string_list *dest;
pack-bitmap.h +1 -1
@@ -60,7 +60,6 @@ struct bitmapped_pack {uint32_t bitmap_pos;uint32_t bitmap_nr; -struct multi_pack_index *from_midx;/* MIDX only */ uint32_t pack_int_id;/* MIDX only */ };
@@ -157,6 +156,7 @@ char *midx_bitmap_filename(struct multi_pack_index *midx);char *pack_bitmap_filename (struct packed_git *p);int bitmap_is_midx (struct bitmap_index *bitmap_git); +struct multi_pack_index *bitmap_midx (struct bitmap_index *bitmap_git);const struct string_list *bitmap_preferred_tips (struct repository *r);int bitmap_is_preferred_refname (struct repository *r,const char *refname);
Signature · 1 line
2.47.0.11.g487258bca34
PATCH 7/11 write_reused_pack_one(): translate bit positions directly
In reply to Taylor BlauA future commit will want to deal with bit positions instead of pack positions from within builtin/pack-objects.c::write_reused_pack_one().
That function at present takes a pack position, so one approach to accommodating the new functionality would be to add a secondary bit position parameter, making the function's declaration look something like:
static void write_reused_pack_one(struct packed_git *reuse_packfile,
size_t pack_pos, size_t bitmap_pos, struct hashfile *out, off_t pack_start, struct pack_window **w_curs);
But because the pack-relative position can be easily derived from the bit position, it makes senes to just pass the latter and let the function itself translate it into a pack-relative position.
To do this, extract a new function bitmap_to_pack_pos() from the existing write_reused_pack() function. This new routine is responsible for performing the conversion from bitmap- to pack-relative positions.
Instead of performing that translation in write_reused_pack(), instead call the new function from within write_reused_pack_one() so that we can just pass a single bit position to it.
--- builtin/pack-objects.c | 78 ++++++++++++++++++++++-------------------- 1 file changed, 41 insertions(+), 37 deletions(-)
builtin/pack-objects.c +41 -37
@@ -1017,6 +1017,42 @@ static off_t find_reused_offset(off_t where)return reused_chunks[lo-1 ].difference; } +static uint32_t bitmap_to_pack_pos (struct packed_git *reuse_packfile, +size_t pos) +{ +if (bitmap_is_midx (bitmap_git)) { +/* +* When doing multi-pack reuse on a +* non-preferred pack, translate bit positions +* from the MIDX pseudo-pack order back to their +* pack-relative positions before attempting +* reuse. +*/ +struct multi_pack_index *m =bitmap_midx (bitmap_git); +uint32_t midx_pos, pack_pos; +off_t pack_ofs; + +if (!m) +BUG ("non-zero bitmap position without MIDX" ); + + midx_pos =pack_pos_to_midx (m, pos); + pack_ofs =nth_midxed_offset (m, midx_pos); + +if (offset_to_pack_pos (reuse_packfile, pack_ofs, &pack_pos) <0 ) +BUG ("could not find expected object at offset %" PRIuMAX" in pack %s" , + (uintmax_t )pack_ofs,pack_basename (reuse_packfile)); + +return pack_pos; + }else { +/* +* Can use bit positions directly, even for MIDX +* bitmaps. See comment in try_partial_reuse() +* for why. +*/ +return pos; + } +} + static void write_reused_pack_one(struct packed_git *reuse_packfile, size_t pos, struct hashfile *out, off_t pack_start,
@@ -1025,9 +1061,10 @@ static void write_reused_pack_one(struct packed_git *reuse_packfile,off_t offset, next, cur;enum object_type type;unsigned long size; +uint32_t pack_pos =bitmap_to_pack_pos (reuse_packfile, pos); - offset =pack_pos_to_offset (reuse_packfile, pos); - next =pack_pos_to_offset (reuse_packfile, pos +1 ); + offset =pack_pos_to_offset (reuse_packfile, pack_pos); + next =pack_pos_to_offset (reuse_packfile, pack_pos +1 );record_reused_object (offset, offset - (hashfile_total (out) - pack_start));
@@ -1191,7 +1228,6 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,size_t pos = (i *BITS_IN_EWORD );for (offset =0 ; offset <BITS_IN_EWORD ; ++offset) { -uint32_t pack_pos;if ((word >> offset) ==0 )break ;
@@ -1201,40 +1237,8 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,if (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr) goto done; -if (bitmap_is_midx (bitmap_git)) { -/* -* When doing multi-pack reuse on a -* non-preferred pack, translate bit positions -* from the MIDX pseudo-pack order back to their -* pack-relative positions before attempting -* reuse. -*/ -struct multi_pack_index *m =bitmap_midx (bitmap_git); -uint32_t midx_pos; -off_t pack_ofs; - -if (!m) -BUG ("non-zero bitmap position without MIDX" ); - - midx_pos =pack_pos_to_midx (m, pos + offset); - pack_ofs =nth_midxed_offset (m, midx_pos); - -if (offset_to_pack_pos (reuse_packfile->p, - pack_ofs, &pack_pos) <0 ) -BUG ("could not find expected object at offset %" PRIuMAX" in pack %s" , - (uintmax_t )pack_ofs, -pack_basename (reuse_packfile->p)); - }else { -/* -* Can use bit positions directly, even for MIDX -* bitmaps. See comment in try_partial_reuse() -* for why. -*/ - pack_pos = pos + offset; - } - -write_reused_pack_one (reuse_packfile->p, pack_pos, f, - pack_start, &w_curs); +write_reused_pack_one (reuse_packfile->p, pos + offset, + f, pack_start, &w_curs);display_progress (progress_state, ++written); } }
Signature · 1 line
2.47.0.11.g487258bca34
Re: [PATCH 07/11] write_reused_pack_one(): translate bit positions directly
Quoted 7 lines · Taylor Blau
builtin/pack-objects.c +7
-0+static uint32_t bitmap_to_pack_pos (struct packed_git *reuse_packfile, +size_t pos) +{ +if (bitmap_is_midx (bitmap_git)) { +/* +* When doing multi-pack reuse on a +* non-preferred pack, translate bit positions
builtin/pack-objects.c static off_t find_reused_offset(off_t where) · line 1036
Quoted 10 lines
builtin/pack-objects.c +10
-0+* from the MIDX pseudo-pack order back to their +* pack-relative positions before attempting +* reuse. +*/ +struct multi_pack_index *m =bitmap_midx (bitmap_git); +uint32_t midx_pos, pack_pos; +off_t pack_ofs; + +if (!m) +BUG ("non-zero bitmap position without MIDX" );
The text of this BUG() seems weird: we haven't asserted a non-zero bitmap position. We're really only checking that bitmap_is_midx() and bitmap_midx() agree that there is a midx. I was going to suggest that the former could be implemented with a NULL-check on the latter, but really, that is already how it works (except that it accesses bitmap_index->midx directly).
So yes, it truly would be a surprising BUG() to see them disagree. :)
I do not mind keeping the BUG() there if you want to be extra careful, but I just found the message text confusing.
Ah...hmm. This is all being copied from the earlier function. So I think the culprit may be patch 6, which swaps:
if (reuse_packfile->bitmap_pos)
for:
if (bitmap_is_midx(bitmap_git))
which is what makes the BUG() text confusing. But then, what about this:
builtin/pack-objects.c static off_t find_reused_offset(off_t where) · line 1054
Quoted 9 lines
builtin/pack-objects.c +9
-0+ }else { +/* +* Can use bit positions directly, even for MIDX +* bitmaps. See comment in try_partial_reuse() +* for why. +*/ +return pos; + } +}
This "even for MIDX" is not really accurate, as we know this else block is for the non-midx case. Are we losing the optimization that the first pack in the midx can be treated the same as the single-pack case (we know that its pack positions and the start of the midx bit positions are identical, which is what the comment it mentions explains)?
-Peff
Re: [PATCH 07/11] write_reused_pack_one(): translate bit positions directly
Quoted 11 lines · Jeff King
Ah...hmm. This is all being copied from the earlier function. So I think the culprit may be patch 6, which swaps:
if (
reuse_packfile->bitmap_pos)for:
if (
bitmap_is_midx(bitmap_git))which is what makes the
BUG()text confusing. But then, what about this:
Quoted 15 lines
builtin/pack-objects.c static off_t find_reused_offset(off_t where) · line 1054
Quoted 9 lines
builtin/pack-objects.c +9
-0+ }else { +/* +* Can use bit positions directly, even for MIDX +* bitmaps. See comment in try_partial_reuse() +* for why. +*/ +return pos; + } +}This "even for MIDX" is not really accurate, as we know this else block is for the non-midx case. Are we losing the optimization that the first pack in the midx can be treated the same as the single-pack case (we know that its pack positions and the start of the midx bit positions are identical, which is what the comment it mentions explains)?
Great catch.
We indeed lost that optimization when converting "if (reuse_packfile->bitmap_pos)" to "if (bitmap_is_midx(bitmap_git))". Let's restore that by keeping the conditional unchanged, which:
- makes the BUG() make sense as written, and
- preserves the optimization where the first pack in a MIDX can be treated the same as if it came from a single-pack bitmap, and bypass the bit position translations.
Thanks for spotting.
Thanks,
Taylor
PATCH 8/11 t5332: enable OFS_DELTAs via test_pack_objects_reused
In reply to Taylor BlauBack when test_pack_objects_reused was introduced via commit 7c01878eeb (t5332-multi-pack-reuse.sh: extract pack-objects helper functions, 2024-02-05), we converted bare pack-objects invocations into one of two wrapped variants, either test_pack_objects_reused or test_pack_objects_reused_all.
The latter passes --delta-base-offset, allowing pack-objects to generate OFS_DELTAs in its output pack. But the former does not, for no good reason.
As we do not want to convert OFS_DELTAs to REF_DELTAs unnecessarily, let's unify these two and pass --delta-base-offset to both.
Instrumenting the codepath
where we convert OFS_DELTAs to REF_DELTAs with a BUG() like so:
builtin/pack-objects.c +2 -0
@@ -1051,6 +1051,8 @@ static void write_reused_pack_one(struct packed_git *reuse_packfile,uint32_t base_pos;struct object_id base_oid; +BUG ("tested" ); +if (offset_to_pack_pos (reuse_packfile, base_offset, &base_pos) <0 ) die(_("expected object at offset %"PRIuMAX" " "in pack %s"),
, and seeing what test(s) fail yields the following.
Test Summary Report
-------------------
t5326-multi-pack-bitmaps.sh (Wstat: 256 (exited 1) Tests: 357 Failed: 6)
Failed tests: 46, 91, 167, 220, 265, 341
Non-zero exit status: 1
t5310-pack-bitmaps.sh (Wstat: 256 (exited 1) Tests: 227 Failed: 6)
Failed tests: 46-47, 120-121, 197-198
Non-zero exit status: 1
t5327-multi-pack-bitmaps-rev.sh (Wstat: 256 (exited 1) Tests: 314 Failed: 6)
Failed tests: 46, 91, 157, 203, 248, 314
Non-zero exit status: 1
So the OFS_DELTA to REF_DELTA conversion is still tested thoroughly in t5310, t5326, and t5327.
--- t/t5332-multi-pack-reuse.sh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
t/t5332-multi-pack-reuse.sh +1 -1
@@ -43,7 +43,7 @@ test_pack_objects_reused_all () { test_pack_objects_reused () { : >trace2.txt && GIT_TRACE2_EVENT="$PWD/trace2.txt" \ - git pack-objects --stdout --revs >got.pack && + git pack-objects --delta-base-offset --stdout --revs >got.pack && test_pack_reused "$1" <trace2.txt && test_packs_reused "$2" <trace2.txt &&
Signature · 1 line
2.47.0.11.g487258bca34
Re: [PATCH 08/11] t5332: enable OFS_DELTAs via test_pack_objects_reused
Quoted 6 lines · Taylor Blau
Back when
test_pack_objects_reusedwas introduced via commit7c01878eeb(t5332-multi-pack-reuse.sh: extract pack-objects helper functions, 2024-02-05), we converted bare pack-objects invocations into one of two wrapped variants, eithertest_pack_objects_reusedortest_pack_objects_reused_all.
Quoted 6 lines
The latter passes
--delta-base-offset, allowing pack-objects to generateOFS_DELTAsin its output pack. But the former does not, for no good reason.As we do not want to convert
OFS_DELTAstoREF_DELTAsunnecessarily, let's unify these two and pass--delta-base-offsetto both.
I think that matches what happens in the real world. I am puzzled that your BUG() instrumenting turns up some conversion cases. Why are we still converting in those cases?
builtin/pack-objects.c
Quoted 4 lines
builtin/pack-objects.c +0
-0
You need to indent or otherwise comment-out this diff. Otherwise "git am" will pick it up as the start of the actual diff, adding the bogus BUG() call to the applied patch (and dropping the rest of your commit message).
-Peff
Re: [PATCH 08/11] t5332: enable OFS_DELTAs via test_pack_objects_reused
Quoted 12 lines · Jeff King
Quoted 10 lines · Taylor Blau
Back when
test_pack_objects_reusedwas introduced via commit7c01878eeb(t5332-multi-pack-reuse.sh: extract pack-objects helper functions, 2024-02-05), we converted bare pack-objects invocations into one of two wrapped variants, eithertest_pack_objects_reusedortest_pack_objects_reused_all.The latter passes
--delta-base-offset, allowing pack-objects to generateOFS_DELTAsin its output pack. But the former does not, for no good reason.
Quoted 6 lines
Quoted 2 lines
As we do not want to convert
OFS_DELTAstoREF_DELTAsunnecessarily, let's unify these two and pass--delta-base-offsetto both.I think that matches what happens in the real world. I am puzzled that your
BUG()instrumenting turns up some conversion cases. Why are we still converting in those cases?
These are cases where we're calling pack-objects directly without passing the --delta-base-offset flag, so all deltas get converted into REF_DELTAs.
Quoted 9 lines
builtin/pack-objects.c
Quoted 4 lines
builtin/pack-objects.c +0
-0You need to indent or otherwise comment-out this diff. Otherwise "git am" will pick it up as the start of the actual diff, adding the bogus
BUG()call to the applied patch (and dropping the rest of your commit message).
Oops, of course. Thanks for spotting again.
Thanks,
Taylor
PATCH 9/11 pack-bitmap: enable cross-pack delta reuse
In reply to Taylor BlauBack when multi-pack bitmaps were first introduced, we performed verbatim pack reuse over the MIDX's preferred pack only. Since all duplicate objects were resolved in favor of that pack, any object from the preferred pack that was stored as an OFS_DELTA is directly reusable.
That's not the case when we are reusing objects from multiple packs, like was introduced via af626ac0e0 (pack-bitmap: enable reuse from all bitmapped packs, 2023-12-14). When reusing an object stored as a delta from some pack other than the preferred one, it's possible that the base was selected from a different pack.
When that's the case, we could have converted those OFS_DELTAs to REF_DELTAs on the fly (like we do when running 'pack-objects' without the --delta-base-offset option). But af626ac0e0 decided instead to kick those objects back into the non-verbatim reuse path, meaning that reusing them was slightly slower.
This patch removes that limitation, and teaches pack-objects to convert deltas (whose base was selected from a different pack in the MIDX) from OFS_DELTAs to REF_DELTAs.
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().
The only tweak we need to make outside of the above is to teach write_reused_pack_verbatim() to only consider words of the reuse_packfile_bitmap as reusable verbatim if the word does not have any bits which are marked in the reuse_as_ref_delta bitmap, in which case they must be converted and cannot be reused verbatim.
--- builtin/pack-objects.c | 29 ++++++++++++++--- pack-bitmap.c | 63 +++++++++++++++++++++++++++---------- pack-bitmap.h | 1 + t/t5332-multi-pack-reuse.sh | 4 +-- 4 files changed, 75 insertions(+), 22 deletions(-)
builtin/pack-objects.c +25 -4
@@ -223,6 +223,7 @@ static size_t reuse_packfiles_nr;static size_t reuse_packfiles_used_nr;static uint32_t reuse_packfile_objects;static struct bitmap *reuse_packfile_bitmap; +static struct bitmap *reuse_as_ref_delta_packfile_bitmap;static int use_bitmap_index_default =1 ;static int use_bitmap_index =-1 ;
@@ -1084,7 +1085,8 @@ static void write_reused_pack_one(struct packed_git *reuse_packfile,assert (base_offset !=0 );/* Convert to REF_DELTA if we must... */ -if (!allow_ofs_delta) { +if (!allow_ofs_delta || +bitmap_get (reuse_as_ref_delta_packfile_bitmap, pos)) {uint32_t base_pos;struct object_id base_oid;
@@ -1160,6 +1162,10 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,if (!bitmap_get (reuse_packfile_bitmap, word_pos *BITS_IN_EWORD + offset))return word_pos; +if (reuse_as_ref_delta_packfile_bitmap && +bitmap_get (reuse_as_ref_delta_packfile_bitmap, + word_pos *BITS_IN_EWORD + offset)) +return word_pos; } pos +=BITS_IN_EWORD - (pos %BITS_IN_EWORD );
@@ -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 ; - + }if (pos > end) pos = end;
@@ -4078,6 +4098,7 @@ static int get_object_list_from_bitmap(struct rev_info *revs) &reuse_packfiles, &reuse_packfiles_nr, &reuse_packfile_bitmap, + &reuse_as_ref_delta_packfile_bitmap, allow_pack_reuse == MULTI_PACK_REUSE);if (reuse_packfiles) {
pack-bitmap.c +47 -16
138 lines not on this page · raw message
pack-bitmap.h +1 -0
@@ -86,6 +86,7 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,struct bitmapped_pack **packs_out, size_t *packs_nr_out, struct bitmap **reuse_out, + struct bitmap **reuse_as_ref_delta_out, int multi_pack_reuse);int rebuild_existing_bitmaps (struct bitmap_index *,struct packing_data *mapping,kh_oid_map_t *reused_bitmaps,int show_progress);
t/t5332-multi-pack-reuse.sh +2 -2
@@ -194,7 +194,7 @@ test_expect_success 'omit delta with uninteresting base (same pack)' ' test_pack_objects_reused 3 1 <in ' -test_expect_success 'omit delta from uninteresting base (cross pack)' ' +test_expect_success 'can retain delta from uninteresting base (cross pack)' ' cat >in <<-EOF && $(git rev-parse $base) ^$(git rev-parse $delta)
@@ -207,7 +207,7 @@ test_expect_success 'omit delta from uninteresting base (cross pack)' ' packs_nr="$(find $packdir -type f -name "pack-*.pack" | wc -l)" && objects_nr="$(git rev-list --count --all --objects)" && - test_pack_objects_reused_all $(($objects_nr - 1)) $packs_nr + test_pack_objects_reused_all $objects_nr $packs_nr ' test_expect_success 'non-omitted delta in MIDX preferred pack' '
Signature · 1 line
2.47.0.11.g487258bca34
Re: [PATCH 09/11] pack-bitmap: enable cross-pack delta reuse
Quoted 21 lines · Taylor Blau
In order to do this, the pack-reuse code within
pack-bitmap.cmarks bits in a separate bitmap called 'reuse_as_ref_delta'. Objects whose bits are marked in that bitmap must be converted fromOFS_DELTAstoREF_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
Quoted 8 lines
`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_deltabitmap, and convert accordingly from withinwrite_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?
Quoted 15 lines
builtin/pack-objects.c +9
-2@@ -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.
builtin/pack-objects.c static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile, · line 1208
Quoted 10 lines
builtin/pack-objects.c +8
-1+*/ + 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?
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.
-Peff
Re: [PATCH 09/11] pack-bitmap: enable cross-pack delta reuse
Quoted 32 lines · Jeff King
Quoted 21 lines · Taylor Blau
In order to do this, the pack-reuse code within
pack-bitmap.cmarks bits in a separate bitmap called 'reuse_as_ref_delta'. Objects whose bits are marked in that bitmap must be converted fromOFS_DELTAstoREF_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
Quoted 8 lines
`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_deltabitmap, and convert accordingly from withinwrite_reused_pack_one().
Quoted 5 lines
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.
Quoted 22 lines
Quoted 22 lines
builtin/pack-objects.c +16
-2@@ -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 ; +
Quoted 8 lines
builtin/pack-objects.c static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile, · line 1208
Quoted 3 lines
builtin/pack-objects.c +1
-1pos +=BITS_IN_EWORD ; - + }This is accessing
reuse_as_ref_delta_packfile_bitmap->wordsdirectly using pos/end as limits. But those come fromreuse_packfile_bitmap. Are we guaranteed to have zero-extended thereuse_as_ref_deltabitmap 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.
Quoted 3 lines
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
PATCH 10/11 pack-bitmap.c: record whether the result was filtered
In reply to Taylor BlauIn a following commit, we will prepare to mark objects for reuse which are stored as deltas, but whose base object wasn't included in the output pack (e.g., because the client already has it).
We can't, however, take advantage of that optimization when the traversal removed objects from the result due to either (a) object filtering, or (b) --unpacked.
That's because in either case, we can't rely on the principle that "if an object appears in the 'haves' bitmap, that the client already has that object", since they may not have it as a result of filtering.
Keep track of whether or not we performed any object filtering during our traversal in preparation to actually implement thin delta conversion.
--- pack-bitmap.c | 12 ++++++++++++ 1 file changed, 12 insertions(+)
pack-bitmap.c +12 -0
@@ -112,6 +112,12 @@ struct bitmap_index {/* "have" bitmap from the last performed walk */ struct bitmap *haves; +/* +* Whether the last performed walk had objects removed from +* 'result' due to object filtering. +*/ +int filtered; +/* Version of the bitmap index */ unsigned int version; };
@@ -1684,6 +1690,8 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,bitmap_unset (to_filter, pos); } + bitmap_git->filtered =1 ; +bitmap_free (tips); }
@@ -1776,6 +1784,8 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,bitmap_unset (to_filter, pos); } + bitmap_git->filtered =1 ; +bitmap_free (tips); }
@@ -1892,6 +1902,8 @@ static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git,if (has_object_pack (&eindex->objects[i]->oid))bitmap_unset (result, objects_nr + i); } + + bitmap_git->filtered =1 ; } struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
Signature · 1 line
2.47.0.11.g487258bca34
Re: [PATCH 10/11] pack-bitmap.c: record whether the result was filtered
Quoted 11 lines · Taylor Blau
In a following commit, we will prepare to mark objects for reuse which are stored as deltas, but whose base object wasn't included in the output pack (e.g., because the client already has it).
We can't, however, take advantage of that optimization when the traversal removed objects from the result due to either (a) object filtering, or (b) --unpacked.
That's because in either case, we can't rely on the principle that "if an object appears in the 'haves' bitmap, that the client already has that object", since they may not have it as a result of filtering.
I think this is a reasonable precaution, though it does make me wonder if the non-reuse code paths are so careful. That is, if we have object Y which is a delta against object X, but we know the other side _could_ have X (because it's reachable from some commit they claim to have), would we ever send a thin delta against X?
I don't recall seeing any protections for that, though I also wouldn't be too surprised if it somehow just works out because we never figure out whether they have X or not. :-/
I wonder, though: should thin deltas just be turned off entirely when filtering is in play?
Likewise for --unpacked (though in practice I think it would never be used with --thin, as it is about generating new on-disk packs).
-Peff
Re: [PATCH 10/11] pack-bitmap.c: record whether the result was filtered
Quoted 5 lines · Jeff King
I wonder, though: should thin deltas just be turned off entirely when filtering is in play?
Likewise for --unpacked (though in practice I think it would never be used with --thin, as it is about generating new on-disk packs).
They should; that's what this commit is setting us up to do in the next one, which does not allocate the "convert to REF_DELTAs" bitmap when filtering is in play.
Thanks,
Taylor
PATCH 11/11 pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap
In reply to Taylor BlauEver since the current verbatim pack-reuse strategy was devised in bb514de356 (pack-objects: improve partial packfile reuse, 2019-12-18), we have skipped sending delta objects whenever we're not sending that object's base.
But it's fine to send such an object as a REF_DELTA against the base object, provided the following are true:
- We know that the client has the object already, i.e. it appears in the 'haves' bitmap.
- The client supports thin packs, i.e. 'pack-objects' was invoked with the '--thin' option.
- The client did not request object filtering, in which case we cannot trust that they actually do have all of the objects in the 'haves' bitmap, since we only filter the 'result' bitmap.
When all of those criteria are met, we can send the delta object verbatim, meaning that we can reuse more objects from existing packs via the verbatim reuse mechanism, which should be faster than kicking those objects back to the slow path.
--- builtin/pack-objects.c | 3 +- pack-bitmap.c | 52 ++++++++++++++++++++--------- pack-bitmap.h | 3 +- t/t5332-multi-pack-reuse.sh | 66 +++++++++++++++++++++++++++++++++++++ 4 files changed, 107 insertions(+), 17 deletions(-)
builtin/pack-objects.c +2 -1
@@ -4099,7 +4099,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs) &reuse_packfiles_nr, &reuse_packfile_bitmap, &reuse_as_ref_delta_packfile_bitmap, - allow_pack_reuse == MULTI_PACK_REUSE); + allow_pack_reuse ==MULTI_PACK_REUSE , + thin);if (reuse_packfiles) { reuse_packfile_objects =bitmap_popcount (reuse_packfile_bitmap);
pack-bitmap.c +37 -15
99 lines not on this page · raw message
pack-bitmap.h +2 -1
@@ -87,7 +87,8 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,size_t *packs_nr_out, struct bitmap **reuse_out, struct bitmap **reuse_as_ref_delta_out, - int multi_pack_reuse); + int multi_pack_reuse, + int thin_deltas);int rebuild_existing_bitmaps (struct bitmap_index *,struct packing_data *mapping,kh_oid_map_t *reused_bitmaps,int show_progress);void free_bitmap_index (struct bitmap_index *);
t/t5332-multi-pack-reuse.sh +66 -0
78 lines not on this page · raw message
Signature · 1 line
2.47.0.11.g487258bca34
Quoted 8 lines · Taylor Blau
This patch series enables more objects to be candidates for verbatim reuse when generating a pack with the aide of reachability bitmaps.
By the end of this series, two new classes of objects are now reuse candidates which were not before. They are:
- Cross-pack deltas. In multi-pack bitmaps, if the delta and base were selected from different packs, the delta was not reusable.
Hmph. Suppose that you need to send object X, you happen to have X as a ofs-delta against Y, but Y may appear in multiple packs.
Even if the copy of Y you are going to send together with X is from the same packfile, you may not be sending all the objects between X and Y in the original local packfile, so you would need to recompute the offset to give ofs-delta X to the distance between X and Y in the resulting packstream, no?
So when you pick the copy of Y out of another pack, what's so different? After emitting Y to the resulting pack stream (and remembering where in the packstream you did so), when it is X's turn to be emitted, shouldn't you be able to compute the distance in the resulting packstream to represent X as an ofs-delta against Y, which should already be happening when you had both X and Y in the same original pack?
Quoted 3 lines
- Thin deltas. In both single- and multi-pack bitmaps, we did not consider reusing deltas whose base object appears in the 'haves' bitmap.
I hope this optimization does not kick in unless the receiving end is prepared to do "index-pack --fix-thin".
I've never thought about this specifically, but it is interesting to realize that by definition "thin" deltas cannot be ofs-deltas.
Quoted 3 lines
Of course,
REF_DELTAshave a less compact representation thanOFS_DELTAs, so the resulting packs will trade off some CPU time for a slightly larger pack.
Is comparing ref- vs ofs- delta a meaningful thing to do in the context of this series?
What does the current code without these patches do in the same situation? Give up on reusing the existing delta and then? If we send the base representation instead, the comparison is "we currently do not use delta, but with this change we can reuse delta (even though we do not bother recompute the offset and instead use ref-delta)".
Do we recompute the delta on the fly and show it as an ofs-delta with the current code? Then the comparison would be "we spend time doing diff-delta once right now but instead reuse an existing one (even though we do not bother recompute the offset and instead use ref-delta)".
Quoted 11 lines · Junio C Hamano
Quoted 8 lines · Taylor Blau
This patch series enables more objects to be candidates for verbatim reuse when generating a pack with the aide of reachability bitmaps.
By the end of this series, two new classes of objects are now reuse candidates which were not before. They are:
- Cross-pack deltas. In multi-pack bitmaps, if the delta and base were selected from different packs, the delta was not reusable.
Quoted 8 lines
Hmph. Suppose that you need to send object X, you happen to have X as a ofs-delta against Y, but Y may appear in multiple packs.
Even if the copy of Y you are going to send together with X is from the same packfile, you may not be sending all the objects between X and Y in the original local packfile, so you would need to recompute the offset to give ofs-delta X to the distance between X and Y in the resulting packstream, no?
That's right. When doing verbatim pack reuse, we mark reused "chunks" (c.f. 'struct reused_chunk'), where each chunk records the offset of the beginning of the chunk in the source pack, and the difference between that value and the corresponding byte in the assembled pack.
So suppose like in your example we have X and Y from the same pack, and we are sending both objects, but not necessarily every object in between the two from the source pack. In that case, X and Y will end up in different chunks.
When we go to actually rewrite the OFS_DELTA for X, we'll compute:
off_t fixup = find_reused_offset(X) - find_reused_offset(Y);
(in the code, X and Y are actually the offsets for each object in the source pack, but I'm using the object names here for clarity).
When there is a non-zero fixup value, we'll patch the OFS_DELTA to account for the gap between it and its base object. The details of how that is done are in builtin/pack-objects.c::write_reused_pack_one(), in the 'if (fixup) { ... }' block.
Quoted 7 lines
So when you pick the copy of Y out of another pack, what's so different? After emitting Y to the resulting pack stream (and remembering where in the packstream you did so), when it is X's turn to be emitted, shouldn't you be able to compute the distance in the resulting packstream to represent X as an ofs-delta against Y, which should already be happening when you had both X and Y in the same original pack?
Good question. The difference is that if you're reusing X and Y from same pack, you know that Y occurs some number of bytes *before* X in the resulting pack.
But if Y comes from a different pack, it may get pushed further back in the MIDX pseudo-pack order. So in that case the assembled pack may list X before Y, in which case X cannot be an OFS_DELTA of Y, since offset deltas require that the base object appears first.
Quoted 6 lines
Quoted 3 lines
- Thin deltas. In both single- and multi-pack bitmaps, we did not consider reusing deltas whose base object appears in the 'haves' bitmap.
I hope this optimization does not kick in unless the receiving end is prepared to do "index-pack --fix-thin".
It does. We only allow computing "thin deltas" when pack-objects was invoked with --thin.
Quoted 2 lines
I've never thought about this specifically, but it is interesting to realize that by definition "thin" deltas cannot be ofs-deltas.
Yep.
Quoted 7 lines
Quoted 3 lines
Of course,
REF_DELTAshave a less compact representation thanOFS_DELTAs, so the resulting packs will trade off some CPU time for a slightly larger pack.Is comparing ref- vs ofs- delta a meaningful thing to do in the context of this series?
Quoted 6 lines
What does the current code without these patches do in the same situation? Give up on reusing the existing delta and then? If we send the base representation instead, the comparison is "we currently do not use delta, but with this change we can reuse delta (even though we do not bother recompute the offset and instead use ref-delta)".
The current code does not reuse deltas when we're either (a) not sending the base, (b) we are sending the base, but it's in a different pack, or
(c) both. When any of those conditions are met, we do not reuse the existing on-disk representation of the delta object verbatim, and instead kick it back to the normal pack generation routine.
That might result in us finding a new base, or applying sending the object's contents as a standalone object.
Quoted 5 lines
Do we recompute the delta on the fly and show it as an ofs-delta with the current code? Then the comparison would be "we spend time doing diff-delta once right now but instead reuse an existing one (even though we do not bother recompute the offset and instead use ref-delta)".
Fair.
Thanks,
Taylor
Quoted 8 lines · Taylor Blau
Quoted 7 lines
So when you pick the copy of Y out of another pack, what's so different? After emitting Y to the resulting pack stream (and remembering where in the packstream you did so), when it is X's turn to be emitted, shouldn't you be able to compute the distance in the resulting packstream to represent X as an ofs-delta against Y, which should already be happening when you had both X and Y in the same original pack?
Quoted 8 lines
Good question. The difference is that if you're reusing X and Y from same pack, you know that Y occurs some number of bytes *before* X in the resulting pack.
But if Y comes from a different pack, it may get pushed further back in the MIDX pseudo-pack order. So in that case the assembled pack may list X before Y, in which case X cannot be an
OFS_DELTAof Y, since offset deltas require that the base object appears first.
That is what we have always done even before we started bitmap based optimization. If we happen to write Y before X, we consider doing ofs-delta for X, but otherwise we do ref-delta for X. We do reorder fairly late in the pipeline when we notice that X that we are about to write out depends on Y that we haven't emitted to avoid this, though. All of that the bitmap-based optimization code path should be able to imitate, I would think.
Quoted 19 lines · Junio C Hamano
Quoted 8 lines · Taylor Blau
Quoted 7 lines
So when you pick the copy of Y out of another pack, what's so different? After emitting Y to the resulting pack stream (and remembering where in the packstream you did so), when it is X's turn to be emitted, shouldn't you be able to compute the distance in the resulting packstream to represent X as an ofs-delta against Y, which should already be happening when you had both X and Y in the same original pack?
Quoted 8 lines
Good question. The difference is that if you're reusing X and Y from same pack, you know that Y occurs some number of bytes *before* X in the resulting pack.
But if Y comes from a different pack, it may get pushed further back in the MIDX pseudo-pack order. So in that case the assembled pack may list X before Y, in which case X cannot be an
OFS_DELTAof Y, since offset deltas require that the base object appears first.
Quoted 7 lines
That is what we have always done even before we started bitmap based optimization. If we happen to write Y before X, we consider doing ofs-delta for X, but otherwise we do ref-delta for X. We do reorder fairly late in the pipeline when we notice that X that we are about to write out depends on Y that we haven't emitted to avoid this, though. All of that the bitmap-based optimization code path should be able to imitate, I would think.
I see..., so yeah: before this patch series we would have not processed X via the bitmap-powered pack reuse mechanism, and after this series we will.
Thanks,
Taylor
Quoted 19 lines · Junio C Hamano
Quoted 8 lines · Taylor Blau
Quoted 7 lines
So when you pick the copy of Y out of another pack, what's so different? After emitting Y to the resulting pack stream (and remembering where in the packstream you did so), when it is X's turn to be emitted, shouldn't you be able to compute the distance in the resulting packstream to represent X as an ofs-delta against Y, which should already be happening when you had both X and Y in the same original pack?
Quoted 8 lines
Good question. The difference is that if you're reusing X and Y from same pack, you know that Y occurs some number of bytes *before* X in the resulting pack.
But if Y comes from a different pack, it may get pushed further back in the MIDX pseudo-pack order. So in that case the assembled pack may list X before Y, in which case X cannot be an
OFS_DELTAof Y, since offset deltas require that the base object appears first.
Quoted 7 lines
That is what we have always done even before we started bitmap based optimization. If we happen to write Y before X, we consider doing ofs-delta for X, but otherwise we do ref-delta for X. We do reorder fairly late in the pipeline when we notice that X that we are about to write out depends on Y that we haven't emitted to avoid this, though. All of that the bitmap-based optimization code path should be able to imitate, I would think.
A small nitpick on your final sentence here. As you note, we do not ever write Y before X, because compute_write_order() always places bases before their deltas in the output pack (and we do not allow cycles of deltas, of course).
And even with bitmaps we'd do the same, as long as those objects are both fed to the regular pack-writing machinery.
It is only the special verbatim-pack-reuse[1] code that is trying to blit out the start of an existing pack that is affected. And in theory there it _could_ try to reorder to produce an ofs delta, but in practice the whole point is to take a single very cheap pass over the start of the pack (or multiple packs in the case of the midx). Doing any reordering would be counterproductive to the "cheap" adjective there (it does not even keep a list of object ids it is sending), so we are better to leave those objects for the regular output code (which does make such a list).
Taylor's series introduces an in-between where we choose not to reorder, but switch to REF_DELTA. That is still cheap on CPU on the generating side, though the resulting pack is slightly larger.
-Peff
[1] I wish we had good names to distinguish the various cases, because the term "reuse" is kind of overloaded. The "slower" regular object-sending path may still reuse verbatim bytes found in an on-disk path. But this "blit out matching parts of a pack without otherwise considering the objects" feature happens outside of that. We called it "pack reuse" back in 2013, but that was not a good name even then. I don't have a good suggestion, though.
Quoted 7 lines · Jeff King
[1] I wish we had good names to distinguish the various cases, because the term "reuse" is kind of overloaded. The "slower" regular object-sending path may still reuse verbatim bytes found in an on-disk path. But this "blit out matching parts of a pack without otherwise considering the objects" feature happens outside of that. We called it "pack reuse" back in 2013, but that was not a good name even then. I don't have a good suggestion, though.
Actually, confusing things more, there are really _three_ layers of reuse:
1. At the beginning of a pack, we can blit out the bytes for objects starting from the beginning of the pack that are being sent (we know any delta will be satisfied since its base comes before it).
2. After that, we process objects one by one, but do so very cheaply by just deciding if we can blit them out one by one, fixing up delta base offsets to account for gaps.
3. Otherwise, we generate an object_entry struct in packing_data for them, try to find new deltas, and so on. We may then reuse the on-disk bytes after deciding they're suitable.
We call all of these "reuse", and certainly both (1) and (2) are "pack reuse", but I think that term is sufficiently vague that it could apply to (3) as well.
-Peff
Quoted 10 lines · Jeff King
Quoted 7 lines · Jeff King
[1] I wish we had good names to distinguish the various cases, because the term "reuse" is kind of overloaded. The "slower" regular object-sending path may still reuse verbatim bytes found in an on-disk path. But this "blit out matching parts of a pack without otherwise considering the objects" feature happens outside of that. We called it "pack reuse" back in 2013, but that was not a good name even then. I don't have a good suggestion, though.
Quoted 6 lines
Actually, confusing things more, there are really _three_ layers of reuse:
1. At the beginning of a pack, we can blit out the bytes for objects starting from the beginning of the pack that are being sent (we know any delta will be satisfied since its base comes before it).
Yes, I wouldn't be worried about that one. The data encoded as an ofs-delta in this section already point at their base correctly in the original pack, and in the resulting pack.
Quoted 3 lines
2. After that, we process objects one by one, but do so very cheaply by just deciding if we can blit them out one by one, fixing up delta base offsets to account for gaps.
This is the part I said "we have to remember where the base was emitted and subtract it from the offset of the delta anyway even if we are reusing delta from the same pack, so what do we need a separate code path for this?" in my initial response.
I guess, "fixing up" could be done by using the difference between offsets in the original pack for this step, which would be an unfortunate design that prevents it from getting reused.
Quoted 3 lines
3. Otherwise, we generate an
object_entrystruct inpacking_datafor them, try to find new deltas, and so on. We may then reuse the on-disk bytes after deciding they're suitable.
It is a bit unfortunate, if we were to trust the existing delta base selection in the pack like we did since Feb 2006 [*], we should be omitting the "try to find new deltas" step. Perhaps that comes for free as the object_entry knows that our object has a delta_base?
Quoted 5 lines
We call all of these "reuse", and certainly both (1) and (2) are "pack reuse", but I think that term is sufficiently vague that it could apply to (3) as well.
-Peff
Quoted 10 lines · Taylor Blau
The first optimization (cross-pack deltas) should help clones and fetches, but the second optimization (thin deltas) will only help fetches, since the 'haves' bitmap will necessarily be empty for clones.
Of course,
REF_DELTAshave a less compact representation thanOFS_DELTAs, so the resulting packs will trade off some CPU time for a slightly larger pack. But we're only talking about a handful of extra bytes, and network bandwidth is pretty cheap, so I think the optimization is worthwhile here too.
It would be nice to see some numbers, even simulated ones from t/perf. Of course we'd like to show off any reduced server CPU for generating a fetch response. But I'd also like to see if the extra steps to find the cross-pack bases have any measurable negative effect (so the ideal there would be a big midx repo that doesn't have a lot of those bases, as it would not be helped much by the optimization and would be hurt by the time spent trying to apply it).
-Peff
Quoted 13 lines · Jeff King
Quoted 10 lines · Taylor Blau
The first optimization (cross-pack deltas) should help clones and fetches, but the second optimization (thin deltas) will only help fetches, since the 'haves' bitmap will necessarily be empty for clones.
Of course,
REF_DELTAshave a less compact representation thanOFS_DELTAs, so the resulting packs will trade off some CPU time for a slightly larger pack. But we're only talking about a handful of extra bytes, and network bandwidth is pretty cheap, so I think the optimization is worthwhile here too.
Quoted 7 lines
It would be nice to see some numbers, even simulated ones from t/perf. Of course we'd like to show off any reduced server CPU for generating a fetch response. But I'd also like to see if the extra steps to find the cross-pack bases have any measurable negative effect (so the ideal there would be a big midx repo that doesn't have a lot of those bases, as it would not be helped much by the optimization and would be hurt by the time spent trying to apply it).
I put together some loose numbers for this, and there is a definite measurable slowdown imposed by this series.
The setup is getting a fresh copy of the kernel, and then repacking it with:
$ git repack -da --cruft --write-midx --write-bitmap-index \
--max-pack-size 1G --max-cruft-size 1G, which on my machine produces the following pack structure:
$ for idx in .git/objects/pack/*.idx
do
echo $(basename $idx) \
$(git show-index <$idx | wc -l)
done | sort -rnk2
pack-8dc61c00e623765c54cbd332f31795bad7edf142.idx 3385859
pack-d84e88715cde55d4d1b09afb23254617a123e668.idx 2064396
pack-cd408bebd5c02719df7621941d92415f4dbb313c.idx 1805431
pack-b11c6ac57f5ecf338314ee59134b0d724d257494.idx 1036443
pack-a42cc1b409940d7e38a4673bca1150d320392bf0.idx 819701
pack-93d255a1000f438a77528907c480c06b277e225d.idx 755019
pack-600621b90dc29c761ee168cc4237b2ff2956b0e8.idx 609754Generating a full clone[^1] with multi-pack reuse enabled (based on the tip of tb/multi-pack-reuse-dupfix) gives me the following timings:
13.94s user 0.27s system 99% cpu 14.207 total
13.93s user 0.30s system 99% cpu 14.223 total
13.90s user 0.33s system 99% cpu 14.229 totalAfter applying the series, I get:
14.94s user 0.33s system 99% cpu 15.279 total
14.92s user 0.32s system 99% cpu 15.244 total
14.87s user 0.40s system 99% cpu 15.280 totalOr around a ~5% slowdown. I think what's really killing us is all of the back and forth in pack-bitmap.c::find_base_bitmap_pos(), where we have to:
- Find the pack-relative position of the base object given its offset.
- Convert that pack-relative position into a lexical position (still relative to the source pack).
- Convert that lexical position into an object ID.
- Call bsearch_midx() to see if we have a copy of that object, and record its MIDX-relative lexical position.
- Convert the MIDX-relative lexical position into its pseudo-pack position.
I think that the first four of those steps are unavoidable. But I think we can do better on the last step if we compute a forward index from MIDX lexical position to pseudo-pack position.
A cheap way to run that experiment is to just add a temporary field into the MIDX to store that mapping, compute it at runtime, and then deduct the time it took to compute that mapping (presumably you'd do it during MIDX creation, and store it in a chunk, etc.).
Here's some code to do that:
--- 8< ---
midx.c +15 -0
@@ -988,3 +988,18 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flagreturn verify_midx_error; } + +void midx_populate_forward_index (struct multi_pack_index *m) +{ +uint32_t i; + +ALLOC_ARRAY (m->forward_idx, m->num_objects); + +trace2_region_enter ("midx" ,"populate_forward_index" , the_repository); + +for (i =0 ; i < m->num_objects; i++) +if (midx_to_pack_pos (m, i, m->forward_idx + i) <0 ) +BUG ("oops" ); + +trace2_region_leave ("midx" ,"populate_forward_index" , the_repository); +}
midx.h +4 -0
@@ -65,6 +65,8 @@ struct multi_pack_index {const unsigned char *chunk_revindex;size_t chunk_revindex_len; +uint32_t *forward_idx; +struct multi_pack_index *base_midx;uint32_t num_objects_in_base;uint32_t num_packs_in_base;
@@ -74,6 +76,8 @@ struct multi_pack_index {char object_dir[FLEX_ARRAY ]; }; +void midx_populate_forward_index (struct multi_pack_index *m); +#define MIDX_PROGRESS (1 << 0)#define MIDX_WRITE_REV_INDEX (1 << 1)#define MIDX_WRITE_BITMAP (1 << 2)
pack-bitmap.c +5 -0
@@ -2092,9 +2092,13 @@ static int find_base_bitmap_pos(struct bitmap_index *bitmap_git,if (!bsearch_midx (&base_oid, bitmap_git->midx, &base_midx_pos))return -1 ; +#if 0 if (midx_to_pack_pos (bitmap_git->midx, base_midx_pos, base_bitmap_pos) <0 )return -1 ; +#else + *base_bitmap_pos = bitmap_git->midx->forward_idx[base_midx_pos]; +#endif }else {/* * We assume delta dependencies always point backwards.
@@ -2316,6 +2320,7 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,assert (result);load_reverse_index (r, bitmap_git); +midx_populate_forward_index (bitmap_git->midx);if (!bitmap_is_midx (bitmap_git) || !bitmap_git->midx->chunk_bitmapped_packs) multi_pack_reuse =0 ;
--- >8 ---
Then when running the same command, we get results that are quite encouraging. The runtime jumps to 24.213 seconds, which is ~9.73 seconds slower than the average of the baseline measurements. But it takes ~10.418 seconds on my machine to compute the forward index. So it's really around 688ms *faster* than the baseline, despite doing a little more work.
The fact that we can improve on the baseline rather than just meet it suggests that implementing this forward index may have some benefit outside of just this series.
Thanks,
Taylor
[^1]: The setup here is:
$ git for-each-ref --format='%(objectname)' refs/heads refs/tags >in
$ git pack-objects --stdout --delta-base-offset --use-bitmap-index --revs <in >/dev/nullQuoted 6 lines · Taylor Blau
Then when running the same command, we get results that are quite encouraging. The runtime jumps to 24.213 seconds, which is ~9.73 seconds slower than the average of the baseline measurements. But it takes ~10.418 seconds on my machine to compute the forward index. So it's really around 688ms *faster* than the baseline, despite doing a little more work.
Sorry, there is a much quicker way to generate the forward index at runtime, which is the following:
--- 8< ---
midx.c +14 -0
@@ -989,3 +989,17 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flagreturn verify_midx_error; } + +void midx_populate_forward_index (struct multi_pack_index *m) +{ +uint32_t i; + +ALLOC_ARRAY (m->forward_idx, m->num_objects); + +trace2_region_enter ("midx" ,"populate_forward_index" , the_repository); + +for (i =0 ; i < m->num_objects; i++) + m->forward_idx[pack_pos_to_midx (m, i)] = i; + +trace2_region_leave ("midx" ,"populate_forward_index" , the_repository); +}
--- >8 ---
I don't know if this makes as much of a difference for regular multi-pack reuse, since there we're only making calls to midx_pair_to_pack_pos(), which already uses midx_pack_order_cmp(), so there isn't any additional translation to do.
Thanks,
Taylor
Quoted 11 lines · Taylor Blau
Quoted 6 lines · Taylor Blau
Then when running the same command, we get results that are quite encouraging. The runtime jumps to 24.213 seconds, which is ~9.73 seconds slower than the average of the baseline measurements. But it takes ~10.418 seconds on my machine to compute the forward index. So it's really around 688ms *faster* than the baseline, despite doing a little more work.
Sorry, there is a much quicker way to generate the forward index at runtime, which is the following:
[...]
Neat. I didn't see timings for this method, but I'd assume it's quite fast. So if it shaves off the same 688ms, I'd expect it to be an overall win. The code itself looks reasonable to me.
I think when you re-post this series it might make sense to add a t/perf script to demonstrate these timings (not just what we're discussing here, but also the overall speedup we're hoping to achieve).
-Peff