Git currently uses ewah bitmaps ( which are based on run-length encoding) to
compress bitmaps. Ewah bitmaps stores bitmaps in the form of run-length
words i.e. instead of storing each and every bit, it tries to find
consecutive bits (having same value) and replace them with the value bit and
the range upto which the bit is present. It is simple and efficient. But one
downside of this approach is that we have to decompress the whole bitmap in
order to find the bit of a certain position.

For small (or medium sized) bitmaps, this is not an issue. But it can be an
issue for large (or extra large) bitmaps. In that case roaring bitmaps are
generally more efficient[1] than ewah itself. Some benchmarks suggests that
roaring bitmaps give more performance benefits than ewah or any other
similar compression technique.

This patch series is currently in RFC state and it aims to let Git use
roaring bitmaps. As this is an RFC patch series (for now), the code are not
fully accurate (i.e. some tests are failing). But it is backward-compatible
(tests related to ewah bitmaps are passing). Some commit messages might need
more explanation and some commits may need a split (specially the one that
implement writing roaring bitmaps). Overall, the structure and code are near
to ready to make the series a formal patch series.

I am submitting it as an RFC (after discussions with mentors) because the
GSoC coding period is about to end. I will continue to work on the patch
series.

Abhradeep Chakraborty (5):
  reachability-bitmaps: add CRoaring library to Git
  roaring.[ch]: apply Git specific changes to the roaring API
  roaring: teach Git to write roaring bitmaps
  roaring: introduce a new config option for roaring bitmaps
  roaring: teach Git to read roaring bitmaps

 Makefile                   |     3 +
 bitmap.c                   |   225 +
 bitmap.h                   |    33 +
 builtin/diff.c             |    10 +-
 builtin/multi-pack-index.c |     5 +
 builtin/pack-objects.c     |    81 +-
 ewah/bitmap.c              |    61 +-
 ewah/ewok.h                |    37 +-
 midx.c                     |     7 +
 midx.h                     |     1 +
 pack-bitmap-write.c        |   326 +-
 pack-bitmap.c              |   969 +-
 pack-bitmap.h              |    27 +-
 roaring/roaring.c          | 20047 +++++++++++++++++++++++++++++++++++
 roaring/roaring.h          |  1028 ++
 t/t5310-pack-bitmaps.sh    |    79 +-
 16 files changed, 22490 insertions(+), 449 deletions(-)
 create mode 100644 bitmap.c
 create mode 100644 bitmap.h
 create mode 100644 roaring/roaring.c
 create mode 100644 roaring/roaring.h

base-commit: d3fa443f97e3a8d75b51341e2d5bac380b7422df

Submitted-As: https://lore.kernel.org/git/pull.1357.git.1663609659.gitgitgadget@gmail.com