diff mbox series

[01/11] pack-bitmap.c: do not pass `pack_pos` to `try_partial_reuse()`

Message ID 80f96385a7724fd2f8bf10c42ccce5b0b454a107.1728505840.git.me@ttaylorr.com (mailing list archive)
State New
Headers show
Series pack-bitmap: convert offset to ref deltas where possible | expand

Commit Message

Taylor Blau Oct. 9, 2024, 8:31 p.m. UTC
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/Zti0xrzCtpWScPjz@nand.local/

Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 pack-bitmap.c | 21 +++++++++------------
 1 file changed, 9 insertions(+), 12 deletions(-)
diff mbox series

Patch

diff --git a/pack-bitmap.c b/pack-bitmap.c
index 9d9b8c4bfbc..706ff26a7b1 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -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_git
 
 		for (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