Reevaluate Array/TypedArray insertion sort threshold
Categories
(Core :: JavaScript Engine, task, P3)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox127 | --- | fixed |
People
(Reporter: jandem, Assigned: jandem)
References
(Blocks 1 open bug)
Details
Attachments
(2 files)
When sorting with a comparator, we use insertion sort instead of merge sort for "small" arrays. The current limit is length < 24 for arrays and length < 8 for typed arrays.
I took these values from the previous self-hosted implementation to not change behavior (the number of comparator calls), but now that the sorting core code is shared we should measure this again and use the same value for both.
|
Assignee | |
Comment 1•7 months ago
|
||
I collected some data on insertion sort vs merge sort. This has the number of comparator calls and the time in ms for lengths 4 to 24 for various cases.
The performance numbers should be taken with a grain of salt because the numbers were pretty noisy.
This shows that the current limit of length < 24 for Array sort is too high: it results in a lot more calls to the comparator function. Insertion sort also has bad worst-case performance for arrays with elements in decreasing order.
A higher limit for insertion sort made sense when we had to allocate temporary objects for merge sort in self-hosted code, but now that we use scratch space in the C++ value vector, a limit of 9-10 seems more reasonable.
|
||
Updated•7 months ago
|
|
|
Assignee | |
Comment 2•7 months ago
|
||
The core sorting code is now shared so we should use the same limit for these two cases.
The maximum length for insertion sort for Array changes from 23 to 8 and for typed
arrays from 7 to 8. Numbers in the bug show this reduces the number of comparator calls.
The self-hosted code likely used a higher limit for arrays because merge sort required an
extra JS array allocation.
Description
•