On 9/19/2022 1:47 PM, Abhradeep Chakraborty via GitGitGadget wrote: > 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. I look forward to your next version. I hope to see some information about the performance characteristics across the two versions. Specifically: 1. How do various test in t/perf/ change between the two formats? 2. For certain test repos (git/git, torvalds/linux, etc.) how much does the .bitmap file change in size across the formats? > Makefile | 3 + > bitmap.c | 225 + > bitmap.h | 33 + ... > ewah/bitmap.c | 61 +- > ewah/ewok.h | 37 +- ... > roaring/roaring.c | 20047 +++++++++++++++++++++++++++++++++++ > roaring/roaring.h | 1028 ++ I wonder if there is value in modifying the structure of these files into a bitmap/ directory and then perhaps ewah/ and roaring/ within each? Just a thought. Thanks, -Stolee
