preface

First of all, what does this code output?

[1.2.13.14.5.6.17.18.9.10.11.12.31.41].sort((a)= >0)
Copy the code

You might be smart enough to say, well, isn’t this an array that returns elements in the same order?

Emmm normally does, and then a buddy (Chrome V59 environment) ran into a problem like this

[1.2.13.14.5.6.17.18.9.10.11.12.31.41].sort((a)= >0)
/ /,1,13,14,5,6,17,2,9,10,11,12,31,41 [18]
[1.2.13.14.5.6.17.18.9.10].sort((a)= >0)
/ /,2,13,14,5,6,17,18,9,10 [1]
Copy the code

I then tested the results on my computer (Chrome V76)

[1.2.13.14.5.6.17.18.9.10.11.12.31.41].sort((a)= >0)
/ /,2,13,14,5,6,17,18,9,10,11,12,31,41 [1]
[1.2.13.14.5.6.17.18.9.10].sort((a)= >0)
/ /,2,13,14,5,6,17,18,9,10 [1]
Copy the code

We know that the comparison function that gives a sort returns 0 to indicate that the two elements currently being compared are equal

Sort ()=>0);

So why does sort(()=>0) look different for arrays of different lengths on earlier versions of Chrome?

This article will do an analysis. Through this article, you can learn:

  • Array.prototype.sort implementation details and legacy issues
  • How to read JS source code

define

arr.sort([compareFunction])
Copy the code

Here we quote a passage from MDN:

If compareFunction(a, b) is less than 0, then A is placed before B;

If compareFunction(a, b) is greater than 0, b will be placed before A.

If compareFunction(a, b) is equal to 0, the relative positions of a and B remain the same. Note: The ECMAScript standard does not guarantee this behavior, and not all browsers comply (e.g. Mozilla prior to 2003).

That is, some browsers do not follow the rule that the relative positions of a and B remain the same when compareFunction(a, b) is equal to 0

Here we see that Chrome V59 does not follow this rule. But if the array size is small, it seems to follow, right?

Here we assume that arrays of different lengths will use different sorting algorithms

Before we look at the source code, what is insert sort and quicksort

Sorting algorithm

Let’s assume that the comparison function is zero

comparefn = (a,b) = > a-b
Copy the code

1. Insert sort

Iterate through the array, inserting each element to be sorted into the appropriate position previously sorted

Insertion sort is divided into direct insertion sort, binary search insertion sort and Hill sort

Since V8 only uses direct insert sort, we will only implement it here. We will not discuss the other ones, but refer to optimized direct insert sort

The implementation code is as follows:

function InsertionSort(array) {
  for (let i = 1; i < array.legnth; i++) {
    let element = array[i];
    // Insert the element element to be sorted into place
    for (let j = i - 1; j >= 0; j--) {
      let tmp = array[j];
      // comparefn > 0 indicates that element comes before TMP
      if (comparefn(tmp, element) > 0) {
        a[j + 1] = tmp;
      } else {
        //
        break;
      }
    }
    a[j + 1] = element; }};Copy the code

2. Quicksort

Set a base value and divide the array into left and right parts using that base value size

At this point, the left and right parts can be sorted independently. Perform the above operations on the left and right parts respectively

Recursively, until the array is sorted

Considering the space consumption, the current quicksort generally refers to the in situ algorithm quicksort

For the in situ algorithm, see en.wikipedia.org/wiki/In-pla…

There are two implementations below, taking the base value to the left or the base value to the right

function qsort(array){
  function swap(arr,i1,i2){
    let tmp = arr[i1]
    arr[i1] = arr[i2]
    arr[i2] = tmp
  }
  function partition(arr, left, right){
    let storeIndex = left // The value is equal to the number of elements found that are less than the reference value
    let pivot = arr[right] / / benchmark
    for(leti=left; i<right; i++){if(arr[i]<pivot){
        swap(arr,storeIndex++,i)
      }
    }
    swap(arr,storeIndex,right)
    return storeIndex
  }
  // The benchmark is on the left
  // function partition(arr, left, right){
  // let storeIndex = left
  // let pivot = arr[left
  //   for(let i = left+1;i<=right;i++){
  // if(arr[i]
  // swap(arr,++storeIndex,i)
  / /}
  / /}
  // swap(arr,storeIndex,left)
  // return storeIndex
  // }
  function sort(arr,left,right){
    if(left<right){
      let storeIndex = partition(arr, left, right);
      sort(arr, left, storeIndex - 1);
      sort(arr, storeIndex + 1, right);
    }
  }
  sort(array, 0, array.length - 1);
  return array
}
Copy the code

