{"thread":{"id":"62300","subject":"[PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","startedAt":"2024-10-09T20:31:00Z","lastAt":"2024-12-18T12:57:56Z","messageCount":31,"participants":["Taylor Blau","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":11},"messages":[{"id":"504638","messageId":"cover.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":null,"subject":"[PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:30:52Z","receivedAt":"2024-10-09T20:31:00Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"This patch series enables more objects to be candidates for verbatim\nreuse when generating a pack with the aide of reachability bitmaps.\n\nBy the end of this series, two new classes of objects are now reuse\ncandidates which were not before. They are:\n\n - Cross-pack deltas. In multi-pack bitmaps, if the delta and base\n were selected from different packs, the delta was not reusable.\n\n - Thin deltas. In both single- and multi-pack bitmaps, we did not\n consider reusing deltas whose base object appears in the 'haves'\n bitmap.\n\nThis series teaches the pack-objects machinery to convert cross-pack\nand thin deltas to reference deltas so that they may be reused.\n\nThe series started off as a couple of patches, each addressing one of\nthe two classes from the above. But as I started refining these\npatches, the series grew longer, as there were a handful of\nopportunities to clean up some of the existing pack-reuse bitmap code.\n\nThe series is organized as follows:\n\n - The first seven patches are various cleanups that make the\n pack-reuse code more readable and prepare us to enable delta reuse\n in more situation as above.\n\n pack-bitmap.c: do not pass `pack_pos` to `try_partial_reuse()`\n pack-bitmap.c: avoid unnecessary `offset_to_pack_pos()`\n pack-bitmap.c: delay calling 'offset_to_pack_pos()'\n pack-bitmap.c: compare `base_offset` to `delta_obj_offset`\n pack-bitmap.c: extract `find_base_bitmap_pos()`\n pack-bitmap: drop `from_midx` field from `bitmapped_pack`\n write_reused_pack_one(): translate bit positions directly\n\n - The next patch is a test fixup:\n\n t5332: enable OFS_DELTAs via test_pack_objects_reused\n\n - The next patch after that enables us to reuse deltas whose base\n appears in another pack:\n\n pack-bitmap: enable cross-pack delta reuse\n\n - The final two patches enable the \"thin deltas\" optimization\n above:\n\n pack-bitmap.c: record whether the result was filtered\n pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap\n\nI think that the first seven patches are worthwhile on their own. I\nconsidered splitting those out into their own series, but decided\nagainst it to so that we could realize their benefit more readily.\n\nThe first optimization (cross-pack deltas) should help clones and\nfetches, but the second optimization (thin deltas) will only help\nfetches, since the 'haves' bitmap will necessarily be empty for\nclones.\n\nOf course, REF_DELTAs have a less compact representation than\nOFS_DELTAs, so the resulting packs will trade off some CPU time for a\nslightly larger pack. But we're only talking about a handful of extra\nbytes, and network bandwidth is pretty cheap, so I think the\noptimization is worthwhile here too.\n\nThanks in advance for your review!\n\nTaylor Blau (11):\n pack-bitmap.c: do not pass `pack_pos` to `try_partial_reuse()`\n pack-bitmap.c: avoid unnecessary `offset_to_pack_pos()`\n pack-bitmap.c: delay calling 'offset_to_pack_pos()'\n pack-bitmap.c: compare `base_offset` to `delta_obj_offset`\n pack-bitmap.c: extract `find_base_bitmap_pos()`\n pack-bitmap: drop `from_midx` field from `bitmapped_pack`\n write_reused_pack_one(): translate bit positions directly\n t5332: enable OFS_DELTAs via test_pack_objects_reused\n pack-bitmap: enable cross-pack delta reuse\n pack-bitmap.c: record whether the result was filtered\n pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap\n\n builtin/pack-objects.c | 110 ++++++++++++--------\n midx.c | 1 -\n pack-bitmap.c | 198 ++++++++++++++++++++++++------------\n pack-bitmap.h | 6 +-\n t/t5332-multi-pack-reuse.sh | 72 ++++++++++++-\n 5 files changed, 275 insertions(+), 112 deletions(-)\n\n\nbase-commit: 777489f9e09c8d0dd6b12f9d90de6376330577a2\n-- \n2.47.0.11.g487258bca34\n"},{"id":"504639","messageId":"80f96385a7724fd2f8bf10c42ccce5b0b454a107.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 01/11] pack-bitmap.c: do not pass `pack_pos` to `try_partial_reuse()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:01Z","receivedAt":"2024-10-09T20:31:03Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The function `try_partial_reuse()` uses its `pack_pos` parameter to\ndetermine if:\n\n - the object specified by that position is in bounds of the pack\n it's operating on, and\n\n - in the case that the specified object is an OFS_DELTA (and we're\n operating on a single-pack reachability bitmap) to ensure that the\n position of the base object occurs earlier than the delta\n\nBut neither of these checks are necessary. The bounds-check is\nredundant because we are operating on bit positions which we know\ncorrespond to objects in some pack, and the caller in\nreuse_partial_packfile_from_bitmap_1() is smart enough to know to stop\nprocessing bits when it is at the end of some pack.\n\nLikewise, the delta dependency check is also unnecessary, because we\ncan use the object offsets within a single pack as a proxy for bit\npositions in that pack's bitmap.\n\nSo let's avoid passing in this redundant piece of information, and\nsave one call to offset_to_pack_pos(), which is O(log N) in the number\nof objects in the pack we're currently processing.\n\n(This all comes from a discussion on a semi-related series from [1]).\n\n[1]: https://lore.kernel.org/git/Zti0xrzCtpWScPjz@nand.local/\n\nSuggested-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 21 +++++++++------------\n 1 file changed, 9 insertions(+), 12 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 9d9b8c4bfbc..706ff26a7b1 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2054,7 +2054,6 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t struct bitmapped_pack *pack,\n \t\t\t size_t bitmap_pos,\n-\t\t\t uint32_t pack_pos,\n \t\t\t off_t offset,\n \t\t\t struct bitmap *reuse,\n \t\t\t struct pack_window **w_curs)\n@@ -2063,9 +2062,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \tenum object_type type;\n \tunsigned long size;\n \n-\tif (pack_pos >= pack->p->num_objects)\n-\t\treturn -1; /* not actually in the pack */\n-\n \tdelta_obj_offset = offset;\n \ttype = unpack_object_header(pack->p, w_curs, &offset, &size);\n \tif (type < 0)\n@@ -2121,8 +2117,13 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t * OFS_DELTA is the default). But let's double check to\n \t\t\t * make sure the pack wasn't written with odd\n \t\t\t * parameters.\n+\t\t\t *\n+\t\t\t * Since we're working on a single-pack bitmap, we can\n+\t\t\t * use the object offset as a proxy for the bit\n+\t\t\t * position, since the bits are ordered by their\n+\t\t\t * positions within the pack.\n \t\t\t */\n-\t\t\tif (base_pos >= pack_pos)\n+\t\t\tif (base_offset >= offset)\n \t\t\t\treturn 0;\n \t\t\tbase_bitmap_pos = pack->bitmap_pos + base_pos;\n \t\t}\n@@ -2184,7 +2185,6 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git\n \n \t\tfor (offset = 0; offset < BITS_IN_EWORD; offset++) {\n \t\t\tsize_t bit_pos;\n-\t\t\tuint32_t pack_pos;\n \t\t\toff_t ofs;\n \n \t\t\tif (word >> offset == 0)\n@@ -2203,12 +2203,9 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git\n \n \t\t\t\tmidx_pos = pack_pos_to_midx(bitmap_git->midx, bit_pos);\n \t\t\t\tofs = nth_midxed_offset(bitmap_git->midx, midx_pos);\n-\n-\t\t\t\tif (offset_to_pack_pos(pack->p, ofs, &pack_pos) < 0)\n-\t\t\t\t\tBUG(\"could not find object in pack %s \"\n-\t\t\t\t\t \"at offset %\"PRIuMAX\" in MIDX\",\n-\t\t\t\t\t pack_basename(pack->p), (uintmax_t)ofs);\n \t\t\t} else {\n+\t\t\t\tuint32_t pack_pos;\n+\n \t\t\t\tpack_pos = cast_size_t_to_uint32_t(st_sub(bit_pos, pack->bitmap_pos));\n \t\t\t\tif (pack_pos >= pack->p->num_objects)\n \t\t\t\t\tBUG(\"advanced beyond the end of pack %s (%\"PRIuMAX\" > %\"PRIu32\")\",\n@@ -2219,7 +2216,7 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git\n \t\t\t}\n \n \t\t\tif (try_partial_reuse(bitmap_git, pack, bit_pos,\n-\t\t\t\t\t pack_pos, ofs, reuse, &w_curs) < 0) {\n+\t\t\t\t\t ofs, reuse, &w_curs) < 0) {\n \t\t\t\t/*\n \t\t\t\t * try_partial_reuse indicated we couldn't reuse\n \t\t\t\t * any bits, so there is no point in trying more\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504640","messageId":"010316f1eb49b46db1ed0b8df10402d3a49013f8.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 02/11] pack-bitmap.c: avoid unnecessary `offset_to_pack_pos()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:04Z","receivedAt":"2024-10-09T20:31:07Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In `try_partial_reuse()`, for any object which is either an OFS_DELTA\nor REF_DELTA, we need to determine the bitmap position for its base.\n\nWe handle the case of single- and multi-pack bitmaps separately:\n\n - For multi-pack bitmaps, we look to see if the MIDX selected the\n base we're looking at to represent that object. If the base object\n was selected from a different pack in the MIDX, we won't reuse the\n delta.\n\n - For single-pack bitmaps, we convert the base object's offset into\n a pack-relative position (identified here as 'base_pos') by\n calling `offset_to_pack_pos()`.\n\nBut we also call `offset_to_pack_pos()` before handling each case\nabove separately. For the MIDX case, this is unnecessary, since we\ndon't need to lookup the base object's pack-relative position;\ninstead, we just care whether the selected copy of that base is from\nthe same pack we're currently operating on.\n\nFor the non-MIDX case, we end up calling offset_to_pack_pos() again,\nyielding the same result, making the earlier call wasteful. This\nbehavior dates back to 519e17ff75 (pack-bitmap: prepare to mark\nobjects from multiple packs for reuse, 2023-12-14).\n\nLet's correct that by avoiding the unconditional call to\n'offset_to_pack_pos()'.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 5 ++---\n 1 file changed, 2 insertions(+), 3 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 706ff26a7b1..5c5c26efe0d 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2069,7 +2069,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \n \tif (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {\n \t\toff_t base_offset;\n-\t\tuint32_t base_pos;\n \t\tuint32_t base_bitmap_pos;\n \n \t\t/*\n@@ -2085,8 +2084,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\tif (!base_offset)\n \t\t\treturn 0;\n \n-\t\toffset_to_pack_pos(pack->p, base_offset, &base_pos);\n-\n \t\tif (bitmap_is_midx(bitmap_git)) {\n \t\t\t/*\n \t\t\t * Cross-pack deltas are rejected for now, but could\n@@ -2105,6 +2102,8 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t\treturn 0;\n \t\t\t}\n \t\t} else {\n+\t\t\tuint32_t base_pos;\n+\n \t\t\tif (offset_to_pack_pos(pack->p, base_offset,\n \t\t\t\t\t &base_pos) < 0)\n \t\t\t\treturn 0;\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504641","messageId":"6118055b55c801f964b5a4b5d001196c00b757ab.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 03/11] pack-bitmap.c: delay calling 'offset_to_pack_pos()'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:07Z","receivedAt":"2024-10-09T20:31:10Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When handling single object reuse from a single-pack bitmap, we first\nconvert the base object's offset into a pack-relative position. Then,\nwe check if the base object's offset occurs after the delta object's\noffset. If that's the case, then we kick the delta'd object back to\nthe slow path.\n\nBut there are a couple of oddities here:\n\n - However unlikely it is that we'll find a delta/base pair with\n base_offset >= offset, it doesn't make sense to convert the base's\n offset to a pack-relative position if we're going to throw out the\n reuse opportunity anyway.\n\n - We \"convert\" the base object's position into bitmap order by\n offsetting it by 'pack->bitmap_pos'. But this makes no sense,\n since single-pack bitmaps have only one pack (by definition), and\n that pack's first object occurs at bit position 0.\n\nLet's clean up this part of 'try_partial_reuse()' by (a) first seeing\nif we can reuse the delta before converting its base object's offset\ninto a pack position, and (b) avoid an unnecessary conversion with\n'pack->bitmap_pos'.\n\n(b) allows us to avoid the intermediate 'base_pos' variable, and\ninstead write directly into 'base_bitmap_pos', which we also change\nhere for further clarity.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 9 +++------\n 1 file changed, 3 insertions(+), 6 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 5c5c26efe0d..faabc0ba0e9 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2102,11 +2102,6 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t\treturn 0;\n \t\t\t}\n \t\t} else {\n-\t\t\tuint32_t base_pos;\n-\n-\t\t\tif (offset_to_pack_pos(pack->p, base_offset,\n-\t\t\t\t\t &base_pos) < 0)\n-\t\t\t\treturn 0;\n \t\t\t/*\n \t\t\t * We assume delta dependencies always point backwards.\n \t\t\t * This lets us do a single pass, and is basically\n@@ -2124,7 +2119,9 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t */\n \t\t\tif (base_offset >= offset)\n \t\t\t\treturn 0;\n-\t\t\tbase_bitmap_pos = pack->bitmap_pos + base_pos;\n+\t\t\tif (offset_to_pack_pos(pack->p, base_offset,\n+\t\t\t\t\t &base_bitmap_pos) < 0)\n+\t\t\t\treturn 0;\n \t\t}\n \n \t\t/*\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504642","messageId":"bc5ff77f63b42dbea70b12f736e48f95fe8d6cf3.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 04/11] pack-bitmap.c: compare `base_offset` to `delta_obj_offset`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:11Z","receivedAt":"2024-10-09T20:31:13Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When comparing the offsets of either half of a delta/base-pair, we\ncompare `base_offset` to `offset`.\n\nThere is nothing functionally wrong with that comparison, but it is\nslightly confusing, since `offset` points to just after the delta\nobject's type header in the pack, whereas `base_offset` points to the\nbeginning of the header.\n\nIn practice, that distinction does not matter, and it is perfectly\nfine to compare base_offset to offset.\n\nBut we already make a copy of `offset` before it is moved forward by\ncalling the function `unpack_object_header()`. So let's use that copy\n(which points at the beginning of the delta object's header) in the\ncomparison so that we are comparing like quantities.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex faabc0ba0e9..3e1034cabf3 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2117,7 +2117,7 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t * position, since the bits are ordered by their\n \t\t\t * positions within the pack.\n \t\t\t */\n-\t\t\tif (base_offset >= offset)\n+\t\t\tif (base_offset >= delta_obj_offset)\n \t\t\t\treturn 0;\n \t\t\tif (offset_to_pack_pos(pack->p, base_offset,\n \t\t\t\t\t &base_bitmap_pos) < 0)\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504643","messageId":"f4dca03d84583b5e8565af3b6759f05cf2b0be3f.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 05/11] pack-bitmap.c: extract `find_base_bitmap_pos()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:14Z","receivedAt":"2024-10-09T20:31:17Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Inside of `try_partial_reuse()` is a block of code that handles\nspecially the case where the object we are attempting reuse on is\neither an OFS_DELTA or a REF_DELTA.\n\nExtract that part of the routine out to a separate function, named\n`find_base_bitmap_pos()`. This will allow us to make that routine\nslightly more complex in order to implement cross-pack and thin-delta\nconversion (which we'll describe in detail in subsequent patches)\nwithout compromising the readability of its caller,\n`try_partial_reuse()`.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 90 ++++++++++++++++++++++++++++-----------------------\n 1 file changed, 49 insertions(+), 41 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 3e1034cabf3..6dbe6a2c5bc 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2047,6 +2047,52 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \treturn NULL;\n }\n \n+static int find_base_bitmap_pos(struct bitmap_index *bitmap_git,\n+\t\t\t\tstruct bitmapped_pack *pack,\n+\t\t\t\toff_t base_offset,\n+\t\t\t\toff_t delta_obj_offset,\n+\t\t\t\tuint32_t *base_bitmap_pos)\n+{\n+\tif (bitmap_is_midx(bitmap_git)) {\n+\t\t/*\n+\t\t * Cross-pack deltas are rejected for now, but could\n+\t\t * theoretically be supported in the future.\n+\t\t *\n+\t\t * We would need to ensure that we're sending both\n+\t\t * halves of the delta/base pair, regardless of whether\n+\t\t * or not the two cross a pack boundary. If they do,\n+\t\t * then we must convert the delta to an REF_DELTA to\n+\t\t * refer back to the base in the other pack.\n+\t\t * */\n+\t\tif (midx_pair_to_pack_pos(bitmap_git->midx, pack->pack_int_id,\n+\t\t\t\t\t base_offset, base_bitmap_pos) < 0)\n+\t\t\treturn -1;\n+\t} else {\n+\t\t/*\n+\t\t * We assume delta dependencies always point backwards.\n+\t\t * This lets us do a single pass, and is basically\n+\t\t * always true due to the way OFS_DELTAs work. You would\n+\t\t * not typically find REF_DELTA in a bitmapped pack,\n+\t\t * since we only bitmap packs we write fresh, and\n+\t\t * OFS_DELTA is the default). But let's double check to\n+\t\t * make sure the pack wasn't written with odd\n+\t\t * parameters.\n+\t\t *\n+\t\t * Since we're working on a single-pack bitmap, we can\n+\t\t * use the object offset as a proxy for the bit\n+\t\t * position, since the bits are ordered by their\n+\t\t * positions within the pack.\n+\t\t */\n+\t\tif (base_offset >= delta_obj_offset)\n+\t\t\treturn -1;\n+\t\tif (offset_to_pack_pos(pack->p, base_offset,\n+\t\t\t\t base_bitmap_pos) < 0)\n+\t\t\treturn -1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n /*\n * -1 means \"stop trying further objects\"; 0 means we may or may not have\n * reused, but you can keep feeding bits.\n@@ -2081,49 +2127,11 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t */\n \t\tbase_offset = get_delta_base(pack->p, w_curs, &offset, type,\n \t\t\t\t\t delta_obj_offset);\n-\t\tif (!base_offset)\n+\t\tif (!base_offset ||\n+\t\t find_base_bitmap_pos(bitmap_git, pack, base_offset,\n+\t\t\t\t\t delta_obj_offset, &base_bitmap_pos) < 0)\n \t\t\treturn 0;\n \n-\t\tif (bitmap_is_midx(bitmap_git)) {\n-\t\t\t/*\n-\t\t\t * Cross-pack deltas are rejected for now, but could\n-\t\t\t * theoretically be supported in the future.\n-\t\t\t *\n-\t\t\t * We would need to ensure that we're sending both\n-\t\t\t * halves of the delta/base pair, regardless of whether\n-\t\t\t * or not the two cross a pack boundary. If they do,\n-\t\t\t * then we must convert the delta to an REF_DELTA to\n-\t\t\t * refer back to the base in the other pack.\n-\t\t\t * */\n-\t\t\tif (midx_pair_to_pack_pos(bitmap_git->midx,\n-\t\t\t\t\t\t pack->pack_int_id,\n-\t\t\t\t\t\t base_offset,\n-\t\t\t\t\t\t &base_bitmap_pos) < 0) {\n-\t\t\t\treturn 0;\n-\t\t\t}\n-\t\t} else {\n-\t\t\t/*\n-\t\t\t * We assume delta dependencies always point backwards.\n-\t\t\t * This lets us do a single pass, and is basically\n-\t\t\t * always true due to the way OFS_DELTAs work. You would\n-\t\t\t * not typically find REF_DELTA in a bitmapped pack,\n-\t\t\t * since we only bitmap packs we write fresh, and\n-\t\t\t * OFS_DELTA is the default). But let's double check to\n-\t\t\t * make sure the pack wasn't written with odd\n-\t\t\t * parameters.\n-\t\t\t *\n-\t\t\t * Since we're working on a single-pack bitmap, we can\n-\t\t\t * use the object offset as a proxy for the bit\n-\t\t\t * position, since the bits are ordered by their\n-\t\t\t * positions within the pack.\n-\t\t\t */\n-\t\t\tif (base_offset >= delta_obj_offset)\n-\t\t\t\treturn 0;\n-\t\t\tif (offset_to_pack_pos(pack->p, base_offset,\n-\t\t\t\t\t &base_bitmap_pos) < 0)\n-\t\t\t\treturn 0;\n-\t\t}\n-\n \t\t/*\n \t\t * And finally, if we're not sending the base as part of our\n \t\t * reuse chunk, then don't send this object either. The base\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504644","messageId":"278beed9cfbca0ec00a113e36d615d1d47a5223f.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 06/11] pack-bitmap: drop `from_midx` field from `bitmapped_pack`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:17Z","receivedAt":"2024-10-09T20:31:20Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"This field was added in 41cd4b478f7 (pack-bitmap: tag bitmapped packs\nwith their corresponding MIDX, 2024-08-27) in order to expose the\nbitmap's MIDX in order to translate bit positions correctly from\nwithin 'pack-objects' during pack-reuse (c.f., 125c32605ab\n(builtin/pack-objects.c: translate bit positions during pack-reuse,\n2024-08-27) for more details).\n\nBut another approach would have been to use the `->midx` field of the\n`struct bitmap_index *` directly, which feels clearer and avoids\nduplicating information.\n\nUnfortunately, we can't access that field directly since it is part of\nthe `bitmap_index` structure which is static within the pack-bitmap.c\ncompilation unit.\n\nSo let's instead introduce a new function which returns that pointer\nto us, and replace the `from_midx` field with uses of that new\nfunction (which we call `bitmap_midx()` here).\n\nSigned-off-by: Taylor Blau \n---\n builtin/pack-objects.c | 4 ++--\n midx.c | 1 -\n pack-bitmap.c | 6 +++++-\n pack-bitmap.h | 2 +-\n 4 files changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0fc0680b402..097bb5ac2ca 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1201,7 +1201,7 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,\n \t\t\tif (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr)\n \t\t\t\tgoto done;\n \n-\t\t\tif (reuse_packfile->bitmap_pos) {\n+\t\t\tif (bitmap_is_midx(bitmap_git)) {\n \t\t\t\t/*\n \t\t\t\t * When doing multi-pack reuse on a\n \t\t\t\t * non-preferred pack, translate bit positions\n@@ -1209,7 +1209,7 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,\n \t\t\t\t * pack-relative positions before attempting\n \t\t\t\t * reuse.\n \t\t\t\t */\n-\t\t\t\tstruct multi_pack_index *m = reuse_packfile->from_midx;\n+\t\t\t\tstruct multi_pack_index *m = bitmap_midx(bitmap_git);\n \t\t\t\tuint32_t midx_pos;\n \t\t\t\toff_t pack_ofs;\n \ndiff --git a/midx.c b/midx.c\nindex 67e0d640046..ca98bfd7c64 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -496,7 +496,6 @@ int nth_bitmapped_pack(struct repository *r, struct multi_pack_index *m,\n \t\t\t\t MIDX_CHUNK_BITMAPPED_PACKS_WIDTH * local_pack_int_id +\n \t\t\t\t sizeof(uint32_t));\n \tbp->pack_int_id = pack_int_id;\n-\tbp->from_midx = m;\n \n \treturn 0;\n }\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 6dbe6a2c5bc..b9ea1fab397 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2326,7 +2326,6 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \t\tpacks[packs_nr].pack_int_id = pack_int_id;\n \t\tpacks[packs_nr].bitmap_nr = pack->num_objects;\n \t\tpacks[packs_nr].bitmap_pos = 0;\n-\t\tpacks[packs_nr].from_midx = bitmap_git->midx;\n \n \t\tobjects_nr = packs[packs_nr++].bitmap_nr;\n \t}\n@@ -2981,6 +2980,11 @@ int bitmap_is_midx(struct bitmap_index *bitmap_git)\n \treturn !!bitmap_git->midx;\n }\n \n+struct multi_pack_index *bitmap_midx(struct bitmap_index *bitmap_git)\n+{\n+\treturn bitmap_git->midx;\n+}\n+\n const struct string_list *bitmap_preferred_tips(struct repository *r)\n {\n \tconst struct string_list *dest;\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex d7f4b8b8e95..a1e8c8936c9 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -60,7 +60,6 @@ struct bitmapped_pack {\n \tuint32_t bitmap_pos;\n \tuint32_t bitmap_nr;\n \n-\tstruct multi_pack_index *from_midx; /* MIDX only */\n \tuint32_t pack_int_id; /* MIDX only */\n };\n \n@@ -157,6 +156,7 @@ char *midx_bitmap_filename(struct multi_pack_index *midx);\n char *pack_bitmap_filename(struct packed_git *p);\n \n int bitmap_is_midx(struct bitmap_index *bitmap_git);\n+struct multi_pack_index *bitmap_midx(struct bitmap_index *bitmap_git);\n \n const struct string_list *bitmap_preferred_tips(struct repository *r);\n int bitmap_is_preferred_refname(struct repository *r, const char *refname);\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504645","messageId":"94e5c96f6859479e0206d6d775eacf54b3639ee5.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 07/11] write_reused_pack_one(): translate bit positions directly","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:21Z","receivedAt":"2024-10-09T20:31:23Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"A future commit will want to deal with bit positions instead of pack\npositions from within builtin/pack-objects.c::write_reused_pack_one().\n\nThat function at present takes a pack position, so one approach to\naccommodating the new functionality would be to add a secondary bit\nposition parameter, making the function's declaration look something\nlike:\n\n static void write_reused_pack_one(struct packed_git *reuse_packfile,\n size_t pack_pos, size_t bitmap_pos,\n struct hashfile *out,\n off_t pack_start,\n struct pack_window **w_curs);\n\nBut because the pack-relative position can be easily derived from the\nbit position, it makes senes to just pass the latter and let the\nfunction itself translate it into a pack-relative position.\n\nTo do this, extract a new function `bitmap_to_pack_pos()` from the\nexisting `write_reused_pack()` function. This new routine is responsible\nfor performing the conversion from bitmap- to pack-relative positions.\n\nInstead of performing that translation in `write_reused_pack()`, instead\ncall the new function from within `write_reused_pack_one()` so that we\ncan just pass a single bit position to it.\n\nSigned-off-by: Taylor Blau \n---\n builtin/pack-objects.c | 78 ++++++++++++++++++++++--------------------\n 1 file changed, 41 insertions(+), 37 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 097bb5ac2ca..7f50d58a235 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1017,6 +1017,42 @@ static off_t find_reused_offset(off_t where)\n \treturn reused_chunks[lo-1].difference;\n }\n \n+static uint32_t bitmap_to_pack_pos(struct packed_git *reuse_packfile,\n+\t\t\t\t size_t pos)\n+{\n+\tif (bitmap_is_midx(bitmap_git)) {\n+\t\t/*\n+\t\t * When doing multi-pack reuse on a\n+\t\t * non-preferred pack, translate bit positions\n+\t\t * from the MIDX pseudo-pack order back to their\n+\t\t * pack-relative positions before attempting\n+\t\t * reuse.\n+\t\t */\n+\t\tstruct multi_pack_index *m = bitmap_midx(bitmap_git);\n+\t\tuint32_t midx_pos, pack_pos;\n+\t\toff_t pack_ofs;\n+\n+\t\tif (!m)\n+\t\t\tBUG(\"non-zero bitmap position without MIDX\");\n+\n+\t\tmidx_pos = pack_pos_to_midx(m, pos);\n+\t\tpack_ofs = nth_midxed_offset(m, midx_pos);\n+\n+\t\tif (offset_to_pack_pos(reuse_packfile, pack_ofs, &pack_pos) < 0)\n+\t\t\tBUG(\"could not find expected object at offset %\"PRIuMAX\" in pack %s\",\n+\t\t\t (uintmax_t)pack_ofs, pack_basename(reuse_packfile));\n+\n+\t\treturn pack_pos;\n+\t} else {\n+\t\t/*\n+\t\t * Can use bit positions directly, even for MIDX\n+\t\t * bitmaps. See comment in try_partial_reuse()\n+\t\t * for why.\n+\t\t */\n+\t\treturn pos;\n+\t}\n+}\n+\n static void write_reused_pack_one(struct packed_git *reuse_packfile,\n \t\t\t\t size_t pos, struct hashfile *out,\n \t\t\t\t off_t pack_start,\n@@ -1025,9 +1061,10 @@ static void write_reused_pack_one(struct packed_git *reuse_packfile,\n \toff_t offset, next, cur;\n \tenum object_type type;\n \tunsigned long size;\n+\tuint32_t pack_pos = bitmap_to_pack_pos(reuse_packfile, pos);\n \n-\toffset = pack_pos_to_offset(reuse_packfile, pos);\n-\tnext = pack_pos_to_offset(reuse_packfile, pos + 1);\n+\toffset = pack_pos_to_offset(reuse_packfile, pack_pos);\n+\tnext = pack_pos_to_offset(reuse_packfile, pack_pos + 1);\n \n \trecord_reused_object(offset,\n \t\t\t offset - (hashfile_total(out) - pack_start));\n@@ -1191,7 +1228,6 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,\n \t\tsize_t pos = (i * BITS_IN_EWORD);\n \n \t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n-\t\t\tuint32_t pack_pos;\n \t\t\tif ((word >> offset) == 0)\n \t\t\t\tbreak;\n \n@@ -1201,40 +1237,8 @@ static void write_reused_pack(struct bitmapped_pack *reuse_packfile,\n \t\t\tif (pos + offset >= reuse_packfile->bitmap_pos + reuse_packfile->bitmap_nr)\n \t\t\t\tgoto done;\n \n-\t\t\tif (bitmap_is_midx(bitmap_git)) {\n-\t\t\t\t/*\n-\t\t\t\t * When doing multi-pack reuse on a\n-\t\t\t\t * non-preferred pack, translate bit positions\n-\t\t\t\t * from the MIDX pseudo-pack order back to their\n-\t\t\t\t * pack-relative positions before attempting\n-\t\t\t\t * reuse.\n-\t\t\t\t */\n-\t\t\t\tstruct multi_pack_index *m = bitmap_midx(bitmap_git);\n-\t\t\t\tuint32_t midx_pos;\n-\t\t\t\toff_t pack_ofs;\n-\n-\t\t\t\tif (!m)\n-\t\t\t\t\tBUG(\"non-zero bitmap position without MIDX\");\n-\n-\t\t\t\tmidx_pos = pack_pos_to_midx(m, pos + offset);\n-\t\t\t\tpack_ofs = nth_midxed_offset(m, midx_pos);\n-\n-\t\t\t\tif (offset_to_pack_pos(reuse_packfile->p,\n-\t\t\t\t\t\t pack_ofs, &pack_pos) < 0)\n-\t\t\t\t\tBUG(\"could not find expected object at offset %\"PRIuMAX\" in pack %s\",\n-\t\t\t\t\t (uintmax_t)pack_ofs,\n-\t\t\t\t\t pack_basename(reuse_packfile->p));\n-\t\t\t} else {\n-\t\t\t\t/*\n-\t\t\t\t * Can use bit positions directly, even for MIDX\n-\t\t\t\t * bitmaps. See comment in try_partial_reuse()\n-\t\t\t\t * for why.\n-\t\t\t\t */\n-\t\t\t\tpack_pos = pos + offset;\n-\t\t\t}\n-\n-\t\t\twrite_reused_pack_one(reuse_packfile->p, pack_pos, f,\n-\t\t\t\t\t pack_start, &w_curs);\n+\t\t\twrite_reused_pack_one(reuse_packfile->p, pos + offset,\n+\t\t\t\t\t f, pack_start, &w_curs);\n \t\t\tdisplay_progress(progress_state, ++written);\n \t\t}\n \t}\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504646","messageId":"9d81d890402f94f4126aedef0845d615d10455bc.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 08/11] t5332: enable OFS_DELTAs via test_pack_objects_reused","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:24Z","receivedAt":"2024-10-09T20:31:26Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Back when test_pack_objects_reused was introduced via commit\n7c01878eeb (t5332-multi-pack-reuse.sh: extract pack-objects helper\nfunctions, 2024-02-05), we converted bare pack-objects invocations\ninto one of two wrapped variants, either test_pack_objects_reused or\ntest_pack_objects_reused_all.\n\nThe latter passes `--delta-base-offset`, allowing pack-objects to\ngenerate OFS_DELTAs in its output pack. But the former does not, for\nno good reason.\n\nAs we do not want to convert OFS_DELTAs to REF_DELTAs unnecessarily,\nlet's unify these two and pass `--delta-base-offset` to both.\n\nInstrumenting the codepath\nwhere we convert OFS_DELTAs to REF_DELTAs with a BUG() like so:\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 0fc0680b402..0f1b22b8674 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1051,6 +1051,8 @@ static void write_reused_pack_one(struct packed_git *reuse_packfile,\n \t\t\tuint32_t base_pos;\n \t\t\tstruct object_id base_oid;\n\n+\t\t\tBUG(\"tested\");\n+\n \t\t\tif (offset_to_pack_pos(reuse_packfile, base_offset, &base_pos) < 0)\n \t\t\t\tdie(_(\"expected object at offset %\"PRIuMAX\" \"\n \t\t\t\t \"in pack %s\"),\n\n, and seeing what test(s) fail yields the following.\n\n Test Summary Report\n -------------------\n t5326-multi-pack-bitmaps.sh (Wstat: 256 (exited 1) Tests: 357 Failed: 6)\n Failed tests: 46, 91, 167, 220, 265, 341\n Non-zero exit status: 1\n t5310-pack-bitmaps.sh (Wstat: 256 (exited 1) Tests: 227 Failed: 6)\n Failed tests: 46-47, 120-121, 197-198\n Non-zero exit status: 1\n t5327-multi-pack-bitmaps-rev.sh (Wstat: 256 (exited 1) Tests: 314 Failed: 6)\n Failed tests: 46, 91, 157, 203, 248, 314\n Non-zero exit status: 1\n\nSo the OFS_DELTA to REF_DELTA conversion is still tested thoroughly in\nt5310, t5326, and t5327.\n\nSigned-off-by: Taylor Blau \n---\n t/t5332-multi-pack-reuse.sh | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/t/t5332-multi-pack-reuse.sh b/t/t5332-multi-pack-reuse.sh\nindex 955ea42769b..8bcb736c75a 100755\n--- a/t/t5332-multi-pack-reuse.sh\n+++ b/t/t5332-multi-pack-reuse.sh\n@@ -43,7 +43,7 @@ test_pack_objects_reused_all () {\n test_pack_objects_reused () {\n \t: >trace2.txt &&\n \tGIT_TRACE2_EVENT=\"$PWD/trace2.txt\" \\\n-\t\tgit pack-objects --stdout --revs >got.pack &&\n+\t\tgit pack-objects --delta-base-offset --stdout --revs >got.pack &&\n \n \ttest_pack_reused \"$1\" \n---\n builtin/pack-objects.c | 29 ++++++++++++++---\n pack-bitmap.c | 63 +++++++++++++++++++++++++++----------\n pack-bitmap.h | 1 +\n t/t5332-multi-pack-reuse.sh | 4 +--\n 4 files changed, 75 insertions(+), 22 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 7f50d58a235..dbcd632483e 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -223,6 +223,7 @@ static size_t reuse_packfiles_nr;\n static size_t reuse_packfiles_used_nr;\n static uint32_t reuse_packfile_objects;\n static struct bitmap *reuse_packfile_bitmap;\n+static struct bitmap *reuse_as_ref_delta_packfile_bitmap;\n \n static int use_bitmap_index_default = 1;\n static int use_bitmap_index = -1;\n@@ -1084,7 +1085,8 @@ static void write_reused_pack_one(struct packed_git *reuse_packfile,\n \t\tassert(base_offset != 0);\n \n \t\t/* Convert to REF_DELTA if we must... */\n-\t\tif (!allow_ofs_delta) {\n+\t\tif (!allow_ofs_delta ||\n+\t\t bitmap_get(reuse_as_ref_delta_packfile_bitmap, pos)) {\n \t\t\tuint32_t base_pos;\n \t\t\tstruct object_id base_oid;\n \n@@ -1160,6 +1162,10 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,\n \t\t\tif (!bitmap_get(reuse_packfile_bitmap,\n \t\t\t\t\tword_pos * BITS_IN_EWORD + offset))\n \t\t\t\treturn word_pos;\n+\t\t\tif (reuse_as_ref_delta_packfile_bitmap &&\n+\t\t\t bitmap_get(reuse_as_ref_delta_packfile_bitmap,\n+\t\t\t\t word_pos * BITS_IN_EWORD + offset))\n+\t\t\t\treturn word_pos;\n \t\t}\n \n \t\tpos += BITS_IN_EWORD - (pos % BITS_IN_EWORD);\n@@ -1182,10 +1188,24 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,\n \tif (pos >= end)\n \t\treturn reuse_packfile->bitmap_pos / BITS_IN_EWORD;\n \n-\twhile (pos < end &&\n-\t reuse_packfile_bitmap->words[pos / BITS_IN_EWORD] == (eword_t)~0)\n+\twhile (pos < end) {\n+\t\tsize_t wpos = pos / BITS_IN_EWORD;\n+\t\teword_t reuse;\n+\n+\t\treuse = reuse_packfile_bitmap->words[wpos];\n+\t\tif (reuse_as_ref_delta_packfile_bitmap) {\n+\t\t\t/*\n+\t\t\t * Can't reuse verbatim any objects which need\n+\t\t\t * to be first rewritten as REF_DELTAs.\n+\t\t\t */\n+\t\t\treuse &= ~reuse_as_ref_delta_packfile_bitmap->words[wpos];\n+\t\t}\n+\n+\t\tif (reuse != (eword_t)~0)\n+\t\t\tbreak;\n+\n \t\tpos += BITS_IN_EWORD;\n-\n+\t}\n \tif (pos > end)\n \t\tpos = end;\n \n@@ -4078,6 +4098,7 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \t\t\t\t\t\t &reuse_packfiles,\n \t\t\t\t\t\t &reuse_packfiles_nr,\n \t\t\t\t\t\t &reuse_packfile_bitmap,\n+\t\t\t\t\t\t &reuse_as_ref_delta_packfile_bitmap,\n \t\t\t\t\t\t allow_pack_reuse == MULTI_PACK_REUSE);\n \n \tif (reuse_packfiles) {\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex b9ea1fab397..8326a20979e 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2054,18 +2054,34 @@ static int find_base_bitmap_pos(struct bitmap_index *bitmap_git,\n \t\t\t\tuint32_t *base_bitmap_pos)\n {\n \tif (bitmap_is_midx(bitmap_git)) {\n+\t\tstruct object_id base_oid;\n+\t\tuint32_t base_pack_pos;\n+\t\tuint32_t base_idx_pos;\n+\t\tuint32_t base_midx_pos;\n+\n \t\t/*\n-\t\t * Cross-pack deltas are rejected for now, but could\n-\t\t * theoretically be supported in the future.\n-\t\t *\n-\t\t * We would need to ensure that we're sending both\n-\t\t * halves of the delta/base pair, regardless of whether\n-\t\t * or not the two cross a pack boundary. If they do,\n-\t\t * then we must convert the delta to an REF_DELTA to\n-\t\t * refer back to the base in the other pack.\n-\t\t * */\n-\t\tif (midx_pair_to_pack_pos(bitmap_git->midx, pack->pack_int_id,\n-\t\t\t\t\t base_offset, base_bitmap_pos) < 0)\n+\t\t * First convert from the base object's offset\n+\t\t * to its pack position in pack order relative\n+\t\t * to its source pack. Use that information to\n+\t\t * find the base object's OID.\n+\t\t */\n+\t\tif (offset_to_pack_pos(pack->p, base_offset,\n+\t\t\t\t &base_pack_pos) < 0)\n+\t\t\treturn -1;\n+\t\tbase_idx_pos = pack_pos_to_index(pack->p, base_pack_pos);\n+\t\tif (nth_packed_object_id(&base_oid, pack->p, base_idx_pos) < 0)\n+\t\t\treturn -1;\n+\n+\t\t/*\n+\t\t * Now find the base object's lexical position\n+\t\t * in the MIDX, and convert that to a bitmap\n+\t\t * position in the MIDX's pseudo-pack order.\n+\t\t */\n+\t\tif (!bsearch_midx(&base_oid, bitmap_git->midx,\n+\t\t\t\t &base_midx_pos))\n+\t\t\treturn -1;\n+\t\tif (midx_to_pack_pos(bitmap_git->midx, base_midx_pos,\n+\t\t\t\t base_bitmap_pos) < 0)\n \t\t\treturn -1;\n \t} else {\n \t\t/*\n@@ -2102,6 +2118,7 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t size_t bitmap_pos,\n \t\t\t off_t offset,\n \t\t\t struct bitmap *reuse,\n+\t\t\t struct bitmap *reuse_as_ref_delta,\n \t\t\t struct pack_window **w_curs)\n {\n \toff_t delta_obj_offset;\n@@ -2116,6 +2133,7 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \tif (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {\n \t\toff_t base_offset;\n \t\tuint32_t base_bitmap_pos;\n+\t\tint cross_pack;\n \n \t\t/*\n \t\t * Find the position of the base object so we can look it up\n@@ -2129,7 +2147,8 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t\t\t delta_obj_offset);\n \t\tif (!base_offset ||\n \t\t find_base_bitmap_pos(bitmap_git, pack, base_offset,\n-\t\t\t\t\t delta_obj_offset, &base_bitmap_pos) < 0)\n+\t\t\t\t\t delta_obj_offset,\n+\t\t\t\t\t &base_bitmap_pos) < 0)\n \t\t\treturn 0;\n \n \t\t/*\n@@ -2142,8 +2161,11 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t */\n \t\tif (!bitmap_get(reuse, base_bitmap_pos))\n \t\t\treturn 0;\n-\t}\n \n+\t\tcross_pack = base_bitmap_pos < pack->bitmap_pos;\n+\t\tif (cross_pack)\n+\t\t\tbitmap_set(reuse_as_ref_delta, bitmap_pos);\n+\t}\n \t/*\n \t * If we got here, then the object is OK to reuse. Mark it.\n \t */\n@@ -2153,7 +2175,8 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \n static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git,\n \t\t\t\t\t\t struct bitmapped_pack *pack,\n-\t\t\t\t\t\t struct bitmap *reuse)\n+\t\t\t\t\t\t struct bitmap *reuse,\n+\t\t\t\t\t\t struct bitmap *reuse_as_ref_delta)\n {\n \tstruct bitmap *result = bitmap_git->result;\n \tstruct pack_window *w_curs = NULL;\n@@ -2220,7 +2243,8 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git\n \t\t\t}\n \n \t\t\tif (try_partial_reuse(bitmap_git, pack, bit_pos,\n-\t\t\t\t\t ofs, reuse, &w_curs) < 0) {\n+\t\t\t\t\t ofs, reuse, reuse_as_ref_delta,\n+\t\t\t\t\t &w_curs) < 0) {\n \t\t\t\t/*\n \t\t\t\t * try_partial_reuse indicated we couldn't reuse\n \t\t\t\t * any bits, so there is no point in trying more\n@@ -2255,12 +2279,14 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t\t\tstruct bitmapped_pack **packs_out,\n \t\t\t\t\tsize_t *packs_nr_out,\n \t\t\t\t\tstruct bitmap **reuse_out,\n+\t\t\t\t\tstruct bitmap **reuse_as_ref_delta_out,\n \t\t\t\t\tint multi_pack_reuse)\n {\n \tstruct repository *r = the_repository;\n \tstruct bitmapped_pack *packs = NULL;\n \tstruct bitmap *result = bitmap_git->result;\n \tstruct bitmap *reuse;\n+\tstruct bitmap *reuse_as_ref_delta = NULL;\n \tsize_t i;\n \tsize_t packs_nr = 0, packs_alloc = 0;\n \tsize_t word_alloc;\n@@ -2333,14 +2359,18 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \tword_alloc = objects_nr / BITS_IN_EWORD;\n \tif (objects_nr % BITS_IN_EWORD)\n \t\tword_alloc++;\n+\n \treuse = bitmap_word_alloc(word_alloc);\n+\treuse_as_ref_delta = bitmap_word_alloc(word_alloc);\n \n \tfor (i = 0; i < packs_nr; i++)\n-\t\treuse_partial_packfile_from_bitmap_1(bitmap_git, &packs[i], reuse);\n+\t\treuse_partial_packfile_from_bitmap_1(bitmap_git, &packs[i],\n+\t\t\t\t\t\t reuse, reuse_as_ref_delta);\n \n \tif (bitmap_is_empty(reuse)) {\n \t\tfree(packs);\n \t\tbitmap_free(reuse);\n+\t\tbitmap_free(reuse_as_ref_delta);\n \t\treturn;\n \t}\n \n@@ -2352,6 +2382,7 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \t*packs_out = packs;\n \t*packs_nr_out = packs_nr;\n \t*reuse_out = reuse;\n+\t*reuse_as_ref_delta_out = reuse_as_ref_delta;\n }\n \n int bitmap_walk_contains(struct bitmap_index *bitmap_git,\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex a1e8c8936c9..e7962ac90e8 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -86,6 +86,7 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t\t\tstruct bitmapped_pack **packs_out,\n \t\t\t\t\tsize_t *packs_nr_out,\n \t\t\t\t\tstruct bitmap **reuse_out,\n+\t\t\t\t\tstruct bitmap **reuse_as_ref_delta_out,\n \t\t\t\t\tint multi_pack_reuse);\n int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,\n \t\t\t kh_oid_map_t *reused_bitmaps, int show_progress);\ndiff --git a/t/t5332-multi-pack-reuse.sh b/t/t5332-multi-pack-reuse.sh\nindex 8bcb736c75a..6edff02d124 100755\n--- a/t/t5332-multi-pack-reuse.sh\n+++ b/t/t5332-multi-pack-reuse.sh\n@@ -194,7 +194,7 @@ test_expect_success 'omit delta with uninteresting base (same pack)' '\n \ttest_pack_objects_reused 3 1 in <<-EOF &&\n \t$(git rev-parse $base)\n \t^$(git rev-parse $delta)\n@@ -207,7 +207,7 @@ test_expect_success 'omit delta from uninteresting base (cross pack)' '\n \tpacks_nr=\"$(find $packdir -type f -name \"pack-*.pack\" | wc -l)\" &&\n \tobjects_nr=\"$(git rev-list --count --all --objects)\" &&\n \n-\ttest_pack_objects_reused_all $(($objects_nr - 1)) $packs_nr\n+\ttest_pack_objects_reused_all $objects_nr $packs_nr\n '\n \n test_expect_success 'non-omitted delta in MIDX preferred pack' '\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504648","messageId":"dffdd794de3255719028a5f2c64d43048a5a5f60.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 10/11] pack-bitmap.c: record whether the result was filtered","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:31Z","receivedAt":"2024-10-09T20:31:33Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In a following commit, we will prepare to mark objects for reuse which\nare stored as deltas, but whose base object wasn't included in the\noutput pack (e.g., because the client already has it).\n\nWe can't, however, take advantage of that optimization when the\ntraversal removed objects from the result due to either (a) object\nfiltering, or (b) --unpacked.\n\nThat's because in either case, we can't rely on the principle that \"if\nan object appears in the 'haves' bitmap, that the client already has\nthat object\", since they may not have it as a result of filtering.\n\nKeep track of whether or not we performed any object filtering during\nour traversal in preparation to actually implement thin delta\nconversion.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 12 ++++++++++++\n 1 file changed, 12 insertions(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 8326a20979e..67ea267ed2a 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -112,6 +112,12 @@ struct bitmap_index {\n \t/* \"have\" bitmap from the last performed walk */\n \tstruct bitmap *haves;\n \n+\t/*\n+\t * Whether the last performed walk had objects removed from\n+\t * 'result' due to object filtering.\n+\t */\n+\tint filtered;\n+\n \t/* Version of the bitmap index */\n \tunsigned int version;\n };\n@@ -1684,6 +1690,8 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,\n \t\t\tbitmap_unset(to_filter, pos);\n \t}\n \n+\tbitmap_git->filtered = 1;\n+\n \tbitmap_free(tips);\n }\n \n@@ -1776,6 +1784,8 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,\n \t\t\tbitmap_unset(to_filter, pos);\n \t}\n \n+\tbitmap_git->filtered = 1;\n+\n \tbitmap_free(tips);\n }\n \n@@ -1892,6 +1902,8 @@ static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git,\n \t\tif (has_object_pack(&eindex->objects[i]->oid))\n \t\t\tbitmap_unset(result, objects_nr + i);\n \t}\n+\n+\tbitmap_git->filtered = 1;\n }\n \n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n-- \n2.47.0.11.g487258bca34\n\n"},{"id":"504649","messageId":"487258bca343078bcb59f22ac0a9a69d69f3c284.1728505840.git.me@ttaylorr.com","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"[PATCH 11/11] pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-09T20:31:34Z","receivedAt":"2024-10-09T20:31:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Ever since the current verbatim pack-reuse strategy was devised in\nbb514de356 (pack-objects: improve partial packfile reuse, 2019-12-18),\nwe have skipped sending delta objects whenever we're not sending that\nobject's base.\n\nBut it's fine to send such an object as a REF_DELTA against the base\nobject, provided the following are true:\n\n - We know that the client has the object already, i.e. it appears\n in the 'haves' bitmap.\n\n - The client supports thin packs, i.e. 'pack-objects' was invoked\n with the '--thin' option.\n\n - The client did not request object filtering, in which case we\n cannot trust that they actually do have all of the objects in the\n 'haves' bitmap, since we only filter the 'result' bitmap.\n\nWhen all of those criteria are met, we can send the delta object\nverbatim, meaning that we can reuse more objects from existing packs\nvia the verbatim reuse mechanism, which should be faster than kicking\nthose objects back to the slow path.\n\nSigned-off-by: Taylor Blau \n---\n builtin/pack-objects.c | 3 +-\n pack-bitmap.c | 52 ++++++++++++++++++++---------\n pack-bitmap.h | 3 +-\n t/t5332-multi-pack-reuse.sh | 66 +++++++++++++++++++++++++++++++++++++\n 4 files changed, 107 insertions(+), 17 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex dbcd632483e..027c64f931f 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4099,7 +4099,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \t\t\t\t\t\t &reuse_packfiles_nr,\n \t\t\t\t\t\t &reuse_packfile_bitmap,\n \t\t\t\t\t\t &reuse_as_ref_delta_packfile_bitmap,\n-\t\t\t\t\t\t allow_pack_reuse == MULTI_PACK_REUSE);\n+\t\t\t\t\t\t allow_pack_reuse == MULTI_PACK_REUSE,\n+\t\t\t\t\t\t thin);\n \n \tif (reuse_packfiles) {\n \t\treuse_packfile_objects = bitmap_popcount(reuse_packfile_bitmap);\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 67ea267ed2a..e8094453ca3 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2131,6 +2131,7 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\t off_t offset,\n \t\t\t struct bitmap *reuse,\n \t\t\t struct bitmap *reuse_as_ref_delta,\n+\t\t\t int thin_deltas,\n \t\t\t struct pack_window **w_curs)\n {\n \toff_t delta_obj_offset;\n@@ -2145,7 +2146,7 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \tif (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {\n \t\toff_t base_offset;\n \t\tuint32_t base_bitmap_pos;\n-\t\tint cross_pack;\n+\t\tint wants_base, cross_pack;\n \n \t\t/*\n \t\t * Find the position of the base object so we can look it up\n@@ -2164,19 +2165,25 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n \t\t\treturn 0;\n \n \t\t/*\n-\t\t * And finally, if we're not sending the base as part of our\n-\t\t * reuse chunk, then don't send this object either. The base\n-\t\t * would come after us, along with other objects not\n-\t\t * necessarily in the pack, which means we'd need to convert\n-\t\t * to REF_DELTA on the fly. Better to just let the normal\n-\t\t * object_entry code path handle it.\n+\t\t * And finally, if we're not sending the base as part of\n+\t\t * our reuse chunk, then either convert the delta to a\n+\t\t * REF_DELTA if the client supports thin deltas, or\n+\t\t * don't send this object either.\n \t\t */\n-\t\tif (!bitmap_get(reuse, base_bitmap_pos))\n-\t\t\treturn 0;\n-\n+\t\twants_base = bitmap_get(reuse, base_bitmap_pos);\n \t\tcross_pack = base_bitmap_pos < pack->bitmap_pos;\n-\t\tif (cross_pack)\n+\n+\t\tif (!wants_base) {\n+\t\t\tif (!thin_deltas)\n+\t\t\t\treturn 0;\n+\t\t\tif (!bitmap_git->haves ||\n+\t\t\t !bitmap_get(bitmap_git->haves, base_bitmap_pos))\n+\t\t\t\treturn 0;\n+\n \t\t\tbitmap_set(reuse_as_ref_delta, bitmap_pos);\n+\t\t} else if (cross_pack) {\n+\t\t\tbitmap_set(reuse_as_ref_delta, bitmap_pos);\n+\t\t}\n \t}\n \t/*\n \t * If we got here, then the object is OK to reuse. Mark it.\n@@ -2188,7 +2195,8 @@ static int try_partial_reuse(struct bitmap_index *bitmap_git,\n static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git,\n \t\t\t\t\t\t struct bitmapped_pack *pack,\n \t\t\t\t\t\t struct bitmap *reuse,\n-\t\t\t\t\t\t struct bitmap *reuse_as_ref_delta)\n+\t\t\t\t\t\t struct bitmap *reuse_as_ref_delta,\n+\t\t\t\t\t\t int thin_deltas)\n {\n \tstruct bitmap *result = bitmap_git->result;\n \tstruct pack_window *w_curs = NULL;\n@@ -2256,7 +2264,7 @@ static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git\n \n \t\t\tif (try_partial_reuse(bitmap_git, pack, bit_pos,\n \t\t\t\t\t ofs, reuse, reuse_as_ref_delta,\n-\t\t\t\t\t &w_curs) < 0) {\n+\t\t\t\t\t thin_deltas, &w_curs) < 0) {\n \t\t\t\t/*\n \t\t\t\t * try_partial_reuse indicated we couldn't reuse\n \t\t\t\t * any bits, so there is no point in trying more\n@@ -2292,7 +2300,8 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t\t\tsize_t *packs_nr_out,\n \t\t\t\t\tstruct bitmap **reuse_out,\n \t\t\t\t\tstruct bitmap **reuse_as_ref_delta_out,\n-\t\t\t\t\tint multi_pack_reuse)\n+\t\t\t\t\tint multi_pack_reuse,\n+\t\t\t\t\tint thin_deltas)\n {\n \tstruct repository *r = the_repository;\n \tstruct bitmapped_pack *packs = NULL;\n@@ -2375,9 +2384,22 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \treuse = bitmap_word_alloc(word_alloc);\n \treuse_as_ref_delta = bitmap_word_alloc(word_alloc);\n \n+\tif (bitmap_git->filtered) {\n+\t\t/*\n+\t\t * If the bitmap traversal filtered objects, then we\n+\t\t * can't trust the client actually has all of the\n+\t\t * objects that appear in the 'haves' bitmap. In that\n+\t\t * case, pretend like we don't support thin-deltas,\n+\t\t * since we can't guarantee that the client has all of\n+\t\t * the objects we think it has.\n+\t\t */\n+\t\tthin_deltas = 0;\n+\t}\n+\n \tfor (i = 0; i < packs_nr; i++)\n \t\treuse_partial_packfile_from_bitmap_1(bitmap_git, &packs[i],\n-\t\t\t\t\t\t reuse, reuse_as_ref_delta);\n+\t\t\t\t\t\t reuse, reuse_as_ref_delta,\n+\t\t\t\t\t\t thin_deltas);\n \n \tif (bitmap_is_empty(reuse)) {\n \t\tfree(packs);\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex e7962ac90e8..1a204fec31e 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -87,7 +87,8 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t\t\tsize_t *packs_nr_out,\n \t\t\t\t\tstruct bitmap **reuse_out,\n \t\t\t\t\tstruct bitmap **reuse_as_ref_delta_out,\n-\t\t\t\t\tint multi_pack_reuse);\n+\t\t\t\t\tint multi_pack_reuse,\n+\t\t\t\t\tint thin_deltas);\n int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,\n \t\t\t kh_oid_map_t *reused_bitmaps, int show_progress);\n void free_bitmap_index(struct bitmap_index *);\ndiff --git a/t/t5332-multi-pack-reuse.sh b/t/t5332-multi-pack-reuse.sh\nindex 6edff02d124..6237c680ae9 100755\n--- a/t/t5332-multi-pack-reuse.sh\n+++ b/t/t5332-multi-pack-reuse.sh\n@@ -51,6 +51,33 @@ test_pack_objects_reused () {\n \tgit index-pack --strict -o got.idx got.pack\n }\n \n+# test_pack_objects_reused_thin \n+test_pack_objects_reused_thin () {\n+\t: >trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$PWD/trace2.txt\" \\\n+\t\tgit pack-objects --thin --delta-base-offset --stdout --revs \\\n+\t\t>got.pack &&\n+\n+\ttest_pack_reused \"$1\" \n+test_pack_objects_reused_filter () {\n+\t: >trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$PWD/trace2.txt\" \\\n+\t\tgit pack-objects --thin --delta-base-offset --stdout --revs \\\n+\t\t\t--thin --filter=\"$1\" \\\n+\t\t>got.pack &&\n+\n+\ttest_pack_reused \"$2\" f &&\n+\t\tgit add f &&\n+\t\ttest_tick &&\n+\t\tgit commit -m \"base\" &&\n+\t\tbase=\"$(git rev-parse HEAD)\" &&\n+\n+\t\ttest_seq 32 >f &&\n+\t\ttest_tick &&\n+\t\tgit commit -a -m \"delta\" &&\n+\t\tdelta=\"$(git rev-parse HEAD)\" &&\n+\n+\t\tgit repack -ad &&\n+\n+\t\ttest_commit other &&\n+\n+\t\tpack=$(git pack-objects --all --unpacked $packdir/pack) &&\n+\t\tgit multi-pack-index write --bitmap \\\n+\t\t\t\t--preferred-pack=pack-$pack.pack &&\n+\n+\t\thave_delta \"$(git rev-parse $delta:f)\" \"$(git rev-parse $base:f)\" &&\n+\n+\t\tcat >in <<-EOF &&\n+\t\t$delta\n+\t\t^$base\n+\t\tEOF\n+\n+\t\ttest_pack_objects_reused_thin 3 1 writes:\n\n> This patch series enables more objects to be candidates for verbatim\n> reuse when generating a pack with the aide of reachability bitmaps.\n>\n> By the end of this series, two new classes of objects are now reuse\n> candidates which were not before. They are:\n>\n> - Cross-pack deltas. In multi-pack bitmaps, if the delta and base\n> were selected from different packs, the delta was not reusable.\n\nHmph. Suppose that you need to send object X, you happen to have X\nas a ofs-delta against Y, but Y may appear in multiple packs.\n\nEven if the copy of Y you are going to send together with X is from\nthe same packfile, you may not be sending all the objects between X\nand Y in the original local packfile, so you would need to recompute\nthe offset to give ofs-delta X to the distance between X and Y in\nthe resulting packstream, no?\n\nSo when you pick the copy of Y out of another pack, what's so\ndifferent? After emitting Y to the resulting pack stream (and\nremembering where in the packstream you did so), when it is X's turn\nto be emitted, shouldn't you be able to compute the distance in the\nresulting packstream to represent X as an ofs-delta against Y, which\nshould already be happening when you had both X and Y in the same\noriginal pack?\n\n> - Thin deltas. In both single- and multi-pack bitmaps, we did not\n> consider reusing deltas whose base object appears in the 'haves'\n> bitmap.\n\nI hope this optimization does not kick in unless the receiving end\nis prepared to do \"index-pack --fix-thin\".\n\nI've never thought about this specifically, but it is interesting to\nrealize that by definition \"thin\" deltas cannot be ofs-deltas.\n\n> Of course, REF_DELTAs have a less compact representation than\n> OFS_DELTAs, so the resulting packs will trade off some CPU time for a\n> slightly larger pack.\n\nIs comparing ref- vs ofs- delta a meaningful thing to do in the\ncontext of this series?\n\nWhat does the current code without these patches do in the same\nsituation? Give up on reusing the existing delta and then? If we\nsend the base representation instead, the comparison is \"we\ncurrently do not use delta, but with this change we can reuse delta\n(even though we do not bother recompute the offset and instead use\nref-delta)\".\n\nDo we recompute the delta on the fly and show it as an ofs-delta\nwith the current code? Then the comparison would be \"we spend time\ndoing diff-delta once right now but instead reuse an existing one\n(even though we do not bother recompute the offset and instead use\nref-delta)\".\n\n"},{"id":"504717","messageId":"ZwgJt19kWVRTQhld@nand.local","threadId":"62300","inReplyTo":"xmqqzfnblxdj.fsf@gitster.g","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-10T17:07:03Z","receivedAt":"2024-10-10T17:07:06Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Oct 10, 2024 at 09:46:00AM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> > This patch series enables more objects to be candidates for verbatim\n> > reuse when generating a pack with the aide of reachability bitmaps.\n> >\n> > By the end of this series, two new classes of objects are now reuse\n> > candidates which were not before. They are:\n> >\n> > - Cross-pack deltas. In multi-pack bitmaps, if the delta and base\n> > were selected from different packs, the delta was not reusable.\n>\n> Hmph. Suppose that you need to send object X, you happen to have X\n> as a ofs-delta against Y, but Y may appear in multiple packs.\n>\n> Even if the copy of Y you are going to send together with X is from\n> the same packfile, you may not be sending all the objects between X\n> and Y in the original local packfile, so you would need to recompute\n> the offset to give ofs-delta X to the distance between X and Y in\n> the resulting packstream, no?\n\nThat's right. When doing verbatim pack reuse, we mark reused \"chunks\"\n(c.f. 'struct reused_chunk'), where each chunk records the offset of the\nbeginning of the chunk in the source pack, and the difference between\nthat value and the corresponding byte in the assembled pack.\n\nSo suppose like in your example we have X and Y from the same pack, and\nwe are sending both objects, but not necessarily every object in between\nthe two from the source pack. In that case, X and Y will end up in\ndifferent chunks.\n\nWhen we go to actually rewrite the OFS_DELTA for X, we'll compute:\n\n off_t fixup = find_reused_offset(X) - find_reused_offset(Y);\n\n(in the code, X and Y are actually the offsets for each object in the\nsource pack, but I'm using the object names here for clarity).\n\nWhen there is a non-zero fixup value, we'll patch the OFS_DELTA to\naccount for the gap between it and its base object. The details of how\nthat is done are in builtin/pack-objects.c::write_reused_pack_one(), in\nthe 'if (fixup) { ... }' block.\n\n> So when you pick the copy of Y out of another pack, what's so\n> different? After emitting Y to the resulting pack stream (and\n> remembering where in the packstream you did so), when it is X's turn\n> to be emitted, shouldn't you be able to compute the distance in the\n> resulting packstream to represent X as an ofs-delta against Y, which\n> should already be happening when you had both X and Y in the same\n> original pack?\n\nGood question. The difference is that if you're reusing X and Y from\nsame pack, you know that Y occurs some number of bytes *before* X in the\nresulting pack.\n\nBut if Y comes from a different pack, it may get pushed further back in\nthe MIDX pseudo-pack order. So in that case the assembled pack may list\nX before Y, in which case X cannot be an OFS_DELTA of Y, since offset\ndeltas require that the base object appears first.\n\n> > - Thin deltas. In both single- and multi-pack bitmaps, we did not\n> > consider reusing deltas whose base object appears in the 'haves'\n> > bitmap.\n>\n> I hope this optimization does not kick in unless the receiving end\n> is prepared to do \"index-pack --fix-thin\".\n\nIt does. We only allow computing \"thin deltas\" when pack-objects was\ninvoked with `--thin`.\n\n> I've never thought about this specifically, but it is interesting to\n> realize that by definition \"thin\" deltas cannot be ofs-deltas.\n\nYep.\n\n> > Of course, REF_DELTAs have a less compact representation than\n> > OFS_DELTAs, so the resulting packs will trade off some CPU time for a\n> > slightly larger pack.\n>\n> Is comparing ref- vs ofs- delta a meaningful thing to do in the\n> context of this series?\n>\n> What does the current code without these patches do in the same\n> situation? Give up on reusing the existing delta and then? If we\n> send the base representation instead, the comparison is \"we\n> currently do not use delta, but with this change we can reuse delta\n> (even though we do not bother recompute the offset and instead use\n> ref-delta)\".\n\nThe current code does not reuse deltas when we're either (a) not sending\nthe base, (b) we are sending the base, but it's in a different pack, or\n(c) both. When any of those conditions are met, we do not reuse the\nexisting on-disk representation of the delta object verbatim, and\ninstead kick it back to the normal pack generation routine.\n\nThat might result in us finding a new base, or applying sending the\nobject's contents as a standalone object.\n\n> Do we recompute the delta on the fly and show it as an ofs-delta\n> with the current code? Then the comparison would be \"we spend time\n> doing diff-delta once right now but instead reuse an existing one\n> (even though we do not bother recompute the offset and instead use\n> ref-delta)\".\n\nFair.\n\nThanks,\nTaylor\n"},{"id":"504741","messageId":"xmqq8quvk8w9.fsf@gitster.g","threadId":"62300","inReplyTo":"ZwgJt19kWVRTQhld@nand.local","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-10-10T20:20:06Z","receivedAt":"2024-10-10T20:20:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n>> So when you pick the copy of Y out of another pack, what's so\n>> different? After emitting Y to the resulting pack stream (and\n>> remembering where in the packstream you did so), when it is X's turn\n>> to be emitted, shouldn't you be able to compute the distance in the\n>> resulting packstream to represent X as an ofs-delta against Y, which\n>> should already be happening when you had both X and Y in the same\n>> original pack?\n>\n> Good question. The difference is that if you're reusing X and Y from\n> same pack, you know that Y occurs some number of bytes *before* X in the\n> resulting pack.\n>\n> But if Y comes from a different pack, it may get pushed further back in\n> the MIDX pseudo-pack order. So in that case the assembled pack may list\n> X before Y, in which case X cannot be an OFS_DELTA of Y, since offset\n> deltas require that the base object appears first.\n\nThat is what we have always done even before we started bitmap based\noptimization. If we happen to write Y before X, we consider doing\nofs-delta for X, but otherwise we do ref-delta for X. We do reorder\nfairly late in the pipeline when we notice that X that we are about\nto write out depends on Y that we haven't emitted to avoid this,\nthough. All of that the bitmap-based optimization code path should\nbe able to imitate, I would think.\n\n"},{"id":"504743","messageId":"Zwg583RghrWdgqO1@nand.local","threadId":"62300","inReplyTo":"xmqq8quvk8w9.fsf@gitster.g","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-10-10T20:32:51Z","receivedAt":"2024-10-10T20:32:53Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Oct 10, 2024 at 01:20:06PM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> >> So when you pick the copy of Y out of another pack, what's so\n> >> different? After emitting Y to the resulting pack stream (and\n> >> remembering where in the packstream you did so), when it is X's turn\n> >> to be emitted, shouldn't you be able to compute the distance in the\n> >> resulting packstream to represent X as an ofs-delta against Y, which\n> >> should already be happening when you had both X and Y in the same\n> >> original pack?\n> >\n> > Good question. The difference is that if you're reusing X and Y from\n> > same pack, you know that Y occurs some number of bytes *before* X in the\n> > resulting pack.\n> >\n> > But if Y comes from a different pack, it may get pushed further back in\n> > the MIDX pseudo-pack order. So in that case the assembled pack may list\n> > X before Y, in which case X cannot be an OFS_DELTA of Y, since offset\n> > deltas require that the base object appears first.\n>\n> That is what we have always done even before we started bitmap based\n> optimization. If we happen to write Y before X, we consider doing\n> ofs-delta for X, but otherwise we do ref-delta for X. We do reorder\n> fairly late in the pipeline when we notice that X that we are about\n> to write out depends on Y that we haven't emitted to avoid this,\n> though. All of that the bitmap-based optimization code path should\n> be able to imitate, I would think.\n\nI see..., so yeah: before this patch series we would have not processed\nX via the bitmap-powered pack reuse mechanism, and after this series we\nwill.\n\nThanks,\nTaylor\n"},{"id":"504817","messageId":"20241011075451.GD18010@coredump.intra.peff.net","threadId":"62300","inReplyTo":"xmqq8quvk8w9.fsf@gitster.g","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-11T07:54:51Z","receivedAt":"2024-10-11T07:54:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 10, 2024 at 01:20:06PM -0700, Junio C Hamano wrote:\n\n> Taylor Blau writes:\n> \n> >> So when you pick the copy of Y out of another pack, what's so\n> >> different? After emitting Y to the resulting pack stream (and\n> >> remembering where in the packstream you did so), when it is X's turn\n> >> to be emitted, shouldn't you be able to compute the distance in the\n> >> resulting packstream to represent X as an ofs-delta against Y, which\n> >> should already be happening when you had both X and Y in the same\n> >> original pack?\n> >\n> > Good question. The difference is that if you're reusing X and Y from\n> > same pack, you know that Y occurs some number of bytes *before* X in the\n> > resulting pack.\n> >\n> > But if Y comes from a different pack, it may get pushed further back in\n> > the MIDX pseudo-pack order. So in that case the assembled pack may list\n> > X before Y, in which case X cannot be an OFS_DELTA of Y, since offset\n> > deltas require that the base object appears first.\n> \n> That is what we have always done even before we started bitmap based\n> optimization. If we happen to write Y before X, we consider doing\n> ofs-delta for X, but otherwise we do ref-delta for X. We do reorder\n> fairly late in the pipeline when we notice that X that we are about\n> to write out depends on Y that we haven't emitted to avoid this,\n> though. All of that the bitmap-based optimization code path should\n> be able to imitate, I would think.\n\nA small nitpick on your final sentence here. As you note, we do not ever\nwrite Y before X, because compute_write_order() always places bases\nbefore their deltas in the output pack (and we do not allow cycles of\ndeltas, of course).\n\nAnd even with bitmaps we'd do the same, as long as those objects are\nboth fed to the regular pack-writing machinery.\n\nIt is only the special verbatim-pack-reuse[1] code that is trying to\nblit out the start of an existing pack that is affected. And in theory\nthere it _could_ try to reorder to produce an ofs delta, but in practice\nthe whole point is to take a single very cheap pass over the start of\nthe pack (or multiple packs in the case of the midx). Doing any\nreordering would be counterproductive to the \"cheap\" adjective there (it\ndoes not even keep a list of object ids it is sending), so we are better\nto leave those objects for the regular output code (which does make such\na list).\n\nTaylor's series introduces an in-between where we choose not to reorder,\nbut switch to REF_DELTA. That is still cheap on CPU on the generating\nside, though the resulting pack is slightly larger.\n\n-Peff\n\n[1] I wish we had good names to distinguish the various cases, because\n the term \"reuse\" is kind of overloaded. The \"slower\" regular\n object-sending path may still reuse verbatim bytes found in an\n on-disk path. But this \"blit out matching parts of a pack without\n otherwise considering the objects\" feature happens outside of that.\n We called it \"pack reuse\" back in 2013, but that was not a good name\n even then. I don't have a good suggestion, though.\n"},{"id":"504818","messageId":"20241011080149.GA560372@coredump.intra.peff.net","threadId":"62300","inReplyTo":"20241011075451.GD18010@coredump.intra.peff.net","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-11T08:01:49Z","receivedAt":"2024-10-11T08:01:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 11, 2024 at 03:54:51AM -0400, Jeff King wrote:\n\n> [1] I wish we had good names to distinguish the various cases, because\n> the term \"reuse\" is kind of overloaded. The \"slower\" regular\n> object-sending path may still reuse verbatim bytes found in an\n> on-disk path. But this \"blit out matching parts of a pack without\n> otherwise considering the objects\" feature happens outside of that.\n> We called it \"pack reuse\" back in 2013, but that was not a good name\n> even then. I don't have a good suggestion, though.\n\nActually, confusing things more, there are really _three_ layers of\nreuse:\n\n 1. At the beginning of a pack, we can blit out the bytes for objects\n starting from the beginning of the pack that are being sent (we\n know any delta will be satisfied since its base comes before it).\n\n 2. After that, we process objects one by one, but do so very cheaply\n by just deciding if we can blit them out one by one, fixing up\n delta base offsets to account for gaps.\n\n 3. Otherwise, we generate an object_entry struct in packing_data for\n them, try to find new deltas, and so on. We may then reuse the\n on-disk bytes after deciding they're suitable.\n\nWe call all of these \"reuse\", and certainly both (1) and (2) are \"pack\nreuse\", but I think that term is sufficiently vague that it could apply\nto (3) as well.\n\n-Peff\n"},{"id":"504819","messageId":"20241011081615.GE18010@coredump.intra.peff.net","threadId":"62300","inReplyTo":"94e5c96f6859479e0206d6d775eacf54b3639ee5.1728505840.git.me@ttaylorr.com","subject":"Re: [PATCH 07/11] write_reused_pack_one(): translate bit positions directly","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-11T08:16:15Z","receivedAt":"2024-10-11T08:16:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2024 at 04:31:21PM -0400, Taylor Blau wrote:\n\n> +static uint32_t bitmap_to_pack_pos(struct packed_git *reuse_packfile,\n> +\t\t\t\t size_t pos)\n> +{\n> +\tif (bitmap_is_midx(bitmap_git)) {\n> +\t\t/*\n> +\t\t * When doing multi-pack reuse on a\n> +\t\t * non-preferred pack, translate bit positions\n> +\t\t * from the MIDX pseudo-pack order back to their\n> +\t\t * pack-relative positions before attempting\n> +\t\t * reuse.\n> +\t\t */\n> +\t\tstruct multi_pack_index *m = bitmap_midx(bitmap_git);\n> +\t\tuint32_t midx_pos, pack_pos;\n> +\t\toff_t pack_ofs;\n> +\n> +\t\tif (!m)\n> +\t\t\tBUG(\"non-zero bitmap position without MIDX\");\n\nThe text of this BUG() seems weird: we haven't asserted a non-zero\nbitmap position. We're really only checking that bitmap_is_midx() and\nbitmap_midx() agree that there is a midx. I was going to suggest that\nthe former could be implemented with a NULL-check on the latter, but\nreally, that is already how it works (except that it accesses\nbitmap_index->midx directly).\n\nSo yes, it truly would be a surprising BUG() to see them disagree. :)\n\nI do not mind keeping the BUG() there if you want to be extra careful,\nbut I just found the message text confusing.\n\nAh...hmm. This is all being copied from the earlier function. So I think\nthe culprit may be patch 6, which swaps:\n\n if (reuse_packfile->bitmap_pos)\n\nfor:\n\n if (bitmap_is_midx(bitmap_git))\n\nwhich is what makes the BUG() text confusing. But then, what about this:\n\n> +\t} else {\n> +\t\t/*\n> +\t\t * Can use bit positions directly, even for MIDX\n> +\t\t * bitmaps. See comment in try_partial_reuse()\n> +\t\t * for why.\n> +\t\t */\n> +\t\treturn pos;\n> +\t}\n> +}\n\nThis \"even for MIDX\" is not really accurate, as we know this else block\nis for the non-midx case. Are we losing the optimization that the first\npack in the midx can be treated the same as the single-pack case (we\nknow that its pack positions and the start of the midx bit positions are\nidentical, which is what the comment it mentions explains)?\n\n-Peff\n"},{"id":"504820","messageId":"20241011081939.GF18010@coredump.intra.peff.net","threadId":"62300","inReplyTo":"9d81d890402f94f4126aedef0845d615d10455bc.1728505840.git.me@ttaylorr.com","subject":"Re: [PATCH 08/11] t5332: enable OFS_DELTAs via test_pack_objects_reused","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-11T08:19:39Z","receivedAt":"2024-10-11T08:19:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2024 at 04:31:24PM -0400, Taylor Blau wrote:\n\n> Back when test_pack_objects_reused was introduced via commit\n> 7c01878eeb (t5332-multi-pack-reuse.sh: extract pack-objects helper\n> functions, 2024-02-05), we converted bare pack-objects invocations\n> into one of two wrapped variants, either test_pack_objects_reused or\n> test_pack_objects_reused_all.\n> \n> The latter passes `--delta-base-offset`, allowing pack-objects to\n> generate OFS_DELTAs in its output pack. But the former does not, for\n> no good reason.\n> \n> As we do not want to convert OFS_DELTAs to REF_DELTAs unnecessarily,\n> let's unify these two and pass `--delta-base-offset` to both.\n\nI think that matches what happens in the real world. I am puzzled that\nyour BUG() instrumenting turns up some conversion cases. Why are we\nstill converting in those cases?\n\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 0fc0680b402..0f1b22b8674 100644\n> --- a/builtin/pack-objects.c\n> +++ b/builtin/pack-objects.c\n\nYou need to indent or otherwise comment-out this diff. Otherwise \"git\nam\" will pick it up as the start of the actual diff, adding the bogus\nBUG() call to the applied patch (and dropping the rest of your commit\nmessage).\n\n-Peff\n"},{"id":"504825","messageId":"20241011083134.GG18010@coredump.intra.peff.net","threadId":"62300","inReplyTo":"ca3a916cd6e93aaa09ccff9f77fc127254222068.1728505840.git.me@ttaylorr.com","subject":"Re: [PATCH 09/11] pack-bitmap: enable cross-pack delta reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-11T08:31:34Z","receivedAt":"2024-10-11T08:31:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2024 at 04:31:28PM -0400, Taylor Blau wrote:\n\n> In order to do this, the pack-reuse code within pack-bitmap.c marks\n> bits in a separate bitmap called 'reuse_as_ref_delta'. Objects whose\n> bits are marked in that bitmap must be converted from OFS_DELTAs to\n> REF_DELTAs.\n> \n> To mark bits in that bitmap, we adjust find_base_bitmap_pos() to\n> return the bitmap position of any delta object's base regardless of\n> whether or not it came from the same pack. This is done by:\n> \n> 1. First converting the base object's into a pack position (via\n> `offset_to_pack_pos()`).\n> \n> 2. Then converting from pack position into into lexical order (via\n> `pack_pos_to_index()`).\n> \n> 3. Then into an object ID (via `nth_packed_object_id()`).\n> \n> 4. Then into a position in the MIDX's lexical order of object IDs\n> (via `bsearch_midx()`).\n> \n> 5. And finally into a position in the MIDX's pseudo-pack order (via\n> `midx_pair_to_pack_pos()`).\n> \n> If we can find that base object in the MIDX, then we use its position\n> in the MIDX's pseudo-pack order to determine whether or not it was\n> selected from the same pack. If it is, no adjustment is necessary.\n> Otherwise, we mark the delta object's position in the new\n> `reuse_as_ref_delta` bitmap, and convert accordingly from within\n> `write_reused_pack_one()`.\n\nOK, that makes sense. It does feel like a non-trivial amount of work to\ndo for each delta we're going to (potentially) reuse from a midx'd pack.\nCan we recognize the common case that the base is in the same pack and\nalso being sent/reused without doing the full conversion to oid and the\nresulting bsearch?\n\n> @@ -1182,10 +1188,24 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,\n> \tif (pos >= end)\n> \t\treturn reuse_packfile->bitmap_pos / BITS_IN_EWORD;\n> \n> -\twhile (pos < end &&\n> -\t reuse_packfile_bitmap->words[pos / BITS_IN_EWORD] == (eword_t)~0)\n> +\twhile (pos < end) {\n> +\t\tsize_t wpos = pos / BITS_IN_EWORD;\n> +\t\teword_t reuse;\n> +\n> +\t\treuse = reuse_packfile_bitmap->words[wpos];\n> +\t\tif (reuse_as_ref_delta_packfile_bitmap) {\n> +\t\t\t/*\n> +\t\t\t * Can't reuse verbatim any objects which need\n> +\t\t\t * to be first rewritten as REF_DELTAs.\n> +\t\t\t */\n> +\t\t\treuse &= ~reuse_as_ref_delta_packfile_bitmap->words[wpos];\n> +\t\t}\n> +\n> +\t\tif (reuse != (eword_t)~0)\n> +\t\t\tbreak;\n> +\n> \t\tpos += BITS_IN_EWORD;\n> -\n> +\t}\n\nThis is accessing reuse_as_ref_delta_packfile_bitmap->words directly\nusing pos/end as limits. But those come from reuse_packfile_bitmap. Are\nwe guaranteed to have zero-extended the reuse_as_ref_delta bitmap as far\nas the original went?\n\nCould we just be calling bitmap_get() here, which would do the length\ncheck for us? Though I guess we would miss out on some whole-word magic\nit is doing. So maybe we need to just do that length check ourselves.\n\n-Peff\n"},{"id":"504826","messageId":"20241011083545.GH18010@coredump.intra.peff.net","threadId":"62300","inReplyTo":"dffdd794de3255719028a5f2c64d43048a5a5f60.1728505840.git.me@ttaylorr.com","subject":"Re: [PATCH 10/11] pack-bitmap.c: record whether the result was filtered","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-11T08:35:45Z","receivedAt":"2024-10-11T08:35:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2024 at 04:31:31PM -0400, Taylor Blau wrote:\n\n> In a following commit, we will prepare to mark objects for reuse which\n> are stored as deltas, but whose base object wasn't included in the\n> output pack (e.g., because the client already has it).\n> \n> We can't, however, take advantage of that optimization when the\n> traversal removed objects from the result due to either (a) object\n> filtering, or (b) --unpacked.\n> \n> That's because in either case, we can't rely on the principle that \"if\n> an object appears in the 'haves' bitmap, that the client already has\n> that object\", since they may not have it as a result of filtering.\n\nI think this is a reasonable precaution, though it does make me wonder\nif the non-reuse code paths are so careful. That is, if we have object Y\nwhich is a delta against object X, but we know the other side _could_\nhave X (because it's reachable from some commit they claim to have),\nwould we ever send a thin delta against X?\n\nI don't recall seeing any protections for that, though I also wouldn't\nbe too surprised if it somehow just works out because we never figure\nout whether they have X or not. :-/\n\nI wonder, though: should thin deltas just be turned off entirely when\nfiltering is in play?\n\nLikewise for --unpacked (though in practice I think it would never be\nused with --thin, as it is about generating new on-disk packs).\n\n-Peff\n"},{"id":"504827","messageId":"20241011083838.GI18010@coredump.intra.peff.net","threadId":"62300","inReplyTo":"cover.1728505840.git.me@ttaylorr.com","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-10-11T08:38:38Z","receivedAt":"2024-10-11T08:38:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 09, 2024 at 04:30:52PM -0400, Taylor Blau wrote:\n\n> The first optimization (cross-pack deltas) should help clones and\n> fetches, but the second optimization (thin deltas) will only help\n> fetches, since the 'haves' bitmap will necessarily be empty for\n> clones.\n> \n> Of course, REF_DELTAs have a less compact representation than\n> OFS_DELTAs, so the resulting packs will trade off some CPU time for a\n> slightly larger pack. But we're only talking about a handful of extra\n> bytes, and network bandwidth is pretty cheap, so I think the\n> optimization is worthwhile here too.\n\nIt would be nice to see some numbers, even simulated ones from t/perf.\nOf course we'd like to show off any reduced server CPU for generating a\nfetch response. But I'd also like to see if the extra steps to find the\ncross-pack bases have any measurable negative effect (so the ideal there\nwould be a big midx repo that doesn't have a lot of those bases, as it\nwould not be helped much by the optimization and would be hurt by the\ntime spent trying to apply it).\n\n-Peff\n"},{"id":"504844","messageId":"xmqqy12uhals.fsf@gitster.g","threadId":"62300","inReplyTo":"20241011080149.GA560372@coredump.intra.peff.net","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-10-11T16:23:43Z","receivedAt":"2024-10-11T16:23:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Oct 11, 2024 at 03:54:51AM -0400, Jeff King wrote:\n>\n>> [1] I wish we had good names to distinguish the various cases, because\n>> the term \"reuse\" is kind of overloaded. The \"slower\" regular\n>> object-sending path may still reuse verbatim bytes found in an\n>> on-disk path. But this \"blit out matching parts of a pack without\n>> otherwise considering the objects\" feature happens outside of that.\n>> We called it \"pack reuse\" back in 2013, but that was not a good name\n>> even then. I don't have a good suggestion, though.\n>\n> Actually, confusing things more, there are really _three_ layers of\n> reuse:\n>\n> 1. At the beginning of a pack, we can blit out the bytes for objects\n> starting from the beginning of the pack that are being sent (we\n> know any delta will be satisfied since its base comes before it).\n\nYes, I wouldn't be worried about that one. The data encoded as an\nofs-delta in this section already point at their base correctly in\nthe original pack, and in the resulting pack.\n\n> 2. After that, we process objects one by one, but do so very cheaply\n> by just deciding if we can blit them out one by one, fixing up\n> delta base offsets to account for gaps.\n\nThis is the part I said \"we have to remember where the base was emitted\nand subtract it from the offset of the delta anyway even if we are\nreusing delta from the same pack, so what do we need a separate code path\nfor this?\" in my initial response.\n\nI guess, \"fixing up\" could be done by using the difference between\noffsets in the original pack for this step, which would be an\nunfortunate design that prevents it from getting reused.\n\n> 3. Otherwise, we generate an object_entry struct in packing_data for\n> them, try to find new deltas, and so on. We may then reuse the\n> on-disk bytes after deciding they're suitable.\n\nIt is a bit unfortunate, if we were to trust the existing delta base\nselection in the pack like we did since Feb 2006 [*], we should be\nomitting the \"try to find new deltas\" step. Perhaps that comes for\nfree as the object_entry knows that our object has a delta_base?\n\n> We call all of these \"reuse\", and certainly both (1) and (2) are \"pack\n> reuse\", but I think that term is sufficiently vague that it could apply\n> to (3) as well.\n>\n> -Peff\n"},{"id":"506562","messageId":"ZykwMW3PIpsPjbwz@nand.local","threadId":"62300","inReplyTo":"20241011081615.GE18010@coredump.intra.peff.net","subject":"Re: [PATCH 07/11] write_reused_pack_one(): translate bit positions directly","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-04T20:36:01Z","receivedAt":"2024-11-04T20:36:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 11, 2024 at 04:16:15AM -0400, Jeff King wrote:\n> Ah...hmm. This is all being copied from the earlier function. So I think\n> the culprit may be patch 6, which swaps:\n>\n> if (reuse_packfile->bitmap_pos)\n>\n> for:\n>\n> if (bitmap_is_midx(bitmap_git))\n>\n> which is what makes the BUG() text confusing. But then, what about this:\n>\n> > +\t} else {\n> > +\t\t/*\n> > +\t\t * Can use bit positions directly, even for MIDX\n> > +\t\t * bitmaps. See comment in try_partial_reuse()\n> > +\t\t * for why.\n> > +\t\t */\n> > +\t\treturn pos;\n> > +\t}\n> > +}\n>\n> This \"even for MIDX\" is not really accurate, as we know this else block\n> is for the non-midx case. Are we losing the optimization that the first\n> pack in the midx can be treated the same as the single-pack case (we\n> know that its pack positions and the start of the midx bit positions are\n> identical, which is what the comment it mentions explains)?\n\nGreat catch.\n\nWe indeed lost that optimization when converting \"if\n(reuse_packfile->bitmap_pos)\" to \"if (bitmap_is_midx(bitmap_git))\".\nLet's restore that by keeping the conditional unchanged, which:\n\n - makes the BUG() make sense as written, and\n\n - preserves the optimization where the first pack in a MIDX can be\n treated the same as if it came from a single-pack bitmap, and\n bypass the bit position translations.\n\nThanks for spotting.\n\nThanks,\nTaylor\n"},{"id":"506563","messageId":"Zykzobmfaun/Ojz0@nand.local","threadId":"62300","inReplyTo":"20241011081939.GF18010@coredump.intra.peff.net","subject":"Re: [PATCH 08/11] t5332: enable OFS_DELTAs via test_pack_objects_reused","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-04T20:50:41Z","receivedAt":"2024-11-04T20:50:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 11, 2024 at 04:19:39AM -0400, Jeff King wrote:\n> On Wed, Oct 09, 2024 at 04:31:24PM -0400, Taylor Blau wrote:\n>\n> > Back when test_pack_objects_reused was introduced via commit\n> > 7c01878eeb (t5332-multi-pack-reuse.sh: extract pack-objects helper\n> > functions, 2024-02-05), we converted bare pack-objects invocations\n> > into one of two wrapped variants, either test_pack_objects_reused or\n> > test_pack_objects_reused_all.\n> >\n> > The latter passes `--delta-base-offset`, allowing pack-objects to\n> > generate OFS_DELTAs in its output pack. But the former does not, for\n> > no good reason.\n> >\n> > As we do not want to convert OFS_DELTAs to REF_DELTAs unnecessarily,\n> > let's unify these two and pass `--delta-base-offset` to both.\n>\n> I think that matches what happens in the real world. I am puzzled that\n> your BUG() instrumenting turns up some conversion cases. Why are we\n> still converting in those cases?\n\nThese are cases where we're calling pack-objects directly without\npassing the --delta-base-offset flag, so all deltas get converted into\nREF_DELTAs.\n\n> > diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> > index 0fc0680b402..0f1b22b8674 100644\n> > --- a/builtin/pack-objects.c\n> > +++ b/builtin/pack-objects.c\n>\n> You need to indent or otherwise comment-out this diff. Otherwise \"git\n> am\" will pick it up as the start of the actual diff, adding the bogus\n> BUG() call to the applied patch (and dropping the rest of your commit\n> message).\n\nOops, of course. Thanks for spotting again.\n\nThanks,\nTaylor\n"},{"id":"506564","messageId":"Zyk12FZ+NcOUALAz@nand.local","threadId":"62300","inReplyTo":"20241011083134.GG18010@coredump.intra.peff.net","subject":"Re: [PATCH 09/11] pack-bitmap: enable cross-pack delta reuse","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-04T21:00:08Z","receivedAt":"2024-11-04T21:00:11Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 11, 2024 at 04:31:34AM -0400, Jeff King wrote:\n> On Wed, Oct 09, 2024 at 04:31:28PM -0400, Taylor Blau wrote:\n>\n> > In order to do this, the pack-reuse code within pack-bitmap.c marks\n> > bits in a separate bitmap called 'reuse_as_ref_delta'. Objects whose\n> > bits are marked in that bitmap must be converted from OFS_DELTAs to\n> > REF_DELTAs.\n> >\n> > To mark bits in that bitmap, we adjust find_base_bitmap_pos() to\n> > return the bitmap position of any delta object's base regardless of\n> > whether or not it came from the same pack. This is done by:\n> >\n> > 1. First converting the base object's into a pack position (via\n> > `offset_to_pack_pos()`).\n> >\n> > 2. Then converting from pack position into into lexical order (via\n> > `pack_pos_to_index()`).\n> >\n> > 3. Then into an object ID (via `nth_packed_object_id()`).\n> >\n> > 4. Then into a position in the MIDX's lexical order of object IDs\n> > (via `bsearch_midx()`).\n> >\n> > 5. And finally into a position in the MIDX's pseudo-pack order (via\n> > `midx_pair_to_pack_pos()`).\n> >\n> > If we can find that base object in the MIDX, then we use its position\n> > in the MIDX's pseudo-pack order to determine whether or not it was\n> > selected from the same pack. If it is, no adjustment is necessary.\n> > Otherwise, we mark the delta object's position in the new\n> > `reuse_as_ref_delta` bitmap, and convert accordingly from within\n> > `write_reused_pack_one()`.\n>\n> OK, that makes sense. It does feel like a non-trivial amount of work to\n> do for each delta we're going to (potentially) reuse from a midx'd pack.\n> Can we recognize the common case that the base is in the same pack and\n> also being sent/reused without doing the full conversion to oid and the\n> resulting bsearch?\n\nI don't think it ends up saving you anything if you don't find anything\nmatching the pack/offset pair in the MIDX. If you perform that lookup\nwith bsearch_midx() and get nothing back, then you have to take the\nslower path above anyway.\n\nMy figuring here was that it would be better to uniformly take a\nslightly slower path instead of taking a hopefully-faster path which\nmight fail, only to then go back to the slower path on top.\n\nOf course, you could do both, or apply some heuristics like avoiding the\ncross-pack lookup if you know you're in the preferred pack, etc. I'm not\nsure how much it is worth doing so, TBH.\n\n> > @@ -1182,10 +1188,24 @@ static size_t write_reused_pack_verbatim(struct bitmapped_pack *reuse_packfile,\n> > \tif (pos >= end)\n> > \t\treturn reuse_packfile->bitmap_pos / BITS_IN_EWORD;\n> >\n> > -\twhile (pos < end &&\n> > -\t reuse_packfile_bitmap->words[pos / BITS_IN_EWORD] == (eword_t)~0)\n> > +\twhile (pos < end) {\n> > +\t\tsize_t wpos = pos / BITS_IN_EWORD;\n> > +\t\teword_t reuse;\n> > +\n> > +\t\treuse = reuse_packfile_bitmap->words[wpos];\n> > +\t\tif (reuse_as_ref_delta_packfile_bitmap) {\n> > +\t\t\t/*\n> > +\t\t\t * Can't reuse verbatim any objects which need\n> > +\t\t\t * to be first rewritten as REF_DELTAs.\n> > +\t\t\t */\n> > +\t\t\treuse &= ~reuse_as_ref_delta_packfile_bitmap->words[wpos];\n> > +\t\t}\n> > +\n> > +\t\tif (reuse != (eword_t)~0)\n> > +\t\t\tbreak;\n> > +\n> > \t\tpos += BITS_IN_EWORD;\n> > -\n> > +\t}\n>\n> This is accessing reuse_as_ref_delta_packfile_bitmap->words directly\n> using pos/end as limits. But those come from reuse_packfile_bitmap. Are\n> we guaranteed to have zero-extended the reuse_as_ref_delta bitmap as far\n> as the original went?\n\nYeah, we know this is OK because both are allocated with the same size\nin reuse_partial_packfile_from_bitmap(), where the relevant portion is:\n\n word_alloc = objects_nr / BITS_IN_EWORD;\n if (objects_nr % BITS_IN_EWORD)\n word_alloc++;\n\n reuse = bitmap_word_alloc(word_alloc);\n reuse_as_ref_delta = bitmap_word_alloc(word_alloc);\n\nall of the bitmap_set() operations on the former are bounded in\ntry_partial_reuse(), but adding a length check can be done here as an\nextra safety measure.\n\n> Could we just be calling bitmap_get() here, which would do the length\n> check for us? Though I guess we would miss out on some whole-word magic\n> it is doing. So maybe we need to just do that length check ourselves.\n\nYeah, we don't use bitmap_get() because we want to access the whole word\nat a time.\n\nThanks,\nTaylor\n"},{"id":"506565","messageId":"Zyk2LgKfwJ5vT3Eq@nand.local","threadId":"62300","inReplyTo":"20241011083545.GH18010@coredump.intra.peff.net","subject":"Re: [PATCH 10/11] pack-bitmap.c: record whether the result was filtered","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-04T21:01:34Z","receivedAt":"2024-11-04T21:01:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 11, 2024 at 04:35:45AM -0400, Jeff King wrote:\n> I wonder, though: should thin deltas just be turned off entirely when\n> filtering is in play?\n>\n> Likewise for --unpacked (though in practice I think it would never be\n> used with --thin, as it is about generating new on-disk packs).\n\nThey should; that's what this commit is setting us up to do in the next\none, which does not allocate the \"convert to REF_DELTAs\" bitmap when\nfiltering is in play.\n\nThanks,\nTaylor\n"},{"id":"507664","messageId":"Zz0aaPdHiFyoRkKg@nand.local","threadId":"62300","inReplyTo":"20241011083838.GI18010@coredump.intra.peff.net","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-19T23:08:24Z","receivedAt":"2024-11-19T23:08:27Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 11, 2024 at 04:38:38AM -0400, Jeff King wrote:\n> On Wed, Oct 09, 2024 at 04:30:52PM -0400, Taylor Blau wrote:\n>\n> > The first optimization (cross-pack deltas) should help clones and\n> > fetches, but the second optimization (thin deltas) will only help\n> > fetches, since the 'haves' bitmap will necessarily be empty for\n> > clones.\n> >\n> > Of course, REF_DELTAs have a less compact representation than\n> > OFS_DELTAs, so the resulting packs will trade off some CPU time for a\n> > slightly larger pack. But we're only talking about a handful of extra\n> > bytes, and network bandwidth is pretty cheap, so I think the\n> > optimization is worthwhile here too.\n>\n> It would be nice to see some numbers, even simulated ones from t/perf.\n> Of course we'd like to show off any reduced server CPU for generating a\n> fetch response. But I'd also like to see if the extra steps to find the\n> cross-pack bases have any measurable negative effect (so the ideal there\n> would be a big midx repo that doesn't have a lot of those bases, as it\n> would not be helped much by the optimization and would be hurt by the\n> time spent trying to apply it).\n\nI put together some loose numbers for this, and there is a definite\nmeasurable slowdown imposed by this series.\n\nThe setup is getting a fresh copy of the kernel, and then repacking it\nwith:\n\n $ git repack -da --cruft --write-midx --write-bitmap-index \\\n --max-pack-size 1G --max-cruft-size 1G\n\n, which on my machine produces the following pack structure:\n\n $ for idx in .git/objects/pack/*.idx\n do\n echo $(basename $idx) \\\n $(git show-index <$idx | wc -l)\n done | sort -rnk2\n pack-8dc61c00e623765c54cbd332f31795bad7edf142.idx 3385859\n pack-d84e88715cde55d4d1b09afb23254617a123e668.idx 2064396\n pack-cd408bebd5c02719df7621941d92415f4dbb313c.idx 1805431\n pack-b11c6ac57f5ecf338314ee59134b0d724d257494.idx 1036443\n pack-a42cc1b409940d7e38a4673bca1150d320392bf0.idx 819701\n pack-93d255a1000f438a77528907c480c06b277e225d.idx 755019\n pack-600621b90dc29c761ee168cc4237b2ff2956b0e8.idx 609754\n\nGenerating a full clone[^1] with multi-pack reuse enabled (based on the tip\nof tb/multi-pack-reuse-dupfix) gives me the following timings:\n\n 13.94s user 0.27s system 99% cpu 14.207 total\n 13.93s user 0.30s system 99% cpu 14.223 total\n 13.90s user 0.33s system 99% cpu 14.229 total\n\nAfter applying the series, I get:\n\n 14.94s user 0.33s system 99% cpu 15.279 total\n 14.92s user 0.32s system 99% cpu 15.244 total\n 14.87s user 0.40s system 99% cpu 15.280 total\n\nOr around a ~5% slowdown. I think what's really killing us is all of the\nback and forth in pack-bitmap.c::find_base_bitmap_pos(), where we have\nto:\n\n - Find the pack-relative position of the base object given its offset.\n - Convert that pack-relative position into a lexical position (still\n relative to the source pack).\n - Convert that lexical position into an object ID.\n - Call bsearch_midx() to see if we have a copy of that object, and\n record its MIDX-relative lexical position.\n - Convert the MIDX-relative lexical position into its pseudo-pack\n position.\n\nI think that the first four of those steps are unavoidable. But I think\nwe can do better on the last step if we compute a forward index from\nMIDX lexical position to pseudo-pack position.\n\nA cheap way to run that experiment is to just add a temporary field into\nthe MIDX to store that mapping, compute it at runtime, and then deduct\nthe time it took to compute that mapping (presumably you'd do it during\nMIDX creation, and store it in a chunk, etc.).\n\nHere's some code to do that:\n\n--- 8< ---\ndiff --git a/midx.c b/midx.c\nindex ca98bfd7c64..2bd892f899c 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -988,3 +988,18 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flag\n\n \treturn verify_midx_error;\n }\n+\n+void midx_populate_forward_index(struct multi_pack_index *m)\n+{\n+\tuint32_t i;\n+\n+\tALLOC_ARRAY(m->forward_idx, m->num_objects);\n+\n+\ttrace2_region_enter(\"midx\", \"populate_forward_index\", the_repository);\n+\n+\tfor (i = 0; i < m->num_objects; i++)\n+\t\tif (midx_to_pack_pos(m, i, m->forward_idx + i) < 0)\n+\t\t\tBUG(\"oops\");\n+\n+\ttrace2_region_leave(\"midx\", \"populate_forward_index\", the_repository);\n+}\ndiff --git a/midx.h b/midx.h\nindex 42d4f8d149e..1ef755fe45b 100644\n--- a/midx.h\n+++ b/midx.h\n@@ -65,6 +65,8 @@ struct multi_pack_index {\n \tconst unsigned char *chunk_revindex;\n \tsize_t chunk_revindex_len;\n\n+\tuint32_t *forward_idx;\n+\n \tstruct multi_pack_index *base_midx;\n \tuint32_t num_objects_in_base;\n \tuint32_t num_packs_in_base;\n@@ -74,6 +76,8 @@ struct multi_pack_index {\n \tchar object_dir[FLEX_ARRAY];\n };\n\n+void midx_populate_forward_index(struct multi_pack_index *m);\n+\n #define MIDX_PROGRESS (1 << 0)\n #define MIDX_WRITE_REV_INDEX (1 << 1)\n #define MIDX_WRITE_BITMAP (1 << 2)\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e8094453ca3..1eb72347c02 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -2092,9 +2092,13 @@ static int find_base_bitmap_pos(struct bitmap_index *bitmap_git,\n \t\tif (!bsearch_midx(&base_oid, bitmap_git->midx,\n \t\t\t\t &base_midx_pos))\n \t\t\treturn -1;\n+#if 0\n \t\tif (midx_to_pack_pos(bitmap_git->midx, base_midx_pos,\n \t\t\t\t base_bitmap_pos) < 0)\n \t\t\treturn -1;\n+#else\n+\t\t*base_bitmap_pos = bitmap_git->midx->forward_idx[base_midx_pos];\n+#endif\n \t} else {\n \t\t/*\n \t\t * We assume delta dependencies always point backwards.\n@@ -2316,6 +2320,7 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \tassert(result);\n\n \tload_reverse_index(r, bitmap_git);\n+\tmidx_populate_forward_index(bitmap_git->midx);\n\n \tif (!bitmap_is_midx(bitmap_git) || !bitmap_git->midx->chunk_bitmapped_packs)\n \t\tmulti_pack_reuse = 0;\n--- >8 ---\n\nThen when running the same command, we get results that are quite\nencouraging. The runtime jumps to 24.213 seconds, which is ~9.73 seconds\nslower than the average of the baseline measurements. But it takes\n~10.418 seconds on my machine to compute the forward index. So it's\nreally around 688ms *faster* than the baseline, despite doing a little\nmore work.\n\nThe fact that we can improve on the baseline rather than just meet it\nsuggests that implementing this forward index may have some benefit\noutside of just this series.\n\nThanks,\nTaylor\n\n[^1]: The setup here is:\n\n $ git for-each-ref --format='%(objectname)' refs/heads refs/tags >in\n $ git pack-objects --stdout --delta-base-offset --use-bitmap-index --revs /dev/null\n"},{"id":"507665","messageId":"Zz0gdHrwC4CTAtZn@nand.local","threadId":"62300","inReplyTo":"Zz0aaPdHiFyoRkKg@nand.local","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-11-19T23:34:12Z","receivedAt":"2024-11-19T23:34:15Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Nov 19, 2024 at 06:08:24PM -0500, Taylor Blau wrote:\n> Then when running the same command, we get results that are quite\n> encouraging. The runtime jumps to 24.213 seconds, which is ~9.73 seconds\n> slower than the average of the baseline measurements. But it takes\n> ~10.418 seconds on my machine to compute the forward index. So it's\n> really around 688ms *faster* than the baseline, despite doing a little\n> more work.\n\nSorry, there is a much quicker way to generate the forward index at\nruntime, which is the following:\n\n--- 8< ---\ndiff --git a/midx.c b/midx.c\nindex 67e0d64004..1023bfa51a 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -989,3 +989,17 @@ int verify_midx_file(struct repository *r, const char *object_dir, unsigned flag\n\n \treturn verify_midx_error;\n }\n+\n+void midx_populate_forward_index(struct multi_pack_index *m)\n+{\n+\tuint32_t i;\n+\n+\tALLOC_ARRAY(m->forward_idx, m->num_objects);\n+\n+\ttrace2_region_enter(\"midx\", \"populate_forward_index\", the_repository);\n+\n+\tfor (i = 0; i < m->num_objects; i++)\n+\t\tm->forward_idx[pack_pos_to_midx(m, i)] = i;\n+\n+\ttrace2_region_leave(\"midx\", \"populate_forward_index\", the_repository);\n+}\n--- >8 ---\n\nI don't know if this makes as much of a difference for regular\nmulti-pack reuse, since there we're only making calls to\nmidx_pair_to_pack_pos(), which already uses midx_pack_order_cmp(), so\nthere isn't any additional translation to do.\n\nThanks,\nTaylor\n"},{"id":"509289","messageId":"20241218125754.GC695807@coredump.intra.peff.net","threadId":"62300","inReplyTo":"Zz0gdHrwC4CTAtZn@nand.local","subject":"Re: [PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2024-12-18T12:57:54Z","receivedAt":"2024-12-18T12:57:56Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 19, 2024 at 06:34:12PM -0500, Taylor Blau wrote:\n\n> On Tue, Nov 19, 2024 at 06:08:24PM -0500, Taylor Blau wrote:\n> > Then when running the same command, we get results that are quite\n> > encouraging. The runtime jumps to 24.213 seconds, which is ~9.73 seconds\n> > slower than the average of the baseline measurements. But it takes\n> > ~10.418 seconds on my machine to compute the forward index. So it's\n> > really around 688ms *faster* than the baseline, despite doing a little\n> > more work.\n> \n> Sorry, there is a much quicker way to generate the forward index at\n> runtime, which is the following:\n> [...]\n\nNeat. I didn't see timings for this method, but I'd assume it's quite\nfast. So if it shaves off the same 688ms, I'd expect it to be an overall\nwin. The code itself looks reasonable to me.\n\nI think when you re-post this series it might make sense to add a t/perf\nscript to demonstrate these timings (not just what we're discussing\nhere, but also the overall speedup we're hoping to achieve).\n\n-Peff\n"}]}