Faster range

[fulmicoton]

ip::ip_range_hit_10_percent                                   280,902               112,715                  -168,187  -59.87%   x 2.49 
 ip::ip_range_hit_10_percent_intersect_with_10_percent         422,246               239,179                  -183,067  -43.36%   x 1.77 
 ip::ip_range_hit_10_percent_intersect_with_10_percent_multi   1,029,849             686,329                  -343,520  -33.36%   x 1.50 
 ip::ip_range_hit_10_percent_intersect_with_90_percent         481,214               298,735                  -182,479  -37.92%   x 1.61 
 ip::ip_range_hit_10_percent_intersect_with_90_percent_multi   1,091,238             1,021,075                 -70,163   -6.43%   x 1.07 
 ip::ip_range_hit_10_percent_multi                             878,829               740,768                  -138,061  -15.71%   x 1.19 
 ip::ip_range_hit_1_percent                                    247,980               136,112                  -111,868  -45.11%   x 1.82 
 ip::ip_range_hit_1_percent_intersect_with_10_percent          299,869               213,348                   -86,521  -28.85%   x 1.41 
 ip::ip_range_hit_1_percent_intersect_with_10_percent_multi    633,218               543,115                   -90,103  -14.23%   x 1.17 
 ip::ip_range_hit_1_percent_intersect_with_1_percent           255,403               182,303                   -73,100  -28.62%   x 1.40 
 ip::ip_range_hit_1_percent_intersect_with_1_percent_multi     509,210               417,750                   -91,460  -17.96%   x 1.22 
 ip::ip_range_hit_1_percent_intersect_with_90_percent          329,676               234,480                   -95,196  -28.88%   x 1.41 
 ip::ip_range_hit_1_percent_intersect_with_90_percent_multi    660,522               528,706                  -131,816  -19.96%   x 1.25 
 ip::ip_range_hit_1_percent_multi                              684,272               515,868                  -168,404  -24.61%   x 1.33 
 ip::ip_range_hit_90_percent                                   429,287               243,950                  -185,337  -43.17%   x 1.76 
 ip::ip_range_hit_90_percent_intersect_with_10_percent         681,977               513,321                  -168,656  -24.73%   x 1.33 
 ip::ip_range_hit_90_percent_intersect_with_10_percent_multi   1,960,244             1,731,199                -229,045  -11.68%   x 1.13 
 ip::ip_range_hit_90_percent_intersect_with_1_percent          299,181               219,425                   -79,756  -26.66%   x 1.36 
 ip::ip_range_hit_90_percent_intersect_with_1_percent_multi    1,175,779             1,041,459                -134,320  -11.42%   x 1.13 
 ip::ip_range_hit_90_percent_intersect_with_90_percent         1,799,396             1,705,019                 -94,377   -5.24%   x 1.06 
 ip::ip_range_hit_90_percent_intersect_with_90_percent_multi   3,138,795             2,916,361                -222,434   -7.09%   x 1.08 
 ip::ip_range_hit_90_percent_multi                             1,759,845             1,471,850                -287,995  -16.36%   x 1.20 
 u64::id_range_hit_10_percent                                  338,957               131,419                  -207,538  -61.23%   x 2.58 
 u64::id_range_hit_10_percent_intersect_with_10_percent        493,492               276,940                  -216,552  -43.88%   x 1.78 
 u64::id_range_hit_10_percent_intersect_with_10_percent_multi  1,165,556             817,999                  -347,557  -29.82%   x 1.42 
 u64::id_range_hit_10_percent_intersect_with_90_percent        559,290               353,221                  -206,069  -36.84%   x 1.58 
 u64::id_range_hit_10_percent_intersect_with_90_percent_multi  1,233,187             896,852                  -336,335  -27.27%   x 1.38 
 u64::id_range_hit_10_percent_multi                            1,027,509             679,481                  -348,028  -33.87%   x 1.51 
 u64::id_range_hit_1_percent                                   317,092               119,386                  -197,706  -62.35%   x 2.66 
 u64::id_range_hit_1_percent_intersect_with_10_percent         350,194               172,752                  -177,442  -50.67%   x 2.03 
 u64::id_range_hit_1_percent_intersect_with_10_percent_multi   741,245               462,469                  -278,776  -37.61%   x 1.60 
 u64::id_range_hit_1_percent_intersect_with_1_percent          282,981               146,007                  -136,974  -48.40%   x 1.94 
 u64::id_range_hit_1_percent_intersect_with_1_percent_multi    577,589               364,590                  -212,999  -36.88%   x 1.58 
 u64::id_range_hit_1_percent_intersect_with_90_percent         378,540               198,718                  -179,822  -47.50%   x 1.90 
 u64::id_range_hit_1_percent_intersect_with_90_percent_multi   770,156               495,954                  -274,202  -35.60%   x 1.55 
 u64::id_range_hit_1_percent_multi                             809,667               492,169                  -317,498  -39.21%   x 1.65 
 u64::id_range_hit_90_percent                                  434,246               207,074                  -227,172  -52.31%   x 2.10 
 u64::id_range_hit_90_percent_intersect_with_10_percent        712,938               482,161                  -230,777  -32.37%   x 1.48 
 u64::id_range_hit_90_percent_intersect_with_10_percent_multi  2,063,949             1,667,329                -396,620  -19.22%   x 1.24 
 u64::id_range_hit_90_percent_intersect_with_1_percent         320,298               181,526                  -138,772  -43.33%   x 1.76 
 u64::id_range_hit_90_percent_intersect_with_1_percent_multi   1,166,335             956,713                  -209,622  -17.97%   x 1.22 
 u64::id_range_hit_90_percent_intersect_with_90_percent        1,819,790             1,617,064                -202,726  -11.14%   x 1.13 
 u64::id_range_hit_90_percent_intersect_with_90_percent_multi  3,145,675             2,777,483                -368,192  -11.70%   x 1.13 
 u64::id_range_hit_90_percent_multi                            1,737,499             1,389,325                -348,174  -20.04%   x 1.25

