Different bitmap sizes support: speedup 'And', 'AndNot', fix 'AndNot', 'Or' and 'Xor'

[marniks7]

Hi, There are 2 type of changes for different bitmap sizes

• 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)