| 219 | } |
| 220 | |
| 221 | void BlockedBloomFilter::Fold() { |
| 222 | // Keep repeating until one of the stop conditions checked inside the loop |
| 223 | // is met |
| 224 | for (;;) { |
| 225 | // If we reached the minimum size of blocked Bloom filter then stop |
| 226 | constexpr int log_num_blocks_min = 4; |
| 227 | if (log_num_blocks_ <= log_num_blocks_min) { |
| 228 | break; |
| 229 | } |
| 230 | |
| 231 | int64_t num_bits = num_blocks_ * 64; |
| 232 | |
| 233 | // Calculate the number of bits set in this blocked Bloom filter |
| 234 | int64_t num_bits_set = 0; |
| 235 | int batch_size_max = 65536; |
| 236 | for (int64_t i = 0; i < num_bits; i += batch_size_max) { |
| 237 | int batch_size = |
| 238 | static_cast<int>(std::min(num_bits - i, static_cast<int64_t>(batch_size_max))); |
| 239 | num_bits_set += |
| 240 | arrow::internal::CountSetBits(reinterpret_cast<const uint8_t*>(blocks_) + i / 8, |
| 241 | /*offset=*/0, batch_size); |
| 242 | } |
| 243 | |
| 244 | // If at least 1/4 of bits is set then stop |
| 245 | if (4 * num_bits_set >= num_bits) { |
| 246 | break; |
| 247 | } |
| 248 | |
| 249 | // Decide how many times to fold at once. |
| 250 | // The resulting size should not be less than log_num_bits_min. |
| 251 | int num_folds = 1; |
| 252 | |
| 253 | while ((log_num_blocks_ - num_folds) > log_num_blocks_min && |
| 254 | (4 * num_bits_set) < (num_bits >> num_folds)) { |
| 255 | ++num_folds; |
| 256 | } |
| 257 | |
| 258 | // Actual update to block Bloom filter bits |
| 259 | SingleFold(num_folds); |
| 260 | } |
| 261 | } |
| 262 | |
| 263 | void BlockedBloomFilter::SingleFold(int num_folds) { |
| 264 | // Calculate number of slices and size of a slice |