gemini-code-assist[bot] commented on code in PR #443:
URL: https://github.com/apache/tvm-ffi/pull/443#discussion_r2797222118
##########
python/tvm_ffi/container.py:
##########
@@ -209,6 +224,146 @@ def __radd__(self, other: Iterable[T]) -> Array[T]:
return type(self)(itertools.chain(other, self))
+@register_object("ffi.List")
+class List(core.Object, MutableSequence[T]):
+ """Mutable list container that represents a mutable sequence in the FFI."""
+
+ # tvm-ffi-stubgen(begin): object/ffi.List
+ # fmt: off
+ # fmt: on
+ # tvm-ffi-stubgen(end)
+
+ def __init__(self, input_list: Iterable[T] = ()) -> None:
+ """Construct a List from a Python sequence."""
+ self.__init_handle_by_constructor__(_ffi_api.List, *input_list)
+
+ @overload
+ def __getitem__(self, idx: SupportsIndex, /) -> T: ...
+
+ @overload
+ def __getitem__(self, idx: slice, /) -> list[T]: ...
+
+ def __getitem__(self, idx: SupportsIndex | slice, /) -> T | list[T]: #
ty: ignore[invalid-method-override]
+ """Return one element or a list for a slice."""
+ length = len(self)
+ return getitem_helper(self, _ffi_api.ListGetItem, length, idx)
+
+ @overload
+ def __setitem__(self, index: SupportsIndex, value: T) -> None: ...
+
+ @overload
+ def __setitem__(self, index: slice[int | None], value: Iterable[T]) ->
None: ...
+
+ def __setitem__(self, index: SupportsIndex | slice[int | None], value: T |
Iterable[T]) -> None:
+ """Set one element or assign a slice."""
+ if isinstance(index, slice):
+ replacement = list(cast(Iterable[T], value))
+ length = len(self)
+ start, stop, step = index.indices(length)
+ if step != 1:
+ target_indices = list(range(start, stop, step))
+ if len(replacement) != len(target_indices):
+ raise ValueError(
+ "attempt to assign sequence of size "
+ f"{len(replacement)} to extended slice of size
{len(target_indices)}"
+ )
+ for i, item in zip(target_indices, replacement):
+ _ffi_api.ListSetItem(self, i, item)
+ return
+ remove_count = max(0, stop - start)
+ for _ in range(remove_count):
+ _ffi_api.ListErase(self, start)
+ for offset, item in enumerate(replacement):
+ _ffi_api.ListInsert(self, start + offset, item)
+ return
Review Comment:
This implementation of slice assignment is inefficient as it calls
`ListErase` and `ListInsert` in a loop, leading to multiple FFI calls and
repeated data shifting. This can be very slow for large slices.
Consider adding a dedicated C++ backend function, e.g.,
`ListReplaceSlice(self, start, stop, replacement)`, that can perform the slice
replacement in a single, more efficient operation. This would involve
calculating the new size, moving the tail of the list if necessary, destructing
old elements, and constructing new ones, all within one C++ function.
##########
include/tvm/ffi/container/list.h:
##########
@@ -0,0 +1,772 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file tvm/ffi/container/list.h
+ * \brief Mutable list type.
+ *
+ * tvm::ffi::List<Any> is an erased mutable sequence container.
+ */
+#ifndef TVM_FFI_CONTAINER_LIST_H_
+#define TVM_FFI_CONTAINER_LIST_H_
+
+#include <tvm/ffi/any.h>
+#include <tvm/ffi/container/array.h>
+#include <tvm/ffi/object.h>
+
+#include <algorithm>
+#include <initializer_list>
+#include <new>
+#include <sstream>
+#include <string>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+namespace tvm {
+namespace ffi {
+
+/*! \brief List node content in list */
+class ListObj : public Object, protected TVMFFISeqCell {
+ public:
+ ~ListObj() {
+ Any* begin = MutableBegin();
+ for (int64_t i = 0; i < length; ++i) {
+ (begin + i)->Any::~Any();
+ }
+ TVM_FFI_ICHECK(data_deleter != nullptr);
+ data_deleter(data);
+ }
+
+ /*! \return The size of the list */
+ size_t size() const { return static_cast<size_t>(length); }
+
+ /*!
+ * \brief Read i-th element from list.
+ * \param i The index
+ * \return the i-th element.
+ */
+ const Any& at(int64_t i) const { return this->operator[](i); }
+
+ /*!
+ * \brief Read i-th element from list.
+ * \param i The index
+ * \return the i-th element.
+ */
+ const Any& operator[](int64_t i) const {
+ if (i < 0 || i >= length) {
+ TVM_FFI_THROW(IndexError) << "Index " << i << " out of bounds " <<
length;
+ }
+ return MutableBegin()[i];
+ }
+
+ /*! \return begin constant iterator */
+ const Any* begin() const { return MutableBegin(); }
+
+ /*! \return end constant iterator */
+ const Any* end() const { return MutableBegin() + length; }
+
+ /*! \brief Release reference to all the elements */
+ void clear() { ShrinkBy(length); }
+
+ /*!
+ * \brief Set i-th element of the list in-place
+ * \param i The index
+ * \param item The value to be set
+ */
+ void SetItem(int64_t i, Any item) {
+ if (i < 0 || i >= length) {
+ TVM_FFI_THROW(IndexError) << "Index " << i << " out of bounds " <<
length;
+ }
+ MutableBegin()[i] = std::move(item);
+ }
+
+ /*!
+ * \brief Constructs a container with n elements. Each element is a copy of
val
+ * \param n The size of the container
+ * \param val The init value
+ * \return Ref-counted ListObj requested
+ */
+ static ObjectPtr<ListObj> CreateRepeated(int64_t n, const Any& val) {
+ ObjectPtr<ListObj> p = ListObj::Empty(n);
+ Any* itr = p->MutableBegin();
+ for (int64_t& i = p->length = 0; i < n; ++i) {
+ new (itr++) Any(val);
+ }
+ return p;
+ }
+
+ /// \cond Doxygen_Suppress
+ static constexpr const int32_t _type_index = TypeIndex::kTVMFFIList;
+ static const constexpr bool _type_final = true;
+ TVM_FFI_DECLARE_OBJECT_INFO_STATIC(StaticTypeKey::kTVMFFIList, ListObj,
Object);
+ /// \endcond
+
+ private:
+ /*! \return begin mutable iterator */
+ Any* MutableBegin() const { return static_cast<Any*>(this->data); }
+
+ /*! \return end mutable iterator */
+ Any* MutableEnd() const { return MutableBegin() + length; }
+
+ /*!
+ * \brief Emplace a new element at the given index
+ * \param idx The index of the element.
+ * \param args The arguments to construct the new element
+ */
+ template <typename... Args>
+ void EmplaceInit(size_t idx, Args&&... args) {
+ Any* itr = MutableBegin() + idx;
+ new (itr) Any(std::forward<Args>(args)...);
+ }
+
+ /*!
+ * \brief Inplace-initialize the elements starting idx from [first, last)
+ * \param idx The starting point
+ * \param first Begin of iterator
+ * \param last End of iterator
+ * \tparam IterType The type of iterator
+ * \return Self
+ */
+ template <typename IterType>
+ ListObj* InitRange(int64_t idx, IterType first, IterType last) {
+ Any* itr = MutableBegin() + idx;
+ for (; first != last; ++first) {
+ Any ref = *first;
+ new (itr++) Any(std::move(ref));
+ }
+ return this;
+ }
+
+ /*!
+ * \brief Move elements from right to left, requires src_begin > dst
+ * \param dst Destination
+ * \param src_begin The start point of copy (inclusive)
+ * \param src_end The end point of copy (exclusive)
+ * \return Self
+ */
+ ListObj* MoveElementsLeft(int64_t dst, int64_t src_begin, int64_t src_end) {
+ Any* from = MutableBegin() + src_begin;
+ Any* to = MutableBegin() + dst;
+ while (src_begin++ != src_end) {
+ *to++ = std::move(*from++);
+ }
+ return this;
+ }
Review Comment:
The manual loop for moving elements can be replaced with `std::move` for
better readability and to potentially leverage compiler optimizations for
memory movement.
```c
ListObj* MoveElementsLeft(int64_t dst, int64_t src_begin, int64_t src_end)
{
Any* from = MutableBegin() + src_begin;
Any* to = MutableBegin() + dst;
std::move(from, from + (src_end - src_begin), to);
return this;
}
```
##########
include/tvm/ffi/container/list.h:
##########
@@ -0,0 +1,772 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file tvm/ffi/container/list.h
+ * \brief Mutable list type.
+ *
+ * tvm::ffi::List<Any> is an erased mutable sequence container.
+ */
+#ifndef TVM_FFI_CONTAINER_LIST_H_
+#define TVM_FFI_CONTAINER_LIST_H_
+
+#include <tvm/ffi/any.h>
+#include <tvm/ffi/container/array.h>
+#include <tvm/ffi/object.h>
+
+#include <algorithm>
+#include <initializer_list>
+#include <new>
+#include <sstream>
+#include <string>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+namespace tvm {
+namespace ffi {
+
+/*! \brief List node content in list */
+class ListObj : public Object, protected TVMFFISeqCell {
+ public:
+ ~ListObj() {
+ Any* begin = MutableBegin();
+ for (int64_t i = 0; i < length; ++i) {
+ (begin + i)->Any::~Any();
+ }
+ TVM_FFI_ICHECK(data_deleter != nullptr);
+ data_deleter(data);
+ }
+
+ /*! \return The size of the list */
+ size_t size() const { return static_cast<size_t>(length); }
+
+ /*!
+ * \brief Read i-th element from list.
+ * \param i The index
+ * \return the i-th element.
+ */
+ const Any& at(int64_t i) const { return this->operator[](i); }
+
+ /*!
+ * \brief Read i-th element from list.
+ * \param i The index
+ * \return the i-th element.
+ */
+ const Any& operator[](int64_t i) const {
+ if (i < 0 || i >= length) {
+ TVM_FFI_THROW(IndexError) << "Index " << i << " out of bounds " <<
length;
+ }
+ return MutableBegin()[i];
+ }
+
+ /*! \return begin constant iterator */
+ const Any* begin() const { return MutableBegin(); }
+
+ /*! \return end constant iterator */
+ const Any* end() const { return MutableBegin() + length; }
+
+ /*! \brief Release reference to all the elements */
+ void clear() { ShrinkBy(length); }
+
+ /*!
+ * \brief Set i-th element of the list in-place
+ * \param i The index
+ * \param item The value to be set
+ */
+ void SetItem(int64_t i, Any item) {
+ if (i < 0 || i >= length) {
+ TVM_FFI_THROW(IndexError) << "Index " << i << " out of bounds " <<
length;
+ }
+ MutableBegin()[i] = std::move(item);
+ }
+
+ /*!
+ * \brief Constructs a container with n elements. Each element is a copy of
val
+ * \param n The size of the container
+ * \param val The init value
+ * \return Ref-counted ListObj requested
+ */
+ static ObjectPtr<ListObj> CreateRepeated(int64_t n, const Any& val) {
+ ObjectPtr<ListObj> p = ListObj::Empty(n);
+ Any* itr = p->MutableBegin();
+ for (int64_t& i = p->length = 0; i < n; ++i) {
+ new (itr++) Any(val);
+ }
+ return p;
+ }
+
+ /// \cond Doxygen_Suppress
+ static constexpr const int32_t _type_index = TypeIndex::kTVMFFIList;
+ static const constexpr bool _type_final = true;
+ TVM_FFI_DECLARE_OBJECT_INFO_STATIC(StaticTypeKey::kTVMFFIList, ListObj,
Object);
+ /// \endcond
+
+ private:
+ /*! \return begin mutable iterator */
+ Any* MutableBegin() const { return static_cast<Any*>(this->data); }
+
+ /*! \return end mutable iterator */
+ Any* MutableEnd() const { return MutableBegin() + length; }
+
+ /*!
+ * \brief Emplace a new element at the given index
+ * \param idx The index of the element.
+ * \param args The arguments to construct the new element
+ */
+ template <typename... Args>
+ void EmplaceInit(size_t idx, Args&&... args) {
+ Any* itr = MutableBegin() + idx;
+ new (itr) Any(std::forward<Args>(args)...);
+ }
+
+ /*!
+ * \brief Inplace-initialize the elements starting idx from [first, last)
+ * \param idx The starting point
+ * \param first Begin of iterator
+ * \param last End of iterator
+ * \tparam IterType The type of iterator
+ * \return Self
+ */
+ template <typename IterType>
+ ListObj* InitRange(int64_t idx, IterType first, IterType last) {
+ Any* itr = MutableBegin() + idx;
+ for (; first != last; ++first) {
+ Any ref = *first;
+ new (itr++) Any(std::move(ref));
+ }
+ return this;
+ }
+
+ /*!
+ * \brief Move elements from right to left, requires src_begin > dst
+ * \param dst Destination
+ * \param src_begin The start point of copy (inclusive)
+ * \param src_end The end point of copy (exclusive)
+ * \return Self
+ */
+ ListObj* MoveElementsLeft(int64_t dst, int64_t src_begin, int64_t src_end) {
+ Any* from = MutableBegin() + src_begin;
+ Any* to = MutableBegin() + dst;
+ while (src_begin++ != src_end) {
+ *to++ = std::move(*from++);
+ }
+ return this;
+ }
+
+ /*!
+ * \brief Move elements from left to right, requires src_begin < dst
+ * \param dst Destination
+ * \param src_begin The start point of move (inclusive)
+ * \param src_end The end point of move (exclusive)
+ * \return Self
+ */
+ ListObj* MoveElementsRight(int64_t dst, int64_t src_begin, int64_t src_end) {
+ Any* from = MutableBegin() + src_end;
+ Any* to = MutableBegin() + (src_end - src_begin + dst);
+ while (src_begin++ != src_end) {
+ *--to = std::move(*--from);
+ }
+ return this;
+ }
Review Comment:
The manual loop for moving elements in reverse can be replaced with
`std::move_backward` for better readability and to potentially leverage
compiler optimizations.
```c
ListObj* MoveElementsRight(int64_t dst, int64_t src_begin, int64_t
src_end) {
Any* from_begin = MutableBegin() + src_begin;
Any* from_end = MutableBegin() + src_end;
Any* to_end = MutableBegin() + (src_end - src_begin + dst);
std::move_backward(from_begin, from_end, to_end);
return this;
}
```
##########
python/tvm_ffi/container.py:
##########
@@ -209,6 +224,146 @@ def __radd__(self, other: Iterable[T]) -> Array[T]:
return type(self)(itertools.chain(other, self))
+@register_object("ffi.List")
+class List(core.Object, MutableSequence[T]):
+ """Mutable list container that represents a mutable sequence in the FFI."""
+
+ # tvm-ffi-stubgen(begin): object/ffi.List
+ # fmt: off
+ # fmt: on
+ # tvm-ffi-stubgen(end)
+
+ def __init__(self, input_list: Iterable[T] = ()) -> None:
+ """Construct a List from a Python sequence."""
+ self.__init_handle_by_constructor__(_ffi_api.List, *input_list)
+
+ @overload
+ def __getitem__(self, idx: SupportsIndex, /) -> T: ...
+
+ @overload
+ def __getitem__(self, idx: slice, /) -> list[T]: ...
+
+ def __getitem__(self, idx: SupportsIndex | slice, /) -> T | list[T]: #
ty: ignore[invalid-method-override]
+ """Return one element or a list for a slice."""
+ length = len(self)
+ return getitem_helper(self, _ffi_api.ListGetItem, length, idx)
+
+ @overload
+ def __setitem__(self, index: SupportsIndex, value: T) -> None: ...
+
+ @overload
+ def __setitem__(self, index: slice[int | None], value: Iterable[T]) ->
None: ...
+
+ def __setitem__(self, index: SupportsIndex | slice[int | None], value: T |
Iterable[T]) -> None:
+ """Set one element or assign a slice."""
+ if isinstance(index, slice):
+ replacement = list(cast(Iterable[T], value))
+ length = len(self)
+ start, stop, step = index.indices(length)
+ if step != 1:
+ target_indices = list(range(start, stop, step))
+ if len(replacement) != len(target_indices):
+ raise ValueError(
+ "attempt to assign sequence of size "
+ f"{len(replacement)} to extended slice of size
{len(target_indices)}"
+ )
+ for i, item in zip(target_indices, replacement):
+ _ffi_api.ListSetItem(self, i, item)
+ return
+ remove_count = max(0, stop - start)
+ for _ in range(remove_count):
+ _ffi_api.ListErase(self, start)
+ for offset, item in enumerate(replacement):
+ _ffi_api.ListInsert(self, start + offset, item)
+ return
+
+ normalized_index = normalize_index(len(self), index)
+ _ffi_api.ListSetItem(self, normalized_index, cast(T, value))
+
+ @overload
+ def __delitem__(self, index: SupportsIndex) -> None: ...
+
+ @overload
+ def __delitem__(self, index: slice[int | None]) -> None: ...
+
+ def __delitem__(self, index: SupportsIndex | slice[int | None]) -> None:
+ """Delete one element or a slice."""
+ if isinstance(index, slice):
+ length = len(self)
+ start, stop, step = index.indices(length)
+ if step == 1:
+ for _ in range(max(0, stop - start)):
+ _ffi_api.ListErase(self, start)
Review Comment:
Deleting a slice by calling `ListErase` in a loop is inefficient due to
multiple FFI calls and repeated shifting of elements. For a slice `[a:b]`, this
results in O((b-a) * N) complexity where it should be O(N).
It would be much more efficient to implement a `ListEraseRange(self, start,
stop)` function in the C++ backend to remove a range of elements in a single
operation.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
