Summary of the problems encountered in front-end sorting

It seems that there has always been a misunderstanding in the front-end circle: the front-end cannot use algorithm knowledge. For a long time, everyone may have been influenced by this statement. Until I encountered a product demand a while ago, I looked back and found that this was not the case.

Front-end sorting

Front-end sorting scenario

The front-end passes the sorting condition to the back-end as a request parameter, and the back-end returns the sorting result as a request response to the front-end, which is a common design. But it is not that suitable for some products.

Imagine a scenario: When you use a food app, do you often switch the sorting method, sort it by price, and then sort by rating.

In actual production, due to factors such as server cost, when a single data query becomes an overall performance bottleneck, it is also considered to optimize performance by sorting it in the front-end.

Sorting algorithm

I feel that there is no need to introduce this. As a basic algorithm in computer science, the description will be copied directly.Wikipedia。

This paragraph exists here purely for the purpose of inheriting the first (man) and the second (shu).

JavaScript sorting

Since we talk about front-end sorting, we will naturally think of JavaScript's native interface first.。

This interface isECMAScript 1st EditionIt exists from beginning to end. Let's see what the description of it looks like in the latest specification.

specification

(compareFn)

Obviously, there is no limit to the specificationsortWhat is the internally implemented sorting algorithm. Even the implementation of the interface does not need to beStable sortingof. This is very important and will be involved many times next.

In this context, the front-end sorting actually depends on the specific implementation of each browser. So, how do mainstream browsers implement sorting? Next, let's briefly compareChrome、FirefoxandMicrosoft Edge。

Implementation in Chrome

Chrome's JavaScript engine is v8. Since it is open source, you can look at the source code directly.

The entire thing is implemented in the JavaScript language. The sorting method part is obviously much more complicated than the quick sort I have seen, but obviously the core algorithm is still quick sorting. The reason for the complexity of the algorithm is that v8 has made many optimizations for performance considerations. (I'll talk about it next)

Implementation in Firefox

It is not possible to determine what the array sorting algorithm that Firefox's JavaScript engine will be about to use. [3]

According to the existing information, SpiderMoney implements merge sorting internally.

Implementation in Microsoft Edge

The core part of the code for the JavaScript engine of Microsoft Edge, Chakra, was opened sourced on Github in early 2016.

By looking at the source code, we can find that Chakra's array sorting algorithm also implements quick sorting. And compared to v8, it only implements purely quick sorting, with no trace of performance optimizations in v8 at all.

Problems with JavaScript array sorting

As we all know, quick sorting is an unstable sorting algorithm, while merge sorting is a stable sorting algorithm. Due to the differences in algorithm selection of different engines, the JavaScript code implemented by the front-end depends on the interface, and the actual sorting effect executed in the browser is inconsistent.

Differences in sort stability need to be triggered by specific scenarios before there is a problem; in many cases, unstable sorting will not have any impact.

If there is no need for stability in the sorting of arrays in actual project development, then you can actually see this, and the implementation differences between browsers are not that important.

But if the project requires that the sort must be stable, then the existence of these differences will not meet the demand. We need to do some extra work for this.

For example:

The final winning rules for the motor vehicle license auction system in a certain city are:

1. Sort inverted by price;

2. The same price will be positively sorted according to the bidding order (i.e. the price submission time).

If sorting is done on the front end, the winner displayed in the browser using quick sort is likely to be inconsistent with expectations.

Explore the differences

Before finding a solution, it is necessary to explore the reasons for the problem.

Why Chrome uses quick sorting

In fact, this situation existed from the beginning.

Chrome beta was released on September 2, 2008. However, shortly after its release, developers submitted #90 bug feedback to the Chromium development group. The array sorting implementation of v8 is not stable.

This bug ISSUE discussion spans a lot. Until November 10, 2015, developers still commented on the implementation of array sorting in v8.

At the same time, we also noticed that the ISSUE has been closed. However, it was reopened by development team members in June 2013 as a reference for discussion of the ECMAScript Next specification.

And the final conclusion of es-discuss is

As described in the finalized ECMAScript 2015 specification cited earlier in this article.

Characteristics of the times

IMHO, this problem was reported at the beginning of Chrome's release, which may have its own special characteristics of the times.

As mentioned above, the first version of Chrome was released in September 2008. According to statistics from statcounter, the two browsers with the highest market share during that period were IE (only IE6 and IE7 at that time) and Firefox, with market share reaching 67.16% and 25.77% respectively. In other words, the combined market share of the two browsers exceeds 90%.

According to another browser sorting algorithm statistics, these two browsers with more than 90% market share adopt stable array sorting. Therefore, it is reasonable to be questioned by developers at the beginning of Chrome's release.

Comply with the specifications

From the Bug ISSUE discussion, we can roughly understand some considerations of development team members in using quick sorting of engine implementation.

One of these is that they believe that the engine must comply with the ECMAScript specification. Since the specification does not require a description of stable sorting, they believe that the implementation of v8 is fully in compliance with the specification.

Performance considerations

In addition, they believe that an important consideration in v8 design is the performance of the engine.

Quick sorting Compared to merge sorting, it performs better overall performance:

Higher computing efficiency. Quick sorting Faster in an actual computer execution environment than other sorting algorithms with the same time complexity (in case of not hitting the worst combination)
Lower space costs. The former has only the space complexity of O(㏒n), and compared with the latter, the space complexity of O(n), the memory consumption is less during runtime.
Performance optimization of v8 in array sorting algorithm

Since v8 is very fond of the performance of the engine, what does it do in array sorting?

By reading the source code, I still learned some basic knowledge.

Mixed Insert Sort
Quick sort is the idea of ​​dividing and conquer, decomposing large arrays and recursing them layer by layer. However, if the recursion depth is too large, the memory resource consumption of the recursive call stack will also be very large. Poor optimization may even cause stack overflow.

The current implementation of v8 is to set a threshold and use insert sorting for small arrays of 10 or less lengths in the lowest layer.

According to code comments and descriptions in Wikipedia, although the average time complexity of insertion sort is O(n²) is worse than that of quick sort O(n㏒n). However, in the running environment, the efficiency of using insert sorting of small arrays is more efficient than fast sorting, so it will not be expanded here.

v8 code example

var QuickSort = function QuickSort(a, from, to) {
  ......
  while (true) {
    // Insertion sort is faster for short arrays.
    if (to - from <= 10) {
      InsertionSort(a, from, to);
      return;
    }
    ......
  }
  ......
};

Three numbers are in

As is known, the quick sorting Achilles heel is that the algorithm degenerates in the worst array combination.

The core of the quick sorting algorithm is to select a benchmark (pivot) and decompose the array that has been compared and exchanged into two number areas according to the benchmark for subsequent recursion. Imagine if, for an already ordered array, the first or last element is always selected every time the reference element is selected, then there will be a number area that is empty every time, and the recursive number of layers will reach n, which will eventually lead to the algorithm's time complexity degradation to O(n²). Therefore, the choice of pivot is very important.

v8 uses the three numbers to get themedian-of-three) Optimization: In addition to the two elements at the beginning and end, another element is selected to participate in the competition of the benchmark element.

The selection strategy for the third element is roughly:

When the length of the array is less than or equal to 1000, select the element at the half position as the target element.
When the length of the array exceeds 1000, select one element at a distance of 200-215 (non-fixed, changing with the length of the array) to determine a batch of candidate elements first. Then sort the candidate elements in this batch, and use the resulting median value as the target element.
Finally, take the median value of the three elements as pivot.

v8 code example

var GetThirdIndex = function(a, from, to) {
  var t_array = new InternalArray();
  // 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;
};

var QuickSort = function QuickSort(a, from, to) {
  ......
  while (true) {
    ......
    if (to - from > 1000) {
      third_index = GetThirdIndex(a, from, to);
    } else {
      third_index = from + ((to - from) >> 1);
    }
  }
  ......
};

Sort in place

While reviewing the quick sorting algorithm, I saw many examples of implementation using JavaScript on the Internet.

But I found that a large part of the code implementation is as follows

