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