| Message ID | pull.1357.git.1663609659.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | introduce Roaring bitmaps to Git | expand |
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
Hi Derrick, On Mon, Sep 19, 2022 at 11:48 PM Derrick Stolee <derrickstolee@github.com> wrote: > 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? Yeah, sure. I will be including the performance test result in the next version :) > > 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. Great idea! Thanks! Will change it in the next version.. Thanks :)
On Mon, Sep 19, 2022 at 05:47:34PM +0000, Abhradeep Chakraborty via GitGitGadget wrote: > 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. Extremely exciting. Congratulations on all of your work so far. I'm hopeful that you'll continue working on this after GSoC is over (for those playing along at home, Abhradeep's coding period was extended by a couple of weeks). But even if you don't, this is a great artifact to leave around on the list for somebody else who is interested in this area to pick up in the future, and benefit from all of the work that you've done so far. I am still working through my post-Git Merge backlog, but I'm looking forward to reading these patches soon. I'm glad that other reviewers have already started to dive in :-). Well done! Thanks, Taylor
On Wed, Sep 21, 2022 at 3:29 AM Taylor Blau <me@ttaylorr.com> wrote: > > On Mon, Sep 19, 2022 at 05:47:34PM +0000, Abhradeep Chakraborty via GitGitGadget wrote: > > 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. > > Extremely exciting. Congratulations on all of your work so far. I'm > hopeful that you'll continue working on this after GSoC is over (for > those playing along at home, Abhradeep's coding period was extended by a > couple of weeks). Yeah, I will continue (or better to say I am continuing) my work. I hope that I can submit the next version in the upcoming few days. Thanks for supporting and guiding me throughout the GSoC period. I have learned a lot of new things during this period. > I am still working through my post-Git Merge backlog, but I'm looking > forward to reading these patches soon. I'm glad that other reviewers > have already started to dive in :-). No problem, I am doing some improvements by this time. By the way, I am very excited to see the Youtube Git-Merge recordings ;) Thanks :)