var quickSort = function(arr) {
if ( <= 1) { return arr; }
var pivotIndex = ( / 2);
var pivot = (pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < ; i++){
if (arr[i] < pivot) {
(arr[i]);
} else {
(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};

The main problem with the above code is:leftandrightTwo number zones store recursive subarrays, so it requires additional storage space for O(n). This is a big gap compared with the theoretical average spatial complexity O(㏒n).

The additional space overhead will also affect the overall speed of the actual runtime. This is also one of the reasons why fast sorting can perform at actual runtimes beyond the same level of time complexity. So generally speaking, fast sorting with better performance will be in-place sorting.

The implementation in v8 source code is to exchange elements on the original array.

Why Firefox uses merge sorting

There is also a story behind it.

In fact, when Firefox was released at the beginning, it did not use a stable sorting algorithm to implement array sorting, which is well documented.

The array sorting algorithm implemented in the original version of Firefox (Firebird) is heap sorting, which is also an unstable sorting algorithm. Therefore, someone later submitted a bug.

The Mozilla development team has conducted a series of discussions on this issue.

From the discussion process, we can draw some points

1. During the same period, Mozilla's competitor was IE6. From the above statistics, we can see that IE6 is stable in sorting.

The father Brendan Eich thinks Stability is good

Quick sorting was used before heap sorting

Based on the main premise that development group members tend to implement stable sorting algorithms, Firefox3 takes merge sorting as a new implementation of array sorting.

Solve the differences in sorting stability

I have said so much above mainly to tell the differences in the sorting implementation of each browser, and to explain some of the more superficial reasons why these differences exist.

But after reading this, readers may still have questions: what should I do if my project just needs to rely on stable sorting?

Solution

In fact, the idea of ​​solving this problem is relatively simple.

The browser chooses different sorting algorithms for different considerations. Some may tend to pursue extreme performance, while others tend to provide a good development experience, but there are rules to follow.

Judging from the current known situation, all mainstream browsers (including IE6, 7, 8) can basically enumerate the implementation of array sorting algorithms:

1. Merge sorting / Timsort

2. Quick sort

So, we can just transform the quick sorting into a stable sorting?

Generally speaking, using unstable sorting for object arrays will affect the results. While other types of arrays themselves use stable or unstable sorting results are equal. Therefore, the plan is roughly as follows:

Preprocess the array to be sorted and add natural order attributes to each object to be sorted, so as not to conflict with other attributes of the object.
Custom sorting comparison method compareFn always uses natural order as the second judgment dimension when pre-judgment is equal.

When facing implementations such as merge sorting, since the algorithm itself is stable, the additional natural order comparison will not change the sorting result, so the scheme compatibility is better.

However, it involves modifying the array to be sorted, and additional space is needed to store natural order properties. It is conceivable that engines like v8 should not use similar methods. However, it is feasible as a sorting plan customized by developers.

Scheme code example

'use strict';

const INDEX = Symbol('index');

function getComparer(compare) {
  return function (left, right) {
    let result = compare(left, right);

    return result === 0 ? left[INDEX] - right[INDEX] : result;
  };
}

function sort(array, compare) {
  array = (
    (item, index) => {
      if (typeof item === 'object') {
        item[INDEX] = index;
      }

      return item;
    }
  );

  return (getComparer(compare));
}

The above is just a simple algorithm modification example that satisfies stable sorting.

The reason why it is simple is that the data structures as array inputs in the actual production environment are complex, and it is necessary to judge whether more types of pre-ordering are required based on the actual situation.

Tag

1. The front-end is now a relatively broad concept. The front-end in this article mainly refers to an environment that uses browsers as carriers and JavaScript as programming languages.

2. This article does not intend to involve the algorithm as a whole. I would like to use common sorting algorithms as the entry point.

3. When confirming the algorithm implemented by Firefox array sorting, a sort-related bug was found in SpiderMoney. Generally speaking, during the discussion, some people suggested using the Timsort algorithm with better performance in extreme cases to replace the merge sorting, but Mozilla engineers said that because the Timsort algorithm has license authorization problems, there is no way to directly use the algorithm in Mozilla's software and wait for the other party's subsequent reply.

Summarize

The above is a summary and solution to the problems encountered in front-end sorting. In recent years, more and more projects are changing towards rich client applications, and the proportion of front-end in projects has increased. With the further improvement of browser computing power in the future, it allows for some more complex calculations. With the change of responsibilities, the front-end form may also undergo some major changes. When walking in the world, you must always have a skill.