Re: Can I use CRoaring library in Git?

From: Derrick Stolee <derrickstolee@github.com>
Date: Jul 17, 2022, 14:43 UTC
Message-ID: <62456232-26af-6883-1f89-53f16863d2d5@github.com>
In-Reply-To: <CAPOJW5x4McofC5fxBvsRAzum28wmeDJCMTMRmY_0oy=32JjKqQ@mail.gmail.com>

On 7/16/22 9:50 AM, Abhradeep Chakraborty wrote:

Show 11 quoted lines

> Hello,
> 
> I need the CRoaring[1] library to use roaring bitmaps. But it has
> Apache license v2 which is not compatible with GPLv2[2].
> 
> Is there a way to use the CRoaring library in Git? Taylor told me that
> contrib/persistent-https tree is also licensed under Apache License
> version 2.
> 
> [1] https://github.com/RoaringBitmap/CRoaring
> [2] https://www.apache.org/licenses/GPL-compatibility.html

I know that working around a license would be the the optimal way to get a battle-tested implementation. Its API should be close enough to the EWAH bitmap implementation that we can transition between the formats easily. Continue pursuing that for now.

However, we always have the option of implementing a version from scratch based on the description in the paper [3]. The benefit there is that we would only need to implement what we need from the format and logic, and we could even get some benefits from exposing some of the internals to the rest of Git's codebase.

[3] https://arxiv.org/pdf/1603.06549.pdf

I mention this because I made an independent C# implementation of Roaring+Run for the Azure Repos back-end. The way that the bitmaps are split into "chunks" of 65k positions was helpful with how the object order was set up: older objects were in early chunks and so deltas only needed the later chunks. When using a chunk, we could lazy-load and unload each chunk as we went through the object order.

So, if we really want to try this, an independent implementation might be the way to start, at least as a prototype while pursuing the licensing angle.

Thanks, -Stolee