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/06/24 07:30:42 UTC
[GitHub] [arrow] jianxind opened a new pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
jianxind opened a new pull request #7531:
URL: https://github.com/apache/arrow/pull/7531
Speedup the typical use case which most data are true values, also add null probability
test case.
Signed-off-by: Frank Du <fr...@intel.com>
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445245990
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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.
Review comment:
I put it to a new header as it could make easy for future optimization further, something like SIMD I proposal before at https://github.com/apache/arrow/pull/7029.
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649198815
Here is the results: https://ci.ursalabs.org/#/builders/73/builds/90/steps/3/logs/result, not know why it not paste here, I see all 0.01% get positive results.
106 BM_PlainEncodingSpacedFloat/32768/1 2.355 GiB/sec 6.385 GiB/sec 171.068 {'run_name': 'BM_PlainEncodingSpacedFloat/3276...
80 BM_PlainDecodingSpacedFloat/32768/1 3.312 GiB/sec 8.534 GiB/sec 157.683 {'run_name': 'BM_PlainDecodingSpacedFloat/3276...
37 BM_PlainDecodingSpacedBoolean/32768/1 595.833 MiB/sec 1.035 GiB/sec 77.882 {'run_name': 'BM_PlainDecodingSpacedBoolean/32...
92 BM_PlainEncodingSpacedDouble/32768/1 3.834 GiB/sec 5.799 GiB/sec 51.278 {'run_name': 'BM_PlainEncodingSpacedDouble/327...
149 BM_PlainEncodingSpacedBoolean/32768/1 270.760 MiB/sec 393.746 MiB/sec 45.422 {'run_name': 'BM_PlainEncodingSpacedBoolean/32...
75 BM_PlainDecodingSpacedDouble/32768/1 4.603 GiB/sec 5.475 GiB/sec 18.954 {'run_name': 'BM_PlainDecodingSpacedDouble/327...
> @ursabot benchmark --suite-filter=parquet-encoding-benchmark
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-648656865
This PR https://github.com/apache/arrow/pull/7532 add the 0.01% benchmark case, I can trigger a benchmark action if 7532 get merged.
Below is the results for 0.01% on my device.
Before
```
BM_PlainEncodingSpacedBoolean/32768/1 74766 ns 74685 ns 9348 bytes_per_second=418.427M/s null_percent=0.01
BM_PlainEncodingSpacedFloat/32768/1 29197 ns 29165 ns 23713 bytes_per_second=4.18549G/s null_percent=0.01
BM_PlainEncodingSpacedDouble/32768/1 31678 ns 31644 ns 22103 bytes_per_second=7.71528G/s null_percent=0.01
BM_PlainDecodingSpacedBoolean/32768/1 34833 ns 34796 ns 20109 bytes_per_second=898.088M/s null_percent=0.01
BM_PlainDecodingSpacedFloat/32768/1 21615 ns 21591 ns 32197 bytes_per_second=5.65367G/s null_percent=0.01
BM_PlainDecodingSpacedDouble/32768/1 24647 ns 24621 ns 28162 bytes_per_second=9.91599G/s null_percent=0.01
```
After
```
BM_PlainEncodingSpacedBoolean/32768/1 51807 ns 51745 ns 13489 bytes_per_second=603.926M/s null_percent=0.01
BM_PlainEncodingSpacedFloat/32768/1 7811 ns 7803 ns 84179 bytes_per_second=15.6441G/s null_percent=0.01
BM_PlainEncodingSpacedDouble/32768/1 13149 ns 13135 ns 49635 bytes_per_second=18.5867G/s null_percent=0.01
BM_PlainDecodingSpacedBoolean/32768/1 18332 ns 18313 ns 38127 bytes_per_second=1.66644G/s null_percent=0.01
BM_PlainDecodingSpacedFloat/32768/1 6634 ns 6627 ns 102921 bytes_per_second=18.4212G/s null_percent=0.01
BM_PlainDecodingSpacedDouble/32768/1 16183 ns 16165 ns 42532 bytes_per_second=15.1027G/s null_percent=0.01
```
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445249689
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scaned with BitBlockCounter
+ arrow::internal::BitBlockCounter data_counter(valid_bits, valid_bits_offset,
+ num_values - leading_bits);
+ auto current_block = data_counter.NextWord();
+ while (idx_src < num_values) {
+ if (current_block.AllSet()) { // All true values
+ int run_length = 0;
+ // Scan forward until a block that has some false values (or the end)
+ while (current_block.length > 0 && current_block.AllSet()) {
+ run_length += current_block.length;
+ current_block = data_counter.NextWord();
+ }
+ // Fill all valid values of this scan
+ std::memcpy(&output[num_valid_values], &src[idx_src], run_length * sizeof(T));
+ num_valid_values += run_length;
+ idx_src += run_length;
+ valid_bits_offset += run_length;
+ // The current_block already computed, advance to next loop
+ continue;
+ } else if (!current_block.NoneSet()) { // Some values are null
+ arrow::internal::BitmapReader valid_bits_reader(valid_bits, valid_bits_offset,
+ current_block.length);
+ for (int64_t i = 0; i < current_block.length; i++) {
+ if (valid_bits_reader.IsSet()) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_reader.Next();
+ }
+ valid_bits_offset += current_block.length;
+ } else { // All null values
+ idx_src += current_block.length;
+ valid_bits_offset += current_block.length;
+ }
+ current_block = data_counter.NextWord();
+ }
+
+ return num_valid_values;
+}
+
+/// \brief Expand the buffer but leave spaces for null entries.
+///
+/// \param[in, out] buffer the in-place buffer
+/// \param[in] num_values total size of buffer including null slots
+/// \param[in] null_count number of null slots
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \return The number of values expanded, including nulls.
+template <typename T>
+inline int SpacedExpand(T* buffer, int num_values, int null_count,
+ const uint8_t* valid_bits, int64_t valid_bits_offset) {
+ constexpr uint64_t kBatchSize = 64;
+ static_assert(kBatchSize == 64, "Invalid batch size, BitBlockCounter stick to 64");
+ constexpr uint64_t kBatchByteSize = kBatchSize / 8;
+
+ // Point to end as we add the spacing from the back.
+ int idx_decode = num_values - null_count - 1;
+ int idx_buffer = num_values - 1;
+ int64_t idx_valid_bits = valid_bits_offset + idx_buffer;
+
+ // Depending on the number of nulls, some of the value slots in buffer may
+ // be uninitialized, and this will cause valgrind warnings / potentially UB
+ std::memset(static_cast<void*>(&buffer[idx_decode + 1]), 0, null_count * sizeof(T));
Review comment:
/arrow/cpp/src/arrow/util/spaced.h:119:14: error: 'void* memset(void*, int, size_t)' clearing an object of non-trivial type 'struct parquet::ByteArray'; use assignment or value-initialization instead [-Werror=class-memaccess]
It get a error without the cast on "C GLib & Ruby / AMD64 Ubuntu 20.04 GLib & Ruby" job
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649911719
Okay, thanks. I think we can leave it as is
----------------------------------------------------------------
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
[GitHub] [arrow] github-actions[bot] commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-648648342
https://issues.apache.org/jira/browse/ARROW-9216
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649849609
+1, merging this. If removing the BitmapReader helps perf it can be done in a follow up PR
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445122603
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scaned with BitBlockCounter
Review comment:
typo: scanned
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scaned with BitBlockCounter
+ arrow::internal::BitBlockCounter data_counter(valid_bits, valid_bits_offset,
+ num_values - leading_bits);
+ auto current_block = data_counter.NextWord();
+ while (idx_src < num_values) {
+ if (current_block.AllSet()) { // All true values
+ int run_length = 0;
+ // Scan forward until a block that has some false values (or the end)
+ while (current_block.length > 0 && current_block.AllSet()) {
+ run_length += current_block.length;
+ current_block = data_counter.NextWord();
+ }
+ // Fill all valid values of this scan
+ std::memcpy(&output[num_valid_values], &src[idx_src], run_length * sizeof(T));
+ num_valid_values += run_length;
+ idx_src += run_length;
+ valid_bits_offset += run_length;
+ // The current_block already computed, advance to next loop
+ continue;
+ } else if (!current_block.NoneSet()) { // Some values are null
+ arrow::internal::BitmapReader valid_bits_reader(valid_bits, valid_bits_offset,
+ current_block.length);
+ for (int64_t i = 0; i < current_block.length; i++) {
+ if (valid_bits_reader.IsSet()) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_reader.Next();
+ }
+ valid_bits_offset += current_block.length;
+ } else { // All null values
+ idx_src += current_block.length;
+ valid_bits_offset += current_block.length;
+ }
+ current_block = data_counter.NextWord();
+ }
+
+ return num_valid_values;
+}
+
+/// \brief Expand the buffer but leave spaces for null entries.
Review comment:
Maybe "Relocate values in buffer into positions of non-null values as indicated by a validity bitmap"?
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scaned with BitBlockCounter
+ arrow::internal::BitBlockCounter data_counter(valid_bits, valid_bits_offset,
+ num_values - leading_bits);
+ auto current_block = data_counter.NextWord();
+ while (idx_src < num_values) {
+ if (current_block.AllSet()) { // All true values
+ int run_length = 0;
+ // Scan forward until a block that has some false values (or the end)
+ while (current_block.length > 0 && current_block.AllSet()) {
+ run_length += current_block.length;
+ current_block = data_counter.NextWord();
+ }
+ // Fill all valid values of this scan
+ std::memcpy(&output[num_valid_values], &src[idx_src], run_length * sizeof(T));
+ num_valid_values += run_length;
+ idx_src += run_length;
+ valid_bits_offset += run_length;
+ // The current_block already computed, advance to next loop
+ continue;
+ } else if (!current_block.NoneSet()) { // Some values are null
+ arrow::internal::BitmapReader valid_bits_reader(valid_bits, valid_bits_offset,
+ current_block.length);
+ for (int64_t i = 0; i < current_block.length; i++) {
+ if (valid_bits_reader.IsSet()) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_reader.Next();
+ }
+ valid_bits_offset += current_block.length;
+ } else { // All null values
+ idx_src += current_block.length;
+ valid_bits_offset += current_block.length;
+ }
+ current_block = data_counter.NextWord();
+ }
+
+ return num_valid_values;
+}
+
+/// \brief Expand the buffer but leave spaces for null entries.
+///
+/// \param[in, out] buffer the in-place buffer
+/// \param[in] num_values total size of buffer including null slots
+/// \param[in] null_count number of null slots
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \return The number of values expanded, including nulls.
+template <typename T>
+inline int SpacedExpand(T* buffer, int num_values, int null_count,
+ const uint8_t* valid_bits, int64_t valid_bits_offset) {
+ constexpr uint64_t kBatchSize = 64;
+ static_assert(kBatchSize == 64, "Invalid batch size, BitBlockCounter stick to 64");
+ constexpr uint64_t kBatchByteSize = kBatchSize / 8;
+
+ // Point to end as we add the spacing from the back.
+ int idx_decode = num_values - null_count - 1;
+ int idx_buffer = num_values - 1;
+ int64_t idx_valid_bits = valid_bits_offset + idx_buffer;
+
+ // Depending on the number of nulls, some of the value slots in buffer may
+ // be uninitialized, and this will cause valgrind warnings / potentially UB
+ std::memset(static_cast<void*>(&buffer[idx_decode + 1]), 0, null_count * sizeof(T));
Review comment:
is this `static_cast` needed?
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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.
Review comment:
I'm slightly ambivalent about having this code in a new header file, but it would make it easier to write unit tests for it, so I think it is OK
----------------------------------------------------------------
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
[GitHub] [arrow] wesm closed pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm closed pull request #7531:
URL: https://github.com/apache/arrow/pull/7531
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445569869
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,200 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scanned with BitBlockCounter
+ arrow::internal::BitBlockCounter data_counter(valid_bits, valid_bits_offset,
+ num_values - leading_bits);
+ auto current_block = data_counter.NextWord();
+ while (idx_src < num_values) {
+ if (current_block.AllSet()) { // All true values
+ int run_length = 0;
+ // Scan forward until a block that has some false values (or the end)
+ while (current_block.length > 0 && current_block.AllSet()) {
+ run_length += current_block.length;
+ current_block = data_counter.NextWord();
+ }
+ // Fill all valid values of this scan
+ std::memcpy(&output[num_valid_values], &src[idx_src], run_length * sizeof(T));
+ num_valid_values += run_length;
+ idx_src += run_length;
+ valid_bits_offset += run_length;
+ // The current_block already computed, advance to next loop
+ continue;
+ } else if (!current_block.NoneSet()) { // Some values are null
+ arrow::internal::BitmapReader valid_bits_reader(valid_bits, valid_bits_offset,
Review comment:
One question: is it actually beneficial to use `BitmapReader` here to process just a run of 64 bits? In other places where I have used BitBlockCounter, that it does not always help
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind edited a comment on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind edited a comment on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649198815
Here is the results: https://ci.ursalabs.org/#/builders/73/builds/90/steps/3/logs/result, not know why it not paste here, I see all 0.01% get positive results.
```
106 BM_PlainEncodingSpacedFloat/32768/1 2.355 GiB/sec 6.385 GiB/sec 171.068 {'run_name': 'BM_PlainEncodingSpacedFloat/3276...
80 BM_PlainDecodingSpacedFloat/32768/1 3.312 GiB/sec 8.534 GiB/sec 157.683 {'run_name': 'BM_PlainDecodingSpacedFloat/3276...
37 BM_PlainDecodingSpacedBoolean/32768/1 595.833 MiB/sec 1.035 GiB/sec 77.882 {'run_name': 'BM_PlainDecodingSpacedBoolean/32...
92 BM_PlainEncodingSpacedDouble/32768/1 3.834 GiB/sec 5.799 GiB/sec 51.278 {'run_name': 'BM_PlainEncodingSpacedDouble/327...
149 BM_PlainEncodingSpacedBoolean/32768/1 270.760 MiB/sec 393.746 MiB/sec 45.422 {'run_name': 'BM_PlainEncodingSpacedBoolean/32...
75 BM_PlainDecodingSpacedDouble/32768/1 4.603 GiB/sec 5.475 GiB/sec 18.954 {'run_name': 'BM_PlainDecodingSpacedDouble/327...
```
> @ursabot benchmark --suite-filter=parquet-encoding-benchmark
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649874368
> +1, merging this. If removing the BitmapReader helps perf it can be done in a follow up PR
Thanks. BitmapReader does help for the 1% and 50% null probability case, the initial implementation is directly using GetBit but I observe some regressions compared to the previous for my setup at least.
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649197066
@ursabot benchmark --suite-filter=parquet-encoding-benchmark --benchmark-filter=BM_Plain
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind edited a comment on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind edited a comment on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649198815
Here is the results: https://ci.ursalabs.org/#/builders/73/builds/90/steps/3/logs/result, not know why it not paste here, I see all 0.01% get positive results.
106 BM_PlainEncodingSpacedFloat/32768/1 2.355 GiB/sec 6.385 GiB/sec 171.068 {'run_name': 'BM_PlainEncodingSpacedFloat/3276...
80 BM_PlainDecodingSpacedFloat/32768/1 3.312 GiB/sec 8.534 GiB/sec 157.683 {'run_name': 'BM_PlainDecodingSpacedFloat/3276...
37 BM_PlainDecodingSpacedBoolean/32768/1 595.833 MiB/sec 1.035 GiB/sec 77.882 {'run_name': 'BM_PlainDecodingSpacedBoolean/32...
92 BM_PlainEncodingSpacedDouble/32768/1 3.834 GiB/sec 5.799 GiB/sec 51.278 {'run_name': 'BM_PlainEncodingSpacedDouble/327...
149 BM_PlainEncodingSpacedBoolean/32768/1 270.760 MiB/sec 393.746 MiB/sec 45.422 {'run_name': 'BM_PlainEncodingSpacedBoolean/32...
75 BM_PlainDecodingSpacedDouble/32768/1 4.603 GiB/sec 5.475 GiB/sec 18.954 {'run_name': 'BM_PlainDecodingSpacedDouble/327...
> @ursabot benchmark --suite-filter=parquet-encoding-benchmark
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445569869
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,200 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scanned with BitBlockCounter
+ arrow::internal::BitBlockCounter data_counter(valid_bits, valid_bits_offset,
+ num_values - leading_bits);
+ auto current_block = data_counter.NextWord();
+ while (idx_src < num_values) {
+ if (current_block.AllSet()) { // All true values
+ int run_length = 0;
+ // Scan forward until a block that has some false values (or the end)
+ while (current_block.length > 0 && current_block.AllSet()) {
+ run_length += current_block.length;
+ current_block = data_counter.NextWord();
+ }
+ // Fill all valid values of this scan
+ std::memcpy(&output[num_valid_values], &src[idx_src], run_length * sizeof(T));
+ num_valid_values += run_length;
+ idx_src += run_length;
+ valid_bits_offset += run_length;
+ // The current_block already computed, advance to next loop
+ continue;
+ } else if (!current_block.NoneSet()) { // Some values are null
+ arrow::internal::BitmapReader valid_bits_reader(valid_bits, valid_bits_offset,
Review comment:
One question: is it actually beneficial to use `BitmapReader` here to process just a run of 64 bits? In other places where I have used BitBlockCounter, I have observed it does not always help
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445281773
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scaned with BitBlockCounter
+ arrow::internal::BitBlockCounter data_counter(valid_bits, valid_bits_offset,
+ num_values - leading_bits);
+ auto current_block = data_counter.NextWord();
+ while (idx_src < num_values) {
+ if (current_block.AllSet()) { // All true values
+ int run_length = 0;
+ // Scan forward until a block that has some false values (or the end)
+ while (current_block.length > 0 && current_block.AllSet()) {
+ run_length += current_block.length;
+ current_block = data_counter.NextWord();
+ }
+ // Fill all valid values of this scan
+ std::memcpy(&output[num_valid_values], &src[idx_src], run_length * sizeof(T));
+ num_valid_values += run_length;
+ idx_src += run_length;
+ valid_bits_offset += run_length;
+ // The current_block already computed, advance to next loop
+ continue;
+ } else if (!current_block.NoneSet()) { // Some values are null
+ arrow::internal::BitmapReader valid_bits_reader(valid_bits, valid_bits_offset,
+ current_block.length);
+ for (int64_t i = 0; i < current_block.length; i++) {
+ if (valid_bits_reader.IsSet()) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_reader.Next();
+ }
+ valid_bits_offset += current_block.length;
+ } else { // All null values
+ idx_src += current_block.length;
+ valid_bits_offset += current_block.length;
+ }
+ current_block = data_counter.NextWord();
+ }
+
+ return num_valid_values;
+}
+
+/// \brief Expand the buffer but leave spaces for null entries.
+///
+/// \param[in, out] buffer the in-place buffer
+/// \param[in] num_values total size of buffer including null slots
+/// \param[in] null_count number of null slots
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \return The number of values expanded, including nulls.
+template <typename T>
+inline int SpacedExpand(T* buffer, int num_values, int null_count,
+ const uint8_t* valid_bits, int64_t valid_bits_offset) {
+ constexpr uint64_t kBatchSize = 64;
+ static_assert(kBatchSize == 64, "Invalid batch size, BitBlockCounter stick to 64");
+ constexpr uint64_t kBatchByteSize = kBatchSize / 8;
+
+ // Point to end as we add the spacing from the back.
+ int idx_decode = num_values - null_count - 1;
+ int idx_buffer = num_values - 1;
+ int64_t idx_valid_bits = valid_bits_offset + idx_buffer;
+
+ // Depending on the number of nulls, some of the value slots in buffer may
+ // be uninitialized, and this will cause valgrind warnings / potentially UB
+ std::memset(static_cast<void*>(&buffer[idx_decode + 1]), 0, null_count * sizeof(T));
Review comment:
Ah that's right. Thanks
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649147883
@ursabot benchmark --suite-filter=parquet-encoding-benchmark
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649548830
@jianxind I think the bot is broken right now because of the changes I recently made in ARROW-9201. @kszucs is going to update it
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445249248
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scaned with BitBlockCounter
+ arrow::internal::BitBlockCounter data_counter(valid_bits, valid_bits_offset,
+ num_values - leading_bits);
+ auto current_block = data_counter.NextWord();
+ while (idx_src < num_values) {
+ if (current_block.AllSet()) { // All true values
+ int run_length = 0;
+ // Scan forward until a block that has some false values (or the end)
+ while (current_block.length > 0 && current_block.AllSet()) {
+ run_length += current_block.length;
+ current_block = data_counter.NextWord();
+ }
+ // Fill all valid values of this scan
+ std::memcpy(&output[num_valid_values], &src[idx_src], run_length * sizeof(T));
+ num_valid_values += run_length;
+ idx_src += run_length;
+ valid_bits_offset += run_length;
+ // The current_block already computed, advance to next loop
+ continue;
+ } else if (!current_block.NoneSet()) { // Some values are null
+ arrow::internal::BitmapReader valid_bits_reader(valid_bits, valid_bits_offset,
+ current_block.length);
+ for (int64_t i = 0; i < current_block.length; i++) {
+ if (valid_bits_reader.IsSet()) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_reader.Next();
+ }
+ valid_bits_offset += current_block.length;
+ } else { // All null values
+ idx_src += current_block.length;
+ valid_bits_offset += current_block.length;
+ }
+ current_block = data_counter.NextWord();
+ }
+
+ return num_valid_values;
+}
+
+/// \brief Expand the buffer but leave spaces for null entries.
Review comment:
done, 3x
----------------------------------------------------------------
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
[GitHub] [arrow] wesm commented on pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
wesm commented on pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#issuecomment-649067717
Benchmark results
```
$ archery benchmark diff --cc=gcc-8 --cxx=g++-8 jianxind/BitBlockSpaced master --suite-filter=parquet-encoding
benchmark baseline contender change % counters
13 BM_PlainDecodingSpacedFloat/32768/1 6.454 GiB/sec 21.480 GiB/sec 232.838 {'iterations': 36805, 'null_percent': 0.01}
54 BM_PlainDecodingSpacedBoolean/32768/1 1.017 GiB/sec 2.031 GiB/sec 99.662 {'iterations': 23083, 'null_percent': 0.01}
53 BM_PlainDecodingSpacedFloat/32768/100 4.087 GiB/sec 6.490 GiB/sec 58.788 {'iterations': 23365, 'null_percent': 1.0}
118 BM_PlainDecodingSpacedDouble/32768/1 11.326 GiB/sec 17.696 GiB/sec 56.237 {'iterations': 32216, 'null_percent': 0.01}
134 BM_PlainDecodingSpacedBoolean/32768/100 755.399 MiB/sec 1.046 GiB/sec 41.803 {'iterations': 16687, 'null_percent': 1.0}
86 BM_PlainDecodingSpacedDouble/32768/100 7.654 GiB/sec 9.557 GiB/sec 24.864 {'iterations': 22049, 'null_percent': 1.0}
43 BM_PlainDecodingInt64/4096 44.856 GiB/sec 51.732 GiB/sec 15.329 {'iterations': 1199214}
56 BM_PlainEncodingFloat/32768 32.768 GiB/sec 36.879 GiB/sec 12.548 {'iterations': 163156}
45 BM_ByteStreamSplitEncode_Double_Sse2/4096 14.178 GiB/sec 15.697 GiB/sec 10.715 {'iterations': 323465}
140 BM_PlainDecodingSpacedBoolean/32768/5000 244.132 MiB/sec 267.167 MiB/sec 9.435 {'iterations': 5521, 'null_percent': 50.0}
98 BM_PlainDecodingFloat/4096 69.756 GiB/sec 75.939 GiB/sec 8.863 {'iterations': 3748990}
41 BM_PlainDecodingFloat/65536 53.684 GiB/sec 57.973 GiB/sec 7.988 {'iterations': 169375}
68 BM_PlainDecodingFloat/1024 37.061 GiB/sec 39.638 GiB/sec 6.955 {'iterations': 6855467}
131 BM_PlainEncodingInt64/32768 33.101 GiB/sec 34.982 GiB/sec 5.683 {'iterations': 87975}
42 BM_ArrowBinaryDict/EncodeLowLevel/262144 79.220 MiB/sec 83.540 MiB/sec 5.453 {'iterations': 36}
62 BM_PlainDecodingSpacedBoolean/32768/1000 520.545 MiB/sec 548.129 MiB/sec 5.299 {'iterations': 11926, 'null_percent': 10.0}
106 BM_ArrowBinaryPlain/EncodeLowLevel/1048576 779.964 MiB/sec 810.645 MiB/sec 3.934 {'iterations': 87}
20 BM_PlainDecodingDouble/1024 65.892 GiB/sec 68.154 GiB/sec 3.434 {'iterations': 6008229}
70 BM_PlainEncodingDouble/32768 31.926 GiB/sec 32.940 GiB/sec 3.176 {'iterations': 86995}
39 BM_ByteStreamSplitEncode_Double_Scalar/4096 2.652 GiB/sec 2.735 GiB/sec 3.151 {'iterations': 59682}
36 BM_PlainDecodingBoolean/1024 1.688 GiB/sec 1.737 GiB/sec 2.907 {'iterations': 1257476}
89 BM_ArrowBinaryDict/EncodeDictDirectInt32/1048576 322.964m items/sec 331.200m items/sec 2.550 {'iterations': 219}
30 BM_ArrowBinaryDict/DecodeArrowNonNull_Dict/4096 204.031 MiB/sec 208.917 MiB/sec 2.395 {'iterations': 5959}
146 BM_ByteStreamSplitEncode_Double_Sse2/32768 15.496 GiB/sec 15.845 GiB/sec 2.256 {'iterations': 44572}
60 BM_PlainDecodingInt64/1024 66.471 GiB/sec 67.795 GiB/sec 1.992 {'iterations': 6157194}
82 BM_ByteStreamSplitEncode_Double_Sse2/65536 14.740 GiB/sec 15.025 GiB/sec 1.933 {'iterations': 21204}
38 BM_ByteStreamSplitEncode_Float_Scalar/65536 20.023 GiB/sec 20.406 GiB/sec 1.913 {'iterations': 57636}
59 BM_DictDecodingInt64_repeats/1024 9.453 GiB/sec 9.629 GiB/sec 1.859 {'iterations': 871513}
44 BM_ByteStreamSplitEncode_Double_Sse2/1024 16.284 GiB/sec 16.576 GiB/sec 1.790 {'iterations': 1520871}
55 BM_PlainEncodingFloat/4096 15.822 GiB/sec 16.072 GiB/sec 1.584 {'iterations': 679740}
92 BM_PlainDecodingFloat/32768 57.401 GiB/sec 58.299 GiB/sec 1.564 {'iterations': 287174}
108 BM_DictDecodingInt64_repeats/4096 21.266 GiB/sec 21.595 GiB/sec 1.544 {'iterations': 484804}
128 BM_PlainDecodingInt64/65536 44.749 GiB/sec 45.350 GiB/sec 1.342 {'iterations': 68450}
72 BM_DictDecodingInt64_literals/65536 4.270 GiB/sec 4.327 GiB/sec 1.329 {'iterations': 6096}
147 BM_PlainEncodingFloat/1024 18.627 GiB/sec 18.869 GiB/sec 1.301 {'iterations': 3439664}
69 BM_DictDecodingInt64_literals/32768 4.835 GiB/sec 4.895 GiB/sec 1.244 {'iterations': 13930}
35 BM_PlainDecodingBoolean/4096 2.043 GiB/sec 2.067 GiB/sec 1.212 {'iterations': 379465}
97 BM_ArrowBinaryPlain/DecodeArrow_Dict/65536 166.085 MiB/sec 167.946 MiB/sec 1.121 {'iterations': 308}
84 BM_DictDecodingInt64_repeats/65536 47.758 GiB/sec 48.238 GiB/sec 1.005 {'iterations': 68893}
116 BM_PlainEncodingSpacedDouble/32768/5000 1.757 GiB/sec 1.774 GiB/sec 0.970 {'iterations': 5070, 'null_percent': 50.0}
77 BM_ArrowBinaryPlain/EncodeLowLevel/262144 854.734 MiB/sec 862.980 MiB/sec 0.965 {'iterations': 397}
104 BM_ByteStreamSplitEncode_Float_Scalar/32768 20.175 GiB/sec 20.366 GiB/sec 0.945 {'iterations': 115548}
50 BM_PlainEncodingInt64/4096 20.325 GiB/sec 20.513 GiB/sec 0.923 {'iterations': 454433}
91 BM_ByteStreamSplitDecode_Float_Scalar/65536 32.834 GiB/sec 33.107 GiB/sec 0.832 {'iterations': 95337}
101 BM_ByteStreamSplitEncode_Float_Sse2/32768 16.479 GiB/sec 16.615 GiB/sec 0.827 {'iterations': 95125}
151 BM_ArrowBinaryDict/DecodeArrow_Dense/32768 309.512 MiB/sec 312.007 MiB/sec 0.806 {'iterations': 1164}
16 BM_ByteStreamSplitDecode_Double_Sse2/1024 22.033 GiB/sec 22.206 GiB/sec 0.784 {'iterations': 2027621}
34 BM_ArrowBinaryPlain/DecodeArrow_Dense/32768 493.753 MiB/sec 497.441 MiB/sec 0.747 {'iterations': 1831}
136 BM_DictDecodingInt64_literals/4096 4.299 GiB/sec 4.330 GiB/sec 0.739 {'iterations': 99329}
5 BM_ByteStreamSplitDecode_Float_Scalar/32768 32.904 GiB/sec 33.114 GiB/sec 0.637 {'iterations': 189504}
58 BM_ArrowBinaryDict/EncodeArrow/262144 183.613 MiB/sec 184.761 MiB/sec 0.625 {'iterations': 86}
142 BM_ByteStreamSplitEncode_Float_Sse2/65536 16.559 GiB/sec 16.662 GiB/sec 0.622 {'iterations': 47855}
87 BM_PlainDecodingSpacedDouble/32768/5000 2.004 GiB/sec 2.016 GiB/sec 0.613 {'iterations': 5753, 'null_percent': 50.0}
4 BM_ArrowBinaryDict/DecodeArrowNonNull_Dense/65536 309.087 MiB/sec 310.879 MiB/sec 0.580 {'iterations': 575}
14 BM_PlainEncodingFloatNaN/1024 18.795 GiB/sec 18.898 GiB/sec 0.548 {'iterations': 3453780}
125 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dict/32768 173.753 MiB/sec 174.668 MiB/sec 0.526 {'iterations': 652}
0 BM_ByteStreamSplitDecode_Double_Scalar/1024 21.766 GiB/sec 21.877 GiB/sec 0.511 {'iterations': 1998483}
107 BM_ArrowBinaryPlain/DecodeArrow_Dict/32768 173.680 MiB/sec 174.563 MiB/sec 0.508 {'iterations': 649}
85 BM_ArrowBinaryDict/EncodeDictDirectInt8/1048576 342.024m items/sec 343.464m items/sec 0.421 {'iterations': 229}
153 BM_ByteStreamSplitDecode_Float_Sse2/4096 32.889 GiB/sec 33.024 GiB/sec 0.412 {'iterations': 1508692}
73 BM_PlainEncodingSpacedBoolean/32768/5000 225.228 MiB/sec 226.116 MiB/sec 0.395 {'iterations': 5037, 'null_percent': 50.0}
105 BM_ArrowBinaryDict/EncodeDictDirectInt64/1048576 314.653m items/sec 315.890m items/sec 0.393 {'iterations': 211}
115 BM_PlainEncodingSpacedFloat/32768/5000 1.049 GiB/sec 1.053 GiB/sec 0.392 {'iterations': 5980, 'null_percent': 50.0}
71 BM_ByteStreamSplitDecode_Float_Scalar/1024 32.845 GiB/sec 32.973 GiB/sec 0.388 {'iterations': 6024469}
127 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dense/32768 495.518 MiB/sec 497.376 MiB/sec 0.375 {'iterations': 1855}
139 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dense/1024 590.236 MiB/sec 592.265 MiB/sec 0.344 {'iterations': 67136}
130 BM_PlainEncodingDouble/4096 20.150 GiB/sec 20.216 GiB/sec 0.330 {'iterations': 449390}
66 BM_ByteStreamSplitDecode_Float_Scalar/4096 32.849 GiB/sec 32.957 GiB/sec 0.329 {'iterations': 1498630}
141 BM_DictDecodingInt64_repeats/32768 44.815 GiB/sec 44.949 GiB/sec 0.299 {'iterations': 130536}
137 BM_ByteStreamSplitEncode_Double_Scalar/65536 2.494 GiB/sec 2.501 GiB/sec 0.297 {'iterations': 3614}
57 BM_PlainEncodingSpacedDouble/32768/1 5.908 GiB/sec 5.922 GiB/sec 0.249 {'iterations': 16769, 'null_percent': 0.01}
126 BM_PlainEncodingSpacedBoolean/32768/1000 364.196 MiB/sec 365.048 MiB/sec 0.234 {'iterations': 8197, 'null_percent': 10.0}
51 BM_PlainEncodingSpacedBoolean/32768/1 453.309 MiB/sec 454.304 MiB/sec 0.220 {'iterations': 10193, 'null_percent': 0.01}
102 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dense/65536 495.031 MiB/sec 496.033 MiB/sec 0.202 {'iterations': 929}
61 BM_ArrowBinaryDict/DecodeArrowNonNull_Dense/32768 310.510 MiB/sec 311.068 MiB/sec 0.180 {'iterations': 1161}
10 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dict/1024 214.300 MiB/sec 214.655 MiB/sec 0.165 {'iterations': 24231}
117 BM_ArrowBinaryPlain/DecodeArrow_Dict/4096 198.115 MiB/sec 198.427 MiB/sec 0.158 {'iterations': 5783}
95 BM_PlainEncodingBoolean/4096 543.998 MiB/sec 544.838 MiB/sec 0.154 {'iterations': 97718}
24 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dict/65536 168.164 MiB/sec 168.401 MiB/sec 0.141 {'iterations': 312}
121 BM_PlainEncodingDoubleNaN/4096 20.174 GiB/sec 20.202 GiB/sec 0.139 {'iterations': 450606}
27 BM_ByteStreamSplitDecode_Float_Sse2/65536 33.132 GiB/sec 33.178 GiB/sec 0.138 {'iterations': 94247}
133 BM_ByteStreamSplitEncode_Float_Scalar/1024 24.168 GiB/sec 24.177 GiB/sec 0.035 {'iterations': 4446965}
6 BM_PlainEncodingBoolean/32768 596.062 MiB/sec 596.237 MiB/sec 0.029 {'iterations': 13404}
96 BM_PlainEncodingSpacedDouble/32768/10000 7.418 GiB/sec 7.419 GiB/sec 0.021 {'iterations': 21200, 'null_percent': 100.0}
135 BM_ArrowBinaryDict/DecodeArrowNonNull_Dense/1024 310.727 MiB/sec 310.710 MiB/sec -0.005 {'iterations': 34918}
122 BM_ByteStreamSplitDecode_Float_Sse2/32768 33.030 GiB/sec 33.026 GiB/sec -0.011 {'iterations': 189236}
52 BM_ByteStreamSplitEncode_Float_Sse2/4096 16.513 GiB/sec 16.511 GiB/sec -0.012 {'iterations': 747372}
124 BM_ArrowBinaryDict/DecodeArrow_Dict/32768 171.177 MiB/sec 171.154 MiB/sec -0.013 {'iterations': 642}
143 BM_ByteStreamSplitEncode_Double_Scalar/1024 4.131 GiB/sec 4.130 GiB/sec -0.023 {'iterations': 381360}
31 BM_ArrowBinaryPlain/EncodeArrow/262144 885.335 MiB/sec 885.024 MiB/sec -0.035 {'iterations': 409}
138 BM_ArrowBinaryDict/EncodeArrow/1048576 134.899 MiB/sec 134.798 MiB/sec -0.075 {'iterations': 16}
152 BM_ByteStreamSplitDecode_Double_Sse2/32768 22.145 GiB/sec 22.128 GiB/sec -0.078 {'iterations': 63135}
94 BM_ArrowBinaryPlain/EncodeArrow/1048576 876.931 MiB/sec 876.138 MiB/sec -0.090 {'iterations': 95}
74 BM_ByteStreamSplitEncode_Float_Scalar/4096 24.337 GiB/sec 24.312 GiB/sec -0.101 {'iterations': 1121800}
17 BM_PlainEncodingSpacedBoolean/32768/100 438.626 MiB/sec 438.161 MiB/sec -0.106 {'iterations': 9917, 'null_percent': 1.0}
23 BM_ByteStreamSplitDecode_Double_Scalar/4096 21.969 GiB/sec 21.937 GiB/sec -0.150 {'iterations': 505480}
29 BM_PlainEncodingBoolean/1024 504.137 MiB/sec 503.353 MiB/sec -0.155 {'iterations': 361267}
81 BM_ByteStreamSplitDecode_Double_Scalar/32768 22.123 GiB/sec 22.086 GiB/sec -0.166 {'iterations': 63356}
79 BM_ArrowBinaryPlain/DecodeArrow_Dense/4096 520.530 MiB/sec 519.569 MiB/sec -0.185 {'iterations': 15019}
90 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dict/4096 199.653 MiB/sec 199.277 MiB/sec -0.188 {'iterations': 5811}
18 BM_ArrowBinaryPlain/DecodeArrow_Dense/65536 498.511 MiB/sec 497.274 MiB/sec -0.248 {'iterations': 914}
63 BM_PlainEncodingSpacedFloat/32768/1000 2.666 GiB/sec 2.659 GiB/sec -0.252 {'iterations': 15101, 'null_percent': 10.0}
48 BM_PlainEncodingInt64/1024 30.345 GiB/sec 30.257 GiB/sec -0.289 {'iterations': 2794982}
111 BM_ArrowBinaryDict/EncodeDictDirectInt16/1048576 338.836m items/sec 337.803m items/sec -0.305 {'iterations': 226}
103 BM_PlainEncodingSpacedBoolean/32768/10000 1.000 GiB/sec 1021.065 MiB/sec -0.317 {'iterations': 22965, 'null_percent': 100.0}
150 BM_ByteStreamSplitEncode_Float_Sse2/1024 16.595 GiB/sec 16.541 GiB/sec -0.327 {'iterations': 3050527}
12 BM_PlainEncodingSpacedFloat/32768/10000 5.810 GiB/sec 5.791 GiB/sec -0.336 {'iterations': 33204, 'null_percent': 100.0}
11 BM_ArrowBinaryDict/DecodeArrow_Dense/65536 312.305 MiB/sec 311.195 MiB/sec -0.355 {'iterations': 578}
28 BM_PlainDecodingSpacedFloat/32768/10000 79.580 GiB/sec 79.296 GiB/sec -0.356 {'iterations': 458065, 'null_percent': 100.0}
93 BM_ArrowBinaryPlain/DecodeArrow_Dict/1024 215.777 MiB/sec 214.937 MiB/sec -0.389 {'iterations': 24328}
80 BM_ByteStreamSplitDecode_Double_Sse2/4096 22.091 GiB/sec 22.004 GiB/sec -0.394 {'iterations': 500794}
132 BM_ArrowBinaryDict/DecodeArrowNonNull_Dict/32768 171.185 MiB/sec 170.464 MiB/sec -0.421 {'iterations': 623}
3 BM_ByteStreamSplitEncode_Double_Scalar/32768 2.721 GiB/sec 2.709 GiB/sec -0.448 {'iterations': 7746}
120 BM_PlainEncodingSpacedDouble/32768/100 5.647 GiB/sec 5.621 GiB/sec -0.464 {'iterations': 16212, 'null_percent': 1.0}
15 BM_ArrowBinaryDict/DecodeArrow_Dict/4096 209.894 MiB/sec 208.845 MiB/sec -0.500 {'iterations': 6147}
21 BM_PlainEncodingBoolean/65536 595.729 MiB/sec 592.693 MiB/sec -0.510 {'iterations': 6697}
47 BM_DictDecodingInt64_literals/1024 3.542 GiB/sec 3.522 GiB/sec -0.556 {'iterations': 327036}
119 BM_ArrowBinaryDict/DecodeArrow_Dict/65536 164.846 MiB/sec 163.849 MiB/sec -0.605 {'iterations': 307}
78 BM_ArrowBinaryDict/DecodeArrow_Dense/1024 310.727 MiB/sec 308.787 MiB/sec -0.625 {'iterations': 35078}
26 BM_ByteStreamSplitDecode_Double_Scalar/65536 20.801 GiB/sec 20.662 GiB/sec -0.669 {'iterations': 29838}
19 BM_ArrowBinaryDict/DecodeArrowNonNull_Dict/65536 164.506 MiB/sec 163.383 MiB/sec -0.683 {'iterations': 303}
88 BM_ArrowBinaryDict/DecodeArrow_Dense/4096 310.023 MiB/sec 307.740 MiB/sec -0.736 {'iterations': 9095}
110 BM_ArrowBinaryDict/DecodeArrowNonNull_Dense/4096 311.762 MiB/sec 309.284 MiB/sec -0.795 {'iterations': 9143}
46 BM_PlainEncodingSpacedFloat/32768/100 4.379 GiB/sec 4.341 GiB/sec -0.867 {'iterations': 24903, 'null_percent': 1.0}
7 BM_PlainDecodingBoolean/65536 2.240 GiB/sec 2.218 GiB/sec -0.954 {'iterations': 25698}
8 BM_PlainEncodingSpacedFloat/32768/1 4.626 GiB/sec 4.578 GiB/sec -1.038 {'iterations': 26300, 'null_percent': 0.01}
32 BM_PlainDecodingBoolean/32768 2.220 GiB/sec 2.194 GiB/sec -1.177 {'iterations': 51255}
65 BM_ArrowBinaryPlain/DecodeArrowNonNull_Dense/4096 524.685 MiB/sec 518.404 MiB/sec -1.197 {'iterations': 15267}
67 BM_ArrowBinaryPlain/DecodeArrow_Dense/1024 592.952 MiB/sec 585.688 MiB/sec -1.225 {'iterations': 66383}
112 BM_PlainEncodingSpacedDouble/32768/1000 4.107 GiB/sec 4.054 GiB/sec -1.296 {'iterations': 11810, 'null_percent': 10.0}
113 BM_PlainEncodingDouble/1024 33.612 GiB/sec 33.138 GiB/sec -1.409 {'iterations': 3017380}
114 BM_PlainEncodingFloatNaN/65536 34.860 GiB/sec 34.317 GiB/sec -1.557 {'iterations': 93962}
144 BM_ByteStreamSplitDecode_Double_Sse2/65536 20.713 GiB/sec 20.338 GiB/sec -1.810 {'iterations': 29081}
83 BM_PlainEncodingDoubleNaN/1024 33.634 GiB/sec 32.997 GiB/sec -1.893 {'iterations': 3089434}
64 BM_PlainEncodingFloatNaN/4096 16.108 GiB/sec 15.785 GiB/sec -2.006 {'iterations': 705993}
25 BM_PlainDecodingSpacedFloat/32768/5000 1020.468 MiB/sec 991.261 MiB/sec -2.862 {'iterations': 5772, 'null_percent': 50.0}
100 BM_ArrowBinaryDict/DecodeArrow_Dict/1024 226.059 MiB/sec 218.945 MiB/sec -3.147 {'iterations': 25619}
123 BM_ByteStreamSplitDecode_Float_Sse2/1024 33.199 GiB/sec 32.024 GiB/sec -3.540 {'iterations': 6102624}
22 BM_PlainEncodingFloatNaN/32768 38.946 GiB/sec 37.443 GiB/sec -3.860 {'iterations': 195749}
33 BM_ArrowBinaryDict/DecodeArrowNonNull_Dict/1024 228.006 MiB/sec 218.889 MiB/sec -3.998 {'iterations': 25756}
9 BM_PlainDecodingSpacedDouble/32768/1000 4.933 GiB/sec 4.723 GiB/sec -4.263 {'iterations': 14081, 'null_percent': 10.0}
149 BM_PlainDecodingInt64/32768 55.800 GiB/sec 52.971 GiB/sec -5.069 {'iterations': 170631}
148 BM_PlainDecodingSpacedFloat/32768/1000 2.621 GiB/sec 2.484 GiB/sec -5.247 {'iterations': 15106, 'null_percent': 10.0}
2 BM_ArrowBinaryDict/EncodeLowLevel/1048576 65.921 MiB/sec 61.856 MiB/sec -6.167 {'iterations': 6}
40 BM_PlainDecodingDouble/4096 50.510 GiB/sec 46.935 GiB/sec -7.078 {'iterations': 1161577}
129 BM_PlainDecodingDouble/65536 46.146 GiB/sec 42.608 GiB/sec -7.667 {'iterations': 68650}
145 BM_PlainDecodingSpacedBoolean/32768/10000 160.761 GiB/sec 147.677 GiB/sec -8.139 {'iterations': 3551935, 'null_percent': 100.0}
49 BM_PlainEncodingDoubleNaN/65536 34.456 GiB/sec 31.483 GiB/sec -8.629 {'iterations': 43904}
99 BM_PlainEncodingDoubleNaN/32768 35.494 GiB/sec 32.291 GiB/sec -9.023 {'iterations': 83973}
109 BM_PlainEncodingInt64/65536 34.301 GiB/sec 30.722 GiB/sec -10.434 {'iterations': 44474}
1 BM_PlainDecodingSpacedDouble/32768/10000 75.319 GiB/sec 67.322 GiB/sec -10.617 {'iterations': 209081, 'null_percent': 100.0}
75 BM_PlainEncodingFloat/65536 35.393 GiB/sec 31.288 GiB/sec -11.598 {'iterations': 92008}
37 BM_PlainEncodingDouble/65536 36.333 GiB/sec 31.845 GiB/sec -12.352 {'iterations': 46380}
76 BM_PlainDecodingDouble/32768 57.959 GiB/sec 47.187 GiB/sec -18.587 {'iterations': 154296}
```
----------------------------------------------------------------
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
[GitHub] [arrow] jianxind commented on a change in pull request #7531: ARROW-9216: [C++] Use BitBlockCounter for plain spaced encoding/decoding
Posted by GitBox <gi...@apache.org>.
jianxind commented on a change in pull request #7531:
URL: https://github.com/apache/arrow/pull/7531#discussion_r445249183
##########
File path: cpp/src/arrow/util/spaced.h
##########
@@ -0,0 +1,199 @@
+// 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 "arrow/util/align_util.h"
+#include "arrow/util/bit_block_counter.h"
+#include "arrow/util/bitmap_reader.h"
+
+namespace arrow {
+namespace util {
+namespace internal {
+
+/// \brief Compress the buffer to spaced, excluding the null entries.
+///
+/// \param[in] src the source buffer
+/// \param[in] num_values the size of source buffer
+/// \param[in] valid_bits bitmap data indicating position of valid slots
+/// \param[in] valid_bits_offset offset into valid_bits
+/// \param[out] output the output buffer spaced
+/// \return The size of spaced buffer.
+template <typename T>
+inline int SpacedCompress(const T* src, int num_values, const uint8_t* valid_bits,
+ int64_t valid_bits_offset, T* output) {
+ int num_valid_values = 0;
+ int idx_src = 0;
+
+ const auto p =
+ arrow::internal::BitmapWordAlign<1>(valid_bits, valid_bits_offset, num_values);
+ // First handle the leading bits
+ const int leading_bits = static_cast<int>(p.leading_bits);
+ while (idx_src < leading_bits) {
+ if (BitUtil::GetBit(valid_bits, valid_bits_offset)) {
+ output[num_valid_values] = src[idx_src];
+ num_valid_values++;
+ }
+ idx_src++;
+ valid_bits_offset++;
+ }
+
+ // The aligned parts scaned with BitBlockCounter
Review comment:
done
----------------------------------------------------------------
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