| 144 | } |
| 145 | |
| 146 | void UpdateLevelHistogram(std::span<const int16_t> levels, std::span<int64_t> histogram) { |
| 147 | const int64_t num_levels = static_cast<int64_t>(levels.size()); |
| 148 | DCHECK_GE(histogram.size(), 1); |
| 149 | const int16_t max_level = static_cast<int16_t>(histogram.size() - 1); |
| 150 | if (max_level == 0) { |
| 151 | histogram[0] += num_levels; |
| 152 | return; |
| 153 | } |
| 154 | |
| 155 | #ifndef NDEBUG |
| 156 | for (auto level : levels) { |
| 157 | ARROW_DCHECK_LE(level, max_level); |
| 158 | } |
| 159 | #endif |
| 160 | |
| 161 | if (max_level == 1) { |
| 162 | // Specialize the common case for non-repeated non-nested columns. |
| 163 | // Summing the levels gives us the number of 1s, and the number of 0s follows. |
| 164 | // We do repeated sums in the int16_t space, which the compiler is likely |
| 165 | // to vectorize efficiently. |
| 166 | constexpr int64_t kChunkSize = 1 << 14; // to avoid int16_t overflows |
| 167 | int64_t hist1 = 0; |
| 168 | auto it = levels.begin(); |
| 169 | while (it != levels.end()) { |
| 170 | const auto chunk_size = std::min<int64_t>(levels.end() - it, kChunkSize); |
| 171 | hist1 += std::accumulate(levels.begin(), levels.begin() + chunk_size, int16_t{0}); |
| 172 | it += chunk_size; |
| 173 | } |
| 174 | histogram[0] += num_levels - hist1; |
| 175 | histogram[1] += hist1; |
| 176 | return; |
| 177 | } |
| 178 | |
| 179 | // The generic implementation issues a series of histogram load-stores. |
| 180 | // However, it limits store-to-load dependencies by interleaving partial histogram |
| 181 | // updates. |
| 182 | constexpr int kUnroll = 4; |
| 183 | std::array<std::vector<int64_t>, kUnroll> partial_hist; |
| 184 | for (auto& hist : partial_hist) { |
| 185 | hist.assign(histogram.size(), 0); |
| 186 | } |
| 187 | int64_t i = 0; |
| 188 | for (; i <= num_levels - kUnroll; i += kUnroll) { |
| 189 | for (int j = 0; j < kUnroll; ++j) { |
| 190 | ++partial_hist[j][levels[i + j]]; |
| 191 | } |
| 192 | } |
| 193 | for (; i < num_levels; ++i) { |
| 194 | ++partial_hist[0][levels[i]]; |
| 195 | } |
| 196 | for (const auto& hist : partial_hist) { |
| 197 | MergeLevelHistogram(histogram, hist); |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | } // namespace parquet |