You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2022/09/02 19:13:30 UTC
[GitHub] [tvm] Lunderberg opened a new pull request, #12692: [Containers] Add Array::Map
Lunderberg opened a new pull request, #12692:
URL: https://github.com/apache/tvm/pull/12692
Previously, an in-place mutation could be applied to an array using `Array::MutateByApply`, but this couldn't be used for transformations that return a new array, or for transformations that return a new type. The PR adds `Array::Map`, which can map to any `ObjectRef` subclass. For mappings that return the same type, this is done by delegating to `Array::MutateByApply`, to take advantage of the same copy-on-write behavior.
For ease of review, this PR consists of two separate commits. The first implements `Array::Map`, while the second performs several small refactors
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] Lunderberg commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
Lunderberg commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r975393751
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
Review Comment:
No problem, and updated!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] Lunderberg commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
Lunderberg commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r974661862
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
Review Comment:
> What will be left over on the copy-on-write instance?
If we have compatible types, and we've reached this point, we've found at least one element for which the `mapped.same_as(*it)` check on line 776 has failed. In that case, `output` will contain everything in the range `[arr->begin(), it)`. That is, `output` contains all elements that are identical, and the first non-identical element. `it` will point to the next element that should be transformed, and so the next loop over `it` can continue where the first loop left off.
> Will there be some items that are incompatible?
It's entirely possible, either at compile-time or at runtime. For example, I could have an `Array<PrimExpr> buffer_shape` and map it to allowed ranges `buffer_shape.Map([](PrimExpr expr) { return Range::FromMinExtent(0, expr);});`, which would be incompatible and identified as such at compile-time. In that case, the `if constexpr` could identify that they cannot be represented by the same underlying array, and can skip the attempts to do so altogether.
If a type is incompatible at runtime, then it will also fail the `mapped.same_as(*it)` check on line 776. So if I have an `Array<Var>` being mapped to `Array<PrimExpr>` with `var_array.Map([&](Var var) { return var.same_as(to_replace) ? replace_with : var;});`, it may or may not be compatible, depending on whether `to_replace` shows up in the array.
> How are those guaranteed to be at the end?
Incompatible items may occur at any point in the mapped output, even at the very first iteration. In that case, the commands executed in the conditional on `!mapped.same_as(*it)` are the same as would be executed up through the first iteration of the mapping loop.
```c++
// Same as the else branch on `compatible_types`
output = ArrayNode::CreateRepeated(arr->size(), U());
// For the first iteration, it is `arr->begin()`, so this would be an
// empty range [begin, begin), nothing is initialized, and this
// statement has no effect.
output->InitRange(0, arr->begin(), it);
// The newly mapped item is stored to the first location of the output.
output->SetItem(it - arr->begin(), std::move(mapped));
// The loop increment that would have happened
it++;
// `it` now points to the second element of the input, and we have one
// mapped element in the output. We're now ready to start the second
// loop, just at the second iteration instead of the first.
```
Essentially, we only need to check for identical return values up until we find a single non-identical element, at which point we know that we can't avoid the copy anyways. But once we reach the first non-identical value, we don't need to repeat the function calls up to that point, because we know that everything is either identical (and can therefore be copied from the input) or is non-identical (is which case it is the first such non-identical value).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] tmoreau89 merged pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
tmoreau89 merged PR #12692:
URL: https://github.com/apache/tvm/pull/12692
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] Lunderberg commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
Lunderberg commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r963829092
##########
include/tvm/runtime/container/array.h:
##########
@@ -574,6 +574,44 @@ class Array : public ObjectRef {
/*! \return The underlying ArrayNode */
ArrayNode* GetArrayNode() const { return static_cast<ArrayNode*>(data_.get()); }
+ /*!
+ * \brief Helper function to apply a map function onto the array.
+ *
+ * \param fmap The transformation function T -> U.
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The type of the returned array, inferred from the
+ * return type of F. If overridden by the user, must be something
+ * that is convertible from the return type of F.
+ *
+ * \note This function performs copy on write optimization. If
+ * `fmap` returns an object of type `T`, and all elements of the
+ * array are mapped to themselves, then the returned array will be
+ * the same as the original, and reference counts of the elements in
+ * the array will not be incremented.
+ *
+ * \return The transformed array.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ Array<U> Map(F fmap) const {
Review Comment:
Thank you on the suggestion, and it ended up being much cleaner that way. Both `Map` and `MutateByApply` are now implemented in terms of the same underlying helper function. The helper function applies both the mutate-in-place and copy-on-write optimizations, with `if constexpr` type checks to avoid attempting the optimization if they wouldn't be possible.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] junrushao commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
junrushao commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r961961353
##########
include/tvm/runtime/container/array.h:
##########
@@ -574,6 +574,44 @@ class Array : public ObjectRef {
/*! \return The underlying ArrayNode */
ArrayNode* GetArrayNode() const { return static_cast<ArrayNode*>(data_.get()); }
+ /*!
+ * \brief Helper function to apply a map function onto the array.
+ *
+ * \param fmap The transformation function T -> U.
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The type of the returned array, inferred from the
+ * return type of F. If overridden by the user, must be something
+ * that is convertible from the return type of F.
+ *
+ * \note This function performs copy on write optimization. If
+ * `fmap` returns an object of type `T`, and all elements of the
+ * array are mapped to themselves, then the returned array will be
+ * the same as the original, and reference counts of the elements in
+ * the array will not be incremented.
+ *
+ * \return The transformed array.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ Array<U> Map(F fmap) const {
Review Comment:
I was curious if we could unify and migrate `MutateByApply` into `Map`?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] Lunderberg commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
Lunderberg commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r961967490
##########
include/tvm/runtime/container/array.h:
##########
@@ -574,6 +574,44 @@ class Array : public ObjectRef {
/*! \return The underlying ArrayNode */
ArrayNode* GetArrayNode() const { return static_cast<ArrayNode*>(data_.get()); }
+ /*!
+ * \brief Helper function to apply a map function onto the array.
+ *
+ * \param fmap The transformation function T -> U.
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The type of the returned array, inferred from the
+ * return type of F. If overridden by the user, must be something
+ * that is convertible from the return type of F.
+ *
+ * \note This function performs copy on write optimization. If
+ * `fmap` returns an object of type `T`, and all elements of the
+ * array are mapped to themselves, then the returned array will be
+ * the same as the original, and reference counts of the elements in
+ * the array will not be incremented.
+ *
+ * \return The transformed array.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ Array<U> Map(F fmap) const {
Review Comment:
Possibly, and that would allow for avoiding copies in a few additional cases (e.g. map from `T` to `Optional<T>`, or to a superclass of `T`) that aren't currently handled. I'll take a quick stab at it and see if I can unify the two.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] Lunderberg commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
Lunderberg commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r974697913
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ }
+
+ return output;
+ }
Review Comment:
Tests added for each of the compatible types, to validate that copies are avoided, and to ensure correct fail-through behavior when a copy is required. A double thanks for requesting it, as it also caught a type conversion error that I had missed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] janetsc commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
janetsc commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r974520581
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
Review Comment:
What will be left over on the copy-on-write instance? Will there be some items that are incompatible? How are those guaranteed to be at the end?
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ }
+
+ return output;
+ }
Review Comment:
General comment - Can you add a unit test to exercise the edge cases in MapHelper?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] janetsc commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
janetsc commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r974706379
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
Review Comment:
Thanks for this explanation!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] Lunderberg commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
Lunderberg commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r974662892
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ }
+
+ return output;
+ }
Review Comment:
Certainly, and thank you for pointing that out! There are some existing tests in [`container_test.cc`](https://github.com/apache/tvm/blob/main/tests/cpp/container_test.cc#L165), along with a large amount of usage when lowering TIR, but no tests that would specifically point to these edge cases.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] tmoreau89 commented on pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
tmoreau89 commented on PR #12692:
URL: https://github.com/apache/tvm/pull/12692#issuecomment-1252819368
@junrushao any additional requests on this PR? Thank you!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] tmoreau89 commented on pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
tmoreau89 commented on PR #12692:
URL: https://github.com/apache/tvm/pull/12692#issuecomment-1252897147
Awesome thank you @Lunderberg @janetsc @junrushao , the PR has been merged!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [tvm] janetsc commented on a diff in pull request #12692: [Containers] Add Array::Map
Posted by GitBox <gi...@apache.org>.
janetsc commented on code in PR #12692:
URL: https://github.com/apache/tvm/pull/12692#discussion_r974706379
##########
include/tvm/runtime/container/array.h:
##########
@@ -706,6 +710,98 @@ class Array : public ObjectRef {
}
return static_cast<ArrayNode*>(data_.get());
}
+
+ /*! \brief Helper method for mutate/map
+ *
+ * A helper function used internally by both `Array::Map` and
+ * `Array::MutateInPlace`. Given an array of data, apply the
+ * mapping function to each element, returning the collected array.
+ * Applies both mutate-in-place and copy-on-write optimizations, if
+ * possible.
+ *
+ * \param data A pointer to the ArrayNode containing input data.
+ * Passed by value to allow for mutate-in-place optimizations.
+ *
+ * \param fmap The mapping function
+ *
+ * \tparam F The type of the mutation function.
+ *
+ * \tparam U The output type of the mutation function. Inferred
+ * from the callable type given. Must inherit from ObjectRef.
+ *
+ * \return The mapped array. Depending on whether mutate-in-place
+ * or copy-on-write optimizations were applicable, may be the same
+ * underlying array as the `data` parameter.
+ */
+ template <typename F, typename U = std::invoke_result_t<F, T>>
+ static ObjectPtr<Object> MapHelper(ObjectPtr<Object> data, F fmap) {
+ if (data == nullptr) {
+ return nullptr;
+ }
+
+ ICHECK(data->IsInstance<ArrayNode>());
+
+ constexpr bool is_same_output_type = std::is_same_v<T, U>;
+
+ if constexpr (is_same_output_type) {
+ if (data.unique()) {
+ // Mutate-in-place path. Only allowed if the output type U is
+ // the same as type T, we have a mutable this*, and there are
+ // no other shared copies of the array.
+ auto arr = static_cast<ArrayNode*>(data.get());
+ for (auto it = arr->MutableBegin(); it != arr->MutableEnd(); it++) {
+ T mapped = fmap(DowncastNoCheck<T>(std::move(*it)));
+ *it = std::move(mapped);
+ }
+ return data;
+ }
+ }
+
+ constexpr bool compatible_types = is_valid_iterator_v<T, U*> || is_valid_iterator_v<U, T*>;
+
+ ObjectPtr<ArrayNode> output = nullptr;
+ auto arr = static_cast<ArrayNode*>(data.get());
+
+ auto it = arr->begin();
+ if constexpr (compatible_types) {
+ // Copy-on-write path, if the output Array<U> might be
+ // represented by the same underlying array as the existing
+ // Array<T>. Typically, this is for functions that map `T` to
+ // `T`, but can also apply to functions that map `T` to
+ // `Optional<T>`, or that map `T` to a subclass or superclass of
+ // `T`.
+ bool all_identical = true;
+ for (; it != arr->end(); it++) {
+ U mapped = fmap(DowncastNoCheck<T>(*it));
+ if (!mapped.same_as(*it)) {
+ all_identical = false;
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ output->InitRange(0, arr->begin(), it);
+ output->SetItem(it - arr->begin(), std::move(mapped));
+ it++;
+ break;
+ }
+ }
+ if (all_identical) {
+ return data;
+ }
+ } else {
+ // Path for incompatible types. The constexpr check for
+ // compatible types isn't strictly necessary, as the first
+ // mapped.same_as(*it) would return false, but we might as well
+ // avoid it altogether.
+ output = ArrayNode::CreateRepeated(arr->size(), U());
+ }
+
+ // Normal path for incompatible types, or post-copy path for
+ // copy-on-write instances.
Review Comment:
Thanks for this explanation! Maybe it would be helpful to others as well to summarize this in the comment block on 796...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org