emkornfield commented on a change in pull request #8156: URL: https://github.com/apache/arrow/pull/8156#discussion_r486459473
########## File path: cpp/src/parquet/level_comparison.h ########## @@ -0,0 +1,91 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. +#pragma once + +#include <algorithm> +#include <cstdint> + +#include "arrow/util/bit_util.h" + +namespace parquet { +namespace internal { + +// These APIs are likely to be revised as part of ARROW-8494 to reduce duplicate code. +// They currently represent minimal functionality for vectorized computation of definition +// levels. + +/// Builds a bitmap by applying predicate to the level vector provided. +/// +/// \param[in] levels Rep or def level array. +/// \param[in] num_levels The number of levels to process (must be [0, 64]) +/// \param[in] predicate The predicate to apply (must have the signature `bool +/// predicate(int16_t)`. +/// \returns The bitmap using least significant "bit" ordering. +/// +/// N.B. Correct byte ordering is dependent on little-endian architectures. +/// +template <typename Predicate> +inline uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, + Predicate predicate) { + // Both clang and GCC can vectorize this automatically with SSE4/AVX2. + uint64_t mask = 0; + for (int x = 0; x < num_levels; x++) { + mask |= static_cast<uint64_t>(predicate(levels[x]) ? 1 : 0) << x; + } + return ::arrow::BitUtil::ToLittleEndian(mask); +} + +/// Builds a bitmap where each set bit indicates the corresponding level is greater Review comment: This is rearranging code from a [prior](https://github.com/apache/arrow/pull/6985) which on my box showed 20% end-to-end parquet to arrow read performance on existing benchmarks, indicating that while cheap the comparison take a considerable amount of time in decoding. **Why generalize in this way?** The generation of bitmaps can be made cheaper than it currently is. Right now parquet RLE encodes rep/def levels. We fully decode these levels into int16_t and then try to reconstruct nested metadata from them. For places where there are actually runs, the bitmaps become much less expensive to generate (its a simple mask of N-bits). For cases when max def/rep-level is one, I don't think comparison would even be necessary for non-RLE encoded data (the data is already in bitmap form). Working at the bitmaps level allows taking advantage of bit-level parallelism at the cost of doing extra for each column (The scalar version of the algorithm I include actually also does the same extra work when compared with the current [reconstruction algorithm](https://github.com/apache/arrow/blob/master/cpp/src/parquet/arrow/reader_internal.cc#L810)). It is also worth pointing out there are roughly three cases to consider: 1. No-nested lists (in which case using this method will directly generate validity bitmaps and be a strict performance win). 2. Single list (when BMI2 is usable I believe this approach will also be faster than any other approach, I'm a little bit less confident when BMI2 isn't usable, but I would expect at least equal performance). 3. Nested lists. At a certain point using something similar to the [batch](https://github.com/apache/arrow/blob/master/cpp/src/parquet/arrow/reader_internal.cc#L810) approach will start to win versus the bitmap approach. This could be as early as 2 lists, but I would guess it is likely >= 3 lists. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected]
