[Stdlib] Use memcpy in List.pop() for trivially movable types#5947
Open
msaelices wants to merge 3 commits intomodular:mainfrom
Open
[Stdlib] Use memcpy in List.pop() for trivially movable types#5947msaelices wants to merge 3 commits intomodular:mainfrom
msaelices wants to merge 3 commits intomodular:mainfrom
Conversation
For types with trivial move semantics, use memcpy to shift trailing elements instead of an element-by-element loop. This follows the same pattern already used in List._realloc() and List.extend(). Signed-off-by: Manuel Saelices <msaelices@gmail.com>
Add benchmarks for List.pop() covering pop from end, front, and middle positions, as well as non-trivially movable types (String) for comparison. Signed-off-by: Manuel Saelices <msaelices@gmail.com>
Use unified closures, black_box, and remove unnecessary raises. Signed-off-by: Manuel Saelices <msaelices@gmail.com>
Contributor
There was a problem hiding this comment.
Pull request overview
This PR optimizes List.pop() to use memcpy for types with trivial move semantics instead of an element-by-element loop when shifting trailing elements. This optimization pattern is already used in other List methods like _realloc() and extend(). The PR also adds comprehensive benchmarks to measure the performance improvement.
Changes:
- Modified
List.pop()to usememcpyfor trivially movable types, achieving up to 2.97x speedup for middle pops on large lists - Added benchmark file with tests for pop operations from different positions (end, front, middle) and for non-trivially movable types
Reviewed changes
Copilot reviewed 2 out of 2 changed files in this pull request and generated no comments.
| File | Description |
|---|---|
| mojo/stdlib/std/collections/list.mojo | Added conditional memcpy optimization in pop() method for trivially movable types |
| mojo/stdlib/benchmarks/collections/bench_list.mojo | New benchmark file measuring pop performance for various positions and type characteristics |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
For types with trivial move semantics, use
memcpyto shift trailing elements inList.pop()instead of an element-by-element loop. This follows the same pattern already used inList._realloc()andList.extend().Benchmarks (median, 10 repetitions)
pop_front[100]pop_front[1000]pop_front[10000]pop_middle[1000]pop_middle[10000]Non-trivially movable types (e.g.
String) are unaffected and continue using the element-by-element loop.