Skip to content

Optimize Array.quicksort#6324

Merged
Amxx merged 6 commits into
OpenZeppelin:masterfrom
Amxx:optimize/quicksort
Jul 3, 2026
Merged

Optimize Array.quicksort#6324
Amxx merged 6 commits into
OpenZeppelin:masterfrom
Amxx:optimize/quicksort

Conversation

@Amxx

@Amxx Amxx commented Jan 30, 2026 •
edited
Loading

Copy link
Copy Markdown
Collaborator

Fixes #6289
Replaces #6319 that include unecessary package updates and lint changes.

I was not able to observe any gas improvements when running tests with array length <= 128.
However, this code change supports increassing our tests to arrays of 256 and 384 elements (which used to not pass because of the stack too deep issue). Testing on 512 elements will still fail (out of gas)

PR Checklist

  • Tests
  • Changeset entry (run npx changeset add)

@Amxx Amxx requested a review from a team as a code owner January 30, 2026 15:35
@changeset-bot

changeset-bot Bot commented Jan 30, 2026 •
edited
Loading

Copy link
Copy Markdown

🦋 Changeset detected

Latest commit: aaeedd0

The changes in this PR will be included in the next version bump.

This PR includes changesets to release 1 package
Name Type
openzeppelin-solidity Minor

Not sure what this means? Click here to learn what changesets are.

Click here if you're a maintainer who wants to add another changeset to this PR

@coderabbitai

coderabbitai Bot commented Jan 30, 2026

Copy link
Copy Markdown
Contributor

Walkthrough

This pull request modifies the _quickSort function in the Arrays utility to optimize recursion depth. The implementation converts the previously recursive quicksort algorithm into a hybrid approach using a while loop for processing larger partitions, while maintaining recursive calls only for smaller partitions. This reduces maximum call stack depth and enables sorting of larger arrays. The changes are applied to both the Solidity contract code and the corresponding JavaScript template. Test coverage is expanded to include larger array sizes, including 384-element arrays.

🚥 Pre-merge checks | ✅ 5
✅ Passed checks (5 passed)
Check name Status Explanation
Title check ✅ Passed Title 'Optimize Array.quicksort' clearly summarizes the main change, directly matching the primary objective of optimizing the quicksort implementation to prevent stack overflow.
Description check ✅ Passed Description relates to the changeset by explaining the fix for issue #6289, mentioning stack depth limitations, and referencing the test expansion and changeset entry.
Linked Issues check ✅ Passed PR changes implement the core requirement from #6289: converting recursive calls to an iterative loop approach. The implementation replaces the base-case guard with a while loop and applies the smaller-partition-first recursion strategy as suggested.
Out of Scope Changes check ✅ Passed All changes are in-scope: contracts/utils/Arrays.sol implements the optimization, scripts/generate/templates/Arrays.js mirrors the implementation, test/utils/Arrays.test.js expands test coverage for validation, and .changeset/ documents the change.
Docstring Coverage ✅ Passed No functions found in the changed files to evaluate docstring coverage. Skipping docstring coverage check.

✏️ Tip: You can configure your own custom pre-merge checks in the settings.

✨ Finishing touches
  • 📝 Generate docstrings
🧪 Generate unit tests (beta)
  • Create PR with unit tests
  • Post copyable unit tests in a comment

Tip

🧪 Unit Test Generation v2 is now available!

We have significantly improved our unit test generation capabilities.

To enable: Add this to your .coderabbit.yaml configuration:

reviews:
  finishing_touches:
    unit_tests:
      enabled: true

Try it out by using the @coderabbitai generate unit tests command on your code files or under ✨ Finishing Touches on the walkthrough!

Have feedback? Share your thoughts on our Discord thread!

Comment @coderabbitai help to get the list of available commands and usage tips.

clawdhash

This comment was marked as spam.

Sign in to view

clawdhash

This comment was marked as spam.

Sign in to view

clawdhash

This comment was marked as spam.

Sign in to view

clawdhash

This comment was marked as spam.

Sign in to view

@Amxx Amxx added this to the 5.7 milestone Feb 26, 2026
@Amxx Amxx requested a review from ernestognw February 26, 2026 14:48
This was referenced Mar 2, 2026
Closed
Closed
@Amxx Amxx mentioned this pull request Mar 13, 2026
Closed
@Amxx Amxx mentioned this pull request Mar 23, 2026
Closed
@Amxx Amxx mentioned this pull request Apr 20, 2026
Closed
1 task
@Amxx Amxx mentioned this pull request May 14, 2026
Closed
3 tasks
@Amxx Amxx mentioned this pull request Jul 3, 2026
Closed
ernestognw
ernestognw approved these changes Jul 3, 2026
View reviewed changes

@ernestognw ernestognw left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Minor nit

Comment thread test/utils/Arrays.test.js
@Amxx Amxx merged commit a22c886 into OpenZeppelin:master Jul 3, 2026
21 checks passed
@Amxx Amxx deleted the optimize/quicksort branch July 3, 2026 16:58
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@ernestognw ernestognw ernestognw approved these changes
+1 more reviewer
@clawdhash clawdhash clawdhash left review comments
Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

5.7

Development

Successfully merging this pull request may close these issues.

Function _quickSort() can be optimized

3 participants

@Amxx @ernestognw @clawdhash