Roaring BITSET!s

[hostilefork]

@BlackATTR

You're the best person to understand what it takes to pull this off.

So I have this hanging around on a branch, which I've rebased to bring up to date. It's more or less working.

@hostilefork

The C code has low-enough dependencies and enough people invested in it that it seems far wiser to find ways to improve and adapt it--and get those changes taken back--than to try and develop an independent codebase for these features.

So I think we should scrap any concept of implementing things like union or XOR on negated bitsets as some parallel evolution.

Earlier in the year, I contributed a significant number of changes to the library, and it's amenable to our use.

There is absolutely no reason to try and write this feature as an independent project. We'd use the same approach, and just have to reinvent the algorithms. It has been hardened by a lot of tests and deployment--so even though some of the code is a little scrappy and hard to follow, it delivers the goods.

@hostilefork

C99 is used in basic ways, like putting variable declarations inside for loops for (int x = 0; x < 10; ++x) {...}, and they also use tagged structs. It's nothing that would be hard to hack out if building on C89 was a priority, but being able to build on C89 is not the kind of thing they would care about (the way something like zlib cares about it)...so that would have to be done as a fork.

Among my patches was building as C++, which is provably useful for statically analysis. That meant I got rid of the tagged struct dependency.

We are no longer worrying about building the core as C89, and accept C99. (The API still can be used by C89 programs.) This may mean we move to using declarations inside for loops as well. It's another one of those "not hard to preprocess out" things:

for (int x = 0; x < 10; ++x) { ... }
=>
{  ; to be generic need to put in a scope, to not conflict with other loops
    int x = 0;
    for (; x < 10; ++x) { ... }
}

They Have A Single-File Form

I'd missed that they had a single-header and single-c file form of the project. Partially because it's called the "Unity Build" and Unity means something else in my programming world.

GitHub - lemire/CRoaringUnityBuild: Dumps of CRoaring unity builds (for convenience)

That really pushes the "we wouldn't do better than this" over the top.

So... I Think We Should Push This Through

@BlackATTR

My only thoughts are about priorities and when it might be the best time to dig into this (as opposed to finishing stackless, etc.).

Well, what's done is done...and this is close to done.

It will make the executable larger, but, like I've mentioned... it doesn't take much to make a gigantic bitset when the implementation is a binary. The size of the code will pale in comparison to a bitset with a high bit set.

I'm going to push it through and merge the branch.