[codecov-commenter]

Codecov Report

Merging #1954 (e5258dd) into main (8f7f1d6) will decrease coverage by 0.01%.
The diff coverage is 97.89%.

📣 This organization is not using Codecov’s GitHub App Integration. We recommend you install it so Codecov can continue to function properly for your repositories. Learn more

@@            Coverage Diff             @@
##             main    #1954      +/-   ##
==========================================
- Coverage   94.52%   94.52%   -0.01%     
==========================================
  Files         311      317       +6     
  Lines       57241    57775     +534     
==========================================
+ Hits        54109    54610     +501     
- Misses       3132     3165      +33     

Impacted Files	Coverage Δ
bitpacker/src/lib.rs	100.00% <ø> (ø)
columnar/src/column_values/mod.rs	95.23% <ø> (+5.58%)	⬆️
columnar/src/column_values/u64_based/bitpacked.rs	94.49% <87.50%> (-4.06%)	⬇️
bitpacker/src/filter_vec/mod.rs	97.97% <97.97%> (ø)
bitpacker/src/bitpacker.rs	98.91% <98.49%> (-0.39%)	⬇️
bitpacker/src/filter_vec/avx2.rs	100.00% <100.00%> (ø)
bitpacker/src/filter_vec/scalar.rs	100.00% <100.00%> (ø)
...es/u128_based/compact_space/build_compact_space.rs	95.45% <100.00%> (+0.71%)	⬆️
.../src/column_values/u128_based/compact_space/mod.rs	98.81% <100.00%> (-0.05%)	⬇️

... and 21 files with indirect coverage changes

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

[PSeitz]

I don't think that should be pub, or is that just for the tests?

[fulmicoton]

Oh, I thought it was a very useful API... Getting a batch of u32s values sounds useful.

[PSeitz]

the change is commented, and that's not how it should work

we could alter the condition, so we always add_blanks when reaching 32 bits value space.

let reached_u32_value_space = amplitude_new_bits <= 32 && amplitude_bits > 32;
if  !reached_u32_value_space && cost >= saved_bits {
    continue;
}

[fulmicoton]

Nice catch! I messed up. In test_worst_case_scenario I never managed to end up with amplitude_bits > 32 so I ended up just putting the assert.

[PSeitz]

test_worst_case_scenario tests the wrong thing, it calls add_blanks unconditionally, but the algorithm could decide that the metadata overhead is too high and not add the blanks to reduce the value space. The logic that needs to be tested in test_worst_case_scenario is get_compact_space. 10_000 blanks may not be enough

The cost per blank is hardcoded currently const COST_PER_BLANK_IN_BITS: usize = 36;

[fulmicoton]

oooohh you are absolutely right!

[fulmicoton]

This time, the unit test does fail without the extra if condition in the test.

[fulmicoton]

I made it private upon your suggestion. We can make it public if it because useful.