Closed Bug 1893977 Opened 6 months ago Closed 5 months ago

Reevaluate Array/TypedArray insertion sort threshold

Categories

(Core :: JavaScript Engine, task, P3)

task

Tracking

()

RESOLVED FIXED
127 Branch
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.

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.

Blocks: sm-js-perf
Severity: -- → S3
Priority: -- → P3

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.

Pushed by jdemooij@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/287f670c824e Use same insertion sort limit for Array and TypedArray sorting. r=iain
Status: ASSIGNED → RESOLVED
Closed: 5 months ago
Resolution: --- → FIXED
Target Milestone: --- → 127 Branch
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: