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 2022/10/29 16:31:37 UTC
[GitHub] [arrow] kshitij12345 opened a new pull request, #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
kshitij12345 opened a new pull request, #14550:
URL: https://github.com/apache/arrow/pull/14550
Implements `binary_slice_bytes` similar to `utf8_slice_codeunits`.
TODO:
* [ ] Tests
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1314890254
@pitrou PTAL :)
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021548927
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
+ binary_slice_bytes_doc);
+ for (const auto& ty : BaseBinaryTypes()) {
Review Comment:
Thanks! The updated code only works with `binary` types.
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
pitrou commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021552048
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
+ binary_slice_bytes_doc);
+ for (const auto& ty : BaseBinaryTypes()) {
Review Comment:
Ok, please ping me when this is ready for review again.
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021554672
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
+ binary_slice_bytes_doc);
+ for (const auto& ty : BaseBinaryTypes()) {
Review Comment:
The PR is ready for review. Have updated the tests to include non-ascii characters and updated the function names.
Except for `R` related testing comment, PR is ready.
(Also will open an issue on JIRA soon)
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] ursabot commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
ursabot commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1315638487
Benchmark runs are scheduled for baseline = 4daf94587d2aac1ee23cea6e94cc99a06512f84a and contender = 058d4f697a06477539e7f9ccf3e7c035f8cfbc5e. 058d4f697a06477539e7f9ccf3e7c035f8cfbc5e is a master commit associated with this PR. Results will be available as each benchmark for each run completes.
Conbench compare runs links:
[Finished :arrow_down:0.0% :arrow_up:0.0%] [ec2-t3-xlarge-us-east-2](https://conbench.ursa.dev/compare/runs/f6d1d58aab834369a92d81cc7f9b214c...5c0a3f2a2a85475c931f1b312c8c18a4/)
[Finished :arrow_down:0.41% :arrow_up:0.0%] [test-mac-arm](https://conbench.ursa.dev/compare/runs/07a5f38130044fc7bbe9afa93869e88c...86cdd7c882994d5b97e8d99d7fbc12ad/)
[Finished :arrow_down:0.27% :arrow_up:0.0%] [ursa-i9-9960x](https://conbench.ursa.dev/compare/runs/a088651a685c4d5ea27dd83191d578a3...7c78d028620b43569d82df04af299d8f/)
[Finished :arrow_down:1.55% :arrow_up:0.0%] [ursa-thinkcentre-m75q](https://conbench.ursa.dev/compare/runs/8bff798b77c4414dad5985d3d350e2c1...eac7f5035a464e7d85d06f61f07aa97f/)
Buildkite builds:
[Finished] [`058d4f69` ec2-t3-xlarge-us-east-2](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-ec2-t3-xlarge-us-east-2/builds/1866)
[Finished] [`058d4f69` test-mac-arm](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-test-mac-arm/builds/1888)
[Finished] [`058d4f69` ursa-i9-9960x](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-ursa-i9-9960x/builds/1855)
[Finished] [`058d4f69` ursa-thinkcentre-m75q](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-ursa-thinkcentre-m75q/builds/1880)
[Finished] [`4daf9458` ec2-t3-xlarge-us-east-2](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-ec2-t3-xlarge-us-east-2/builds/1865)
[Finished] [`4daf9458` test-mac-arm](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-test-mac-arm/builds/1887)
[Finished] [`4daf9458` ursa-i9-9960x](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-ursa-i9-9960x/builds/1854)
[Finished] [`4daf9458` ursa-thinkcentre-m75q](https://buildkite.com/apache-arrow/arrow-bci-benchmark-on-ursa-thinkcentre-m75q/builds/1879)
Supported benchmarks:
ec2-t3-xlarge-us-east-2: Supported benchmark langs: Python, R. Runs only benchmarks with cloud = True
test-mac-arm: Supported benchmark langs: C++, Python, R
ursa-i9-9960x: Supported benchmark langs: Python, R, JavaScript
ursa-thinkcentre-m75q: Supported benchmark langs: C++, Java
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
pitrou commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021552449
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
+ binary_slice_bytes_doc);
+ for (const auto& ty : BaseBinaryTypes()) {
Review Comment:
Yes, I think you can open an issue about `binary_replace_slice`.
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou merged pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
pitrou merged PR #14550:
URL: https://github.com/apache/arrow/pull/14550
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1305513770
Gentle ping @AlenkaF @jorisvandenbossche :)
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
pitrou commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1019355193
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
Review Comment:
```suggestion
"Slice binary string",
```
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
Review Comment:
I think `binary_slice` is explanatory enough.
##########
cpp/src/arrow/compute/kernels/scalar_string_test.cc:
##########
@@ -2119,6 +2119,96 @@ TYPED_TEST(TestStringKernels, SliceCodeunitsNegPos) {
#endif // ARROW_WITH_UTF8PROC
+TYPED_TEST(TestBaseBinaryKernels, SliceBytesBasic) {
+ SliceOptions options{2, 4};
+ this->CheckUnary("binary_slice_bytes", R"(["foo", "fo", null, "foo "])", this->type(),
+ R"(["o", "", null, "o "])", &options);
+
+ // end is beyond 0, but before start (hence empty)
+ SliceOptions options_edgecase_1{-3, 1};
+ this->CheckUnary("binary_slice_bytes", R"(["foods"])", this->type(), R"([""])",
+ &options_edgecase_1);
+
+ // this is a safeguard agains an optimization path possible, but actually a tricky case
+ SliceOptions options_edgecase_2{-6, -2};
+ this->CheckUnary("binary_slice_bytes", R"(["foods"])", this->type(), R"(["foo"])",
+ &options_edgecase_2);
+
+ auto input = ArrayFromJSON(this->type(), R"(["foods"])");
+ EXPECT_RAISES_WITH_MESSAGE_THAT(
+ Invalid,
+ testing::HasSubstr(
+ "Function 'binary_slice_bytes' cannot be called without options"),
+ CallFunction("binary_slice_bytes", {input}));
+
+ SliceOptions options_invalid{2, 4, 0};
+ EXPECT_RAISES_WITH_MESSAGE_THAT(
+ Invalid, testing::HasSubstr("Slice step cannot be zero"),
+ CallFunction("binary_slice_bytes", {input}, &options_invalid));
+}
+
+TYPED_TEST(TestBaseBinaryKernels, SliceBytesPosPos) {
+ SliceOptions options{2, 4};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
+ this->type(), R"(["", "", "", "o", "od", "od"])", &options);
+ SliceOptions options_step{1, 5, 2};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
+ this->type(), R"(["", "", "o", "o", "od", "od"])", &options_step);
+ SliceOptions options_step_neg{5, 1, -2};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
+ this->type(), R"(["", "", "", "o", "d", "so"])", &options_step_neg);
+ options_step_neg.stop = 0;
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food","foods"])",
+ this->type(), R"(["", "", "o", "o", "do", "so"])", &options_step_neg);
+}
+
+TYPED_TEST(TestBaseBinaryKernels, SliceBytesPosNeg) {
+ SliceOptions options{2, -1};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
Review Comment:
These tests would be better without any letter repetition in the source values. Otherwise the results might end up correct even with an incorrect implementation.
##########
r/src/compute.cpp:
##########
@@ -449,7 +449,7 @@ std::shared_ptr<arrow::compute::FunctionOptions> make_compute_options(
return std::make_shared<Options>(cpp11::as_cpp<std::string>(options["characters"]));
}
- if (func_name == "utf8_slice_codeunits") {
+ if (func_name == "utf8_slice_codeunits" || func_name == "binary_slice_bytes") {
Review Comment:
Should a test be created on the R side?
@thisisnic @paleolimbot Perhaps one of you can help.
##########
python/pyarrow/tests/test_compute.py:
##########
@@ -536,6 +537,24 @@ def test_slice_compatibility():
start, stop, step) == result
+def test_binary_slice_compatibility():
+ arr = pa.array((el.encode('ascii')
+ for el in ["", "a", "ab", "abc", "abcd", "abcde"]))
Review Comment:
Can write this in more idiomatic way. Also, it's nicer with some non-ASCII data:
```suggestion
arr = pa.array([b"", b"a", b"a\xff", b"a\xffc", b"a\xffcd", b"a\xffcde"])
```
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
Review Comment:
```suggestion
// and therefore we also need this
```
##########
cpp/src/arrow/compute/kernels/scalar_string_test.cc:
##########
@@ -2119,6 +2119,96 @@ TYPED_TEST(TestStringKernels, SliceCodeunitsNegPos) {
#endif // ARROW_WITH_UTF8PROC
+TYPED_TEST(TestBaseBinaryKernels, SliceBytesBasic) {
+ SliceOptions options{2, 4};
+ this->CheckUnary("binary_slice_bytes", R"(["foo", "fo", null, "foo "])", this->type(),
+ R"(["o", "", null, "o "])", &options);
+
+ // end is beyond 0, but before start (hence empty)
+ SliceOptions options_edgecase_1{-3, 1};
+ this->CheckUnary("binary_slice_bytes", R"(["foods"])", this->type(), R"([""])",
+ &options_edgecase_1);
+
+ // this is a safeguard agains an optimization path possible, but actually a tricky case
+ SliceOptions options_edgecase_2{-6, -2};
+ this->CheckUnary("binary_slice_bytes", R"(["foods"])", this->type(), R"(["foo"])",
+ &options_edgecase_2);
+
+ auto input = ArrayFromJSON(this->type(), R"(["foods"])");
+ EXPECT_RAISES_WITH_MESSAGE_THAT(
+ Invalid,
+ testing::HasSubstr(
+ "Function 'binary_slice_bytes' cannot be called without options"),
+ CallFunction("binary_slice_bytes", {input}));
+
+ SliceOptions options_invalid{2, 4, 0};
+ EXPECT_RAISES_WITH_MESSAGE_THAT(
+ Invalid, testing::HasSubstr("Slice step cannot be zero"),
+ CallFunction("binary_slice_bytes", {input}, &options_invalid));
+}
+
+TYPED_TEST(TestBaseBinaryKernels, SliceBytesPosPos) {
+ SliceOptions options{2, 4};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
+ this->type(), R"(["", "", "", "o", "od", "od"])", &options);
+ SliceOptions options_step{1, 5, 2};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
+ this->type(), R"(["", "", "o", "o", "od", "od"])", &options_step);
+ SliceOptions options_step_neg{5, 1, -2};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
+ this->type(), R"(["", "", "", "o", "d", "so"])", &options_step_neg);
+ options_step_neg.stop = 0;
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food","foods"])",
+ this->type(), R"(["", "", "o", "o", "do", "so"])", &options_step_neg);
+}
+
+TYPED_TEST(TestBaseBinaryKernels, SliceBytesPosNeg) {
+ SliceOptions options{2, -1};
+ this->CheckUnary("binary_slice_bytes", R"(["", "f", "fo", "foo", "food", "foods"])",
Review Comment:
Also, it would be nice to put some non-ASCII bytes in there as well, to check that slicing is really byte-wise.
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
Review Comment:
```suggestion
("For each binary string in `strings`, emit the substring defined by\n"
```
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] paleolimbot commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
paleolimbot commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021685149
##########
r/src/compute.cpp:
##########
@@ -449,7 +449,7 @@ std::shared_ptr<arrow::compute::FunctionOptions> make_compute_options(
return std::make_shared<Options>(cpp11::as_cpp<std::string>(options["characters"]));
}
- if (func_name == "utf8_slice_codeunits") {
+ if (func_name == "utf8_slice_codeunits" || func_name == "binary_slice") {
Review Comment:
I made ARROW-18321 and self-assigned 🙂
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
pitrou commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021545816
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
+ binary_slice_bytes_doc);
+ for (const auto& ty : BaseBinaryTypes()) {
Review Comment:
@kshitij12345 I agree with that.
For the record, currently it's a bit of a mixed bag: `binary_reverse` doesn't support string input, but `binary_replace_slice` can... and can produce invalid output, for example:
```python
>>> pc.binary_replace_slice(["hé"], 1, 2, "x")
<pyarrow.lib.StringArray object at 0x7fdbc09937c0>
[
"hx�"
]
>>> pc.binary_replace_slice(["hé"], 1, 2, "x").validate(full=True)
Traceback (most recent call last):
...
ArrowInvalid: Invalid UTF8 sequence at string index 0
```
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1295893049
https://issues.apache.org/jira/browse/ARROW-17301
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1009064077
##########
cpp/src/arrow/compute/kernels/scalar_string_test.cc:
##########
@@ -2119,6 +2119,96 @@ TYPED_TEST(TestStringKernels, SliceCodeunitsNegPos) {
#endif // ARROW_WITH_UTF8PROC
+TYPED_TEST(TestBaseBinaryKernels, SliceBytesBasic) {
Review Comment:
Inspired from `utf8_slice_codeunits` tests
https://github.com/apache/arrow/blob/884e81bf2ffd410cbffac9727b94617532c8d915/cpp/src/arrow/compute/kernels/scalar_string_test.cc#L2013
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1009064514
##########
python/pyarrow/tests/test_compute.py:
##########
@@ -536,6 +537,24 @@ def test_slice_compatibility():
start, stop, step) == result
+def test_binary_slice_compatibility():
Review Comment:
Inspired from `utf8_slice_codeunits` test
https://github.com/apache/arrow/blob/884e81bf2ffd410cbffac9727b94617532c8d915/python/pyarrow/tests/test_compute.py#L525-L537
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] AlenkaF commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
AlenkaF commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1305873429
Thank you for the PR @kshitij12345!
@pitrou @rok would you mind having a look at this 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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
pitrou commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021566058
##########
r/src/compute.cpp:
##########
@@ -449,7 +449,7 @@ std::shared_ptr<arrow::compute::FunctionOptions> make_compute_options(
return std::make_shared<Options>(cpp11::as_cpp<std::string>(options["characters"]));
}
- if (func_name == "utf8_slice_codeunits") {
+ if (func_name == "utf8_slice_codeunits" || func_name == "binary_slice") {
Review Comment:
@rok @AlenkaF Would one of you have to time to help @kshitij12345 write some R test here?
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1295893057
:warning: Ticket **has not been started in JIRA**, please click 'Start Progress'.
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1296264889
cc: @AlenkaF @jorisvandenbossche
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on PR #14550:
URL: https://github.com/apache/arrow/pull/14550#issuecomment-1310599207
@pitrou Thanks for the review. Will address them over the weekend.
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1020725816
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
+ binary_slice_bytes_doc);
+ for (const auto& ty : BaseBinaryTypes()) {
Review Comment:
I don't think Binary Slice should support UTF-8 strings as slicing them incorrectly will return invalid UTF-8 string
Eg. `\"\xc2\xa2\"` slicing this [0:1] will return ``\"\xc2\"` which is invalid UTF.
I think this should just support Binary types. Wdyt @pitrou ?
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] kshitij12345 commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
kshitij12345 commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021551561
##########
cpp/src/arrow/compute/kernels/scalar_string_ascii.cc:
##########
@@ -2409,6 +2409,172 @@ void AddAsciiStringReplaceSlice(FunctionRegistry* registry) {
DCHECK_OK(registry->AddFunction(std::move(func)));
}
+// ----------------------------------------------------------------------
+// Slice
+
+namespace {
+struct SliceBytesTransform : StringSliceTransformBase {
+ int64_t MaxCodeunits(int64_t ninputs, int64_t input_bytes) override {
+ const SliceOptions& opt = *this->options;
+ if ((opt.start >= 0) != (opt.stop >= 0)) {
+ // If start and stop don't have the same sign, we can't guess an upper bound
+ // on the resulting slice lengths, so return a worst case estimate.
+ return input_bytes;
+ }
+ int64_t max_slice_bytes = (opt.stop - opt.start + opt.step - 1) / opt.step;
+ return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
+ }
+
+ int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
+ if (options->step >= 1) {
+ return SliceForward(input, input_string_bytes, output);
+ }
+ return SliceBackward(input, input_string_bytes, output);
+ }
+
+ int64_t SliceForward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in forward order (step > 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced;
+ const uint8_t* end_sliced;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+ // First, compute begin_sliced and end_sliced
+ if (opt.start >= 0) {
+ // start counting from the left
+ begin_sliced = std::min(begin + opt.start, end);
+ if (opt.stop > opt.start) {
+ // continue counting from begin_sliced
+ const int64_t length = opt.stop - opt.start;
+ end_sliced = std::min(begin_sliced + length, end);
+ } else if (opt.stop < 0) {
+ // from the end
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ } else {
+ // start counting from the right
+ begin_sliced = std::max(end + opt.start, begin);
+ if (opt.stop > 0) {
+ // continue counting from the left, we cannot start from begin_sliced because we
+ // don't know how many bytes are between begin and begin_sliced
+ end_sliced = std::min(begin + opt.stop, end);
+ // and therefore we also needs this
+ if (end_sliced <= begin_sliced) {
+ // zero length slice
+ return 0;
+ }
+ } else if ((opt.stop < 0) && (opt.stop > opt.start)) {
+ // stop is negative, but larger than start, so we count again from the right
+ // in some cases we can optimize this, depending on the shortest path (from end
+ // or begin_sliced), but begin_sliced and opt.start can be 'out of sync',
+ // for instance when start=-100, when the string length is only 10.
+ end_sliced = std::max(end + opt.stop, begin_sliced);
+ } else {
+ // zero length slice
+ return 0;
+ }
+ }
+
+ // Second, copy computed slice to output
+ DCHECK(begin_sliced <= end_sliced);
+ if (opt.step == 1) {
+ // fast case, where we simply can finish with a memcpy
+ std::copy(begin_sliced, end_sliced, output);
+ return end_sliced - begin_sliced;
+ }
+
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+
+ while (i < end_sliced) {
+ *dest = *i;
+ // skip step codeunits
+ i += opt.step;
+ dest++;
+ }
+ return dest - output;
+ }
+
+ int64_t SliceBackward(const uint8_t* input, int64_t input_string_bytes,
+ uint8_t* output) {
+ // Slice in reverse order (step < 0)
+ const SliceOptions& opt = *this->options;
+ const uint8_t* begin = input;
+ const uint8_t* end = input + input_string_bytes;
+ const uint8_t* begin_sliced = begin;
+ const uint8_t* end_sliced = end;
+
+ if (!input_string_bytes) {
+ return 0;
+ }
+
+ if (opt.start >= 0) {
+ // +1 because begin_sliced acts as as the end of a reverse iterator
+ begin_sliced = std::min(begin + opt.start + 1, end);
+ } else {
+ // -1 because start=-1 means the last byte, which is 0 advances
+ begin_sliced = std::max(end + opt.start + 1, begin);
+ }
+ begin_sliced--;
+
+ // similar to opt.start
+ if (opt.stop >= 0) {
+ end_sliced = std::min(begin + opt.stop + 1, end);
+ } else {
+ end_sliced = std::max(end + opt.stop + 1, begin);
+ }
+ end_sliced--;
+
+ // Copy computed slice to output
+ uint8_t* dest = output;
+ const uint8_t* i = begin_sliced;
+ while (i > end_sliced) {
+ // write a single codepoint
+ *dest = *i;
+ // and skip the remainder
+ i += opt.step;
+ dest++;
+ }
+
+ return dest - output;
+ }
+};
+
+template <typename Type>
+using SliceBytes = StringTransformExec<Type, SliceBytesTransform>;
+
+} // namespace
+
+const FunctionDoc binary_slice_bytes_doc(
+ "Slice string",
+ ("For each string in `strings`, emit the substring defined by\n"
+ "(`start`, `stop`, `step`) as given by `SliceOptions` where `start` is\n"
+ "inclusive and `stop` is exclusive. All three values are measured in\n"
+ "bytes.\n"
+ "If `step` is negative, the string will be advanced in reversed order.\n"
+ "An error is raised if `step` is zero.\n"
+ "Null inputs emit null."),
+ {"strings"}, "SliceOptions", /*options_required=*/true);
+
+void AddAsciiStringSlice(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("binary_slice_bytes", Arity::Unary(),
+ binary_slice_bytes_doc);
+ for (const auto& ty : BaseBinaryTypes()) {
Review Comment:
Also, I think `binary_replace_slice` should only work with `binary` types (as there is `utf8_replace_slice` for string types). And if user wants to actually play with byte data then they must manually cast it to that.
Probably worth an issue?
--
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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] paleolimbot commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
paleolimbot commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021630921
##########
r/src/compute.cpp:
##########
@@ -449,7 +449,7 @@ std::shared_ptr<arrow::compute::FunctionOptions> make_compute_options(
return std::make_shared<Options>(cpp11::as_cpp<std::string>(options["characters"]));
}
- if (func_name == "utf8_slice_codeunits") {
+ if (func_name == "utf8_slice_codeunits" || func_name == "binary_slice") {
Review Comment:
Sorry I missed this ping on Thursday...I'm happy to do this but it's slightly easier to do on a separate 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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a diff in pull request #14550: ARROW-17301: [C++] Implement compute function "binary_slice"
Posted by GitBox <gi...@apache.org>.
pitrou commented on code in PR #14550:
URL: https://github.com/apache/arrow/pull/14550#discussion_r1021663802
##########
r/src/compute.cpp:
##########
@@ -449,7 +449,7 @@ std::shared_ptr<arrow::compute::FunctionOptions> make_compute_options(
return std::make_shared<Options>(cpp11::as_cpp<std::string>(options["characters"]));
}
- if (func_name == "utf8_slice_codeunits") {
+ if (func_name == "utf8_slice_codeunits" || func_name == "binary_slice") {
Review Comment:
It's ok for me if done on a separate 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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org