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/07 03:12:29 UTC
[GitHub] [arrow] guyuqi opened a new pull request #7121: ARROW-8633: [C++] Add ValidateAscii function
guyuqi opened a new pull request #7121:
URL: https://github.com/apache/arrow/pull/7121
The patch is to implement ValidateAscii function.
The benchmark and test facilities are also added.
### The benchmark on x86:
**Original:**
```
Run on (20 X 3000 MHz CPU s)
CPU Caches:
L1 Data 32K (x10)
L1 Instruction 32K (x10)
L2 Unified 256K (x10)
L3 Unified 25600K (x1)
Load Average: 4.79, 5.63, 2.68
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------------
ValidateTinyAscii 2.39 ns 2.39 ns 276349157 bytes_per_second=3.8964G/s
ValidateTinyNonAscii 8.21 ns 8.21 ns 85421905 bytes_per_second=1.24781G/s
ValidateSmallAscii 10.9 ns 10.9 ns 65497418 bytes_per_second=11.6721G/s
ValidateSmallAlmostAscii 46.1 ns 46.1 ns 15204522 bytes_per_second=2.99142G/s
ValidateSmallNonAscii 84.6 ns 84.6 ns 8303767 bytes_per_second=1.47429G/s
ValidateLargeAscii 4997 ns 4997 ns 136960 bytes_per_second=18.6385G/s
ValidateLargeAlmostAscii 30575 ns 30575 ns 22651 bytes_per_second=3.04752G/s
ValidateLargeNonAscii 73714 ns 73713 ns 9385 bytes_per_second=1.26467G/s
```
**Enable simd**
```
Run on (20 X 3000 MHz CPU s)
CPU Caches:
L1 Data 32K (x10)
L1 Instruction 32K (x10)
L2 Unified 256K (x10)
L3 Unified 25600K (x1)
Load Average: 4.79, 5.63, 2.68
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------------
ValidateTinyAscii 6.36 ns 6.36 ns 100259371 bytes_per_second=1.46438G/s
ValidateTinyNonAscii 11.3 ns 11.3 ns 61604638 bytes_per_second=926.575M/s
ValidateSmallAscii 9.74 ns 9.74 ns 71987411 bytes_per_second=13.0987G/s
ValidateSmallAlmostAscii 51.1 ns 51.1 ns 13677942 bytes_per_second=2.69774G/s
ValidateSmallNonAscii 84.5 ns 84.5 ns 8135065 bytes_per_second=1.47735G/s
ValidateLargeAscii 2363 ns 2363 ns 298863 bytes_per_second=39.4107G/s
ValidateLargeAlmostAscii 31006 ns 31006 ns 22642 bytes_per_second=3.00508G/s
ValidateLargeNonAscii 76222 ns 76222 ns 8703 bytes_per_second=1.22305G/s
```
### The benchmark on Arm64
**Original:**
```
Run on (46 X 2600 MHz CPU s)
Load Average: 0.19, 0.66, 1.73
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------------
ValidateTinyAscii 14.7 ns 14.7 ns 47461698 bytes_per_second=646.682M/s
ValidateTinyNonAscii 48.0 ns 48.0 ns 14576733 bytes_per_second=218.46M/s
ValidateSmallAscii 109 ns 109 ns 6404395 bytes_per_second=1.1667G/s
ValidateSmallAlmostAscii 275 ns 275 ns 2544737 bytes_per_second=513.185M/s
ValidateSmallNonAscii 555 ns 555 ns 1261830 bytes_per_second=230.408M/s
ValidateLargeAscii 78511 ns 78502 ns 8915 bytes_per_second=1.18649G/s
ValidateLargeAlmostAscii 179928 ns 179907 ns 3891 bytes_per_second=530.347M/s
ValidateLargeNonAscii 415107 ns 415058 ns 1686 bytes_per_second=229.994M/s
```
**Enable simd**
```
Run on (46 X 2600 MHz CPU s)
Load Average: 0.19, 0.66, 1.73
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations UserCounters...
-----------------------------------------------------------------------------------
ValidateTinyAscii 65.9 ns 65.9 ns 10597823 bytes_per_second=144.749M/s
ValidateTinyNonAscii 48.0 ns 48.0 ns 14584553 bytes_per_second=218.732M/s
ValidateSmallAscii 83.7 ns 83.7 ns 8367346 bytes_per_second=1.52478G/s
ValidateSmallAlmostAscii 275 ns 275 ns 2542186 bytes_per_second=512.498M/s
ValidateSmallNonAscii 555 ns 555 ns 1261774 bytes_per_second=230.301M/s
ValidateLargeAscii 3109 ns 3108 ns 225186 bytes_per_second=29.9637G/s
ValidateLargeAlmostAscii 179998 ns 179974 ns 3889 bytes_per_second=530.149M/s
ValidateLargeNonAscii 414228 ns 414181 ns 1691 bytes_per_second=230.481M/s
```
`ValidateLargeAscii` case will get performance boost when leveraging simd:
- x86: `18.6385G/s -> 39.4107G/s`
- Arm64: `1.18649G/s -> 29.9637G/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] guyuqi commented on a change in pull request #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
guyuqi commented on a change in pull request #7121:
URL: https://github.com/apache/arrow/pull/7121#discussion_r429709020
##########
File path: cpp/src/arrow/util/utf8.h
##########
@@ -171,6 +172,99 @@ inline bool ValidateUTF8(const util::string_view& str) {
return ValidateUTF8(data, length);
}
+inline bool ValidateAsciiSw(const uint8_t* data, int64_t len) {
+ uint8_t orall = 0;
+
+ if (len >= 16) {
+ uint64_t or1 = 0, or2 = 0;
+ const uint8_t* data2 = data + 8;
+
+ do {
+ or1 |= *(const uint64_t*)data;
+ or2 |= *(const uint64_t*)data2;
+ data += 16;
+ data2 += 16;
+ len -= 16;
+ } while (len >= 16);
+
+ orall = !((or1 | or2) & 0x8080808080808080ULL) - 1;
+ }
+
+ while (len--) orall |= *data++;
Review comment:
Thanks, @wesm !
----------------------------------------------------------------
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] guyuqi commented on a change in pull request #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
guyuqi commented on a change in pull request #7121:
URL: https://github.com/apache/arrow/pull/7121#discussion_r422628358
##########
File path: cpp/src/arrow/util/utf8_util_benchmark.cc
##########
@@ -70,16 +70,44 @@ static void BenchmarkUTF8Validation(
state.SetBytesProcessed(state.iterations() * s.size());
}
+static void BenchmarkASCIIValidation(
+ benchmark::State& state, // NOLINT non-const reference
+ const std::string& s, bool expected) {
+ auto data = reinterpret_cast<const uint8_t*>(s.data());
+ auto data_size = static_cast<int64_t>(s.size());
+
+ InitializeUTF8();
+#if defined(ARROW_HAVE_NEON) || defined(ARROW_HAVE_SSE4_2)
Review comment:
Yup, it makes sense.
The PR was updated, thanks for your comments.
----------------------------------------------------------------
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 #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #7121:
URL: https://github.com/apache/arrow/pull/7121#issuecomment-625005075
https://issues.apache.org/jira/browse/ARROW-8633
----------------------------------------------------------------
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 #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
wesm commented on pull request #7121:
URL: https://github.com/apache/arrow/pull/7121#issuecomment-633346288
@guyuqi thanks for this, I plan to use it to provide ASCII validation for string kernels that can only handle ASCII inputs
----------------------------------------------------------------
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] kiszk commented on a change in pull request #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
kiszk commented on a change in pull request #7121:
URL: https://github.com/apache/arrow/pull/7121#discussion_r422498790
##########
File path: cpp/src/arrow/util/utf8_util_benchmark.cc
##########
@@ -70,16 +70,44 @@ static void BenchmarkUTF8Validation(
state.SetBytesProcessed(state.iterations() * s.size());
}
+static void BenchmarkASCIIValidation(
+ benchmark::State& state, // NOLINT non-const reference
+ const std::string& s, bool expected) {
+ auto data = reinterpret_cast<const uint8_t*>(s.data());
+ auto data_size = static_cast<int64_t>(s.size());
+
+ InitializeUTF8();
+#if defined(ARROW_HAVE_NEON) || defined(ARROW_HAVE_SSE4_2)
Review comment:
How about calling a single function `ValidateAscii` at caller side? Then, the function calls simd or non-simd function based on ifdef. It makes code simple by reducing the number of the repetition `#if defined(ARROW_HAVE_NEON) || defined(ARROW_HAVE_SSE4_2) ...`.
[Here](https://github.com/apache/arrow/blob/master/cpp/src/arrow/util/byte_stream_split.h#L614-L622) is an example.
----------------------------------------------------------------
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 #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
wesm commented on a change in pull request #7121:
URL: https://github.com/apache/arrow/pull/7121#discussion_r429672945
##########
File path: cpp/src/arrow/util/utf8.h
##########
@@ -171,6 +172,99 @@ inline bool ValidateUTF8(const util::string_view& str) {
return ValidateUTF8(data, length);
}
+inline bool ValidateAsciiSw(const uint8_t* data, int64_t len) {
+ uint8_t orall = 0;
+
+ if (len >= 16) {
+ uint64_t or1 = 0, or2 = 0;
+ const uint8_t* data2 = data + 8;
+
+ do {
+ or1 |= *(const uint64_t*)data;
+ or2 |= *(const uint64_t*)data2;
+ data += 16;
+ data2 += 16;
+ len -= 16;
+ } while (len >= 16);
+
+ orall = !((or1 | or2) & 0x8080808080808080ULL) - 1;
+ }
+
+ while (len--) orall |= *data++;
Review comment:
nit: braces
##########
File path: cpp/src/arrow/util/utf8.h
##########
@@ -171,6 +172,99 @@ inline bool ValidateUTF8(const util::string_view& str) {
return ValidateUTF8(data, length);
}
+inline bool ValidateAsciiSw(const uint8_t* data, int64_t len) {
+ uint8_t orall = 0;
+
+ if (len >= 16) {
+ uint64_t or1 = 0, or2 = 0;
+ const uint8_t* data2 = data + 8;
+
+ do {
+ or1 |= *(const uint64_t*)data;
+ or2 |= *(const uint64_t*)data2;
+ data += 16;
+ data2 += 16;
+ len -= 16;
+ } while (len >= 16);
+
+ orall = !((or1 | or2) & 0x8080808080808080ULL) - 1;
+ }
+
+ while (len--) orall |= *data++;
+
+ if (orall < 0x80)
+ return true;
+ else
+ return false;
+}
+
+#ifdef ARROW_HAVE_NEON
+inline bool ValidateAsciiSimd(const uint8_t* data, int64_t len) {
+ if (len >= 32) {
+ const uint8_t* data2 = data + 16;
+ uint8x16_t or1 = vdupq_n_u8(0), or2 = or1;
+
+ while (len >= 32) {
+ const uint8x16_t input1 = vld1q_u8(data);
+ const uint8x16_t input2 = vld1q_u8(data2);
+
+ or1 = vorrq_u8(or1, input1);
+ or2 = vorrq_u8(or2, input2);
+
+ data += 32;
+ data2 += 32;
+ len -= 32;
+ }
+
+ or1 = vorrq_u8(or1, or2);
+ if (vmaxvq_u8(or1) >= 0x80) return false;
+ }
+
+ return ValidateAsciiSw(data, len);
+}
+#endif // ARROW_HAVE_NEON
+
+#if defined(ARROW_HAVE_SSE4_2)
+inline bool ValidateAsciiSimd(const uint8_t* data, int64_t len) {
+ if (len >= 32) {
+ const uint8_t* data2 = data + 16;
+ __m128i or1 = _mm_set1_epi8(0), or2 = or1;
+
+ while (len >= 32) {
+ __m128i input1 = _mm_lddqu_si128((const __m128i*)data);
+ __m128i input2 = _mm_lddqu_si128((const __m128i*)data2);
+
+ or1 = _mm_or_si128(or1, input1);
+ or2 = _mm_or_si128(or2, input2);
+
+ data += 32;
+ data2 += 32;
+ len -= 32;
+ }
+
+ or1 = _mm_or_si128(or1, or2);
+ if (_mm_movemask_epi8(_mm_cmplt_epi8(or1, _mm_set1_epi8(0)))) return false;
Review comment:
braces
##########
File path: cpp/src/arrow/util/utf8.h
##########
@@ -171,6 +172,99 @@ inline bool ValidateUTF8(const util::string_view& str) {
return ValidateUTF8(data, length);
}
+inline bool ValidateAsciiSw(const uint8_t* data, int64_t len) {
+ uint8_t orall = 0;
+
+ if (len >= 16) {
+ uint64_t or1 = 0, or2 = 0;
+ const uint8_t* data2 = data + 8;
+
+ do {
+ or1 |= *(const uint64_t*)data;
+ or2 |= *(const uint64_t*)data2;
+ data += 16;
+ data2 += 16;
+ len -= 16;
+ } while (len >= 16);
+
+ orall = !((or1 | or2) & 0x8080808080808080ULL) - 1;
+ }
+
+ while (len--) orall |= *data++;
+
+ if (orall < 0x80)
+ return true;
+ else
+ return false;
Review comment:
braces
----------------------------------------------------------------
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 #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
wesm closed pull request #7121:
URL: https://github.com/apache/arrow/pull/7121
----------------------------------------------------------------
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 #7121: ARROW-8633: [C++] Add ValidateAscii function
Posted by GitBox <gi...@apache.org>.
wesm commented on pull request #7121:
URL: https://github.com/apache/arrow/pull/7121#issuecomment-625432981
Aside from the particular implementation details, having an ASCII validation function would be useful to me (and can be turned into an array function, too), so would like to see this functionality in the repo
----------------------------------------------------------------
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