Selector: Optimize jQuery.uniqueSort duplicate removal#5830
Conversation
gibson042
left a comment
There was a problem hiding this comment.
This makes sense intuitively, and I also confirmed that this is significantly faster in practice after refactoring the new implementation for an apples-to-apples comparison regarding how to loop: https://jsfiddle.net/fnr2jLgz/
I'd like to accept this, but we should iterate on optimizing its post-gzip size.
| var j = 0, | ||
| i = 0; |
There was a problem hiding this comment.
These can both just start at one, eliminating the initial reassignment.
| var j = 0, | |
| i = 0; | |
| var j = 1, | |
| i = 1; |
| j = 1; | ||
| for ( i = 1; i < results.length; i++ ) { |
There was a problem hiding this comment.
| j = 1; | |
| for ( i = 1; i < results.length; i++ ) { | |
| for ( ; i < results.length; i++ ) { |
This deviates from most of our loops, which have the form they do because of a historical need to work with NodeLists in which the numeric length might be shadowed by a constituent element with id "length". But performance-wise, it's much preferable to avoid walking off the end of a collection, especially when it is an array (#3769), and I'd like to migrate to this pattern (and I think we're safe here even without broad migration).
And all that aside, this should be preceded by an explanatory comment, e.g.
| j = 1; | |
| for ( i = 1; i < results.length; i++ ) { | |
| // Pack the first instance of each unique element into the start of | |
| // results (starting at index 1 because index 0 is always kept), then | |
| // splice away the tail of duplicates. | |
| for ( ; i < results.length; i++ ) { |
| while ( j-- ) { | ||
| splice.call( results, duplicates[ j ], 1 ); | ||
| } | ||
| splice.call( results, j, results.length - j ); |
There was a problem hiding this comment.
deleteCount can be omitted to delete all elements from the specified index.
| splice.call( results, j, results.length - j ); | |
| splice.call( results, j ); |
And we can also get a substantial speedup of this final step when dealing with an actual array rather than a jQuery instance (about 3x in V8/Chrome and 1.5x in JavaScriptCore/Safari):
| splice.call( results, j, results.length - j ); | |
| if (Array.isArray(results)) { | |
| results.length = j; | |
| } else { | |
| splice.call( results, j ); | |
| } |
|
@gibson042 i updated as per u suggested |
Refactor the duplicate removal logic in `jQuery.uniqueSort` to improve performance and reduce memory overhead. The previous implementation relied on repeated splice operations inside a loop and used an auxiliary duplicates array, resulting in O(N²) time complexity and O(N) additional space in the worst case. This patch replaces that logic with a two-pointer array compaction approach that performs deduplication in a single pass and trims the array with a single splice call. Key improvements: - Reduces time complexity of duplicate removal from O(N²) to O(N) - Eliminates auxiliary array usage (O(N) → O(1) space) - Preserves existing behavior and output ordering - Keeps in-place mutation semantics unchanged Closes gh-5830
|
Landed on |
Summary
This PR refactors the duplicate removal logic in jQuery.uniqueSort to improve performance and reduce memory overhead.
The previous implementation relied on repeated splice operations inside a loop and used an auxiliary duplicates array, resulting in O(N²) time complexity and O(N) additional space in the worst case.
This patch replaces that logic with a two-pointer array compaction approach that performs deduplication in a single pass and trims the array with a single splice call.
Key improvements: