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/09/25 11:59:43 UTC
[GitHub] [arrow] maartenbreddels opened a new pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
maartenbreddels opened a new pull request #8271:
URL: https://github.com/apache/arrow/pull/8271
Contains:
* split_pattern kernel with max_split and reverse option
* split_whitespace_ascii similar to Python's bytes.split
* split_whitespace_utf8 similar to Python's str.split
It should be easy to add new split methods, e.g. a regex one in the future.
This PR mostly done, except for:
* Expose the options/kernels to Python, like done in #7593
* There is 1 test commented out, because it fails for unknown reasons:
```c++
this->CheckUnary("split_pattern", R"(["foo bar", "foo", null])", this->list_type(),
R"([["foo", "bar"], ["foo"], null])", &options);
```
Fails with the following output:
```
Failed:
Got:
[
[
[
"foo",
"bar"
]
],
[
[
"foo"
],
null
]
]
Expected:
[
[
[
"foo",
"bar"
]
],
[
[
"foo"
],
null
]
]
```
It seems the test framework does not consider these equal, possibly due to the null value.
This also raised a question: Should both the list entry *and* the string array entry have a missing/null value if the input string contains a null value? I think it should because if we ask for the underlying string array, and the string value that the missing list entry points to is not a missing value, it will be an empty string, which seems odd to me.
In the code, I've commented out the null_builder, instead of removing it, for reviewing, enabling it also does not pass the unit test (that was commented out).
Similar to `match_substring`, the kernel `split_pattern` could also be executed on BinaryArray's, but I'm not sure what the proper way is to make this work. Instantiating new templates would increase the binary size, so maybe there is a smarter way to do this. And possibly this should be done in a different PR, together with `match_substring`.
cc @TomAugspurger
Related #8231
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500950247
##########
File path: cpp/src/arrow/compute/kernels/scalar_string_benchmark.cc
##########
@@ -66,6 +66,11 @@ static void MatchSubstring(benchmark::State& state) {
UnaryStringBenchmark(state, "match_substring", &options);
}
+static void SplitPattern(benchmark::State& state) {
+ SplitPatternOptions options("abac");
+ UnaryStringBenchmark(state, "split_pattern", &options);
Review comment:
I've changed the pattern to "a", which is more meaningful for a true benchmark. But I use these as a sanity check if there aren't and major performance issues after refactoring, so I'd like to keep this in.
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500867702
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
Review comment:
done https://issues.apache.org/jira/browse/ARROW-10208
----------------------------------------------------------------
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] maartenbreddels commented on pull request #8271: ARROW-9991: [C++] Split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-712319882
Thanks for the reviews Antoine!
----------------------------------------------------------------
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] pitrou closed pull request #8271: ARROW-9991: [C++] Split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou closed pull request #8271:
URL: https://github.com/apache/arrow/pull/8271
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500266219
##########
File path: python/pyarrow/compute.py
##########
@@ -253,6 +255,68 @@ def match_substring(array, pattern):
MatchSubstringOptions(pattern))
+def split_pattern(array, pattern, max_splits=-1, reverse=False):
Review comment:
No, it should work with direct keyword arguments. See https://github.com/apache/arrow/blob/master/python/pyarrow/tests/test_compute.py#L233-L260 for a test.
----------------------------------------------------------------
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] jorisvandenbossche commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
jorisvandenbossche commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r497492333
##########
File path: python/pyarrow/compute.py
##########
@@ -253,6 +255,68 @@ def match_substring(array, pattern):
MatchSubstringOptions(pattern))
+def split_pattern(array, pattern, max_splits=-1, reverse=False):
+ """
+ Replace string by a list of strings, separated by *pattern*.
+
+ Parameters
+ ----------
+ array : pyarrow.Array or pyarrow.ChunkedArray
+ pattern : str
+ pattern to split by
+ max_splits : int
+ If not -1, the maximum number of splits.
+ reverse : bool
+ Start splitting from the right, only meaningful when max_splits != -1
+
+ Returns
+ -------
+ result : pyarrow.Array or pyarrow.ChunkedArray
+ """
+ return call_function("split_pattern", [array],
+ SplitPatternOptions(pattern, max_splits, reverse))
Review comment:
(ah, I see you commented about that above yourself)
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500898893
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
Ah, I see what you mean. It would probably be ok to make this change, then.
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500899382
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
Perhaps you can file a separate JIRA for this?
----------------------------------------------------------------
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] pitrou commented on pull request #8271: ARROW-9991: [C++] Split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-712204248
macOS CI failures are unrelated.
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500071766
##########
File path: python/pyarrow/compute.py
##########
@@ -253,6 +255,68 @@ def match_substring(array, pattern):
MatchSubstringOptions(pattern))
+def split_pattern(array, pattern, max_splits=-1, reverse=False):
+ """
+ Replace string by a list of strings, separated by *pattern*.
+
+ Parameters
+ ----------
+ array : pyarrow.Array or pyarrow.ChunkedArray
+ pattern : str
+ pattern to split by
+ max_splits : int
+ If not -1, the maximum number of splits.
+ reverse : bool
+ Start splitting from the right, only meaningful when max_splits != -1
+
+ Returns
+ -------
+ result : pyarrow.Array or pyarrow.ChunkedArray
+ """
+ return call_function("split_pattern", [array],
+ SplitPatternOptions(pattern, max_splits, reverse))
Review comment:
I can take a look, I think it makes sense to add this indeed.
----------------------------------------------------------------
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 #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-698894038
https://issues.apache.org/jira/browse/ARROW-9991
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500084727
##########
File path: python/pyarrow/compute.py
##########
@@ -253,6 +255,68 @@ def match_substring(array, pattern):
MatchSubstringOptions(pattern))
+def split_pattern(array, pattern, max_splits=-1, reverse=False):
Review comment:
I see that changed in #8163, nice work. But that would make the API less friendly, having to pass in the options, instead of having an argument with default parameters. If you are strongly in favor of this, I'm ok with it, I'm not sure how 'user friendly' the arrow API needs to be.
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r504609655
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
Review comment:
Taken this out, so irrelevant now.
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500874404
##########
File path: python/pyarrow/tests/test_compute.py
##########
@@ -230,6 +230,51 @@ def test_match_substring():
assert expected.equals(result)
+def test_split_pattern():
Review comment:
It is more a coverage/sanity check, it is not a duplication of the C++ test. I'd like to keep it for now, as it triggered many issues during dev/refactoring.
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r501601274
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
Review comment:
They don't need to, so no?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<list_offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ BuilderType builder(input.type, ctx->memory_pool());
+ KERNEL_RETURN_IF_ERROR(ctx, builder.ReserveData(output_nbytes_max));
+ KERNEL_RETURN_IF_ERROR(ctx, builder.Resize(output_nstrings_max));
Review comment:
I'm skeptical this is a good idea to reserve `output_nstrings_max`, as this will allocate much more than necessary in most cases.
##########
File path: docs/source/cpp/compute.rst
##########
@@ -393,6 +393,34 @@ Containment tests
* \(3) Output is true iff the corresponding input element is equal to one
of the elements in :member:`SetLookupOptions::value_set`.
+
+String splitting
+~~~~~~~~~~~~~~~~
+
+These functions split strings into list of strings. All kernels take a
+max_splits and a reverse argument, where max_splits == -1 means no limit. When
+reverse is true, the splitting is done starting from the end of the string. Note
+that when max_splits == -1, reverse has no effect.
+
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+| Function name | Arity | Input types | Output type | Options class | Notes |
++==========================+============+=========================+===================+==================================+=========+
+| split_pattern | Unary | String-like | List-like | :struct:`SplitPatternOptions` | \(1) |
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+| utf8_split_whitespace | Unary | String-like | List-like | :struct:`SplitOptions` | \(2) |
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+| ascii_split_whitespace | Unary | String-like | List-like | :struct:`SplitOptions` | \(3) |
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+
+* \(1) The string is split when an exact pattern is found (the pattern itself is
+not included in the output).
+
+* \(2) A non-zero length sequence of Unicode defined whitespace codepoints is seen as separator.
+
+* \(3) A non-zero length sequence of ASCII defined whitespace bytes (\t, \n \v,
+\f, \r and ' ') is seen as separator.
Review comment:
I think you'll need to escape the literal strings here (`\t` etc.).
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<list_offset_type>::max()) {
Review comment:
I don't think this should be done statically. Instead, you should accumulate until the capacity limit is reached, and then raise the error.
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
Review comment:
You should also take into account `options.max_splits`, no?
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500898893
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
Ah, I see what you mean. It would probably be ok to make this change, then, _if_ we make most options arguments keyword-only.
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r497570569
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
Review comment:
I'll also note it's a pity to allocate a `vector` dynamically for each input string. Perhaps you can store this scratch space on the instance instead?
----------------------------------------------------------------
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] jorisvandenbossche commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
jorisvandenbossche commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500954601
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
+
+ // FirstTimeBitmapWriter bitmap_writer(buffer_output_string_bitmap->mutable_data(),
+ // /*offset=*/0, output_nstrings_max);
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type output_string_offset = 0;
+ offset_type output_string_count = 0;
+
+ // we always start at the beginning
+ *output_list_offsets++ = output_string_count;
+ *output_string_offsets++ = output_string_offset;
+
+ for (int64_t i = 0; i < input_nstrings; i++) {
+ offset_type input_string_nbytes;
+ const uint8_t* input_string = input_boxed.GetValue(i, &input_string_nbytes);
+ // if (input_boxed.IsValid(i)) {
+ Split(input_string, input_string_nbytes, &output_string_offsets,
+ &output_string_count, &output_string_offset, &output_string_data, options);
+ // null_builder.UnsafeAppend(true);
+ // } else {
+ // null_builder.UnsafeAppend(false);
+ // }
+
+ *output_list_offsets++ = output_string_count;
+ }
+ // bitmap_writer.Finish();
+ // trim off extra memory usage
+ KERNEL_RETURN_IF_ERROR(ctx,
+ buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (output_string_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+ // TODO: how to truncate the bitmap?
+ auto output_string_null_count = 0; // null_builder.false_count();
+ std::shared_ptr<Buffer> buffer_output_string_bitmap = nullptr;
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Finish(&buffer_output_string_bitmap));
+
+ std::shared_ptr<ArrayData> output_string_array =
+ ArrayData::Make(input.type, output_string_count,
+ {buffer_output_string_bitmap, buffer_output_string_offsets,
+ buffer_output_string_data},
+ output_string_null_count);
+ output_list_data->child_data.push_back(output_string_array);
+
+ } else {
+ const auto& input = checked_cast<const ScalarType&>(*batch[0].scalar());
+ auto result = checked_pointer_cast<ListScalarType>(MakeNullScalar(out->type()));
+ if (input.is_valid) {
+ result->is_valid = true;
+ offset_type input_nbytes = static_cast<offset_type>(input.value->size());
+
+ offset_type output_nbytes_max = input_nbytes;
+
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(Status::CapacityError(
+ "Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type string_output_offset = 0;
+ offset_type string_output_count = 0;
+
+ // we always start at the beginning
+ *output_string_offsets++ = string_output_offset;
+
+ const uint8_t* input_string = input.value->data();
+ Split(input_string, input_nbytes, &output_string_offsets, &string_output_count,
+ &string_output_offset, &output_string_data, options);
+
+ KERNEL_RETURN_IF_ERROR(
+ ctx, buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (string_output_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+
+ std::shared_ptr<ArrayData> output_string_array = ArrayData::Make(
+ input.type, string_output_count,
+ {nullptr, buffer_output_string_offsets, buffer_output_string_data});
+ result->value = std::make_shared<ArrayType>(output_string_array);
+ }
+ out->value = result;
+ }
+ }
+};
+
+template <typename Type, typename ListType>
+struct SplitPatternTransform : SplitBaseTransform<Type, ListType, SplitPatternOptions,
+ SplitPatternTransform<Type, ListType>> {
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using offset_type = typename Type::offset_type;
+ static Status CheckOptions(const SplitPatternOptions& options) {
+ if (options.pattern.length() == 0) {
+ return Status::Invalid("Empty separator");
+ }
+ return Status::OK();
+ }
+ static bool Find(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ const uint8_t* i = begin;
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ while ((i + pattern_length <= end)) {
+ i = std::search(i, end, pattern, pattern + pattern_length);
+ if (i != end) {
+ *separator_begin = i;
+ *separator_end = i + pattern_length;
+ return true;
+ }
+ }
+ return false;
+ }
+ static bool FindReverse(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ std::reverse_iterator<const uint8_t*> ri(end);
+ std::reverse_iterator<const uint8_t*> rend(begin);
+ std::reverse_iterator<const uint8_t*> pattern_rbegin(pattern + pattern_length);
+ std::reverse_iterator<const uint8_t*> pattern_rend(pattern);
+ while (begin <= ri.base() - pattern_length) {
+ ri = std::search(ri, rend, pattern_rbegin, pattern_rend);
+ if (ri != rend) {
+ *separator_begin = ri.base() - pattern_length;
+ *separator_end = ri.base();
+ return true;
+ }
+ }
+ return false;
+ }
+ static int64_t CalculateMaxSplits(const ArrayType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
+ // anymore
+ int64_t output_nstrings_max = 0;
+ for (offset_type i = 0; i < input.length(); i++) {
+ output_nstrings_max += 1 + input.value_length(i) / options.pattern.length();
+ }
+ return output_nstrings_max;
+ }
+ static int64_t CalculateMaxSplits(const ScalarType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
+ // anymore
+ return 1 + input.value->size() / options.pattern.length();
+ }
+};
+
+void AddSplitPattern(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("split_pattern", Arity::Unary());
Review comment:
Then `binary_split_pattern` seems "most correct"? Although I personally don't really like the fact that this naming scheme "hides" useful string functionality behind the `binary_` prefix (which is the same with `binary_length`, though)
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500909112
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
+
+ // FirstTimeBitmapWriter bitmap_writer(buffer_output_string_bitmap->mutable_data(),
+ // /*offset=*/0, output_nstrings_max);
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type output_string_offset = 0;
+ offset_type output_string_count = 0;
+
+ // we always start at the beginning
+ *output_list_offsets++ = output_string_count;
+ *output_string_offsets++ = output_string_offset;
+
+ for (int64_t i = 0; i < input_nstrings; i++) {
+ offset_type input_string_nbytes;
+ const uint8_t* input_string = input_boxed.GetValue(i, &input_string_nbytes);
+ // if (input_boxed.IsValid(i)) {
+ Split(input_string, input_string_nbytes, &output_string_offsets,
+ &output_string_count, &output_string_offset, &output_string_data, options);
+ // null_builder.UnsafeAppend(true);
+ // } else {
+ // null_builder.UnsafeAppend(false);
+ // }
+
+ *output_list_offsets++ = output_string_count;
+ }
+ // bitmap_writer.Finish();
+ // trim off extra memory usage
+ KERNEL_RETURN_IF_ERROR(ctx,
+ buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (output_string_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+ // TODO: how to truncate the bitmap?
+ auto output_string_null_count = 0; // null_builder.false_count();
+ std::shared_ptr<Buffer> buffer_output_string_bitmap = nullptr;
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Finish(&buffer_output_string_bitmap));
+
+ std::shared_ptr<ArrayData> output_string_array =
+ ArrayData::Make(input.type, output_string_count,
+ {buffer_output_string_bitmap, buffer_output_string_offsets,
+ buffer_output_string_data},
+ output_string_null_count);
+ output_list_data->child_data.push_back(output_string_array);
+
+ } else {
+ const auto& input = checked_cast<const ScalarType&>(*batch[0].scalar());
+ auto result = checked_pointer_cast<ListScalarType>(MakeNullScalar(out->type()));
+ if (input.is_valid) {
+ result->is_valid = true;
+ offset_type input_nbytes = static_cast<offset_type>(input.value->size());
+
+ offset_type output_nbytes_max = input_nbytes;
+
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(Status::CapacityError(
+ "Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type string_output_offset = 0;
+ offset_type string_output_count = 0;
+
+ // we always start at the beginning
+ *output_string_offsets++ = string_output_offset;
+
+ const uint8_t* input_string = input.value->data();
+ Split(input_string, input_nbytes, &output_string_offsets, &string_output_count,
+ &string_output_offset, &output_string_data, options);
+
+ KERNEL_RETURN_IF_ERROR(
+ ctx, buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (string_output_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+
+ std::shared_ptr<ArrayData> output_string_array = ArrayData::Make(
+ input.type, string_output_count,
+ {nullptr, buffer_output_string_offsets, buffer_output_string_data});
+ result->value = std::make_shared<ArrayType>(output_string_array);
+ }
+ out->value = result;
+ }
+ }
+};
+
+template <typename Type, typename ListType>
+struct SplitPatternTransform : SplitBaseTransform<Type, ListType, SplitPatternOptions,
+ SplitPatternTransform<Type, ListType>> {
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using offset_type = typename Type::offset_type;
+ static Status CheckOptions(const SplitPatternOptions& options) {
+ if (options.pattern.length() == 0) {
+ return Status::Invalid("Empty separator");
+ }
+ return Status::OK();
+ }
+ static bool Find(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ const uint8_t* i = begin;
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ while ((i + pattern_length <= end)) {
+ i = std::search(i, end, pattern, pattern + pattern_length);
+ if (i != end) {
+ *separator_begin = i;
+ *separator_end = i + pattern_length;
+ return true;
+ }
+ }
+ return false;
+ }
+ static bool FindReverse(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ std::reverse_iterator<const uint8_t*> ri(end);
+ std::reverse_iterator<const uint8_t*> rend(begin);
+ std::reverse_iterator<const uint8_t*> pattern_rbegin(pattern + pattern_length);
+ std::reverse_iterator<const uint8_t*> pattern_rend(pattern);
+ while (begin <= ri.base() - pattern_length) {
+ ri = std::search(ri, rend, pattern_rbegin, pattern_rend);
+ if (ri != rend) {
+ *separator_begin = ri.base() - pattern_length;
+ *separator_end = ri.base();
+ return true;
+ }
+ }
+ return false;
+ }
+ static int64_t CalculateMaxSplits(const ArrayType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
+ // anymore
+ int64_t output_nstrings_max = 0;
+ for (offset_type i = 0; i < input.length(); i++) {
+ output_nstrings_max += 1 + input.value_length(i) / options.pattern.length();
+ }
+ return output_nstrings_max;
+ }
+ static int64_t CalculateMaxSplits(const ScalarType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
+ // anymore
+ return 1 + input.value->size() / options.pattern.length();
+ }
+};
+
+void AddSplitPattern(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("split_pattern", Arity::Unary());
Review comment:
I don't know, because it can in principle also take binary arrays.
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500243584
##########
File path: cpp/src/arrow/compute/kernels/scalar_string_test.cc
##########
@@ -53,8 +53,19 @@ class BaseTestStringKernels : public ::testing::Test {
std::shared_ptr<DataType> offset_type() {
return TypeTraits<OffsetType>::type_singleton();
}
+ std::shared_ptr<DataType> list_type();
};
+template <>
+std::shared_ptr<DataType> BaseTestStringKernels<LargeStringType>::list_type() {
+ return large_list(this->type());
Review comment:
because it may have a lot of elements, leading to a long list. But you are right, all cases are possible, e.g. a large string with just a few really large elements, or a normal string that will split into more elements.
Any idea what to do? this made the most sense to me.
----------------------------------------------------------------
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 #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-698894038
https://issues.apache.org/jira/browse/ARROW-9991
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500873548
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
Yes, that would be nicer, but *args is not passed in the auto compute wrapper. Also, https://github.com/apache/arrow/blob/master/python/pyarrow/tests/test_compute.py#L68 would fail.
However, given @jorisvandenbossche comment about having pattern an array/scalar (i.e. making the kernel binary) would remove the issue.
I make it `*, pattern` now, with the downside of having to write ` pc.utf8_split_whitespace(arr, options={})` instead of no arguments.
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r504654993
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<list_offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ BuilderType builder(input.type, ctx->memory_pool());
+ KERNEL_RETURN_IF_ERROR(ctx, builder.ReserveData(output_nbytes_max));
+ KERNEL_RETURN_IF_ERROR(ctx, builder.Resize(output_nstrings_max));
Review comment:
It does!
----------------------------------------------------------------
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] pitrou commented on pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-712014021
@maartenbreddels Don't hesitate to tell me when this PR is ready 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500907752
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
https://issues.apache.org/jira/browse/ARROW-10209
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r504608040
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<list_offset_type>::max()) {
Review comment:
I agree, this made sense before I used the builders.
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500275273
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
Review comment:
This was related to the issue related to the test that is commented out (and described in the opening post). Reading @jorisvandenbossche explanation I think I did it correctly, and this code can be ignored. I think there is an issue with equality testing and null values in lists (as described above).
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500282031
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
Review comment:
If there is such an issue, it would be good to open a dedicated JIRA with a reproducer. Let's not bury this in the comments of a string compute PR :-)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500265136
##########
File path: cpp/src/arrow/compute/kernels/scalar_string_test.cc
##########
@@ -53,8 +53,19 @@ class BaseTestStringKernels : public ::testing::Test {
std::shared_ptr<DataType> offset_type() {
return TypeTraits<OffsetType>::type_singleton();
}
+ std::shared_ptr<DataType> list_type();
};
+template <>
+std::shared_ptr<DataType> BaseTestStringKernels<LargeStringType>::list_type() {
+ return large_list(this->type());
Review comment:
I think this is overkill for now. Let's just always return a regular list. Large lists will have a sizeable overhead, especially with many small splits.
If there's a user request for it, we may later add an option to return a large list instead.
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500879612
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
I'm surprised about what you're saying. There may be a misunderstanding.
----------------------------------------------------------------
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] jorisvandenbossche commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
jorisvandenbossche commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r497481336
##########
File path: python/pyarrow/compute.py
##########
@@ -253,6 +255,68 @@ def match_substring(array, pattern):
MatchSubstringOptions(pattern))
+def split_pattern(array, pattern, max_splits=-1, reverse=False):
+ """
+ Replace string by a list of strings, separated by *pattern*.
+
+ Parameters
+ ----------
+ array : pyarrow.Array or pyarrow.ChunkedArray
+ pattern : str
+ pattern to split by
+ max_splits : int
+ If not -1, the maximum number of splits.
+ reverse : bool
+ Start splitting from the right, only meaningful when max_splits != -1
+
+ Returns
+ -------
+ result : pyarrow.Array or pyarrow.ChunkedArray
+ """
+ return call_function("split_pattern", [array],
+ SplitPatternOptions(pattern, max_splits, reverse))
Review comment:
This might be premature optimization, but in theory the `pattern` could also be a second argument (`[array, pattern]`), keeping the option open to later implement `[array, array_of_patterns]` where both could be an array of the same length? (in case you want a different split pattern per value)
That would also make SplitOptions could be shared between both `split_pattern` and `split_whitespace`
##########
File path: cpp/src/arrow/compute/api_scalar.h
##########
@@ -49,6 +49,23 @@ struct ARROW_EXPORT MatchSubstringOptions : public FunctionOptions {
std::string pattern;
};
+struct ARROW_EXPORT SplitOptions : public FunctionOptions {
+ explicit SplitOptions(int64_t max_splits = -1, bool reverse = false)
+ : max_splits(max_splits), reverse(reverse) {}
+
+ int64_t max_splits;
+ bool reverse;
Review comment:
Can you add a doc comment here?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
+
+ // FirstTimeBitmapWriter bitmap_writer(buffer_output_string_bitmap->mutable_data(),
+ // /*offset=*/0, output_nstrings_max);
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type output_string_offset = 0;
+ offset_type output_string_count = 0;
+
+ // we always start at the beginning
+ *output_list_offsets++ = output_string_count;
+ *output_string_offsets++ = output_string_offset;
+
+ for (int64_t i = 0; i < input_nstrings; i++) {
+ offset_type input_string_nbytes;
+ const uint8_t* input_string = input_boxed.GetValue(i, &input_string_nbytes);
+ // if (input_boxed.IsValid(i)) {
+ Split(input_string, input_string_nbytes, &output_string_offsets,
+ &output_string_count, &output_string_offset, &output_string_data, options);
+ // null_builder.UnsafeAppend(true);
+ // } else {
+ // null_builder.UnsafeAppend(false);
+ // }
+
+ *output_list_offsets++ = output_string_count;
+ }
+ // bitmap_writer.Finish();
+ // trim off extra memory usage
+ KERNEL_RETURN_IF_ERROR(ctx,
+ buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (output_string_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+ // TODO: how to truncate the bitmap?
+ auto output_string_null_count = 0; // null_builder.false_count();
+ std::shared_ptr<Buffer> buffer_output_string_bitmap = nullptr;
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Finish(&buffer_output_string_bitmap));
+
+ std::shared_ptr<ArrayData> output_string_array =
+ ArrayData::Make(input.type, output_string_count,
+ {buffer_output_string_bitmap, buffer_output_string_offsets,
+ buffer_output_string_data},
+ output_string_null_count);
+ output_list_data->child_data.push_back(output_string_array);
+
+ } else {
+ const auto& input = checked_cast<const ScalarType&>(*batch[0].scalar());
+ auto result = checked_pointer_cast<ListScalarType>(MakeNullScalar(out->type()));
+ if (input.is_valid) {
+ result->is_valid = true;
+ offset_type input_nbytes = static_cast<offset_type>(input.value->size());
+
+ offset_type output_nbytes_max = input_nbytes;
+
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(Status::CapacityError(
+ "Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type string_output_offset = 0;
+ offset_type string_output_count = 0;
+
+ // we always start at the beginning
+ *output_string_offsets++ = string_output_offset;
+
+ const uint8_t* input_string = input.value->data();
+ Split(input_string, input_nbytes, &output_string_offsets, &string_output_count,
+ &string_output_offset, &output_string_data, options);
+
+ KERNEL_RETURN_IF_ERROR(
+ ctx, buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (string_output_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+
+ std::shared_ptr<ArrayData> output_string_array = ArrayData::Make(
+ input.type, string_output_count,
+ {nullptr, buffer_output_string_offsets, buffer_output_string_data});
+ result->value = std::make_shared<ArrayType>(output_string_array);
+ }
+ out->value = result;
+ }
+ }
+};
+
+template <typename Type, typename ListType>
+struct SplitPatternTransform : SplitBaseTransform<Type, ListType, SplitPatternOptions,
+ SplitPatternTransform<Type, ListType>> {
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using offset_type = typename Type::offset_type;
+ static Status CheckOptions(const SplitPatternOptions& options) {
+ if (options.pattern.length() == 0) {
+ return Status::Invalid("Empty separator");
+ }
+ return Status::OK();
+ }
+ static bool Find(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ const uint8_t* i = begin;
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ while ((i + pattern_length <= end)) {
+ i = std::search(i, end, pattern, pattern + pattern_length);
+ if (i != end) {
+ *separator_begin = i;
+ *separator_end = i + pattern_length;
+ return true;
+ }
+ }
+ return false;
+ }
+ static bool FindReverse(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ std::reverse_iterator<const uint8_t*> ri(end);
+ std::reverse_iterator<const uint8_t*> rend(begin);
+ std::reverse_iterator<const uint8_t*> pattern_rbegin(pattern + pattern_length);
+ std::reverse_iterator<const uint8_t*> pattern_rend(pattern);
+ while (begin <= ri.base() - pattern_length) {
+ ri = std::search(ri, rend, pattern_rbegin, pattern_rend);
+ if (ri != rend) {
+ *separator_begin = ri.base() - pattern_length;
+ *separator_end = ri.base();
+ return true;
+ }
+ }
+ return false;
+ }
+ static int64_t CalculateMaxSplits(const ArrayType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
+ // anymore
+ int64_t output_nstrings_max = 0;
+ for (offset_type i = 0; i < input.length(); i++) {
+ output_nstrings_max += 1 + input.value_length(i) / options.pattern.length();
+ }
+ return output_nstrings_max;
+ }
+ static int64_t CalculateMaxSplits(const ScalarType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
+ // anymore
+ return 1 + input.value->size() / options.pattern.length();
+ }
+};
+
+void AddSplitPattern(FunctionRegistry* registry) {
+ auto func = std::make_shared<ScalarFunction>("split_pattern", Arity::Unary());
Review comment:
Should the kernel name be `string_split_pattern` instead of `split_pattern`? (like we have `string_is_ascii` and not `is_ascii` and `binary_length` and not `length`)
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r504609441
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<list_offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ BuilderType builder(input.type, ctx->memory_pool());
+ KERNEL_RETURN_IF_ERROR(ctx, builder.ReserveData(output_nbytes_max));
+ KERNEL_RETURN_IF_ERROR(ctx, builder.Resize(output_nstrings_max));
Review comment:
I agree, with the builders, there is less need for this. I've changed this to be the number of input strings, which is a lower limit but should reduce some reallocs. Does that make sense?
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500868020
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
Review comment:
done https://issues.apache.org/jira/browse/ARROW-10207
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500268258
##########
File path: python/pyarrow/compute.py
##########
@@ -253,6 +255,68 @@ def match_substring(array, pattern):
MatchSubstringOptions(pattern))
+def split_pattern(array, pattern, max_splits=-1, reverse=False):
Review comment:
It's true that the docstring is a bit suboptimal still. Hopefully we can improve that in the future:
```
>>> pc.min_max?
Signature: pc.min_max(arg, *, options=None, memory_pool=None, **kwargs)
Docstring:
Call compute function 'min_max' with the given argument.
Parameters
----------
arg : Array-like or scalar-like
Argument to compute function
memory_pool : pyarrow.MemoryPool, optional
If not passed, will allocate memory from the default memory pool.
options : pyarrow.compute.MinMaxOptions, optional
Parameters altering compute function semantics
**kwargs: optional
Parameters for MinMaxOptions constructor. Either `options`
or `**kwargs` can be passed, but not both at the same time.
```
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500897047
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
when you have ```def __init__(self, pattern, *, max_splits=-1, reverse=False):``` you'd expect to be able to write `result = pc.split_pattern(arr, "---")` (without the pattern keyword). But that fails (`E TypeError: wrapper() takes 1 positional argument but 2 were given`).
in code, this would make it pass:
```patch
diff --git a/python/pyarrow/compute.py b/python/pyarrow/compute.py
index 7b4ccd965..ee67bb39d 100644
--- a/python/pyarrow/compute.py
+++ b/python/pyarrow/compute.py
@@ -107,10 +107,10 @@ _option_classes = {
}
-def _handle_options(name, option_class, options, kwargs):
- if kwargs:
+def _handle_options(name, option_class, options, args, kwargs):
+ if kwargs or args:
if options is None:
- return option_class(**kwargs)
+ return option_class(*args, **kwargs)
raise TypeError(
"Function {!r} called with both an 'options' argument "
"and additional named arguments"
@@ -133,8 +133,8 @@ def _simple_unary_function(name):
option_class = _option_classes.get(name)
if option_class is not None:
- def wrapper(arg, *, options=None, memory_pool=None, **kwargs):
- options = _handle_options(name, option_class, options, kwargs)
+ def wrapper(arg, *args, options=None, memory_pool=None, **kwargs):
+ options = _handle_options(name, option_class, options, args, kwargs)
return func.call([arg], options, memory_pool)
else:
def wrapper(arg, *, memory_pool=None):
```
Is this more clear?
----------------------------------------------------------------
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] jorisvandenbossche commented on pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
jorisvandenbossche commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-701380049
> This also raised a question: Should both the list entry and the string array entry have a missing/null value if the input string contains a null value? I think it should because if we ask for the underlying string array, and the string value that the missing list entry points to is not a missing value, it will be an empty string, which seems odd to me.
Buf if the original string was a null, then the output also contains a (top-level) null, and not a list with a null?
And then such top-level nulls are typically not put as an entry in the actual values array (or at least when arrow is building up a list array itself, the format might also not allow otherwise). Eg:
```
In [10]: arr = pa.array([["a", "b"], None, ["c"], [None]])
In [11]: arr
Out[11]:
<pyarrow.lib.ListArray object at 0x7f2316c1d108>
[
[
"a",
"b"
],
null,
[
"c"
],
[
null
]
]
In [12]: arr.values
Out[12]:
<pyarrow.lib.StringArray object at 0x7f2316c1d5e8>
[
"a",
"b",
"c",
null
]
```
(so only the null that was inside a list is represented as null in the underlying values array)
----------------------------------------------------------------
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] pitrou commented on pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-712151765
Will update for the new `FunctionDoc` functionality and then merge.
----------------------------------------------------------------
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] pitrou commented on pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-704826423
@maartenbreddels Please ping me when you need a new review.
----------------------------------------------------------------
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] pitrou commented on pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-704890478
> I can imagine that we also want to support binary_split_pattern, so should we have to separate kernel names for this, or keep it split_pattern and implement support for binary in the future?
The implementation would be exactly the same, right? I think "split_pattern" is fine.
> API docs: I'm not sure the compute.rst docs I added should follow some standard, or if that table can be produce using some tool, I've done it by hand for now.
We do it by hand indeed.
> Should split_pattern be a binary kernel, where pattern is the second argument?
I don't think that would make sense, no.
----------------------------------------------------------------
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] pitrou commented on pull request #8271: ARROW-9991: [C++] Split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-712205549
Thank you very much @maartenbreddels !
----------------------------------------------------------------
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] maartenbreddels commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r500951363
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
+
+ // FirstTimeBitmapWriter bitmap_writer(buffer_output_string_bitmap->mutable_data(),
+ // /*offset=*/0, output_nstrings_max);
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type output_string_offset = 0;
+ offset_type output_string_count = 0;
+
+ // we always start at the beginning
+ *output_list_offsets++ = output_string_count;
+ *output_string_offsets++ = output_string_offset;
+
+ for (int64_t i = 0; i < input_nstrings; i++) {
+ offset_type input_string_nbytes;
+ const uint8_t* input_string = input_boxed.GetValue(i, &input_string_nbytes);
+ // if (input_boxed.IsValid(i)) {
+ Split(input_string, input_string_nbytes, &output_string_offsets,
+ &output_string_count, &output_string_offset, &output_string_data, options);
+ // null_builder.UnsafeAppend(true);
+ // } else {
+ // null_builder.UnsafeAppend(false);
+ // }
+
+ *output_list_offsets++ = output_string_count;
+ }
+ // bitmap_writer.Finish();
+ // trim off extra memory usage
+ KERNEL_RETURN_IF_ERROR(ctx,
+ buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (output_string_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+ // TODO: how to truncate the bitmap?
+ auto output_string_null_count = 0; // null_builder.false_count();
+ std::shared_ptr<Buffer> buffer_output_string_bitmap = nullptr;
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Finish(&buffer_output_string_bitmap));
+
+ std::shared_ptr<ArrayData> output_string_array =
+ ArrayData::Make(input.type, output_string_count,
+ {buffer_output_string_bitmap, buffer_output_string_offsets,
+ buffer_output_string_data},
+ output_string_null_count);
+ output_list_data->child_data.push_back(output_string_array);
+
+ } else {
+ const auto& input = checked_cast<const ScalarType&>(*batch[0].scalar());
+ auto result = checked_pointer_cast<ListScalarType>(MakeNullScalar(out->type()));
+ if (input.is_valid) {
+ result->is_valid = true;
+ offset_type input_nbytes = static_cast<offset_type>(input.value->size());
+
+ offset_type output_nbytes_max = input_nbytes;
+
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(Status::CapacityError(
+ "Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type string_output_offset = 0;
+ offset_type string_output_count = 0;
+
+ // we always start at the beginning
+ *output_string_offsets++ = string_output_offset;
+
+ const uint8_t* input_string = input.value->data();
+ Split(input_string, input_nbytes, &output_string_offsets, &string_output_count,
+ &string_output_offset, &output_string_data, options);
+
+ KERNEL_RETURN_IF_ERROR(
+ ctx, buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (string_output_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+
+ std::shared_ptr<ArrayData> output_string_array = ArrayData::Make(
+ input.type, string_output_count,
+ {nullptr, buffer_output_string_offsets, buffer_output_string_data});
+ result->value = std::make_shared<ArrayType>(output_string_array);
+ }
+ out->value = result;
+ }
+ }
+};
+
+template <typename Type, typename ListType>
+struct SplitPatternTransform : SplitBaseTransform<Type, ListType, SplitPatternOptions,
+ SplitPatternTransform<Type, ListType>> {
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using offset_type = typename Type::offset_type;
+ static Status CheckOptions(const SplitPatternOptions& options) {
+ if (options.pattern.length() == 0) {
+ return Status::Invalid("Empty separator");
+ }
+ return Status::OK();
+ }
+ static bool Find(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ const uint8_t* i = begin;
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ while ((i + pattern_length <= end)) {
+ i = std::search(i, end, pattern, pattern + pattern_length);
+ if (i != end) {
+ *separator_begin = i;
+ *separator_end = i + pattern_length;
+ return true;
+ }
+ }
+ return false;
+ }
+ static bool FindReverse(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ std::reverse_iterator<const uint8_t*> ri(end);
+ std::reverse_iterator<const uint8_t*> rend(begin);
+ std::reverse_iterator<const uint8_t*> pattern_rbegin(pattern + pattern_length);
+ std::reverse_iterator<const uint8_t*> pattern_rend(pattern);
+ while (begin <= ri.base() - pattern_length) {
+ ri = std::search(ri, rend, pattern_rbegin, pattern_rend);
+ if (ri != rend) {
+ *separator_begin = ri.base() - pattern_length;
+ *separator_end = ri.base();
+ return true;
+ }
+ }
+ return false;
+ }
+ static int64_t CalculateMaxSplits(const ArrayType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
Review comment:
Thanks for those tips, this improved the code a lot. If the offsets were preallocated is there a helper class to wrap that? (say after https://issues.apache.org/jira/browse/ARROW-10207 is fixed).
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r497546569
##########
File path: cpp/src/arrow/compute/kernels/scalar_string_benchmark.cc
##########
@@ -66,6 +66,11 @@ static void MatchSubstring(benchmark::State& state) {
UnaryStringBenchmark(state, "match_substring", &options);
}
+static void SplitPattern(benchmark::State& state) {
+ SplitPatternOptions options("abac");
+ UnaryStringBenchmark(state, "split_pattern", &options);
Review comment:
Is there really a point in benchmarking random data? Presumably 0 split will happen...
You also don't need to worry about benchmarks in this PR, they may be added later.
##########
File path: cpp/src/arrow/util/utf8.h
##########
@@ -350,6 +362,42 @@ static inline bool UTF8Decode(const uint8_t** data, uint32_t* codepoint) {
return true;
}
+static inline bool UTF8DecodeReverse(const uint8_t** data, uint32_t* codepoint) {
+ const uint8_t* str = *data;
+ if (*str < 0x80) { // ascci
+ *codepoint = *str--;
+ } else if (ARROW_PREDICT_TRUE(Utf8IsContinuation(*str))) {
Review comment:
Nit: instead of the `if` nesting here, it may be clearer to handle errors before:
```c++
if (ARROW_PREDICT_FALSE(!Utf8IsContinuation(*str))) {
return false;
}
```
##########
File path: cpp/src/arrow/compute/kernels/scalar_string_test.cc
##########
@@ -53,8 +53,19 @@ class BaseTestStringKernels : public ::testing::Test {
std::shared_ptr<DataType> offset_type() {
return TypeTraits<OffsetType>::type_singleton();
}
+ std::shared_ptr<DataType> list_type();
};
+template <>
+std::shared_ptr<DataType> BaseTestStringKernels<LargeStringType>::list_type() {
+ return large_list(this->type());
Review comment:
I don't think that makes sense. Why would you return a large list when the embedded type is a large string?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
Review comment:
Hmm, can you use `arrow::util::string_view` instead?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
Review comment:
I think you should try using `VisitArrayDataInline<Type>` instead of redoing all this by hand.
##########
File path: python/pyarrow/tests/test_compute.py
##########
@@ -230,6 +230,51 @@ def test_match_substring():
assert expected.equals(result)
+def test_split_pattern():
Review comment:
It doesn't really make sense to duplicate C++ tests on the Python side.
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
+ self.split_options.reset(
+ new CSplitOptions(max_splits, reverse))
+
+ cdef const CFunctionOptions* get_options(self) except NULL:
+ return self.split_options.get()
+
+
+cdef class SplitPatternOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitPatternOptions] split_pattern_options
+
+ def __init__(self, pattern, max_splits, reverse):
Review comment:
Perhaps:
```python
def __init__(self, pattern, *, max_splits, reverse):
```
?
##########
File path: python/pyarrow/compute.py
##########
@@ -253,6 +255,68 @@ def match_substring(array, pattern):
MatchSubstringOptions(pattern))
+def split_pattern(array, pattern, max_splits=-1, reverse=False):
Review comment:
You don't need this, it will be exposed automatically. However, you'll need to expand `_option_classes`.
##########
File path: python/pyarrow/_compute.pyx
##########
@@ -560,6 +560,29 @@ cdef class MatchSubstringOptions(FunctionOptions):
return self.match_substring_options.get()
+cdef class SplitOptions(FunctionOptions):
+ cdef:
+ unique_ptr[CSplitOptions] split_options
+
+ def __init__(self, max_splits, reverse):
Review comment:
We should probably use keyword-only arguments here:
```python
def __init__(self, *, max_splits, reverse):
```
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
+
+ // FirstTimeBitmapWriter bitmap_writer(buffer_output_string_bitmap->mutable_data(),
+ // /*offset=*/0, output_nstrings_max);
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type output_string_offset = 0;
+ offset_type output_string_count = 0;
+
+ // we always start at the beginning
+ *output_list_offsets++ = output_string_count;
+ *output_string_offsets++ = output_string_offset;
+
+ for (int64_t i = 0; i < input_nstrings; i++) {
+ offset_type input_string_nbytes;
+ const uint8_t* input_string = input_boxed.GetValue(i, &input_string_nbytes);
+ // if (input_boxed.IsValid(i)) {
+ Split(input_string, input_string_nbytes, &output_string_offsets,
+ &output_string_count, &output_string_offset, &output_string_data, options);
+ // null_builder.UnsafeAppend(true);
+ // } else {
+ // null_builder.UnsafeAppend(false);
+ // }
+
+ *output_list_offsets++ = output_string_count;
+ }
+ // bitmap_writer.Finish();
+ // trim off extra memory usage
+ KERNEL_RETURN_IF_ERROR(ctx,
+ buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (output_string_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+ // TODO: how to truncate the bitmap?
+ auto output_string_null_count = 0; // null_builder.false_count();
+ std::shared_ptr<Buffer> buffer_output_string_bitmap = nullptr;
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Finish(&buffer_output_string_bitmap));
+
+ std::shared_ptr<ArrayData> output_string_array =
+ ArrayData::Make(input.type, output_string_count,
+ {buffer_output_string_bitmap, buffer_output_string_offsets,
+ buffer_output_string_data},
+ output_string_null_count);
+ output_list_data->child_data.push_back(output_string_array);
+
+ } else {
+ const auto& input = checked_cast<const ScalarType&>(*batch[0].scalar());
+ auto result = checked_pointer_cast<ListScalarType>(MakeNullScalar(out->type()));
+ if (input.is_valid) {
+ result->is_valid = true;
+ offset_type input_nbytes = static_cast<offset_type>(input.value->size());
+
+ offset_type output_nbytes_max = input_nbytes;
+
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(Status::CapacityError(
+ "Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+
+ // the output offset goes slightly slower then the input (due to skipping pattern)
+ offset_type string_output_offset = 0;
+ offset_type string_output_count = 0;
+
+ // we always start at the beginning
+ *output_string_offsets++ = string_output_offset;
+
+ const uint8_t* input_string = input.value->data();
+ Split(input_string, input_nbytes, &output_string_offsets, &string_output_count,
+ &string_output_offset, &output_string_data, options);
+
+ KERNEL_RETURN_IF_ERROR(
+ ctx, buffer_output_string_data->Resize(output_string_offsets[-1],
+ /*shrink_to_fit=*/true));
+ KERNEL_RETURN_IF_ERROR(ctx, buffer_output_string_offsets->Resize(
+ (string_output_count + 1) * sizeof(offset_type),
+ /*shrink_to_fit=*/true));
+
+ std::shared_ptr<ArrayData> output_string_array = ArrayData::Make(
+ input.type, string_output_count,
+ {nullptr, buffer_output_string_offsets, buffer_output_string_data});
+ result->value = std::make_shared<ArrayType>(output_string_array);
+ }
+ out->value = result;
+ }
+ }
+};
+
+template <typename Type, typename ListType>
+struct SplitPatternTransform : SplitBaseTransform<Type, ListType, SplitPatternOptions,
+ SplitPatternTransform<Type, ListType>> {
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using offset_type = typename Type::offset_type;
+ static Status CheckOptions(const SplitPatternOptions& options) {
+ if (options.pattern.length() == 0) {
+ return Status::Invalid("Empty separator");
+ }
+ return Status::OK();
+ }
+ static bool Find(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ const uint8_t* i = begin;
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ while ((i + pattern_length <= end)) {
+ i = std::search(i, end, pattern, pattern + pattern_length);
+ if (i != end) {
+ *separator_begin = i;
+ *separator_end = i + pattern_length;
+ return true;
+ }
+ }
+ return false;
+ }
+ static bool FindReverse(const uint8_t* begin, const uint8_t* end,
+ const uint8_t** separator_begin, const uint8_t** separator_end,
+ const SplitPatternOptions& options) {
+ const uint8_t* pattern = reinterpret_cast<const uint8_t*>(options.pattern.c_str());
+ const int64_t pattern_length = options.pattern.length();
+ // this is O(n*m) complexity, we could use the Knuth-Morris-Pratt algorithm used in
+ // the match kernel
+ std::reverse_iterator<const uint8_t*> ri(end);
+ std::reverse_iterator<const uint8_t*> rend(begin);
+ std::reverse_iterator<const uint8_t*> pattern_rbegin(pattern + pattern_length);
+ std::reverse_iterator<const uint8_t*> pattern_rend(pattern);
+ while (begin <= ri.base() - pattern_length) {
+ ri = std::search(ri, rend, pattern_rbegin, pattern_rend);
+ if (ri != rend) {
+ *separator_begin = ri.base() - pattern_length;
+ *separator_end = ri.base();
+ return true;
+ }
+ }
+ return false;
+ }
+ static int64_t CalculateMaxSplits(const ArrayType& input,
+ const SplitPatternOptions& options) {
+ // Worst case is e.g. [' ', ' '] split by ' ' -> [['', '', ''], ['', '']]
+ // i.e. the length of each string divided by the pattern length + 1
+ // This can double the amount of strings, thus not fit into a (32bit) list or string
Review comment:
More than double. Your example shows it growing from 2 to 5, but if the pattern is length 1 (probably a common case?) you're really allocating one output string per input byte. This is probably too much.
Instead, you may use:
* a presized `BufferBuilder` for the string bytes
* a dynamically-sized `TypedBufferBuilder<offset_type>` for the string offsets
* a presized `TypedBufferBuilder<int32_t>` for the list offsets
And the output's null bitmap is the same as the input's null bitmap, so no need to recompute it!
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
+ KERNEL_ASSIGN_OR_RAISE(output_list_data->buffers[1], ctx,
+ ctx->Allocate((input_nstrings + 1) * sizeof(offset_type)));
+ offset_type* output_list_offsets =
+ output_list_data->GetMutableValues<offset_type>(1);
+
+ // allocate output string array data
+ // this is a bit low level, should we use a builder?
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_data, ctx,
+ ctx->Allocate((output_nbytes_max)));
+ KERNEL_ASSIGN_OR_RAISE(auto buffer_output_string_offsets, ctx,
+ ctx->Allocate(output_nstrings_max * sizeof(offset_type)));
+
+ offset_type* output_string_offsets =
+ reinterpret_cast<offset_type*>(buffer_output_string_offsets->mutable_data());
+ uint8_t* output_string_data = buffer_output_string_data->mutable_data();
+ // TypedBufferBuilder<bool> null_builder; // TODO: should we pass a mem poool?
+ // KERNEL_RETURN_IF_ERROR(ctx, null_builder.Reserve(output_nstrings_max));
Review comment:
Why is all this commented out? Is this PR unfinished?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
Review comment:
If so, can you open a JIRA so that this doesn't get lost?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +809,475 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using offset_type = typename Type::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using Builder = typename TypeTraits<Type>::BuilderType;
+ using State = OptionsWrapper<Options>;
+
+ static void Split(const uint8_t* input_string, offset_type input_string_nbytes,
+ offset_type** output_string_offsets, offset_type* string_output_count,
+ offset_type* string_output_offset, uint8_t** output_string_data,
+ const Options& options) {
+ const uint8_t* begin = input_string;
+ const uint8_t* end = begin + input_string_nbytes;
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ std::vector<std::pair<const uint8_t*, const uint8_t*>> parts;
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::FindReverse(begin, i, &separator_begin, &separator_end, options)) {
+ parts.emplace_back(separator_end, i);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(begin, i);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ auto part = *it;
+ // copy the string data
+ for (auto j = part.first; j < part.second; j++) {
+ *(*output_string_data)++ = *j;
+ (*string_output_offset)++;
+ }
+ // write out the string entry (offset)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (Derived::Find(i, end, &separator_begin, &separator_end, options)) {
+ // copy the part till the beginning of the 'cut'
+ while (i < separator_begin) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // 'finish' the string by writing the offset
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ // jump of the part we cut out
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // copy bytes after the pattern
+ while (i < end) {
+ *(*output_string_data)++ = *i++;
+ (*string_output_offset)++;
+ }
+ // and write out the trailing part (can be an empty string)
+ *(*output_string_offsets)++ = *string_output_offset;
+ (*string_output_count)++;
+ }
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ Options options = State::Get(ctx);
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+ ArrayData* output_list_data = out->mutable_array();
+
+ offset_type input_nbytes = input_boxed.total_values_length();
+ offset_type input_nstrings = static_cast<offset_type>(input.length);
+
+ offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ // Why is the offset buffer not preallocated?
Review comment:
Well, it depends. Did you declare a scalar kernel?
----------------------------------------------------------------
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] pitrou commented on a change in pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#discussion_r501601274
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
Review comment:
They don't need to, so no?
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<list_offset_type>::max()) {
+ ctx->SetStatus(
+ Status::CapacityError("Result might not fit in a 32bit list or string array, "
+ "convert to large_utf8"));
+ return;
+ }
+
+ BuilderType builder(input.type, ctx->memory_pool());
+ KERNEL_RETURN_IF_ERROR(ctx, builder.ReserveData(output_nbytes_max));
+ KERNEL_RETURN_IF_ERROR(ctx, builder.Resize(output_nstrings_max));
Review comment:
I'm skeptical this is a good idea to reserve `output_nstrings_max`, as this will allocate much more than necessary in most cases.
##########
File path: docs/source/cpp/compute.rst
##########
@@ -393,6 +393,34 @@ Containment tests
* \(3) Output is true iff the corresponding input element is equal to one
of the elements in :member:`SetLookupOptions::value_set`.
+
+String splitting
+~~~~~~~~~~~~~~~~
+
+These functions split strings into list of strings. All kernels take a
+max_splits and a reverse argument, where max_splits == -1 means no limit. When
+reverse is true, the splitting is done starting from the end of the string. Note
+that when max_splits == -1, reverse has no effect.
+
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+| Function name | Arity | Input types | Output type | Options class | Notes |
++==========================+============+=========================+===================+==================================+=========+
+| split_pattern | Unary | String-like | List-like | :struct:`SplitPatternOptions` | \(1) |
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+| utf8_split_whitespace | Unary | String-like | List-like | :struct:`SplitOptions` | \(2) |
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+| ascii_split_whitespace | Unary | String-like | List-like | :struct:`SplitOptions` | \(3) |
++--------------------------+------------+-------------------------+-------------------+----------------------------------+---------+
+
+* \(1) The string is split when an exact pattern is found (the pattern itself is
+not included in the output).
+
+* \(2) A non-zero length sequence of Unicode defined whitespace codepoints is seen as separator.
+
+* \(3) A non-zero length sequence of ASCII defined whitespace bytes (\t, \n \v,
+\f, \r and ' ') is seen as separator.
Review comment:
I think you'll need to escape the literal strings here (`\t` etc.).
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
+ if (output_nstrings_max > std::numeric_limits<list_offset_type>::max()) {
Review comment:
I don't think this should be done statically. Instead, you should accumulate until the capacity limit is reached, and then raise the error.
##########
File path: cpp/src/arrow/compute/kernels/scalar_string.cc
##########
@@ -809,6 +812,418 @@ struct IsUpperAscii : CharacterPredicateAscii<IsUpperAscii> {
}
};
+// splitting
+
+template <typename Type, typename ListType, typename Options, typename Derived>
+struct SplitBaseTransform {
+ // TODO: assert offsets types are the same?
+ using string_offset_type = typename Type::offset_type;
+ using list_offset_type = typename ListType::offset_type;
+ using ArrayType = typename TypeTraits<Type>::ArrayType;
+ using ArrayListType = typename TypeTraits<ListType>::ArrayType;
+ using ListScalarType = typename TypeTraits<ListType>::ScalarType;
+ using ScalarType = typename TypeTraits<Type>::ScalarType;
+ using BuilderType = typename TypeTraits<Type>::BuilderType;
+ using ListOffsetsBuilderType = TypedBufferBuilder<list_offset_type>;
+ using State = OptionsWrapper<Options>;
+
+ std::vector<util::string_view> parts;
+ Options options;
+
+ explicit SplitBaseTransform(Options options) : options(options) {}
+
+ Status Split(const util::string_view& s, BuilderType* builder) {
+ const uint8_t* begin = reinterpret_cast<const uint8_t*>(s.data());
+ const uint8_t* end = begin + s.length();
+
+ int64_t max_splits = options.max_splits;
+ // if there is no max splits, reversing does not make sense (and is probably less
+ // efficient), but is useful for testing
+ if (options.reverse) {
+ // note that i points 1 further than the 'current'
+ const uint8_t* i = end;
+ // we will record the parts in reverse order
+ if (max_splits > -1) {
+ parts.reserve(max_splits + 1);
+ }
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).FindReverse(begin, i, &separator_begin,
+ &separator_end, options)) {
+ parts.emplace_back(reinterpret_cast<const char*>(separator_end),
+ i - separator_end);
+ i = separator_begin;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ parts.emplace_back(reinterpret_cast<const char*>(begin), i - begin);
+ // now we do the copying
+ for (auto it = parts.rbegin(); it != parts.rend(); ++it) {
+ RETURN_NOT_OK(builder->Append(*it));
+ }
+ parts.clear();
+ } else {
+ const uint8_t* i = begin;
+ while (max_splits != 0) {
+ const uint8_t *separator_begin, *separator_end;
+ // find with whatever algo the part we will 'cut out'
+ if (static_cast<Derived&>(*this).Find(i, end, &separator_begin, &separator_end,
+ options)) {
+ // the part till the beginning of the 'cut'
+ RETURN_NOT_OK(
+ builder->Append(i, static_cast<string_offset_type>(separator_begin - i)));
+ i = separator_end;
+ max_splits--;
+ } else {
+ // if we cannot find a separator, we're done
+ break;
+ }
+ }
+ // trailing part
+ RETURN_NOT_OK(builder->Append(i, static_cast<string_offset_type>(end - i)));
+ }
+ return Status::OK();
+ }
+ static Status CheckOptions(const Options& options) { return Status::OK(); }
+ static void Exec(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ Options options = State::Get(ctx);
+ Derived splitter(options); // we make an instance to reuse the parts vectors
+ splitter.Split(ctx, batch, out);
+ }
+
+ void Split(KernelContext* ctx, const ExecBatch& batch, Datum* out) {
+ EnsureLookupTablesFilled(); // only needed for unicode
+ KERNEL_RETURN_IF_ERROR(ctx, Derived::CheckOptions(options));
+
+ if (batch[0].kind() == Datum::ARRAY) {
+ const ArrayData& input = *batch[0].array();
+ ArrayType input_boxed(batch[0].array());
+
+ string_offset_type input_nbytes = input_boxed.total_values_length();
+ string_offset_type input_nstrings = static_cast<string_offset_type>(input.length);
+
+ string_offset_type output_nbytes_max = input_nbytes;
+ int64_t output_nstrings_max = Derived::CalculateMaxSplits(input_boxed, options);
Review comment:
You should also take into account `options.max_splits`, no?
----------------------------------------------------------------
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] maartenbreddels commented on pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-704888455
@pitrou @jorisvandenbossche I think this is ready for review, provided the points below are not an issue.
Open questions
* kernel name: string_split_pattern vs split_pattern. I can imagine that we also want to support binary_split_pattern, so should we have to separate kernel names for this, or keep it split_pattern and implement support for binary in the future?
* API docs: I'm not sure the compute.rst docs I added should follow some standard, or if that table can be produce using some tool, I've done it by hand for now.
* Should split_pattern be a binary kernel, where pattern is the second argument? As @jorisvandenbossche suggested we could start by only implementing only the second argument being a scalar. I tried to implement this, but I had to change the testing framework/tools for this a lot. So I think the should be a separate issue, otherwise this PR will never end. OTOH, this will mean a breaking change.
----------------------------------------------------------------
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] maartenbreddels commented on pull request #8271: ARROW-9991: [C++] split kernels for strings/binary
Posted by GitBox <gi...@apache.org>.
maartenbreddels commented on pull request #8271:
URL: https://github.com/apache/arrow/pull/8271#issuecomment-712043258
Hi @pitrou, yes, I've addressed all comments, should be good for a (last?) review.
----------------------------------------------------------------
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