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/05/27 03:24:15 UTC
[GitHub] [arrow] cyb70289 opened a new pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
cyb70289 opened a new pull request #7285:
URL: https://github.com/apache/arrow/pull/7285
Unaligned bitmap comparision are currently processed bit-by-bit.
Comparing word-by-word in uint64 improves performance significantly.
Bechmark(comparing two identical bitmaps with 64K bits) jumps from
86M/s to 5.7G/s on my test machine.
NOTE: This patch may hurt performance if two bitmaps differ at the very
begining bits, as it always loads and compares 64 bits if possible. Bit
by bit comparison will notice the difference and return false earlier.
This should not be a problem in practice.
----------------------------------------------------------------
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 #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
wesm commented on a change in pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#discussion_r433296037
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
Review comment:
https://google.github.io/styleguide/cppguide.html
We indeed use snake_case for member accessors (this used to be the guidance in the Google C++ style guide but they might have made some changes).
----------------------------------------------------------------
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] cyb70289 commented on a change in pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on a change in pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#discussion_r433027819
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
+ if (nwords > 1) {
+ bit_length -= (nwords - 1) * 64;
+
+ uint64_t left_word0 = BitUtil::ToLittleEndian(util::SafeLoadAs<uint64_t>(left));
+ uint64_t right_word0 = BitUtil::ToLittleEndian(util::SafeLoadAs<uint64_t>(right));
+
+ do {
Review comment:
Done. Much cleaner code after refinement. Thanks.
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
+ if (nwords > 1) {
+ bit_length -= (nwords - 1) * 64;
+
+ uint64_t left_word0 = BitUtil::ToLittleEndian(util::SafeLoadAs<uint64_t>(left));
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
[GitHub] [arrow] fsaintjacques commented on a change in pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
fsaintjacques commented on a change in pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#discussion_r432527849
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
Review comment:
Use snake_case for variables, e.g. `n_words`.
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
+ if (nwords > 1) {
+ bit_length -= (nwords - 1) * 64;
+
+ uint64_t left_word0 = BitUtil::ToLittleEndian(util::SafeLoadAs<uint64_t>(left));
+ uint64_t right_word0 = BitUtil::ToLittleEndian(util::SafeLoadAs<uint64_t>(right));
+
+ do {
Review comment:
Make a shift lambda:
```
auto shift = [](uint64_t word, uint64_t next, uint8_t shift) -> uint64_t {
if (shift == 0) return word;
return (word >> shift) | (next << (64 - shift);
};
auto next = load_word(left);
auto left_word = shift(left_word0, next, left_offset);
left_word0 = next;
```
I'd also think it would be worth transforming the loop into a fixed for-loop.
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
+ if (nwords > 1) {
+ bit_length -= (nwords - 1) * 64;
+
+ uint64_t left_word0 = BitUtil::ToLittleEndian(util::SafeLoadAs<uint64_t>(left));
Review comment:
It would be more readable if you wrap load into a lambda. The compiler will inline it.
```c++
auto load_word = [](uint8_t* bytes) { return BitUtil::ToLittleEndian(util::SafeLoadAs<uint64_t>(bytes)); }
auto left_word0 = load_word(left);
auto right_word0 = load_word(right);
```
----------------------------------------------------------------
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] fsaintjacques closed pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
fsaintjacques closed pull request #7285:
URL: https://github.com/apache/arrow/pull/7285
----------------------------------------------------------------
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] fsaintjacques edited a comment on pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
fsaintjacques edited a comment on pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#issuecomment-637034980
----------------------------------------------------------------
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] fsaintjacques commented on pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
fsaintjacques commented on pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#issuecomment-635953947
> NOTE: This patch may hurt performance if two bitmaps differ at the very
> begining bits, as it always loads and compares 64 bits if possible. Bit
> by bit comparison will notice the difference and return false earlier.
> This should not be a problem in practice.
This should be negligible in practice. The processor still load in unit of words.
----------------------------------------------------------------
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 #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
wesm commented on a change in pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#discussion_r433296380
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
Review comment:
FWIW I think `nwords` is fine, we use `nbytes` in plenty of places.
----------------------------------------------------------------
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 #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#issuecomment-634390288
https://issues.apache.org/jira/browse/ARROW-8843
----------------------------------------------------------------
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] cyb70289 commented on pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#issuecomment-634555761
Before (apply only benchmark code)
```
BitmapEqualsWithoutOffset/8192 195 ns 195 ns 3618366 bytes_per_second=39.1055G/s
BitmapEqualsWithOffset/8192 91272 ns 91235 ns 7673 bytes_per_second=85.6307M/s
```
After
```
BitmapEqualsWithoutOffset/8192 193 ns 193 ns 3635971 bytes_per_second=39.6261G/s
BitmapEqualsWithOffset/8192 1332 ns 1331 ns 510343 bytes_per_second=5.73058G/s
----------------------------------------------------------------
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] fsaintjacques commented on pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
fsaintjacques commented on pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#issuecomment-637034980
@cyb70289 Thank for this. For future reference, if you add a new benchmark, do it first as a seperate commit, and then add the improvement in a following (chronologically) second commit. You'll be able to check the difference with ursabot, e.g. `... benchmark [filter] <sha_of_first_commit>`.
----------------------------------------------------------------
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] cyb70289 commented on a change in pull request #7285: ARROW-8843: [C++] Compare bitmaps in words
Posted by GitBox <gi...@apache.org>.
cyb70289 commented on a change in pull request #7285:
URL: https://github.com/apache/arrow/pull/7285#discussion_r433019772
##########
File path: cpp/src/arrow/util/bit_util.cc
##########
@@ -246,6 +246,49 @@ bool BitmapEquals(const uint8_t* left, int64_t left_offset, const uint8_t* right
}
// Unaligned slow case
+ left += left_offset / 8;
+ right += right_offset / 8;
+ left_offset %= 8;
+ right_offset %= 8;
+
+ // process in 64 bits
+ int64_t nwords = bit_length / 64;
Review comment:
Thank you. Will change.
A quick question, is there formal doc for arrow C++ coding style?
I see class names are camel case.
Most variables are snake case, with [some exceptions](https://github.com/apache/arrow/blob/f0ed8e2343569047204c5c1a0a24e379c0d23c30/cpp/src/arrow/util/bit_util.h#L890).
Most function names are camel case, with [some exceptions](https://github.com/apache/arrow/blob/f0ed8e2343569047204c5c1a0a24e379c0d23c30/cpp/src/arrow/util/bit_util.h#L503)(simple getter should be snake case?)
----------------------------------------------------------------
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