Re: What is the status of GSoC 2022 work on making Git use roaring bitmaps?

["Jakub Narębski" <jnareb@gmail.com>]

Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com> writes:

Hello Abhradeep,

Thank you for your response.

> On Fri, Mar 24, 2023 at 3:32 AM Jakub Narębski <jnareb@gmail.com> wrote:
>> Taylor Blau <me@ttaylorr.com> writes:
>>> On Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:
>>>>
>>>> Could you tell me what is the status of the Abhradeep Chakraborty work
>>>> in integrating roaring bitmaps (using CRoaring) in addition to, or
>>>> replacing current EWAH bitmaps (using ewok)? The last communication
>>>> about this shows that the patches were on the road to being merged in,
>>>> see e.g. https://medium.com/@abhra303/gsoc-final-report-feaaacfae737 ,
>>>> but there is no mention of 'roaring' in Git's code or documentation.
>>>
>>> Abhradeep started working on a prototype to teach Git how to read and
>>> write Roaring+Run bitmaps in this series:
>>>
>>>   https://lore.kernel.org/git/pull.1357.git.1663609659.gitgitgadget@gmail.com/
>>>
>>> Some folks gave it a review, but there wasn't any serious traction and I
>>> don't think that Abhradeep has had a chance to come back to the series.
>>>
>>> For what it's worth, I would love if Abhradeep (or anybody else
>>> interested in working on this area) picked it back up, either using that
>>> series as a starting point or going from scratch.
>>
>> When I searched the mailing list archives, the thread was never continued.
>
> Hello community,
>
> I have to apologize for the fact that I didn't continue the patch
> series. I wasn't involved in the community either. I am currently too
> busy to enhance my skills to get into a company of "my dream
> engineering environment". The problem is that it needs much effort and
> time to achieve that.
>
> I have always had a love for the Git project and the community. But
> unfortunately I can't contribute to it right now and I don't think I
> can contribute to it prior to my course ends (i.e. June, 2023). I
> would be happy if anybody else pick the issue and continue the work
> where I left off. I am even ready to guide/mentor/help.

Life happens; we can certainly understand the lack of time for work on,
especially as a student.

> There are certain things in my mind (other than roaring bitmaps) that
> I previously shared with Kaartik and Taylor. I will continue to be a
> part of this community and will make contributions after my college
> ends.

Thank you in advance for your offer.

[...]
>>> Abhradeep promised[1] that he'd include some performance work in his
>>> next version of that series. I think the main things we'd be interested
>>> in are:
>>>
>>>   - Does using Roaring provide a file-size advantage over
>>>     EWAH-compressed bitmaps?
>>>   - Does Roaring make it faster to inflate bitmaps? To deflate them?
>>
>> As far as I understand it, after reading articles about EWAH[2] and
>> about Roaring Bitmaps[3][4], the Roaring have the advantage that you
>> don't need to decompress (inflate) bitmaps to perform bitwise operations
>> on them.
>>
>> Run-Length-Encoding (RLE) formats like EWAH can be made to perform
>> operations without decompressing, but only if operations are symmetric.
>> The AND and OR operations are symmetrical, but AND NOT is not.  The last
>> is used by Git to find "want"-ed that are not present (not "have") is
>> not.  That is why Git needs to decompress bitmap and perform
>> operation.

At least that is why I think for any operations Git does decompress the
bitmap into an ordinary bitset / plain bitmap for operations.

>> If I understand it correctly, for both cases (EWAH and Roaring) you can
>> do membership check without decompressing bitmap.
>>
>>
>> [2] Daniel Lemire et al. "Sorting improves word-aligned bitmap indexes",
>>     arXiv:0901.3751
>>
>> [3] Samy Chambi, Daniel Lemire et al. "Optimizing Druid with Roaring
>>     bitmaps", https://dl.acm.org/doi/10.1145/2938503.2938515
>> [4] Daniel Lemire et al. "Roaring Bitmaps: Implementation of an
>>     Optimized Software Library", arXiv:1709.07821v3

The last work includes some benchmark.  I understand that those
benchmarks do not necessary match the particulars of Git's use of
compressed bitmaps, but they are there.

>>> Deflating bitmaps doesn't matter as much, IMHO, since that is a cost
>>> that we pay only when we first have to compress bitmaps before writing
>>> them. But if we could significantly reduce the inflation cost, that
>>> would be an advantage to using Roaring+Run bitmaps over EWAH ones since
>>> they would be faster to decompress at read-time.
>>
>> Well, if Roaring were to be significantly slower when deflating, but
>> only slightly faster when using / inflating, that would affect their
>> evaluation.
>
> IMHO, I don't think Roaring bitmaps would make any significant performance
> improvements. It may be faster to decompress, but I believe it takes more
> in memory computation than the EWAH. My biggest concern is its dynamic
> nature. It can dynamically change its underlying data structure into an array,
> bitmap or RLE. I didn't test the performance though and I shouldn't draw any
> conclusions about it.

Benchmarks results in section 5. "Experiments", in the D. Lemire et al.
paper "Roaring Bitmaps: Implementation of an Optimized Software Library"
does not include detailed information about memory usage during
operations (beside mentioning that BitMagic solution, which is one
solution they compare Roaring Bitmaps against, has exorbitant memory
usage).

However, there are some relevant results that can be found in this
paper, namely:

- Roaring had consitently smaller memory usage in bits per value than
  EWAH, though the difference is not large (e.g. 2.60 vs 3.29, or 0.60
  vs 0.64 for different examples of Roaring vs EWAH)
- time needed to iterate through all values was also smaller, for
  example 5.87 Roaring vs 13.1 EWAH
- EWAH, WAH, and Concise has terrible random-access membership check
  performance; uncompressed is fastest, but Roaring is only 20x slower
  than uncompressed (e.g. 3.74 for bitset[5] vs 63.6 for Roaring,
  vs 3260 for EWAH)
- for computing two-by-two intersections (AND), unions (OR), differences
  (AND NOT), and symmetric differences (XOR) Roaring is fastest or
  second-fastest after uncompressed bitset; EWAH is always slower
- for compting wide union of 200 sets, Roaring is generally faster (in
  several instances several time faster than alternative), except for
  two cases where is about 20% or 10% slower than best (but not than
  EWAH).

[5]: https://github.com/lemire/cbitset


> I am extremely sorry for the inconvenience and I hope you'll understand the
> situation.

Thank you for all your work on reachability bitmaps.

Best,
--
Jakub Narębski