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

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

[Jakub Narębski]

Hello,

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.

Moreover, there is no proposal to finish this on the GSoC 2023 ideas
page: https://git.github.io/SoC-2023-Ideas/ .  Is it because it would be
too small of a project?  Or maybe it turned out that roaring bitmaps
were not a good idea - though I haven't found mentions of any benchmarks
of roaring vs EWAH in the mailing list archives?  Or perhaps there is no
one to mentor this proposal?

Regards,
--
Jakub Narębski

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

[Taylor Blau]

Hi Jakub,

On Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:
> Hello,
>
> 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.

> Moreover, there is no proposal to finish this on the GSoC 2023 ideas
> page: https://git.github.io/SoC-2023-Ideas/ .  Is it because it would be
> too small of a project?  Or maybe it turned out that roaring bitmaps
> were not a good idea - though I haven't found mentions of any benchmarks
> of roaring vs EWAH in the mailing list archives?  Or perhaps there is no
> one to mentor this proposal?

I don't have the capacity to mentor a student this cycle, and I am
probably the most interested among potential mentors in seeing this
project through ;-).

I don't think that it's too small (in fact, it was probably an error on
my part to include this as a potential stretch goal in Abhradeep's
project). We don't have any evidence that it's a good or bad idea.

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?

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.

Thanks,
Taylor

[1]: https://lore.kernel.org/git/CAPOJW5wkXrV8eOysz6aJ5jN2u_u-iTX_3om3tSDKw+EmfCJBEw@mail.gmail.com/

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

[Jakub Narębski]

Hello Taylor,

Thanks for a fast response.

Taylor Blau <me@ttaylorr.com> writes:
> On Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:
>> Hello,
>>
>> 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.

>> Moreover, there is no proposal to finish this on the GSoC 2023 ideas
>> page: https://git.github.io/SoC-2023-Ideas/ .  Is it because it would be
>> too small of a project?  Or maybe it turned out that roaring bitmaps
>> were not a good idea - though I haven't found mentions of any benchmarks
>> of roaring vs EWAH in the mailing list archives?  Or perhaps there is no
>> one to mentor this proposal?
>
> I don't have the capacity to mentor a student this cycle, and I am
> probably the most interested among potential mentors in seeing this
> project through ;-).

Ah, so it is mostly the last issue - lack of a potential mentor for
conntinuing this project.

> I don't think that it's too small (in fact, it was probably an error on
> my part to include this as a potential stretch goal in Abhradeep's
> project). We don't have any evidence that it's a good or bad idea.
>
> 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.

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

>
> 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.

>
> [1]: https://lore.kernel.org/git/CAPOJW5wkXrV8eOysz6aJ5jN2u_u-iTX_3om3tSDKw+EmfCJBEw@mail.gmail.com/

Regards,
--
Jakub Narębski

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

[Abhradeep Chakraborty]

On Fri, Mar 24, 2023 at 3:32 AM Jakub Narębski <jnareb@gmail.com> wrote:
>
> Hello Taylor,
>
> Thanks for a fast response.
>
> Taylor Blau <me@ttaylorr.com> writes:
> > On Thu, Mar 23, 2023 at 08:26:11PM +0100, Jakub Narębski wrote:
> >> Hello,
> >>
> >> 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.

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.

> >> Moreover, there is no proposal to finish this on the GSoC 2023 ideas
> >> page: https://git.github.io/SoC-2023-Ideas/ .  Is it because it would be
> >> too small of a project?  Or maybe it turned out that roaring bitmaps
> >> were not a good idea - though I haven't found mentions of any benchmarks
> >> of roaring vs EWAH in the mailing list archives?  Or perhaps there is no
> >> one to mentor this proposal?
> >
> > I don't have the capacity to mentor a student this cycle, and I am
> > probably the most interested among potential mentors in seeing this
> > project through ;-).
>
> Ah, so it is mostly the last issue - lack of a potential mentor for
> conntinuing this project.
>
> > I don't think that it's too small (in fact, it was probably an error on
> > my part to include this as a potential stretch goal in Abhradeep's
> > project). We don't have any evidence that it's a good or bad idea.

