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

From: Han-Wen Nienhuys <hanwen@google.com>
Date: Aug 1, 2023, 11:54 UTC
Message-ID: <CAFQ2z_MmUDMTc7wyR1X8oxXdtz54_0HZmS2Q8iv9YMoqZmh0hQ@mail.gmail.com>
In-Reply-To: <CANQwDwe8Po-2KxNjWQ+RW+hYGLF=4sYTjQJxcVSAOtbtpfVRhQ@mail.gmail.com>

On Tue, Aug 1, 2023 at 1:35 PM Jakub Narębski <jnareb@gmail.com> wrote:

Show 32 quoted lines

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