[PATCH 00/11] pack-bitmap: convert offset to ref deltas where possible

This patch series enables more objects to be candidates for verbatim reuse when generating a pack with the aide of reachability bitmaps.

By the end of this series, two new classes of objects are now reuse candidates which were not before. They are:

  - Cross-pack deltas. In multi-pack bitmaps, if the delta and base
    were selected from different packs, the delta was not reusable.

  - Thin deltas. In both single- and multi-pack bitmaps, we did not
    consider reusing deltas whose base object appears in the 'haves'
    bitmap.

This series teaches the pack-objects machinery to convert cross-pack and thin deltas to reference deltas so that they may be reused.

The series started off as a couple of patches, each addressing one of the two classes from the above. But as I started refining these patches, the series grew longer, as there were a handful of opportunities to clean up some of the existing pack-reuse bitmap code.

The series is organized as follows:

  - The first seven patches are various cleanups that make the
    pack-reuse code more readable and prepare us to enable delta reuse
    in more situation as above.

      pack-bitmap.c: do not pass `pack_pos` to `try_partial_reuse()`
      pack-bitmap.c: avoid unnecessary `offset_to_pack_pos()`
      pack-bitmap.c: delay calling 'offset_to_pack_pos()'
      pack-bitmap.c: compare `base_offset` to `delta_obj_offset`
      pack-bitmap.c: extract `find_base_bitmap_pos()`
      pack-bitmap: drop `from_midx` field from `bitmapped_pack`
      write_reused_pack_one(): translate bit positions directly

  - The next patch is a test fixup:

      t5332: enable OFS_DELTAs via test_pack_objects_reused

  - The next patch after that enables us to reuse deltas whose base
    appears in another pack:

      pack-bitmap: enable cross-pack delta reuse

  - The final two patches enable the "thin deltas" optimization
    above:

      pack-bitmap.c: record whether the result was filtered
      pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap

I think that the first seven patches are worthwhile on their own. I considered splitting those out into their own series, but decided against it to so that we could realize their benefit more readily.

The first optimization (cross-pack deltas) should help clones and fetches, but the second optimization (thin deltas) will only help fetches, since the 'haves' bitmap will necessarily be empty for clones.

Of course, REF_DELTAs have a less compact representation than OFS_DELTAs, so the resulting packs will trade off some CPU time for a slightly larger pack. But we're only talking about a handful of extra bytes, and network bandwidth is pretty cheap, so I think the optimization is worthwhile here too.

Thanks in advance for your review!

Taylor Blau (11):
  pack-bitmap.c: do not pass `pack_pos` to `try_partial_reuse()`
  pack-bitmap.c: avoid unnecessary `offset_to_pack_pos()`
  pack-bitmap.c: delay calling 'offset_to_pack_pos()'
  pack-bitmap.c: compare `base_offset` to `delta_obj_offset`
  pack-bitmap.c: extract `find_base_bitmap_pos()`
  pack-bitmap: drop `from_midx` field from `bitmapped_pack`
  write_reused_pack_one(): translate bit positions directly
  t5332: enable OFS_DELTAs via test_pack_objects_reused
  pack-bitmap: enable cross-pack delta reuse
  pack-bitmap.c: record whether the result was filtered
  pack-bitmap: enable reusing deltas with base objects in 'haves' bitmap

 builtin/pack-objects.c      | 110 ++++++++++++--------
 midx.c                      |   1 -
 pack-bitmap.c               | 198 ++++++++++++++++++++++++------------
 pack-bitmap.h               |   6 +-
 t/t5332-multi-pack-reuse.sh |  72 ++++++++++++-
 5 files changed, 275 insertions(+), 112 deletions(-)

base-commit: 777489f9e09c8d0dd6b12f9d90de6376330577a2