Bitmap Versions Save

This release adds a proper ReaderFrom (see https://pkg.go.dev/io#ReaderFrom) implementation on the bitmap itself, with a couple of more tests and benchmarks. https://github.com/kelindar/bitmap/pull/17

What's Changed

• Implement ReaderFrom interface by @kelindar in https://github.com/kelindar/bitmap/pull/17

Full Changelog: https://github.com/kelindar/bitmap/compare/v1.1.3...v1.1.4

This release introduces 2 type of changes for different bitmap sizes by @marniks7 (see: https://github.com/kelindar/bitmap/pull/16)

• Fix 'AndNot', 'Or' and 'Xor' operations
• Speedup 'And', 'AndNot'

Fix 'AndNot', 'Or' and 'Xor'

• 'AndNot' works as set subtraction, this is what i believe expected from Readme

books.And(recent)
books.And(ebooks)
books.AndNot(bestsellers) 

• 'Or' and 'Xor' only growth if needed, never shrinks, so, actually i reverted balance function change introduced recently. We should take into consideration both one bits of dst and b bitmaps

Speedup And

1. [0....1kk].And([0...1k]) = [0...1k] ER=AR: dst bitmap shrinks to the smallest size
2. [0....1k].And([0...1kk]) = [0...1k] ER: this PR fixes this case, it shrinks dst bitmap to the smallest possible size ([0...1k]) AR: dst bitmap grows to 1kk bitmap, while for 'And' operation the best possible result is [0...1k]

8 consecutive And bitmaps improvement

ER1: benefits for cases when position of one bits at the start ER2: NO benefits for cases when position of one bits at the end

benchstat benchmark/500k-large-groups/kelindar/benchmark-results-old.txt benchmark/500k-large-groups/kelindar/benchmark-results-new.txt
name                               old time/op    new time/op    delta
FindPriceV2_11position               18.4µs ± 3%     1.3µs ± 9%  -93.13%  (p=0.000 n=8+10)
FindPriceV2_3824position             17.9µs ± 4%     2.8µs ± 5%  -84.64%  (p=0.000 n=10+10)
FindPriceV2_3824position_OptStats    19.9µs ± 5%     3.5µs ± 5%  -82.16%  (p=0.000 n=9+10)
FindPriceV2_9701position             22.3µs ± 7%    20.3µs ± 4%   -8.92%  (p=0.000 n=10+9)
FindPriceV2_MultiplePricesErr        15.1µs ± 2%     2.1µs ± 2%  -85.99%  (p=0.000 n=10+9)

name                               old alloc/op   new alloc/op   delta
FindPriceV2_11position                 177B ± 0%      176B ± 0%   -0.56%  (p=0.000 n=10+10)
FindPriceV2_3824position               177B ± 0%      176B ± 0%   -0.56%  (p=0.000 n=10+10)
FindPriceV2_3824position_OptStats      225B ± 0%      224B ± 0%   -0.44%  (p=0.000 n=10+10)
FindPriceV2_9701position               177B ± 0%      177B ± 0%     ~     (all equal)
FindPriceV2_MultiplePricesErr          128B ± 0%      128B ± 0%     ~     (all equal)

name                               old allocs/op  new allocs/op  delta
FindPriceV2_11position                 6.00 ± 0%      6.00 ± 0%     ~     (all equal)
FindPriceV2_3824position               6.00 ± 0%      6.00 ± 0%     ~     (all equal)
FindPriceV2_3824position_OptStats      11.0 ± 0%      11.0 ± 0%     ~     (all equal)
FindPriceV2_9701position               6.00 ± 0%      6.00 ± 0%     ~     (all equal)
FindPriceV2_MultiplePricesErr          4.00 ± 0%      4.00 ± 0%     ~     (all equal)

This release fixes #14 - bitmap trimmed but was not reinitialized.

This release fixes https://github.com/kelindar/bitmap/issues/12 with uneven bitmap size.

This is further speeding up Range() roughly by 20% and Filter() by around 5%. It will also now quickly skip empty pages. The contract for Range() is changed as the function callback can no longer be halted. It should be okay for most cases as bitmaps need to be actually pre-filtered prior to the iteration. https://github.com/kelindar/bitmap/pull/10

This speeds up Range() and Filter() by roughly 30% according to my benchmarks. Specifically, Filter() is now branchless but uses slightly more stack space. #7

Changelog

• Mirrored Min() and Max() with MinZero() and MaxZero() and added nicer documentation for it. https://github.com/kelindar/bitmap/pull/6

Changelog

• Unrolled POPCNT for 30% speedup in Count() https://github.com/kelindar/bitmap/pull/4
• Fix non amd64 builds https://github.com/kelindar/bitmap/pull/5

Support for uneven bitmaps and, andn, or and xor.

Exports Grow() method and some code cleanup.