RFC introduce Roaring bitmaps to Git

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
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1357%2FAbhra303%2Froaring-bitmap-exp-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1357/Abhra303/roaring-bitmap-exp-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1357

gitgitgadget