V8 source code analysis

Now that you understand the basic sorting algorithm, let’s explore the source code.

Compare chrome V59 and Chrome V76 v8 implementation differences

How to find v8 source code for chrome version

Open the chrome: / / version

The JavaScript shown above is a version of V8

Google Chrome 76.0.3809.132 (official version) (64-bit) (Cohort: Stable) Windows 10 OS Version 1809 (Build 17763.316) JavaScript V8 7.6.303.29Copy the code

It is also as stated in V8’s Version numbering Scheme

Chromium 76 corresponds to v8 7.6

Then we went straight to V8 to view the source code, here mainly to see the two versions

5.9.221

Corresponding sorting algorithm source address

It is better combined with test cases/test/mjsunit/array-sort

As you can see, the early implementation logic for V8 sorting was written in JS and the corresponding implementation was ArraySort

utils.InstallFunctions(GlobalArray.prototype, DONT_ENUM, [
  ...
  "sort", getFunction("sort", ArraySort), ... ] )Copy the code
  • ArraySort

I don’t have any useful code, just go to InnerArraySort, right

function ArraySort(comparefn) {
  CHECK_OBJECT_COERCIBLE(this."Array.prototype.sort");

  var array = TO_OBJECT(this);
  var length = TO_LENGTH(array.length);
  return InnerArraySort(array, length, comparefn);
}
Copy the code
  • InnerArraySort

Array-like objects and empty arrays are treated in a special way, and then sorted

// comparefn is not callable (undefined, non-function, etc.), set the default function
if(! IS_CALLABLE(comparefn)) { comparefn =function (x, y) {
    if (x === y) return 0;
    if (% _IsSmi(x) && % _IsSmi(y)) {
      return % SmiLexicographicCompare(x, y);
    }
    x = TO_STRING(x);
    y = TO_STRING(y);
    if (x == y) return 0;
    else return x < y ? - 1 : 1;
  };
}
if (length < 2) return array;

var is_array = IS_ARRAY(array);
var max_prototype_element;
if(! is_array) {// Sort array objects like {length:10,0:'c',10:'b'}, compatible with JSC standards
  // Inheritance attributes are taken into account, so it may not be efficient, but there are fewer cases where sorting is required
  / / anyone can also look at the example https://github.com/v8/v8/blob/5.9.221/test/mjsunit/array-sort.js#L337
  /* let f1 = {1: "c", 3: "f"} let f2 = {6: "a", length: 10} f2.__proto__ = f1 f2 // {6: "a", length: 10,__proto__:{1: "c", 3: "f"}} Array.prototype.sort.call(f2) // {0: "a", 1: "b", 2: "c", 3: "f", length: 10} */
  // Returns the number of all attributes in the prototype chain and itself
  max_prototype_element = CopyFromPrototype(array, length);
}
// Quick RemoveArrayHoles: Copy the defined elements from the end of the array to fill the previous holes (the end becomes a hole)
// Quick RemoveArrayHoles are not supported and will return -1
// Otherwise returns the number of defined elements
var num_non_undefined = % RemoveArrayHoles(array, length);
// Handle things like array objects
if (num_non_undefined == - 1) {
  // Returns the number of defined instance attributes of the class array object
  num_non_undefined = SafeRemoveArrayHoles(array);
}

QuickSort(array, 0, num_non_undefined);

if(! is_array && (num_non_undefined +1 < max_prototype_element)) {
  // Handle cases like the same attribute of the prototype
  ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
}

return array;
Copy the code

Other special treatments are not covered in this text, but we will look directly at sorting implementations

  • QuickSort
function QuickSort (a, from, to) {
  // The benchmark selects the first element
  var third_index = 0;
  while (true) {
    // The length of the array to be sorted <= 10 uses insertion sort
    if (to - from< =10) {
      InsertionSort(a, from, to);
      return;
    }
    if (to - from > 1000) {
      // Every 200 ~ 215 (according to length & 15) elements,
      // Then sort the values and subscript the intermediate values
      // Sort is a recursive call
      third_index = GetThirdIndex(a, from, to);
    } else {
      // Set the intermediate element to the base value
      third_index = from + ((to - from) > >1);
    }
    // Take the median of the first, middle element (the reference value obtained above), and the last element as the reference value
    var v0 = a[from];
    var v1 = a[to - 1];
    var v2 = a[third_index];
    var c01 = comparefn(v0, v1);
    if (c01 > 0) {
      // v1 < v0, so swap them.
      var tmp = v0;
      v0 = v1;
      v1 = tmp;
    } // v0 <= v1.
    var c02 = comparefn(v0, v2);
    if (c02 >= 0) {
      // v2 <= v0 <= v1.
      var tmp = v0;
      v0 = v2;
      v2 = v1;
      v1 = tmp;
    } else {
      // v0 <= v1 && v0 < v2
      var c12 = comparefn(v1, v2);
      if (c12 > 0) {
        // v0 <= v2 < v1
        vartmp = v1; v1 = v2; v2 = tmp; }}V0 <= v1 <= v2
    a[from] = v0;
    a[to - 1] = v2;
    var pivot = v1;
    var low_end = from + 1;   // The upper bound of the element smaller than the reference value
    var high_start = to - 1;  // The lower bound of the element greater than the reference value
    // Swap the base value with the element from + 1
    // The element in the form position must be placed after the element in the form position
    a[third_index] = a[low_end];
    a[low_end] = pivot;

    // The partition function ranks the elements less than (assuming ascending sort) the base value to the left
    partition: for (var i = low_end + 1; i < high_start; i++) {
      var element = a[i];
      var order = comparefn(element, pivot);
      if (order < 0) {
        a[i] = a[low_end];
        a[low_end] = element;
        low_end++;
      } else if (order > 0) {
        // When the element to be sorted is greater than the base value,
        // Interchangeably with the first element to the right that is less than the reference value
        do {
          high_start--;
          if (high_start == i) break partition;
          var top_elem = a[high_start];
          order = comparefn(top_elem, pivot);
        } while (order > 0);
        a[i] = a[high_start];
        a[high_start] = element;
        // This element is less than the base value and needs to be placed to the left of the base value
        if (order < 0) { element = a[i]; a[i] = a[low_end]; a[low_end] = element; low_end++; }}}// Sort the two subarrays
    // Process those with fewer elements to sort first
    if (to - high_start < low_end - from) {
      QuickSort(a, high_start, to);
      to = low_end;
    } else {
      QuickSort(a, from, low_end);
      from= high_start; }}};Copy the code

Do all sorts of processing on the benchmark selection, see the notes in detail

Take normal ascending sort as an example

Array = comparefn,2,13,14,5,6,17,18,9,10,11,12,31,14,51 [1] = (a, b) = > a - bCopy the code

The first execution process is as follows:

  1. third_index = 7, from = 0, to = 15, pivot = a[7] = 18, low_end = 1, high_start = 14, a[7] = a[1] = 2, a[1] = 18

    ,18,13,14,5,6,17,2,9,10,11,12,31,14,51 [1]

  2. Enter the partition loop and start the comparison at I =2
  3. I =2, since A [I] < pivot, then a[2] = a[low_end] = a[1] = 18, low_end =2

    ,13,18,14,5,6,17,2,9,10,11,12,31,14,51 [1]

  4. It is not until I =12 that a[I]=31 > pivot appears, after which low_end = 11

    ,13,14,5,6,17,2,9,10,11,12,18,31,14,51 [1]

  5. I =12, since A [12] =31 > pivot,high_start = 13, since a[13] < pivot,a[I =12]=a[13]=14,a[13]=31

    ,13,14,5,6,17,2,9,10,11,12,18,14,31,51 [1]

  6. And since A [13] < pivot,a[12] = A [low_end] = a[11] = 18,a[11] = 31, low_end = 12

    ,13,14,5,6,17,2,9,10,11,12,14,18,31,51 [1]

  7. I < high_start not true, loop interrupted
  8. To-high_start = 14-13=1, low_end-from = 12, QuickSort(a,13,14) and QuickSort(a,0,12) respectively
  9. Continue a new round of execution

It doesn’t seem to be a problem, but what about the first example

Array = comparefn,2,13,14,5,6,17,18,9,10,11,12,31,14,51 [1] = (a, b) = > 0Copy the code

The first execution process is as follows:

  1. third_index = 7, from = 0, to = 15, v0=a[0]=1,v[1]=a[14]=51,v[2]=a[7]=18,
  2. Comparefn (v0, v2)>=0, v2 <= v0 <= v1, V0 =18,v1=1,v2=51, A [0]=18,a[14]=51,pivot = v1=1, LOW_end =1, high_start = 14, a[7] = a[1] = 2, a[1] = 1

    [18,1,13,14,5,6,17,2,9,10,11,12,31,14,51]

  3. The partition loop is entered, and the comparison starts at I =2. Since comparefn(Element, pivot)=0, no processing is done until the end of the loop
  4. To high_start = 14-14=0, low_end-from =0 QuickSort(a,0,0)
  5. End, return,1,13,14,5,6,17,2,9,10,11,12,31,14,51 [18]

As you can see, there are two problems with v8 source code

① V0, V1, V2 exchange processing code

comparefn = (a,b) = >0
function swap ([v0, v1, v2]) {
  / / given where v0, v1 and v2
  // Sort v0<=v1<=v2
  var c01 = comparefn(v0, v1);
  if (c01 > 0) {
    // v1 < v0, so swap them.
    var tmp = v0;
    v0 = v1;
    v1 = tmp;
  }
  // v0 <= v1.
  var c02 = comparefn(v0, v2);
  if (c02 > 0) {
    // v2 < v0 <= v1
    var tmp = v0;
    v0 = v2;
    v2 = v1;
    v1 = tmp;
  } else {
    // v0 <= v1 && v0 <= v2
    var c12 = comparefn(v1, v2);
    if (c12 > 0) {
      // v1 > v2
      vartmp = v1; v1 = v2; v2 = tmp; }}return [v0, v1, v2]
}

Copy the code

C02 is changed to > to ensure that v0 and V2 will not be exchanged when they are the same

② Reassign

The original code did this after the swap, without taking into account the equality case

a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1;   // Upper bound of elements lower than pivot.
var high_start = to - 1;  // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
Copy the code

Assuming that the order of v0,v1, and v2 remains the same, but the original value of a[to-1] is v1 and now becomes V2, the order should be changed at the beginning of the assignment

var v0 = a[from];
var v1 = a[third_index];
var v2 = a[to - 1];
Copy the code

A [third_index] swaps with a[low_end]

if(comparefn(pivot,a[low_end])! = =0){
  a[third_index] = a[low_end];
  a[low_end] = pivot;
} else {
  a[third_index] = pivot
}
Copy the code

Optimized fast sorting function

function ArraySort (array, comparefn) {
  function InsertionSort (a, from, to) {
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
        var order = comparefn(tmp, element);
        if (order > 0) {
          a[j + 1] = tmp;
        } else {
          break;
        }
      }
      a[j + 1] = element; }};function GetThirdIndex (a, from, to) {
    var t_array = new Array(a);// Use both 'from' and 'to' to determine the pivot candidates.
    var increment = 200 + ((to - from) & 15);
    var j = 0;
    from+ =1;
    to -= 1;
    for (var i = from; i < to; i += increment) {
      t_array[j] = [i, a[i]];
      j++;
    }
    t_array.sort(function (a, b) {
      return comparefn(a[1], b[1]);
    });
    var third_index = t_array[t_array.length >> 1] [0];
    return third_index;
  }
  function QuickSort (a, from, to) {
    // The benchmark selects the first element
    var third_index = 0;
    while (true) {
      // The length of the array to be sorted <= 10 uses insertion sort
      if (to - from< =10) {
        InsertionSort(a, from, to);
        return;
      }
      if (to - from > 1000) {
        // Every 200 ~ 215 (according to length & 15) elements,
        // Then sort the values and subscript the intermediate values
        // Sort is a recursive call
        third_index = GetThirdIndex(a, from, to);
      } else {
        // Set the intermediate element to the base value
        third_index = from + ((to - from) > >1);
      }
      // Take the median of the first, middle element (the reference value obtained above), and the last element as the reference value
      var v0 = a[from];
      var v1 = a[third_index];
      var v2 = a[to - 1];
      var c01 = comparefn(v0, v1);
      if (c01 > 0) {
        // v1 < v0, so swap them.
        var tmp = v0;
        v0 = v1;
        v1 = tmp;
      }
      // v0 <= v1.
      var c02 = comparefn(v0, v2);
      if (c02 > 0) {
        // v2 < v0 <= v1
        var tmp = v0;
        v0 = v2;
        v2 = v1;
        v1 = tmp;
      } else {
        // v0 <= v1 && v0 <= v2
        var c12 = comparefn(v1, v2);
        if (c12 > 0) {
          // v1 > v2
          vartmp = v1; v1 = v2; v2 = tmp; }}V0 <= v1 <= v2
      a[from] = v0;
      a[to - 1] = v2;
      var pivot = v1;
      var low_end = from + 1;   // The upper bound of the element smaller than the reference value
      var high_start = to - 1;  // The lower bound of the element greater than the reference value
      // Swap the base value with the element from + 1
      // The element in the form position must be placed after the element in the form position
      if(comparefn(pivot, a[low_end]) ! = =0) {
        a[third_index] = a[low_end];
        a[low_end] = pivot;
      } else {
        a[third_index] = pivot
      }

      // The partition function ranks the elements less than (assuming ascending sort) the base value to the left
      partition: for (var i = low_end + 1; i < high_start; i++) {
        var element = a[i];
        var order = comparefn(element, pivot);
        if (order < 0) {
          a[i] = a[low_end];
          a[low_end] = element;
          low_end++;
        } else if (order > 0) {
          // When the element to be sorted is greater than the base value,
          // Interchangeably with the first element to the right that is less than the reference value
          do {
            high_start--;
            if (high_start == i) break partition;
            var top_elem = a[high_start];
            order = comparefn(top_elem, pivot);
          } while (order > 0);
          a[i] = a[high_start];
          a[high_start] = element;
          // This element is less than the base value and needs to be placed to the left of the base value
          if (order < 0) { element = a[i]; a[i] = a[low_end]; a[low_end] = element; low_end++; }}}// Sort the two subarrays
      // Process those with fewer elements to sort first
      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from= high_start; }}}; QuickSort(array,0, array.length)
  return array
}
ArraySort([1.2.13.14.5.6.17.18.9.10.11.12.31.41], () = >0)
//  [1, 2, 13, 14, 5, 6, 17, 18, 9, 10, 11, 12, 31, 41]
ArraySort([1.2.13.14.5.6.17.18.9.10.11.12.31.41],(a,b)=>a-b)
//  [1, 2, 5, 6, 9, 10, 11, 12, 13, 14, 17, 18, 31, 41]
Copy the code

7.6.303

In V8 version 7.0, array.prototype. sort was changed from js to Torque, a typescript-like, strongly typed language.

SRC /js/array.js in V8 was removed in version 7.2 or later, and the intermediate versions were used to migrate other methods of array

Source path /third_party/v8/builtins/array-sort.tq

It can be seen that the implementation of SORT has changed to TimSort algorithm

To put it simply:

  1. Scan an array, determine monotone ascending segment and strictly monotone descending segment, and reverse the strictly descending segment. We call this segment run.
  2. Define the minimum run length, and run shorter than this length is merged by insertion sort until the length is greater than the minimum run length;
  3. Repeatedly merge some adjacent runs, avoid merging runs with very different lengths until the whole sorting is complete.

The implementation is more complex, this article will not go into the details, see the implementation of TimSort article

other

When looking at the source code found another implementation difference

chrome v59

[1.2.3.4.5].sort(v= >0)
// [1, 5, 2, 4, 3, undefined x 2]
Copy the code

chrome 76

[1.2.3.4.5].sort(v= >0)
// [1, 2, 3, 4, 5, empty × 2]
Copy the code

The implementation of the new version should be more scientific

There are some interesting differences that you can see here

conclusion

The earlier version of V8 has a buggy implementation of fast sorting, which makes it ok to use insertion sort when arrays are small

The new version of Chrome uses v8 to implement stable sorting and address some potential issues (different from what developers wanted).

Finally, share a tip for finding JS method implementations in V8 source code

  1. According to the part of the file name quickly find file: help.github.com/en/articles…
  2. Type “array.prototype. sort” in:file to search for files with all the contents matching array.prototype. sort
  3. Js method in/SRC/js/and/SRC/runtime/directory, reference from www.zhihu.com/question/59…
  4. The source code is best viewed with test/ mjSUNit

reference

  1. Es5 Chinese specification
  2. MDN-Array.prototype.sort
  3. [Depth] Digging through the SOURCE code of the V8 engine, I found the front-end algorithm you want
  4. JavaScript thematic interpretation of v8 sort source code
  5. Getting things sorted in V8