703446 - tune merge sort implementation

Status: NEW

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

The bug #701560 changes the merge sort implementation to use a comparator template, not a function pointer, without changing the implementation itself. It would be interesting to investigate at least the following:

1. Investigate different values of INS_SORT_LIMIT. I observed that setting INS_SORT_LIMIT to 3 instead of the current 4 made the sort to run up to 10% in few samples. But this requires broader testing.

2. Investigate dynamic INS_SORT_LIMIT to eliminate the need for the final copy as suggested in bug 701560 comment 2.

3. Investigate another suggestion from the bug 701560 comment 2 of using a binary merge when the second array run is much smaller than the first one.

4. Consider decreasing the scratch space length requirement to nelems/2 via using in place merge when the smaller run to merge is copied first to the scratch space.

Comment 1

[Emanuel Hoogeveen [:ehoogeveen]]

It would be interesting to see how time spent in the current sorting function breaks down in terms of
1) comparisons (calling into js, long strings etc.)
2) moves (large objects, deep copying)
3) sorting function overhead (complexity, bad code)

For instance if comparisons are a big bottleneck and the number of objects to sort is not extremely large (merge sort is very comparison-efficient when the two arrays to merge are large), one could consider combining Ford-Johnson sort (optimal binary insertion) with optimal merging (a la Christen, 1978).

If on the other hand moves or sorting function overhead play a big role, then Ford-Johnson sort (which has O(n²) moves and fairly high complexity) is probably not worth trying.

Will the sorting function be used for many different kinds of lists or is its application limited to a few well known types of objects?