search

isoos / bit_array

Bit array implementation in Dart
https://pub.dev/packages/bit_array
BSD 3-Clause "New" or "Revised" License
11 stars 5 forks source link

Render masks to constant lists. #23

Open modulovalue opened 10 months ago

modulovalue commented 10 months ago

Consider the _bitMask and _clearMask masks:

final _bitMask = List<int>.generate(32, (i) => 1 << i);
final _clearMask = List<int>.generate(32, (i) => ~(1 << i));

We can bake them into constant lists:

// print("const _bitMask = [${List<int>.generate(32, (i) => 1 << i).join(", ")}];");
const _bitMask = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648];

// print("const _clearMask = [${List<int>.generate(32, (i) => ~(1 << i)).join(", ")}];");
const _clearMask = [4294967294, 4294967293, 4294967291, 4294967287, 4294967279, 4294967263, 4294967231, 4294967167, 4294967039, 4294966783, 4294966271, 4294965247, 4294963199, 4294959103, 4294950911, 4294934527, 4294901759, 4294836223, 4294705151, 4294443007, 4293918719, 4292870143, 4290772991, 4286578687, 4278190079, 4261412863, 4227858431, 4160749567, 4026531839, 3758096383, 3221225471, 2147483647];

This appears to be a clear improvement (especially when it comes to AOT):

JIT
without baking: 8.3s~
with baking: 8s~
AOT
without baking: 9.4s~
with baking: 8.1s~

I din't bother with _cardinalityBitCounts because of #20.

@isoos what do you think?

isoos commented 10 months ago

I'm not sure how the change explains 300+ ms of runtime, but yeah, of course, we shall change it.

modulovalue commented 10 months ago

I'm not sure how the change explains 300+ ms of runtime

One of the masks is used by setBit and I suppose there's some inefficiency that adds up.

Note: CRoaring doesn't use tables for its setBit operation, but bit ops directly. That might be faster, I'm not sure, but with baked lists it's fast enough for my use case so I've not investigated that further.