Skip to content

Render masks to constant lists. #23

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
modulovalue opened this issue Dec 23, 2023 · 2 comments
Open

Render masks to constant lists. #23

modulovalue opened this issue Dec 23, 2023 · 2 comments

Comments

@modulovalue
Copy link

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
Copy link
Owner

isoos commented Dec 23, 2023

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

@modulovalue
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants