深入解讀V8源碼中的Array.sort()方法

在V8引擎的源碼中，Array.sort()方法是一個非常重要的排序方法。如果我們想深入了解這個方法的具體實現(xiàn)，就需要去查看V8引擎的源碼。下面將對V8源碼中的Array.sort()方法進行詳細的解讀。

源碼地址

V8源碼Array
710行開始為sort()相關(guān)

Array.sort()方法是那種排序呢？

去看源碼主要是源于這個問題

// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.

源碼中的第一句話就回答了我的問題

// 通常使用快速排序算法
// 如果數(shù)組長度小于23，則插入排序效率更好

既然都打開了，索性就看看源碼叭，看看sort到底做了些啥
我把一整坨源碼碼分成一塊一塊來看，讓自己比較清晰的知道sort到底干了些啥，下面是閱讀代碼時，自己的思路梳理

第一塊代碼

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;
  };
}

第一塊內(nèi)容判斷，如果傳進來的參數(shù)不可回調(diào)，則給一個默認的回調(diào)函數(shù)
這個回調(diào)函數(shù)，判斷倆值是不是 Smi

// Smi：小整數(shù)(Small integers)V8引擎中的元素類型之一
`https://medium.com/@justjavac/v8-internals-how-small-is-a-small-integer-ba5e17a3ae5f`
// PS: markdown語法有問題，這里直接貼出 url

如果是則進行小整數(shù)字典序比較
什么是字典序

否則將兩個值轉(zhuǎn)換成字符串進行字符串比較大小
字符串如何比較大小

第二塊代碼

var InsertionSort = function InsertionSort(a, from, to) {
  ...
};
var QuickSort = function QuickSort(a, from, to) {
  if (to - from <= 10) {
    InsertionSort(a, from, to);
    return;
  }
  ...
};

第二塊就是正常的快速排序和插入排序
這里采取的是數(shù)量小于10的數(shù)組使用 InsertionSort(插入)，比10大的數(shù)組則使用 QuickSort(快速)。

第三塊代碼

if (!is_array) {
  // For compatibility with JSC, we also sort elements inherited from
  // the prototype chain on non-Array objects.
  // We do this by copying them to this object and sorting only
  // own elements. This is not very efficient, but sorting with
  // inherited elements happens very, very rarely, if at all.
  // The specification allows "implementation dependent" behavior
  // if an element on the prototype chain has an element that
  // might interact with sorting.
  max_prototype_element = CopyFromPrototype(array, length);
}

這塊代碼里面的注釋，講的還是比較詳細的，百度翻譯也非常nice

// 為了與JSC兼容，我們還在非數(shù)組對象上對從原型鏈繼承的元素進行排序。
// 我們通過將它們復制到這個對象并只對自己的元素排序來實現(xiàn)這一點。
// 這不是很有效，但是使用繼承的元素進行排序的情況很少發(fā)生，如果有的話。
// 如果原型鏈上的元素具有可能與排序交互的元素，則規(guī)范允許“依賴于實現(xiàn)”的行為。

第四塊代碼

// Copy elements in the range 0..length from obj's prototype chain
// to obj itself, if obj has holes. Return one more than the maximal index
// of a prototype property.
var CopyFromPrototype = function CopyFromPrototype(obj, length) {
  var max = 0;
  for (var proto = %object_get_prototype_of(obj); 
        proto;
        proto = %object_get_prototype_of(proto)) {
        var indices = IS_PROXY(proto) ? length : %GetArrayKeys(proto, length);
        if (IS_NUMBER(indices)) {
            // It's an interval.
            var proto_length = indices;
            for (var i = 0; i < proto_length; i++) {
                if (!HAS_OWN_PROPERTY(obj, i) && HAS_OWN_PROPERTY(proto, i)) {
                obj[i] = proto[i];
                if (i >= max) { max = i + 1; }
            }
        }
        } 
        else {
            for (var i = 0; i < indices.length; i++) {
                var index = indices[i];
                if (!HAS_OWN_PROPERTY(obj, index) && HAS_OWN_PROPERTY(proto, index)) {
                    obj[index] = proto[index];
                    if (index >= max) { max = index + 1; }
                }
            }
        }
    }
    return max;
};

這塊代碼是對于非數(shù)組的一個處理
注釋里面說到

// 如果obj有holes(能猜出大概意思，不咋好翻譯這個hole)
// 就把obj原型鏈上0-length所有元素賦值給obj本身
// 返回一個max，max是比原型屬性索引最大值+1

返回的max會在下面用到

第五塊代碼

if (!is_array && (num_non_undefined + 1 < max_prototype_element)) {
  // For compatibility with JSC, we shadow any elements in the prototype
  // chain that has become exposed by sort moving a hole to its position.
  ShadowPrototypeElements(array, num_non_undefined, max_prototype_element);
}

注釋翻譯：

// 為了與JSC兼容
// 我們對原型鏈中通過sort將一個hole移動到其位置而暴露的所有元素
// 進行shadow處理。

可能因為英語語法水平不夠，單看注釋還有點不明白
大致意思是，把“掀開的東西，再蓋上”
直接看下面一塊代碼，看看這個shadow操作到底干了啥叭

第六塊代碼

// Set a value of "undefined" on all indices in the range from..to
// where a prototype of obj has an element. I.e., shadow all prototype
// elements in that range.
var ShadowPrototypeElements = function(obj, from, to) {
  for (var proto = %object_get_prototype_of(obj); proto;
        proto = %object_get_prototype_of(proto)) {
        var indices = IS_PROXY(proto) ? to : %GetArrayKeys(proto, to);
        if (IS_NUMBER(indices)) {
          // It's an interval.
          var proto_length = indices;
          for (var i = from; i < proto_length; i++) {
            if (HAS_OWN_PROPERTY(proto, i)) {
              obj[i] = UNDEFINED;
            }
          }
        } 
        else {
            for (var i = 0; i < indices.length; i++) {
                var index = indices[i];
                if (from <= index && HAS_OWN_PROPERTY(proto, index)) {
                    obj[index] = UNDEFINED;
                }
            }
        }
    }
};

這塊代碼就是shadow操作，注釋翻譯如下：

// 在范圍從..到obj原型包含元素的所有索引上設置一個“undefined”值。
// 換句話說
// 在該范圍內(nèi)對所有原型元素進行shadow處理。

其中：
I.e.是拉丁文id est 的縮寫，它的意思就是“那就是說，換句話說”
英文不夠你用了是不你還要寫拉丁文？！

果然大致的意思猜的沒錯
在剛剛把對象的原型屬性的復制，現(xiàn)在要設置undefined來shadow他了

第七塊代碼

if (num_non_undefined == -1) {
  // There were indexed accessors in the array.
  // Move array holes and undefineds to the end using a Javascript function
  // that is safe in the presence of accessors.
  num_non_undefined = SafeRemoveArrayHoles(array);
}

意思是 數(shù)組中有索引訪問器。使用JS函數(shù)將數(shù)組hole和未定義項移到末尾，該函數(shù)在訪問器存在時是安全的。
下面是安全移出數(shù)組hole方法

var SafeRemoveArrayHoles = function SafeRemoveArrayHoles(obj) {
  // Copy defined elements from the end to fill in all holes and undefineds
  // in the beginning of the array.  Write undefineds and holes at the end
  // after loop is finished.
    var first_undefined = 0;
    var last_defined = length - 1;
    var num_holes = 0;
    while (first_undefined < last_defined) {
        // Find first undefined element.
        while (first_undefined < last_defined &&
            !IS_UNDEFINED(obj[first_undefined])) {
            first_undefined++;
        }
        // Maintain the invariant num_holes = the number of holes in the original
        // array with indices <= first_undefined or > last_defined.
        if (!HAS_OWN_PROPERTY(obj, first_undefined)) {
          num_holes++;
        }
        // Find last defined element.
        while (first_undefined < last_defined &&
            IS_UNDEFINED(obj[last_defined])) {
            if (!HAS_OWN_PROPERTY(obj, last_defined)) {
                num_holes++;
            }
            last_defined--;
        }
        if (first_undefined < last_defined) {
            // Fill in hole or undefined.
            obj[first_undefined] = obj[last_defined];
            obj[last_defined] = UNDEFINED;
        }
    }
    // If there were any undefineds in the entire array, first_undefined
    // points to one past the last defined element.  Make this true if
    // there were no undefineds, as well, so that first_undefined == number
    // of defined elements.
    if (!IS_UNDEFINED(obj[first_undefined])) first_undefined++;
    // Fill in the undefineds and the holes.  There may be a hole where
    // an undefined should be and vice versa.
    var i;
    for (i = first_undefined; i < length - num_holes; i++) {
        obj[i] = UNDEFINED;
    }
    for (i = length - num_holes; i < length; i++) {
        // For compatability with Webkit, do not expose elements in the prototype.
        if (i in %object_get_prototype_of(obj)) {
            obj[i] = UNDEFINED;
        } else {
            delete obj[i];
        }
    }
    // Return the number of defined elements.
    return first_undefined;
};

還會判斷數(shù)組長度

if (length < 2) return array;

• 《魔獸世界》懷舊服 從入門到精通指南
• 萬道仙訣游戲技巧與攻略大全最新指南
• 火柴人小游戲最新版攻略全講解
• 捕獵魂獸游戲攻略技巧大全最新：斗羅大陸全面指南
• 養(yǎng)蠱傳奇游戲攻略大全