Yeah, It is big enough to take an extra 3 months of code and discussions.

> > 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.
>
> 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
>
> >
> > 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.

> >
> > [1]: https://lore.kernel.org/git/CAPOJW5wkXrV8eOysz6aJ5jN2u_u-iTX_3om3tSDKw+EmfCJBEw@mail.gmail.com/
>
> Regards,
> --
> Jakub Narębski

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

Thanks :)

Regards,
Abhradeep Chakraborty

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

[Jakub Narębski]

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

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

[Han-Wen Nienhuys]

On Sat, Mar 25, 2023 at 6:40 PM Jakub Narębski <jnareb@gmail.com> wrote:
> >>> 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?

I modified JGit to write Roaring bitmaps instead of EWAH bitmaps. The
resulting difference in file sizes are small, and actually favor EWAH:

$ ls -l {ewah-repos,roaring-repos}/*.git/objects/pack/*.bitmap
-r--r----- 1 hanwen primarygroup 26257386 Jul 31 15:04
ewah-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap
-r--r----- 1 hanwen primarygroup 27621579 Jul 31 15:20
roaring-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap

-r--r----- 1 hanwen primarygroup  1037356 Jul 31 14:46
ewah-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap
-r--r----- 1 hanwen primarygroup  1242608 Jul 31 14:45
roaring-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap

-- 
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--
Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Paul Manicle, Liana Sebastian

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

[Taylor Blau]

On Mon, Jul 31, 2023 at 07:46:18PM +0200, Han-Wen Nienhuys wrote:
> On Sat, Mar 25, 2023 at 6:40 PM Jakub Narębski <jnareb@gmail.com> wrote:
> > >>> 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?
>
> I modified JGit to write Roaring bitmaps instead of EWAH bitmaps. The
> resulting difference in file sizes are small, and actually favor EWAH:
>
> $ ls -l {ewah-repos,roaring-repos}/*.git/objects/pack/*.bitmap
> -r--r----- 1 hanwen primarygroup 26257386 Jul 31 15:04
> ewah-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap
> -r--r----- 1 hanwen primarygroup 27621579 Jul 31 15:20
> roaring-repos/android-pfb.git/objects/pack/pack-b14c35ec7fc3bb20884abe51a81c832be5983fdc.bitmap
>
> -r--r----- 1 hanwen primarygroup  1037356 Jul 31 14:46
> ewah-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap
> -r--r----- 1 hanwen primarygroup  1242608 Jul 31 14:45
> roaring-repos/gerrit.git/objects/pack/pack-fe46c7f96a2910f5775a2ff3bef7e4fa0e779f91.bitmap

This was one of my hopes with Roaring+Run, too, but I think that it's a
non-starter with our current object ordering for reachability bitmaps.

I did the same experiment a few months ago in my fork of git.git, and
consistently was able to produce smaller bitmaps when EWAH compressed as
compared to Roaring+Run. I think the reason is that our bitmaps are
pretty sparse, and so often have a lot of 0's, interspersed with a few
1's.

Depending on container alignment, a single 1's bit surrounded by zeros
will often get encoded as a length 0 "run" container. This means that
instead of storing that information in a single bit like we would with
EWAH, we use two 16-bit unsigned values to store (a) the position[^1],
and (b) length of the run.

The length is entirely wasted space, since the bytes are zeros, and
storing the position is significantly less efficient than storing a
sparse bit position in EWAH.

I haven't proved conclusively one way or the other where Roaring+Run is
significantly faster than EWAH or vice-versa. There are some cases where
the former is a clear winner, and other cases where it's the latter.

In any event, my extremely WIP patches to make this mostly work are
available here:

  https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps

One thing that I was able to do to produce slightly smaller Roaring+Run
encoded .bitmap files is to store some of the bitmaps as XORs against
earlier bitmaps, similar to what we do with EWAH. Often XORing the raw
bits, and then compressing that with Roaring+Run can be significantly
smaller than storing another full Roaring+Run bitset.

That's the only part that I've had trouble getting to make it
consistently work, and I haven't had time to get back to it, so it's
been collecting dust since the end of May.

Thanks,
Taylor

[^1]: Not the bit position, exactly, but rather the 16 least-significant
  bits of the bit position, since all values in the same container share
  the 16 most-significant bits being a multiple of 2^16.

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

[Han-Wen Nienhuys]

On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau <me@ttaylorr.com> wrote:
> I haven't proved conclusively one way or the other where Roaring+Run is
> significantly faster than EWAH or vice-versa. There are some cases where
> the former is a clear winner, and other cases where it's the latter.
>
> In any event, my extremely WIP patches to make this mostly work are
> available here:
>
>   https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps
>

thanks. For anyone reading along, the changes to JGit are here

https://git.eclipse.org/r/c/jgit/jgit/+/203448

I was looking into this because I was hoping that roaring might
decrease peak memory usage.

I don't have firm evidence that it's better or worse, but I did
observe that runtime and memory usage during GC (which is heavy on
bitmap operations due to delta/xor encoding) was unchanged. That makes
me pessimistic that there are significant gains to be had.

> One thing that I was able to do to produce slightly smaller Roaring+Run

Just for my edification: what is "Roaring + Run" ?

--
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--
Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Paul Manicle, Liana Sebastian

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

[Jakub Narębski]

Hello,

On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys <hanwen@google.com> wrote:
> On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau <me@ttaylorr.com> wrote:
> >
> > I haven't proved conclusively one way or the other where Roaring+Run is
> > significantly faster than EWAH or vice-versa. There are some cases where
> > the former is a clear winner, and other cases where it's the latter.
> >
> > In any event, my extremely WIP patches to make this mostly work are
> > available here:
> >
> >   https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps
> >
>
> thanks. For anyone reading along, the changes to JGit are here
>
> https://git.eclipse.org/r/c/jgit/jgit/+/203448
>
> I was looking into this because I was hoping that roaring might
> decrease peak memory usage.
>
> I don't have firm evidence that it's better or worse, but I did
> observe that runtime and memory usage during GC (which is heavy on
> bitmap operations due to delta/xor encoding) was unchanged. That makes
> me pessimistic that there are significant gains to be had.

The major advantage Roaring bitmaps have over EWAH and other
simple Run Length Encoding based compression algorithms is that
bitmap operations can be done on compressed bitmaps: there is no
need to uncompress bitmap to do (want1 OR want2 AND NOT have).

If I remember correctly, Git (the C implementation) basically un-compresses
bitmaps to make use of them when using them during fetch.

Some operations can be done on EWAH without decompression, but
non-symmetric full-bitmap operation line AND NOT is not one of them.

Best,
-- 
Jakub Narębski

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

[Han-Wen Nienhuys]

On Tue, Aug 1, 2023 at 1:35 PM Jakub Narębski <jnareb@gmail.com> wrote:
>
> Hello,
>
> On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys <hanwen@google.com> wrote:
> > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau <me@ttaylorr.com> wrote:
> > >
> > > I haven't proved conclusively one way or the other where Roaring+Run is
> > > significantly faster than EWAH or vice-versa. There are some cases where
> > > the former is a clear winner, and other cases where it's the latter.
> > >
> > > In any event, my extremely WIP patches to make this mostly work are
> > > available here:
> > >
> > >   https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps
> > >
> >
> > thanks. For anyone reading along, the changes to JGit are here
> >
> > https://git.eclipse.org/r/c/jgit/jgit/+/203448
> >
> > I was looking into this because I was hoping that roaring might
> > decrease peak memory usage.
> >
> > I don't have firm evidence that it's better or worse, but I did
> > observe that runtime and memory usage during GC (which is heavy on
> > bitmap operations due to delta/xor encoding) was unchanged. That makes
> > me pessimistic that there are significant gains to be had.
>
> The major advantage Roaring bitmaps have over EWAH and other
> simple Run Length Encoding based compression algorithms is that
> bitmap operations can be done on compressed bitmaps: there is no
> need to uncompress bitmap to do (want1 OR want2 AND NOT have).

Are you sure? The source code for and and andNot look rather similar
in that they seem to do operations on whole RLE sections at a time,

https://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L498

https://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L405

Looking at the EWAH format as documented for git-bitmap-format, EWAH
allows for RLE on both 1s and 0s. It should be possible to efficiently
clear out a section of the target if the second operand of andNot has
RLE encoded run of 1s.

-- 
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Liana Sebastian

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

[Jakub Narębski]

Hello,

On Tue, 1 Aug 2023 at 13:54, Han-Wen Nienhuys <hanwen@google.com> wrote:
> On Tue, Aug 1, 2023 at 1:35 PM Jakub Narębski <jnareb@gmail.com> wrote:
> > On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys <hanwen@google.com> wrote:
> > > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau <me@ttaylorr.com> wrote:
> > > >
> > > > I haven't proved conclusively one way or the other where Roaring+Run is
> > > > significantly faster than EWAH or vice-versa. There are some cases where
> > > > the former is a clear winner, and other cases where it's the latter.
> > > >
> > > > In any event, my extremely WIP patches to make this mostly work are
> > > > available here:
> > > >
> > > >   https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps
> > > >
> > >
> > > thanks. For anyone reading along, the changes to JGit are here
> > >
> > > https://git.eclipse.org/r/c/jgit/jgit/+/203448
> > >
> > > I was looking into this because I was hoping that roaring might
> > > decrease peak memory usage.
> > >
> > > I don't have firm evidence that it's better or worse, but I did
> > > observe that runtime and memory usage during GC (which is heavy on
> > > bitmap operations due to delta/xor encoding) was unchanged. That makes
> > > me pessimistic that there are significant gains to be had.
> >
> > The major advantage Roaring bitmaps have over EWAH and other
> > simple Run Length Encoding based compression algorithms is that
> > bitmap operations can be done on compressed bitmaps: there is no
> > need to uncompress bitmap to do (want1 OR want2 AND NOT have).
>
> Are you sure? The source code for and and andNot look rather similar
> in that they seem to do operations on whole RLE sections at a time,
>
> https://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L498
>
> https://sourcegraph.com/github.com/lemire/javaewah/-/blob/src/main/java/com/googlecode/javaewah/EWAHCompressedBitmap.java?L405
>
> Looking at the EWAH format as documented for git-bitmap-format, EWAH
> allows for RLE on both 1s and 0s. It should be possible to efficiently
> clear out a section of the target if the second operand of andNot has
> RLE encoded run of 1s.

You are right, I seem to have misremembered the statement from the
EWAH paper.

Lemma 2 in "Sorting improves word-aligned bitmap indexes" (arXiv:0901.3751v7)
states that the bitmap operation of L bitmaps is computable in
O(L*compressed size),
and for updatable L-ary operation like symmetric boolean operation
the bitmap operation is computable in O(log(L)*compressed size).

Now I am not sure if I understand the code of Git correctly, but it seems like
in pack-bitmap.c the `add_commit_to_bitmap()` function stores the result
of OR operation on bitmaps as an uncompressed bitmap:
https://github.com/git/git/blob/master/pack-bitmap.c#L1030

Best,
-- 
Jakub Narębski

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

[Taylor Blau]

On Tue, Aug 01, 2023 at 01:26:19PM +0200, Han-Wen Nienhuys wrote:
> > One thing that I was able to do to produce slightly smaller Roaring+Run
>
> Just for my edification: what is "Roaring + Run" ?

Roaring+Run refers to a modified version of the Roaring bitset
compression scheme which has an additional container type to represent
runs of a single (set) bit.

The run container stores the lower 16-bits of bit position of the start
of the run, and then it uses another 16-bit value to store the length of
the run.

For more, this paper from David Lemire is a good start:

  https://arxiv.org/pdf/1402.6407.pdf

Thanks,
Taylor

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

[Taylor Blau]

On Tue, Aug 01, 2023 at 01:34:32PM +0200, Jakub Narębski wrote:
> Hello,
>
> On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys <hanwen@google.com> wrote:
> > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau <me@ttaylorr.com> wrote:
> > >
> > > I haven't proved conclusively one way or the other where Roaring+Run is
> > > significantly faster than EWAH or vice-versa. There are some cases where
> > > the former is a clear winner, and other cases where it's the latter.
> > >
> > > In any event, my extremely WIP patches to make this mostly work are
> > > available here:
> > >
> > >   https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps
> > >
> >
> > thanks. For anyone reading along, the changes to JGit are here
> >
> > https://git.eclipse.org/r/c/jgit/jgit/+/203448
> >
> > I was looking into this because I was hoping that roaring might
> > decrease peak memory usage.
> >
> > I don't have firm evidence that it's better or worse, but I did
> > observe that runtime and memory usage during GC (which is heavy on
> > bitmap operations due to delta/xor encoding) was unchanged. That makes
> > me pessimistic that there are significant gains to be had.
>
> The major advantage Roaring bitmaps have over EWAH and other
> simple Run Length Encoding based compression algorithms is that
> bitmap operations can be done on compressed bitmaps: there is no
> need to uncompress bitmap to do (want1 OR want2 AND NOT have).

Yeah, this is definitely where the majority of CPU savings seems to
remain. The existing implementation in my branch is much too eager to
uncompress bitmaps when we need to perform a logical/binary operation on
them.

I think with some more surgery we could leave bitmaps in a compressed
state for longer. I am not sure whether or not we should ever uncompress
the bitmaps, though it's possible that doing so is beneficial since
uncompressed bitmaps have better query performance (albeit more costly
memory usage).

Thanks,
Taylor

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

[Jakub Narębski]

Hello

On Tue, 1 Aug 2023 at 19:34, Taylor Blau <me@ttaylorr.com> wrote:
> On Tue, Aug 01, 2023 at 01:34:32PM +0200, Jakub Narębski wrote:
> > On Tue, 1 Aug 2023 at 13:26, Han-Wen Nienhuys <hanwen@google.com> wrote:
> > > On Mon, Jul 31, 2023 at 10:18 PM Taylor Blau <me@ttaylorr.com> wrote:
> > > >
> > > > I haven't proved conclusively one way or the other where Roaring+Run is
> > > > significantly faster than EWAH or vice-versa. There are some cases where
> > > > the former is a clear winner, and other cases where it's the latter.
> > > >
> > > > In any event, my extremely WIP patches to make this mostly work are
> > > > available here:
> > > >
> > > >   https://github.com/ttaylorr/git/compare/tb/roaring-bitmaps
> > > >
> > >
> > > thanks. For anyone reading along, the changes to JGit are here
> > >
> > > https://git.eclipse.org/r/c/jgit/jgit/+/203448
> > >
> > > I was looking into this because I was hoping that roaring might
> > > decrease peak memory usage.
> > >
> > > I don't have firm evidence that it's better or worse, but I did
> > > observe that runtime and memory usage during GC (which is heavy on
> > > bitmap operations due to delta/xor encoding) was unchanged. That makes
> > > me pessimistic that there are significant gains to be had.
> >
> > The major advantage Roaring bitmaps have over EWAH and other
> > simple Run Length Encoding based compression algorithms is that
> > bitmap operations can be done on compressed bitmaps: there is no
> > need to uncompress bitmap to do (want1 OR want2 AND NOT have).
>
> Yeah, this is definitely where the majority of CPU savings seems to
> remain. The existing implementation in my branch is much too eager to
> uncompress bitmaps when we need to perform a logical/binary operation on
> them.

As I understand it, the current code in Git (in C implementation) uses
uncompressed bitmap to store the result of OR-ing, but it uses compressed
EWAH to perform <uncompressed result> OR <EWAH-compressed bitmap>.

> I think with some more surgery we could leave bitmaps in a compressed
> state for longer. I am not sure whether or not we should ever uncompress
> the bitmaps, though it's possible that doing so is beneficial since
> uncompressed bitmaps have better query performance (albeit more costly
> memory usage).

I'm not sure if it would be worth the complexity, but supposedly you can
perform L bitwise OR operations in O(log(L)) instead of O(L). Current C code
computes OR operation sequentially, see above, and also
  https://github.com/git/git/blob/master/pack-bitmap.c#L103\0

There might be thousands of "wants" and of "haves", but is it common?

Best,
-- 
Jakub Narębski