You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Godot's list is implemented as a linked list, where direct index access operations (operator[]) do not have constant time complexity (see the code below). This characteristic can lead to unintended performance degradation, especially in scenarios where such access patterns are frequent.
T &operator[](int p_index) {
CRASH_BAD_INDEX(p_index, size());
Element *I = front();
int c = 0;
while (c < p_index) {
I = I->next();
c++;
}
return I->get();
}
The convenience of operator[] for element access in List can sometimes obscure the underlying performance implications, especially for those who might not be immediately aware that List is a linked list, not an array or array-like structure. For some performance degradation examples, see #88785 and #80857 , both of them are using operator[] in a for loop which is doing repeated pointer chasing all the time.
It's worth noting how other languages handle similar situations, in C++, the std::list does not support direct index access via operator[] or an at() method, rust takes a similar approach with its LinkedList where direct index access is also notably absent, promoting the use of iterators for traversing the list.
Thoughts for Improvement
I understand that this part of the codebase is quite mature and any changes to it would need to be considered very carefully. With utmost respect for the original design decisions, I'd like to propose some thoughts aimed at making the performance characteristics of list access more transparent:
Static Analysis Tools: Introduce static analysis tooling or linting warnings that can alert developers when operator[] is used on a List, especially in loops. This approach maintains backward compatibility while guiding developers towards more efficient patterns, like using iterators.
Deprecation: Consider deprecating operator[] for List, this is undoubtedly a more significant change. Deprecation could be accompanied by providing a new method with explicit performance implications in its naming (e.g., get_by_index_traversal).
(Also this is about code style not feature request, so I suppose posting a issue here is enough?)
Steps to reproduce
No
Minimal reproduction project (MRP)
N/A
The text was updated successfully, but these errors were encountered:
I have a feeling I tried this originally a few years ago as an experiment, but it would be nice if we could remove / hide, even if just in the core c++, as agreed it is too easy to do by accident.
Tested versions
All
System information
All
Issue description
Godot's list is implemented as a linked list, where direct index access operations (operator[]) do not have constant time complexity (see the code below). This characteristic can lead to unintended performance degradation, especially in scenarios where such access patterns are frequent.
The convenience of operator[] for element access in List can sometimes obscure the underlying performance implications, especially for those who might not be immediately aware that List is a linked list, not an array or array-like structure. For some performance degradation examples, see #88785 and #80857 , both of them are using operator[] in a for loop which is doing repeated pointer chasing all the time.
It's worth noting how other languages handle similar situations, in C++, the std::list does not support direct index access via operator[] or an at() method, rust takes a similar approach with its LinkedList where direct index access is also notably absent, promoting the use of iterators for traversing the list.
Thoughts for Improvement
I understand that this part of the codebase is quite mature and any changes to it would need to be considered very carefully. With utmost respect for the original design decisions, I'd like to propose some thoughts aimed at making the performance characteristics of list access more transparent:
Static Analysis Tools: Introduce static analysis tooling or linting warnings that can alert developers when operator[] is used on a List, especially in loops. This approach maintains backward compatibility while guiding developers towards more efficient patterns, like using iterators.
Deprecation: Consider deprecating operator[] for List, this is undoubtedly a more significant change. Deprecation could be accompanied by providing a new method with explicit performance implications in its naming (e.g., get_by_index_traversal).
(Also this is about code style not feature request, so I suppose posting a issue here is enough?)
Steps to reproduce
No
Minimal reproduction project (MRP)
N/A
The text was updated successfully, but these errors were encountered: