[0/6,GSoC] bitmap: integrate a lookup table extension to the bitmap format

Message

Derrick Stolee via GitGitGadget June 20, 2022, 12:33 p.m. UTC

When parsing the .bitmap file, git loads all the bitmaps one by one even if
some of the bitmaps are not necessary. We can remove this overhead by
loading only the necessary bitmaps. A look up table extension can solve this
issue.

The proposed table has:

 * a list of nr_entries object ids. These objects are commits that has
   bitmaps. Ids are stored in lexicographic order (for better searching).
 * a list of <offset, xor-offset> pairs (4-byte integers, network-byte
   order). The i'th pair denotes the offset and xor-offset(respectively) of
   the bitmap of i'th commit in the previous list. These two informations
   are necessary because only in this way bitmaps can be found without
   parsing all the bitmap.
 * a 4-byte integer for table specific flags (none exists currently).

Whenever git want to parse the bitmap for a specific commit, it will first
refer to the table and will look for the offset and xor-offset for that
commit. Git will then try to parse the bitmap located at the offset
position. The xor-offset can be used to find the xor-bitmap for the
bitmap(if any). This process is recursive and will end if xor-offset is null
(i.e. there is no xor-bitmap left).

Abhradeep Chakraborty (5):
  Documentation/technical: describe bitmap lookup table extension
  pack-bitmap: prepare to read lookup table extension
  pack-bitmap-write.c: write lookup table extension
  bitmap-commit-table: add tests for the bitmap lookup table
  bitmap-lookup-table: add performance tests

Taylor Blau (1):
  builtin/pack-objects.c: learn pack.writeBitmapLookupTable

 Documentation/config/pack.txt             |   7 +
 Documentation/technical/bitmap-format.txt |  31 ++++
 builtin/pack-objects.c                    |   8 +
 pack-bitmap-write.c                       |  59 +++++++-
 pack-bitmap.c                             | 172 +++++++++++++++++++++-
 pack-bitmap.h                             |   1 +
 t/perf/p5310-pack-bitmaps.sh              |  60 +++++---
 t/perf/p5326-multi-pack-bitmaps.sh        |  55 ++++---
 t/t5310-pack-bitmaps.sh                   |  14 ++
 t/t5326-multi-pack-bitmaps.sh             |  19 +++
 10 files changed, 375 insertions(+), 51 deletions(-)


base-commit: 5699ec1b0aec51b9e9ba5a2785f65970c5a95d84
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1266%2FAbhra303%2Fbitmap-commit-table-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1266/Abhra303/bitmap-commit-table-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1266