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

From: Taylor Blau <me@ttaylorr.com>
Date: Oct 9, 2024, 20:31 UTC
Message-ID: <80f96385a7724fd2f8bf10c42ccce5b0b454a107.1728505840.git.me@ttaylorr.com>
In-Reply-To: <cover.1728505840.git.me@ttaylorr.com>

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

-- 
2.47.0.11.g487258bca34