You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2020/04/23 10:45:54 UTC
[GitHub] [arrow] pitrou commented on a change in pull request #6985: ARROW-8413: [C++][Parquet] Refactor Generating validity bitmap for values column
pitrou commented on a change in pull request #6985:
URL: https://github.com/apache/arrow/pull/6985#discussion_r413696312
##########
File path: cpp/cmake_modules/SetupCxxFlags.cmake
##########
@@ -40,12 +40,13 @@ if(ARROW_CPU_FLAG STREQUAL "x86")
set(CXX_SUPPORTS_SSE4_2 TRUE)
else()
set(ARROW_SSE4_2_FLAG "-msse4.2")
- set(ARROW_AVX2_FLAG "-mavx2")
+ set(ARROW_AVX2_FLAG "-march=core-avx2")
Review comment:
It would be nice if you could try again.
##########
File path: cpp/cmake_modules/SetupCxxFlags.cmake
##########
@@ -40,12 +40,13 @@ if(ARROW_CPU_FLAG STREQUAL "x86")
set(CXX_SUPPORTS_SSE4_2 TRUE)
else()
set(ARROW_SSE4_2_FLAG "-msse4.2")
- set(ARROW_AVX2_FLAG "-mavx2")
+ set(ARROW_AVX2_FLAG "-march=core-avx2")
# skylake-avx512 consists of AVX512F,AVX512BW,AVX512VL,AVX512CD,AVX512DQ
set(ARROW_AVX512_FLAG "-march=skylake-avx512")
check_cxx_compiler_flag(${ARROW_SSE4_2_FLAG} CXX_SUPPORTS_SSE4_2)
endif()
check_cxx_compiler_flag(${ARROW_AVX2_FLAG} CXX_SUPPORTS_AVX2)
+ check_cxx_compiler_flag(${ARROW_AVX2_FLAG} CXX_SUPPORTS_AVX2)
Review comment:
This doesn't seem useful :-)
##########
File path: cpp/src/parquet/column_reader.cc
##########
@@ -50,6 +51,140 @@ using arrow::internal::checked_cast;
namespace parquet {
+namespace {
+
+inline void CheckLevelRange(const int16_t* levels, int64_t num_levels,
+ const int16_t max_expected_level) {
+ int16_t min_level = std::numeric_limits<int16_t>::max();
+ int16_t max_level = std::numeric_limits<int16_t>::min();
+ for (int x = 0; x < num_levels; x++) {
+ min_level = std::min(levels[x], min_level);
+ max_level = std::max(levels[x], max_level);
+ }
+ if (ARROW_PREDICT_FALSE(num_levels > 0 && (min_level < 0 || max_level > max_level))) {
+ throw ParquetException("definition level exceeds maximum");
+ }
+}
+
+#if !defined(ARROW_HAVE_BMI2)
+
+inline void DefinitionLevelsToBitmapScalar(
+ const int16_t* def_levels, int64_t num_def_levels, const int16_t max_definition_level,
+ const int16_t max_repetition_level, int64_t* values_read, int64_t* null_count,
+ uint8_t* valid_bits, int64_t valid_bits_offset) {
+ // We assume here that valid_bits is large enough to accommodate the
+ // additional definition levels and the ones that have already been written
+ ::arrow::internal::BitmapWriter valid_bits_writer(valid_bits, valid_bits_offset,
+ num_def_levels);
+
+ // TODO(itaiin): As an interim solution we are splitting the code path here
+ // between repeated+flat column reads, and non-repeated+nested reads.
+ // Those paths need to be merged in the future
+ for (int i = 0; i < num_def_levels; ++i) {
+ if (def_levels[i] == max_definition_level) {
+ valid_bits_writer.Set();
+ } else if (max_repetition_level > 0) {
+ // repetition+flat case
+ if (def_levels[i] == (max_definition_level - 1)) {
+ valid_bits_writer.Clear();
+ *null_count += 1;
+ } else {
+ continue;
+ }
+ } else {
+ // non-repeated+nested case
+ if (def_levels[i] < max_definition_level) {
+ valid_bits_writer.Clear();
+ *null_count += 1;
+ } else {
+ throw ParquetException("definition level exceeds maximum");
+ }
+ }
+
+ valid_bits_writer.Next();
+ }
+ valid_bits_writer.Finish();
+ *values_read = valid_bits_writer.position();
+}
+#endif
+
+template <bool has_repeated_parent>
+void DefinitionLevelsToBitmapSimd(const int16_t* def_levels, int64_t num_def_levels,
+ const int16_t required_definition_level,
+ int64_t* values_read, int64_t* null_count,
+ uint8_t* valid_bits, int64_t valid_bits_offset) {
+ constexpr int64_t kBitMaskSize = 64;
+ int64_t set_count = 0;
+ *values_read = 0;
+ while (num_def_levels > 0) {
+ int64_t batch_size = std::min(num_def_levels, kBitMaskSize);
+ CheckLevelRange(def_levels, batch_size, required_definition_level);
+ uint64_t defined_bitmap = internal::GreaterThanBitmap(def_levels, batch_size,
+ required_definition_level - 1);
+ if (has_repeated_parent) {
+ // This is currently a specialized code path assuming only (nested) lists
+ // present through the leaf (i.e. no structs).
+ // Upper level code only calls this method
+ // when the leaf-values are nullable (otherwise no spacing is needed),
+ // Because only nested lists exists it is sufficient to know that the field
+ // was either null or included it (i.e. >= previous definition level -> > previous
+ // definition - 1). If there where structs mixed in, we need to know the def_level
+ // of the repeated parent so we can check for def_level > "def level of repeated
+ // parent".
+ uint64_t present_bitmap = internal::GreaterThanBitmap(
+ def_levels, batch_size, required_definition_level - 2);
+ *values_read += internal::AppendSelectedBitsToValidityBitmap(
+ /*new_bits=*/defined_bitmap,
+ /*selection_bitmap*/ present_bitmap, valid_bits, &valid_bits_offset,
+ &set_count);
+ } else {
+ internal::AppendToValidityBitmap(
+ /*new_bits=*/defined_bitmap,
+ /*new_bit_count=*/batch_size, valid_bits, &valid_bits_offset, &set_count);
+ *values_read += batch_size;
+ }
+ def_levels += batch_size;
+ num_def_levels -= batch_size;
+ }
+ *null_count += *values_read - set_count;
+}
+
+inline void DefinitionLevelsToBitmapDispatch(
+ const int16_t* def_levels, int64_t num_def_levels, const int16_t max_definition_level,
+ const int16_t max_repetition_level, int64_t* values_read, int64_t* null_count,
+ uint8_t* valid_bits, int64_t valid_bits_offset) {
+ if (max_repetition_level > 0) {
+#if ARROW_LITTLE_ENDIAN
+
+#if defined(ARROW_HAVE_BMI2)
+ // BMI2 is required for efficient bit extraction.
+ DefinitionLevelsToBitmapSimd</*has_repeated_parent=*/true>(
+ def_levels, num_def_levels, max_definition_level, values_read, null_count,
+ valid_bits, valid_bits_offset);
+#else
+ DefinitionLevelsToBitmapScalar(def_levels, num_def_levels, max_definition_level,
+ max_repetition_level, values_read, null_count,
+ valid_bits, valid_bits_offset);
+#endif // ARROW_HAVE_BMI2
+
+ } else {
+ // No Special intsturction are used for non-repeated case.
Review comment:
"instructions"
##########
File path: cpp/src/parquet/column_reader.cc
##########
@@ -50,6 +51,140 @@ using arrow::internal::checked_cast;
namespace parquet {
+namespace {
+
+inline void CheckLevelRange(const int16_t* levels, int64_t num_levels,
Review comment:
I think it would be nice to move the low-level handling of levels to a dedicated C++ file.
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
+/// than rhs.
+static inline int64_t GreaterThanBitmap(const int16_t* levels, int64_t num_levels,
Review comment:
Why does it return `int64_t` rather than `uint64_t`?
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
+/// than rhs.
+static inline int64_t GreaterThanBitmap(const int16_t* levels, int64_t num_levels,
+ int16_t rhs) {
+ return LevelsToBitmap(levels, num_levels, [&](int16_t value) { return value > rhs; });
+}
+
+/// Append bits number_of_bits from new_bits to valid_bits and valid_bits_offset.
+///
+/// \param[in] new_bits The zero-padded bitmap to append.
+/// \param[in] number_of_bits The number of bits to append from new_bits.
+/// \param[in] valid_bits_length The number of bytes allocated in valid_bits.
+/// \param[in] valid_bits_offset The bit-offset at which to start appending new bits.
+/// \param[in,out] valid_bits The validity bitmap to append to.
+/// \returns The new bit offset inside of valid_bits.
+static inline int64_t AppendBitmap(uint64_t new_bits, int64_t number_of_bits,
Review comment:
Function name is far too generic. How about `AppendWordToBitmap`?
##########
File path: cpp/src/parquet/level_conversion_test.cc
##########
@@ -0,0 +1,162 @@
+// 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.
+
+#include "parquet/level_conversion.h"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include <string>
+
+#include "arrow/util/bit_util.h"
+
+namespace parquet {
+namespace internal {
+
+using ::testing::ElementsAreArray;
+
+std::string ToString(const uint8_t* bitmap, int64_t bit_count) {
Review comment:
Please, a more specific name (such as `BitmapToString`).
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
+/// than rhs.
+static inline int64_t GreaterThanBitmap(const int16_t* levels, int64_t num_levels,
+ int16_t rhs) {
+ return LevelsToBitmap(levels, num_levels, [&](int16_t value) { return value > rhs; });
+}
+
+/// Append bits number_of_bits from new_bits to valid_bits and valid_bits_offset.
+///
+/// \param[in] new_bits The zero-padded bitmap to append.
Review comment:
"zero-padded" doesn't give a clue. Are the `number_of_bits` LSBs appended?
##########
File path: cpp/src/parquet/level_conversion_test.cc
##########
@@ -0,0 +1,162 @@
+// 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.
+
+#include "parquet/level_conversion.h"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include <string>
+
+#include "arrow/util/bit_util.h"
+
+namespace parquet {
+namespace internal {
+
+using ::testing::ElementsAreArray;
+
+std::string ToString(const uint8_t* bitmap, int64_t bit_count) {
+ return arrow::internal::Bitmap(bitmap, /*offset*/ 0, /*length=*/bit_count).ToString();
+}
+
+std::string ToString(const std::vector<uint8_t>& bitmap, int64_t bit_count) {
Review comment:
Ditto here.
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
Review comment:
"corresponding"?
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
+/// than rhs.
+static inline int64_t GreaterThanBitmap(const int16_t* levels, int64_t num_levels,
+ int16_t rhs) {
+ return LevelsToBitmap(levels, num_levels, [&](int16_t value) { return value > rhs; });
+}
+
+/// Append bits number_of_bits from new_bits to valid_bits and valid_bits_offset.
+///
+/// \param[in] new_bits The zero-padded bitmap to append.
+/// \param[in] number_of_bits The number of bits to append from new_bits.
+/// \param[in] valid_bits_length The number of bytes allocated in valid_bits.
+/// \param[in] valid_bits_offset The bit-offset at which to start appending new bits.
+/// \param[in,out] valid_bits The validity bitmap to append to.
+/// \returns The new bit offset inside of valid_bits.
+static inline int64_t AppendBitmap(uint64_t new_bits, int64_t number_of_bits,
+ int64_t valid_bits_length, int64_t valid_bits_offset,
+ uint8_t* valid_bits) {
+ // Selection masks to retrieve all low order bits for each bytes.
+ constexpr uint64_t kLsbSelectionMasks[] = {
+ 0, // unused.
+ 0x0101010101010101,
+ 0x0303030303030303,
+ 0x0707070707070707,
+ 0x0F0F0F0F0F0F0F0F,
+ 0x1F1F1F1F1F1F1F1F,
+ 0x3F3F3F3F3F3F3F3F,
+ 0x7F7F7F7F7F7F7F7F,
+ };
+ int64_t valid_byte_offset = valid_bits_offset / 8;
+ int64_t bit_offset = valid_bits_offset % 8;
+
+ int64_t new_offset = valid_bits_offset + number_of_bits;
+ union ByteAddressableBitmap {
+ explicit ByteAddressableBitmap(uint64_t mask) : mask(mask) {}
+ uint64_t mask;
+ uint8_t bytes[8];
+ };
+
+ if (bit_offset != 0) {
+ int64_t bits_to_carry = 8 - bit_offset;
+ // Get the mask the will select the lower order bits (the ones to carry
+ // over to the existing byte and shift up.
+ const ByteAddressableBitmap carry_bits(kLsbSelectionMasks[bits_to_carry]);
+ // Mask to select non-carried bits.
+ const ByteAddressableBitmap inverse_selection(~carry_bits.mask);
+ // Fill out the last incomplete byte in the output, by extracting the least
+ // siginficant bits from the first byte.
+ const ByteAddressableBitmap new_bitmap(new_bits);
+ // valid bits should be a valid bitmask so all trailing bytes hsould be unset
+ // so no mask is need to start.
+ valid_bits[valid_byte_offset] =
+ valid_bits[valid_byte_offset] | // See above the
+ (((new_bitmap.bytes[0] & carry_bits.bytes[0])) << bit_offset);
+
+ // We illustrate logic with a 3-byte example in little endian/LSB order.
+ // Note this ordering is the reversed from HEX masks above with are expressed
+ // big-endian/MSB and shifts right move the bits to the left (division).
+ // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
+ // Shifted mask should look like this assuming bit offset = 6:
+ // 2 3 4 5 6 7 N N 10 11 12 13 14 15 N N 18 19 20 21 22 23 N N
Review comment:
??? Why are the "N"s lost here?
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
+/// than rhs.
+static inline int64_t GreaterThanBitmap(const int16_t* levels, int64_t num_levels,
+ int16_t rhs) {
+ return LevelsToBitmap(levels, num_levels, [&](int16_t value) { return value > rhs; });
+}
+
+/// Append bits number_of_bits from new_bits to valid_bits and valid_bits_offset.
+///
+/// \param[in] new_bits The zero-padded bitmap to append.
+/// \param[in] number_of_bits The number of bits to append from new_bits.
+/// \param[in] valid_bits_length The number of bytes allocated in valid_bits.
+/// \param[in] valid_bits_offset The bit-offset at which to start appending new bits.
+/// \param[in,out] valid_bits The validity bitmap to append to.
+/// \returns The new bit offset inside of valid_bits.
+static inline int64_t AppendBitmap(uint64_t new_bits, int64_t number_of_bits,
+ int64_t valid_bits_length, int64_t valid_bits_offset,
+ uint8_t* valid_bits) {
+ // Selection masks to retrieve all low order bits for each bytes.
+ constexpr uint64_t kLsbSelectionMasks[] = {
Review comment:
This entire function looks cryptic.
1) ideally this would be in `bit-util.h`
2) why not add something like a `AppendWord(uint64_t word, int64_t nbits)` to `BitmapWriter` or `FirstTimeBitmapWriter`?
3) the implementation looks gratuitously complicated
##########
File path: cpp/src/parquet/level_conversion_test.cc
##########
@@ -0,0 +1,162 @@
+// 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.
+
+#include "parquet/level_conversion.h"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include <string>
+
+#include "arrow/util/bit_util.h"
+
+namespace parquet {
+namespace internal {
+
+using ::testing::ElementsAreArray;
+
+std::string ToString(const uint8_t* bitmap, int64_t bit_count) {
+ return arrow::internal::Bitmap(bitmap, /*offset*/ 0, /*length=*/bit_count).ToString();
+}
+
+std::string ToString(const std::vector<uint8_t>& bitmap, int64_t bit_count) {
+ return ToString(bitmap.data(), bit_count);
+}
+
+TEST(TestGreaterThanBitmap, GeneratesExpectedBitmasks) {
+ std::vector<int16_t> levels = {0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7};
+ EXPECT_EQ(GreaterThanBitmap(levels.data(), /*num_levels=*/0, /*rhs*/ 0), 0);
+ EXPECT_EQ(GreaterThanBitmap(levels.data(), /*num_levels=*/64, /*rhs*/ 8), 0);
+ EXPECT_EQ(GreaterThanBitmap(levels.data(), /*num_levels=*/64, /*rhs*/ -1),
+ 0xFFFFFFFFFFFFFFFF);
+ // Should be zero padded.
+ EXPECT_EQ(GreaterThanBitmap(levels.data(), /*num_levels=*/47, /*rhs*/ -1),
+ 0x7FFFFFFFFFFF);
+ EXPECT_EQ(GreaterThanBitmap(levels.data(), /*num_levels=*/64, /*rhs*/ 6),
+ 0x8080808080808080);
+}
+
+TEST(TestAppendBitmap, TestOffsetOverwritesCorrectBitsOnExistingByte) {
+ auto check_append = [](const std::string& expected_bits, int64_t offset) {
+ std::vector<uint8_t> valid_bits = {0x00};
+ constexpr int64_t kBitsAfterAppend = 8;
+ ASSERT_EQ(
+ AppendBitmap(/*new_bits=*/0xFF, /*number_of_bits*/ 8 - offset,
+ /*valid_bits_length=*/valid_bits.size(), offset, valid_bits.data()),
+ kBitsAfterAppend);
+ EXPECT_EQ(ToString(valid_bits, kBitsAfterAppend), expected_bits);
+ };
+ check_append("11111111", 0);
+ check_append("01111111", 1);
+ check_append("00111111", 2);
+ check_append("00011111", 3);
+ check_append("00001111", 4);
+ check_append("00000111", 5);
+ check_append("00000011", 6);
+ check_append("00000001", 7);
+}
+
+TEST(TestAppendBitmap, TestOffsetShiftBitsCorrectly) {
+ constexpr uint64_t kPattern = 0x9A9A9A9A9A9A9A9A;
+ auto check_append = [&](const std::string& leading_bits, const std::string& middle_bits,
+ const std::string& trailing_bits, int64_t offset) {
+ ASSERT_GE(offset, 8);
+ std::vector<uint8_t> valid_bits(/*count=*/10, 0);
+ valid_bits[0] = 0x99;
+
+ AppendBitmap(/*new_bits=*/kPattern, /*number_of_bits*/ 64,
+ /*valid_bits_length=*/valid_bits.size(), offset, valid_bits.data());
+ EXPECT_EQ(valid_bits[0], 0x99); // shouldn't get chanked.
+ EXPECT_EQ(ToString(valid_bits.data() + 1, /*num_bits=*/8), leading_bits);
+ for (int x = 2; x < 9; x++) {
+ EXPECT_EQ(ToString(valid_bits.data() + x, /*num_bits=*/8), middle_bits);
+ }
+ EXPECT_EQ(ToString(valid_bits.data() + 9, /*num_bits=*/8), trailing_bits);
+ };
+ // Original Pattern = "01011001"
+ check_append(/*leading_bits= */ "01011001", /*middle_bits=*/"01011001",
+ /*trailing_bits=*/"00000000", /*offset=*/8);
+ check_append("00101100", "10101100", "10000000", 9);
+ check_append("00010110", "01010110", "01000000", 10);
+ check_append("00001011", "00101011", "00100000", 11);
+ check_append("00000101", "10010101", "10010000", 12);
+ check_append("00000010", "11001010", "11001000", 13);
+ check_append("00000001", "01100101", "01100100", 14);
+ check_append("00000000", "10110010", "10110010", 15);
+}
+
+TEST(TestAppendBitmap, AllBytesAreWrittenWithEnoughSpace) {
+ std::vector<uint8_t> valid_bits(/*count=*/9, 0);
+
+ uint64_t bitmap = 0xFFFFFFFFFFFFFFFF;
+ AppendBitmap(bitmap, /*number_of_bits*/ 7,
+ /*valid_bits_length=*/valid_bits.size(),
+ /*valid_bits_offset=*/1,
+ /*valid_bits=*/valid_bits.data());
+ EXPECT_THAT(valid_bits, ElementsAreArray(std::vector<uint8_t>{
+ 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x01}));
+}
+
+TEST(TestAppendBitmap, OnlyApproriateBytesWrittenWhenLessThen8BytesAvailable) {
+ std::vector<uint8_t> valid_bits = {0x00, 0x00};
+
+ uint64_t bitmap = 0x1FF;
+ AppendBitmap(bitmap, /*number_of_bits*/ 7,
+ /*valid_bits_length=*/2,
+ /*valid_bits_offset=*/1,
+ /*valid_bits=*/valid_bits.data());
+
+ EXPECT_THAT(valid_bits, ElementsAreArray(std::vector<uint8_t>{0xFE, 0x00}));
+
+ AppendBitmap(bitmap, /*number_of_bits*/ 9,
+ /*valid_bits_length=*/2,
+ /*valid_bits_offset=*/1,
+ /*valid_bits=*/valid_bits.data());
+ EXPECT_THAT(valid_bits, ElementsAreArray(std::vector<uint8_t>{0xFE, 0x03}));
+}
+
+TEST(TestAppendToValidityBitmap, BasicOperation) {
+ std::vector<uint8_t> validity_bitmap(/*count*/ 8, 0);
+ int64_t valid_bitmap_offset = 1;
+ int64_t set_bit_count = 5;
+ AppendToValidityBitmap(/*new_bits*/ 0x99, /*new_bit_count=*/31, validity_bitmap.data(),
+ &valid_bitmap_offset, &set_bit_count);
+ EXPECT_EQ(ToString(validity_bitmap, valid_bitmap_offset),
+ "01001100 10000000 00000000 00000000");
+ EXPECT_EQ(set_bit_count, /*5 + 4 set bits=*/9);
+}
+
+TEST(TestAppendSelectedBitsToValidityBitmap, BasicOperation) {
+#if !defined(ARROW_HAVE_BMI2)
Review comment:
Then just don't define the test.
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
+/// than rhs.
+static inline int64_t GreaterThanBitmap(const int16_t* levels, int64_t num_levels,
+ int16_t rhs) {
+ return LevelsToBitmap(levels, num_levels, [&](int16_t value) { return value > rhs; });
+}
+
+/// Append bits number_of_bits from new_bits to valid_bits and valid_bits_offset.
+///
+/// \param[in] new_bits The zero-padded bitmap to append.
+/// \param[in] number_of_bits The number of bits to append from new_bits.
+/// \param[in] valid_bits_length The number of bytes allocated in valid_bits.
+/// \param[in] valid_bits_offset The bit-offset at which to start appending new bits.
+/// \param[in,out] valid_bits The validity bitmap to append to.
+/// \returns The new bit offset inside of valid_bits.
+static inline int64_t AppendBitmap(uint64_t new_bits, int64_t number_of_bits,
+ int64_t valid_bits_length, int64_t valid_bits_offset,
+ uint8_t* valid_bits) {
+ // Selection masks to retrieve all low order bits for each bytes.
+ constexpr uint64_t kLsbSelectionMasks[] = {
+ 0, // unused.
+ 0x0101010101010101,
+ 0x0303030303030303,
+ 0x0707070707070707,
+ 0x0F0F0F0F0F0F0F0F,
+ 0x1F1F1F1F1F1F1F1F,
+ 0x3F3F3F3F3F3F3F3F,
+ 0x7F7F7F7F7F7F7F7F,
+ };
+ int64_t valid_byte_offset = valid_bits_offset / 8;
+ int64_t bit_offset = valid_bits_offset % 8;
+
+ int64_t new_offset = valid_bits_offset + number_of_bits;
+ union ByteAddressableBitmap {
+ explicit ByteAddressableBitmap(uint64_t mask) : mask(mask) {}
+ uint64_t mask;
+ uint8_t bytes[8];
+ };
+
+ if (bit_offset != 0) {
+ int64_t bits_to_carry = 8 - bit_offset;
+ // Get the mask the will select the lower order bits (the ones to carry
+ // over to the existing byte and shift up.
+ const ByteAddressableBitmap carry_bits(kLsbSelectionMasks[bits_to_carry]);
+ // Mask to select non-carried bits.
+ const ByteAddressableBitmap inverse_selection(~carry_bits.mask);
+ // Fill out the last incomplete byte in the output, by extracting the least
+ // siginficant bits from the first byte.
+ const ByteAddressableBitmap new_bitmap(new_bits);
+ // valid bits should be a valid bitmask so all trailing bytes hsould be unset
+ // so no mask is need to start.
+ valid_bits[valid_byte_offset] =
+ valid_bits[valid_byte_offset] | // See above the
+ (((new_bitmap.bytes[0] & carry_bits.bytes[0])) << bit_offset);
+
+ // We illustrate logic with a 3-byte example in little endian/LSB order.
+ // Note this ordering is the reversed from HEX masks above with are expressed
+ // big-endian/MSB and shifts right move the bits to the left (division).
+ // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
+ // Shifted mask should look like this assuming bit offset = 6:
+ // 2 3 4 5 6 7 N N 10 11 12 13 14 15 N N 18 19 20 21 22 23 N N
+ // clang-format on
+ uint64_t shifted_new_bits = (new_bits & inverse_selection.mask) >> bits_to_carry;
+ // captured_carry:
+ // 0 1 N N N N N N 8 9 N N N N N N 16 17 N N N N N N
+ uint64_t captured_carry = carry_bits.mask & new_bits;
+ // mask_cary_bits:
+ // N N N N N N 8 9 N N N N N N 16 17 N N N N N N N N
+ uint64_t mask_carry_bits = (captured_carry >> 8) << bit_offset;
+
+ new_bits = shifted_new_bits | mask_carry_bits;
+ // Don't overwrite the first byte
+ valid_byte_offset += 1;
+ number_of_bits -= bits_to_carry;
+ }
+
+ int64_t bytes_for_new_bits = ::arrow::BitUtil::BytesForBits(number_of_bits);
+ if (valid_bits_length - ::arrow::BitUtil::BytesForBits(valid_bits_offset) >=
+ static_cast<int64_t>(sizeof(new_bits))) {
+ // This should be the common case and inlined as a single instruction which
+ // should be cheaper then the general case of calling mempcy, so it is likely
+ // worth the extra branch.
+ std::memcpy(valid_bits + valid_byte_offset, &new_bits, sizeof(new_bits));
+ } else {
+ std::memcpy(valid_bits + valid_byte_offset, &new_bits, bytes_for_new_bits);
+ }
+ return new_offset;
+}
+
+/// \brief Appends bit values to the validitdy bimap_valid bits, based on bitmaps
+/// generated by GreaterThanBitmap, and the appropriate treshold definition_leve.
Review comment:
I don't think it makes sense for this to be a helper function.
##########
File path: cpp/src/parquet/level_conversion.h
##########
@@ -0,0 +1,191 @@
+// 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 <cstdint>
+#include "arrow/util/bit_util.h"
+
+#if defined(ARROW_HAVE_BMI2)
+#include "x86intrin.h"
+#endif
+
+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>
+uint64_t LevelsToBitmap(const int16_t* levels, int64_t num_levels, Predicate predicate) {
+ // Both clang and GCC can vectorize this automatically with AVX2.
+ uint64_t mask = 0;
+ for (int x = 0; x < num_levels; x++) {
+ mask |= static_cast<int64_t>(predicate(levels[x]) ? 1 : 0) << x;
+ }
+ return mask;
+}
+
+/// Builds a bitmap where each set bit indicates the correspond level is greater
+/// than rhs.
+static inline int64_t GreaterThanBitmap(const int16_t* levels, int64_t num_levels,
+ int16_t rhs) {
+ return LevelsToBitmap(levels, num_levels, [&](int16_t value) { return value > rhs; });
+}
+
+/// Append bits number_of_bits from new_bits to valid_bits and valid_bits_offset.
+///
+/// \param[in] new_bits The zero-padded bitmap to append.
+/// \param[in] number_of_bits The number of bits to append from new_bits.
+/// \param[in] valid_bits_length The number of bytes allocated in valid_bits.
+/// \param[in] valid_bits_offset The bit-offset at which to start appending new bits.
+/// \param[in,out] valid_bits The validity bitmap to append to.
+/// \returns The new bit offset inside of valid_bits.
+static inline int64_t AppendBitmap(uint64_t new_bits, int64_t number_of_bits,
+ int64_t valid_bits_length, int64_t valid_bits_offset,
+ uint8_t* valid_bits) {
+ // Selection masks to retrieve all low order bits for each bytes.
+ constexpr uint64_t kLsbSelectionMasks[] = {
+ 0, // unused.
+ 0x0101010101010101,
+ 0x0303030303030303,
+ 0x0707070707070707,
+ 0x0F0F0F0F0F0F0F0F,
+ 0x1F1F1F1F1F1F1F1F,
+ 0x3F3F3F3F3F3F3F3F,
+ 0x7F7F7F7F7F7F7F7F,
+ };
+ int64_t valid_byte_offset = valid_bits_offset / 8;
+ int64_t bit_offset = valid_bits_offset % 8;
+
+ int64_t new_offset = valid_bits_offset + number_of_bits;
+ union ByteAddressableBitmap {
+ explicit ByteAddressableBitmap(uint64_t mask) : mask(mask) {}
+ uint64_t mask;
+ uint8_t bytes[8];
+ };
+
+ if (bit_offset != 0) {
+ int64_t bits_to_carry = 8 - bit_offset;
+ // Get the mask the will select the lower order bits (the ones to carry
+ // over to the existing byte and shift up.
+ const ByteAddressableBitmap carry_bits(kLsbSelectionMasks[bits_to_carry]);
+ // Mask to select non-carried bits.
+ const ByteAddressableBitmap inverse_selection(~carry_bits.mask);
+ // Fill out the last incomplete byte in the output, by extracting the least
+ // siginficant bits from the first byte.
+ const ByteAddressableBitmap new_bitmap(new_bits);
+ // valid bits should be a valid bitmask so all trailing bytes hsould be unset
+ // so no mask is need to start.
+ valid_bits[valid_byte_offset] =
+ valid_bits[valid_byte_offset] | // See above the
+ (((new_bitmap.bytes[0] & carry_bits.bytes[0])) << bit_offset);
+
+ // We illustrate logic with a 3-byte example in little endian/LSB order.
+ // Note this ordering is the reversed from HEX masks above with are expressed
+ // big-endian/MSB and shifts right move the bits to the left (division).
+ // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
+ // Shifted mask should look like this assuming bit offset = 6:
+ // 2 3 4 5 6 7 N N 10 11 12 13 14 15 N N 18 19 20 21 22 23 N N
+ // clang-format on
+ uint64_t shifted_new_bits = (new_bits & inverse_selection.mask) >> bits_to_carry;
+ // captured_carry:
+ // 0 1 N N N N N N 8 9 N N N N N N 16 17 N N N N N N
+ uint64_t captured_carry = carry_bits.mask & new_bits;
+ // mask_cary_bits:
+ // N N N N N N 8 9 N N N N N N 16 17 N N N N N N N N
+ uint64_t mask_carry_bits = (captured_carry >> 8) << bit_offset;
+
+ new_bits = shifted_new_bits | mask_carry_bits;
+ // Don't overwrite the first byte
+ valid_byte_offset += 1;
+ number_of_bits -= bits_to_carry;
+ }
+
+ int64_t bytes_for_new_bits = ::arrow::BitUtil::BytesForBits(number_of_bits);
+ if (valid_bits_length - ::arrow::BitUtil::BytesForBits(valid_bits_offset) >=
+ static_cast<int64_t>(sizeof(new_bits))) {
+ // This should be the common case and inlined as a single instruction which
+ // should be cheaper then the general case of calling mempcy, so it is likely
+ // worth the extra branch.
+ std::memcpy(valid_bits + valid_byte_offset, &new_bits, sizeof(new_bits));
+ } else {
+ std::memcpy(valid_bits + valid_byte_offset, &new_bits, bytes_for_new_bits);
+ }
+ return new_offset;
+}
+
+/// \brief Appends bit values to the validitdy bimap_valid bits, based on bitmaps
+/// generated by GreaterThanBitmap, and the appropriate treshold definition_leve.
+///
+/// \param[in] new_bits Bitmap to append (intrepreted as Little-endian/LSB).
+/// \param[in] new_bit_count The number of bits to append from new_bits.
+/// \param[in,out] validity_bitmap The validity bitmap to update.
+/// \param[in,out] validity_bitmap_offset The offset to start appending bits to in
+/// valid_bits (updated to latest bitmap).
+/// \param[in,out] set_bit_count The number of set bits appended is added to
+/// set_bit_count.
+void AppendToValidityBitmap(uint64_t new_bits, int64_t new_bit_count,
+ uint8_t* validity_bitmap, int64_t* validity_bitmap_offset,
+ int64_t* set_bit_count) {
+ int64_t min_valid_bits_size =
+ ::arrow::BitUtil::BytesForBits(new_bit_count + *validity_bitmap_offset);
+
+ *set_bit_count += ::arrow::BitUtil::PopCount(new_bits);
+ *validity_bitmap_offset = AppendBitmap(new_bits, new_bit_count, min_valid_bits_size,
+ *validity_bitmap_offset, validity_bitmap);
+}
+
+/// The same as AppendToValidityBitmap but only appends bits from bitmap that have
+/// a corresponding bit set in selection_bitmap.
+///
+/// \returns The number of bits appended.
+///
+/// N.B. This is only implemented for archiectures that suppor the BMI2 instruction
+/// set.
+int64_t AppendSelectedBitsToValidityBitmap(uint64_t new_bits, uint64_t selection_bitmap,
+ uint8_t* validity_bitmap,
+ int64_t* validity_bitmap_offset,
+ int64_t* set_bit_count) {
+#if defined(ARROW_HAVE_BMI2)
+ // If the parent list was empty at for the given slot it should not be added to the
+ // bitmap.
+ uint64_t selected_bits = _pext_u64(new_bits, selection_bitmap);
+ int64_t selected_count =
+ static_cast<int64_t>(::arrow::BitUtil::PopCount(selection_bitmap));
+
+ AppendToValidityBitmap(selected_bits, selected_count, validity_bitmap,
+ validity_bitmap_offset, set_bit_count);
+ return selected_count;
+#else
+ // We shouldn't get here.
Review comment:
Then please only define this function if `ARROW_HAVE_BMI2` is defined.
----------------------------------------------------------------
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:
users@infra.apache.org