ZRoaring: flat roaring bitmaps

Showcase
21

That seems to be a good idea. I’ve done this along with adding automatic compaction when blocks are shrunk and now were around 90% of croaring’s speed on this benchmark :slight_smile:.

Of course that means 2 allocations instead of one and a slightly less happy deinit. But I can accept that.

zig build bench -Doptimize=ReleaseFast 
$ zig build bench -Doptimize=ReleaseFast
--------------------------------------------------
overall:
--------------------------------------------------
CRoaring: 11430 ops 20.698ms   0.55MB ops/sec
ZRoaring: 11430 ops 22.894ms   0.50MB ops/sec

                                  ratio -- 0.90 🥔

--------------------------------------------------
individual ops: speed=ops/sec
--------------------------------------------------
op                 cr speed zr speed #    ratio
--------------------------------------------------
clear              1.62MB   35.25MB  240  21.82 ⚡
run_optimize       0.61MB   0.60MB   365  0.99  👍🏻
shrink_to_fit      4.17MB   1.20MB   330  0.29  💩
portable_serialize 0.70MB   0.94MB   105  1.34  ⚡
frozen_serialize   2.31MB   2.28MB   85   0.99  👍🏻
minimum            32.69MB  34.56MB  580  1.06  👍🏻
maximum            14.55MB  7.65MB   585  0.53  💩
add                12.09MB  10.37MB  2200 0.86  🥔
rank               10.29MB  9.69MB   25   0.94  👍🏻
select             8.72MB   8.43MB   30   0.97  👍🏻
contains           22.46MB  22.67MB  580  1.01  👍🏻
add_many           2.52MB   2.86MB   915  1.13  ⚡
add_range_closed   2.37MB   2.29MB   1545 0.96  👍🏻
contains_range     16.02MB  17.40MB  570  1.09  ⚡
range_cardinality  6.67MB   5.15MB   5    0.77  🥔
remove             11.65MB  11.98MB  630  1.03  👍🏻
and                0.34MB   0.41MB   420  1.22  ⚡
or                 196.69kB 219.31kB 305  1.12  ⚡
xor                157.98kB 180.81kB 375  1.14  ⚡
andnot             217.86kB 0.33MB   320  1.50  ⚡
lazy_or            161.72kB 239.00kB 250  1.48  ⚡
or_inplace         0.32MB   0.34MB   390  1.05  👍🏻
and_inplace        140.05kB 142.59kB 60   1.02  👍🏻
is_subset          134.90kB 144.89kB 180  1.07  ⚡
equals             26.55MB  6.86MB   30   0.26  💩
and_cardinality    0.74MB   1.05MB   40   1.42  ⚡
or_cardinality     0.79MB   0.93MB   45   1.18  ⚡
xor_cardinality    0.95MB   0.94MB   35   0.99  👍🏻
andnot_cardinality 0.81MB   0.96MB   20   1.18  ⚡
jaccard_index      0.88MB   1.06MB   40   1.20  ⚡
or_many            19.59kB  12.23kB  130  0.62  💩
22

I’ve just pushed some minor optimizations which bring the overall benchmark i’ve been sharing up around 1% to 91% from 90% last time.

More importantly, I’ve improved the overall benchmark a bit. It now uses clear (which is an alias to deinit) instead of clear_retaining_capacity.

As a result clear is no longer like 20x faster :sweat_smile: . And the overall benchmark is now a more honest comparison with CRoaring.

Overall plot:

image
image1210×942 36.3 KB

$ zig build bench -Doptimize=ReleaseFast 
$ zig build bench -Doptimize=ReleaseFast
----------------------------------------------------
overall:
----------------------------------------------------
CRoaring: 23450 ops 46.171ms   0.508MB ops/sec
ZRoaring: 23450 ops 50.605ms   0.463MB ops/sec

                                 ratio -- 0.912 🥔

----------------------------------------------------
individual ops: speed=ops/sec
----------------------------------------------------
op                   cr speed zr speed #    ratio
----------------------------------------------------
clear                1.62MB   1.66MB   530  1.03  👍🏻
run_optimize         0.46MB   0.40MB   780  0.88  🥔
shrink_to_fit        4.21MB   3.08MB   700  0.73  💩
portable_serialize   3.07MB   2.32MB   210  0.75  🥔
portable_deserialize 216.75kB 0.42MB   860  1.94  ⚡
frozen_serialize     3.03MB   2.39MB   170  0.79  🥔
minimum              27.32MB  26.72MB  970  0.98  👍🏻
maximum              21.53MB  18.53MB  950  0.86  🥔
add                  12.05MB  12.03MB  4470 1.00  👍🏻
rank                 9.69MB   9.69MB   50   1.00  👍🏻
select               8.72MB   4.50MB   60   0.52  💩
contains             23.15MB  22.07MB  800  0.95  👍🏻
add_many             2.52MB   3.11MB   1900 1.24  ⚡
add_range_closed     2.46MB   2.21MB   3210 0.90  🥔
contains_range       19.16MB  18.89MB  1050 0.99  👍🏻
range_cardinality    8.33MB   5.52MB   10   0.66  💩
remove               12.06MB  12.43MB  1360 1.03  👍🏻
and                  0.26MB   0.27MB   930  1.04  👍🏻
or                   201.05kB 189.69kB 610  0.94  👍🏻
xor                  155.58kB 183.67kB 750  1.18  ⚡
andnot               212.07kB 0.43MB   640  2.04  ⚡
lazy_or              168.66kB 226.22kB 500  1.34  ⚡
or_inplace           0.31MB   0.33MB   780  1.08  ⚡
and_inplace          147.68kB 154.56kB 120  1.05  👍🏻
is_subset            134.64kB 139.47kB 360  1.04  👍🏻
equals               28.99MB  20.62MB  60   0.71  💩
and_cardinality      0.66MB   0.77MB   80   1.16  ⚡
or_cardinality       0.75MB   0.76MB   90   1.03  👍🏻
xor_cardinality      0.93MB   0.91MB   70   0.98  👍🏻
andnot_cardinality   0.70MB   0.82MB   40   1.17  ⚡
jaccard_index        0.80MB   0.79MB   80   0.98  👍🏻
or_many              20.50kB  11.80kB  260  0.58  💩
1 Like