Specialize BitArray set ops to improve performance #18
Comments
|
I think this could be done within the same method, no need to change the API for it: Or maybe the API could have a method that return |
This would allow others to use that Uint32List in unsafe ways (unless we wrap it in UnmodifiableListView or something like that, but this, again, introduces a level of indirection that might negatively impact performance). One use case that I have for What do you think about something like the following: // Alongside BitArray
abstract class BitArrayOps {
// XOR reference https://github.com/RoaringBitmap/CRoaring/blob/13407ae912cbe16d28f196966a1989b714b4996d/src/bitset.c#L346-L357 (not or)
// @pragma(...inline...) ... does inlining work if private members are being used ...?
void inplaceOr(BitArray subject, BitArray object) {
final left = subject._data;
final right = object._data;
final length = min(left.length, right.length);
for (var i = 0; i < length; i++) {
left[i] |= right[i];
}
}
// ... Others ...
} |
|
Couple of options so far:
It is important to recognize that the primary reason for this package is to be efficient, so maybe specialized methods would be preferable compared to API simplicity. However, it would be nice to see how much overhead e.g. the |
|
I agree with everything you said. I'll give it a go and let you know how it went. |
|
Here are some results:
if (set is BitArray) {
return BitArrayOps.inplaceOr(this, set);
} else {
final iter = set.asUint32Iterable().iterator;
for (var i = 0; i < _data.length && iter.moveNext(); i++) {
_data[i] |= iter.current;
}
}I draw the following conclusion: the |
|
Thank you for the benchmarks! I think it is reassuring that we can keep the current API surface, while also improve performance. What's your plan: would you have the time to prepare PRs (and also hopefully tests) for these? |
|
My goal right now is to see whether a Dart-native bit array can be competitive with other bit arrays. I've tried binding CRoaring to Dart https://github.com/modulovalue/roaring_dart, but neither its compressed bitmaps nor its plain old bitset were able to outperform your bit array, which I'm attributing to FFI overhead. It doesn't look like the existing tests will be able to cover the changes that this would introduce. I agree, it would be good to have some additional ones. Specializing static void inplaceAnd(BitArray a, BitArray b) {
final aData = a._data;
final bData = b._data;
final min = math.min(aData.length, bData.length);
var i = 0;
for (; i < min; i++) {
aData[i] &= bData[i];
}
for (; i < aData.length; i++) {
aData[i] = 0;
}
} |
There are quite a few issues that I've opened. I think I'll try to submit a PR with some tests once you've had the time to look through them and give a LGTM. (and Happy Holidays!) |
|
I think you are doing a great investigation and preparation work here, I'll be happy to integrate it into the package. I'll have a bit hectic holiday schedule, but I'll set out time to review PRs if/when you happen to submit them. |
Hey @isoos,
I think there's a simple way to improve the performance of all the set operations of
BitArrayon otherBitArrays by specializing them to take aBitArrayand using that knowledge to avoid using iterators.That is, I've observed that we can be more efficient if we replace the following:
with
I'm not proposing to replace the existing set operations, but to add new ones that work on
BitArrays only.What do you think?
The text was updated successfully, but these errors were encountered: