Skip to content

Latest commit

 

History

History
355 lines (297 loc) · 19.1 KB

深入理解Js数组.md

File metadata and controls

355 lines (297 loc) · 19.1 KB
Raw

深入理解Js数组

在Js中数组存在两种形式，一种是与C/C++等相同的在连续内存中存放数据的快数组，另一种是HashTable结构的慢数组，是一种典型的字典形式。

描述

在本文中所有的测试都是基于V8引擎的，使用的浏览器版本为Chrome 83.0，当然直接使用Node也是可以的。通常创建数组一般用以下三种方式，当然对于直接更改length属性的方式也可以达到改变数组长度的目的，从而实现创建指定长度的数组，只是并不常用。

var arr = [];
var arr = Array(100);
var arr = new Array(100);

对于上面三种方式，第一种使用字面量创建数组的方式是最常用的，第二种与第三种方式本质上是一样的，Array内部实现会判断this指针。在V8引擎中，直接创建数组默认的方式是创建快数组，会直接为数组开辟一定大小的内存，关于这一点可以直接在Chrome的Memory选项卡下首先保存快照然后在Console执行如下代码，可以看到内存增加了25MB左右，说明其开辟了一块内存区域供数组使用，假如使用Node的话可以执行process.memoryUsage();来查看内存占用。

var LIMIT = 6 * 1024 * 1024;
var arr = new Array(LIMIT);

对于快数组，其开辟了一块连续的内存区域用来提供数据存储，在遍历的效率上会高得多。对于慢数组，是HashTable结构，可以认为其就是一个对象，只不过索引的值只能为数字，在实际使用中这个数字索引会被强制转为字符串，在遍历的效率上会慢的多，但是对于一个数组是慢数组且为稀疏数组的情况下，可以节省大量内存区域。
对于快数组，直接赋值，可以看到完成操作需要27ms。

var LIMIT = 6 * 1024 * 1024;
var arr = new Array(LIMIT);
console.time("Array");
for(var i=0; i<LIMIT; i++) arr[i]=i;
console.timeEnd("Array");
// Array: 27.64697265625ms

对于慢数组，本例首先push一个值用来进行扩容操作，引擎会自动将该数组转换为慢数组，关于为什么本次扩容操作会引起快慢数组的转换会在下边讲到，其他操作与快数组类似，可以看到完成操作需要627ms。

var LIMIT = 6 * 1024 * 1024;
var arr = new Array(LIMIT);
arr.push(1); // 为了将快数组转换为慢数组
console.time("Array");
for(var i=0; i<LIMIT; i++) arr[i]=i;
console.timeEnd("Array");
// Array: 627.759033203125ms

如果在快数组中并不连续插入数据，而是作为稀疏数组去使用，在稀疏的程度不高的时候依旧是快数组的形式，并不会触发转换为慢数组的操作。

var LIMIT = 6 * 1024 * 1024;
var arr = new Array(LIMIT);
console.time("Array");
for(var i=0; i<LIMIT; i += 2) arr[i]=i; // 循环的i为 i += 2
console.timeEnd("Array");
// Array: 15.27001953125ms

在数组中插入不同类型的数据并不一定会引起快慢数组的转换，例如下面这个例子中插入了字符串、数值、布尔类型的值以及对象的引用，在插入效率上并不低。

var LIMIT = 6 * 1024 * 1024;
var arr = new Array(LIMIT);
var obj = {};
console.time("Array");
for(var i=1; i<LIMIT; i++) {
    if(i < 100) arr[i] = i;
    else if(i < 1000) arr[i] = "T";
    else if(i < 10000) arr[i] = true;
    else arr[i] = obj;
}
console.timeEnd("Array");
// Array: 32.123046875ms

关于稀疏数组中的empty，是一个空的对象引用，在ES6的文档中规定了empty就是等于undefined的，在任何情况下都应该这样对待empty，在indexOf、filter、forEach中会自动忽略掉empty，在includes中会认为其等于undefined，map中则会保留empty。

var arr = new Array(3);
arr[0] = 1;
console.log(arr); // (3) [1, empty × 2]
console.log(arr[1] === undefined); // true
console.log(arr.indexOf(undefined)); // -1
console.log(arr.filter(v => v)); // [1]
arr.forEach( v => console.log(v)); // 1
console.log(arr.includes(undefined)); // true
console.log(arr.map(v => v)); // [1, empty × 2]

如果必须要开辟一个密集数组，也就是不存在empty的情况，可以使用下面的方式去开辟。

[...new Array(3)]; // (3) [undefined, undefined, undefined]
Array.apply(null, new Array(3)); // (3) [undefined, undefined, undefined]
Array.from(new Array(3)); // (3) [undefined, undefined, undefined]

在Js中还存在类型化数组，ArrayBuffer是一种数据类型，用来表示一个通用的、固定长度的二进制数据缓冲区，不能直接操纵一个ArrayBuffer中的内容，需要创建一个类型化数组的视图或一个描述缓冲数据格式的DataView，使用它们来读写缓冲区中的内容。简单来说就是一块大的连续的内存区域，可以用它来做一些高效的存取操作等。

var LIMIT = 6 * 1024 * 1024;
var buffer = new ArrayBuffer(LIMIT);
var arr = new Int32Array(buffer);
console.time("Array");
for(var i=0; i<LIMIT; i++) arr[i]=i;
console.timeEnd("Array");
// Array: 30.139892578125ms

对于快慢数组，两者的也有各自的特点，在实际使用的过程中是存在相互转换的，在存储方式、内存使用、遍历效率方面有如下总结：

  • 存储方式方面：快数组内存中是连续的，慢数组在内存中是零散分配的。
  • 内存使用方面：由于快数组内存是连续的，可能需要开辟一大块供其使用，其中还可能有很多空洞，是比较费内存的。慢数组不会有空洞的情况，且都是零散的内存，比较节省内存空间。
  • 遍历效率方面：快数组由于是空间连续的，遍历速度很快，而慢数组每次都要寻找key 的位置，遍历效率会差一些。

源码分析

简单分析V8引擎的数组方面的内容，COMMIT ID为db4822d。通过在V8数组的定义可以了解到，数组可以处于两种模式，Fast模式的存储结构是FixedArray并且长度小于等于elements.length，可以通过push和pop增加和缩小数组。slow模式的存储结构是一个以数字为键的HashTable。

// v8/src/objects/js-array.h // line 19
// The JSArray describes JavaScript Arrays
//  Such an array can be in one of two modes:
//    - fast, backing storage is a FixedArray and length <= elements.length();
//       Please note: push and pop can be used to grow and shrink the array.
//    - slow, backing storage is a HashTable with numbers as keys.
class JSArray : public JSObject {
 public:
  // [length]: The length property.
  DECL_ACCESSORS(length, Object)
 
 //...

快数组

快数组是一种线性的存储方式，内部存储是连续的内存，新创建的空数组，默认的存储方式是快数组，快数组长度是可变的，可以根据元素的增加和删除来动态调整存储空间大小，内部是通过扩容和收缩机制实现。首先来分析以下扩容机制，默认的空数组预分配的大小为4，当数组进行扩充操作例如push时，数组的内存若不够则将进行扩容，最小的扩容容量为16，扩容的公式为new_capacity = old_capacity + old_capacity /2 + 16，即申请一块原容量1.5倍加16这样大小的内存，将原数据拷贝到新内存，然后length + 1，并返回length。

// v8/src/objects/js-array.h // line 105
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;

// v8/src/objects/js-objects.h // line 537
static const uint32_t kMinAddedElementsCapacity = 16;

// v8/src/objects/js-objects.h // line 540 // 计算扩容后的容量
// Computes the new capacity when expanding the elements of a JSObject.
static uint32_t NewElementsCapacity(uint32_t old_capacity) {
    // (old_capacity + 50%) + kMinAddedElementsCapacity
    return old_capacity + (old_capacity >> 1) + kMinAddedElementsCapacity;
}

// v8/src/code-stub-assembler.cc // line 5137 // 扩容的实现
Node* CodeStubAssembler::CalculateNewElementsCapacity(Node* old_capacity,
                                                      ParameterMode mode) {
  CSA_SLOW_ASSERT(this, MatchesParameterMode(old_capacity, mode));
  Node* half_old_capacity = WordOrSmiShr(old_capacity, 1, mode);
  Node* new_capacity = IntPtrOrSmiAdd(half_old_capacity, old_capacity, mode);
  Node* padding =
      IntPtrOrSmiConstant(JSObject::kMinAddedElementsCapacity, mode);
  return IntPtrOrSmiAdd(new_capacity, padding, mode);
}

// v8/src/code-stub-assembler.cc // line 5202 // 内存的拷贝
// Allocate the new backing store.
Node* new_elements = AllocateFixedArray(to_kind, new_capacity, mode);
// Copy the elements from the old elements store to the new.
// The size-check above guarantees that the |new_elements| is allocated
// in new space so we can skip the write barrier.
CopyFixedArrayElements(from_kind, elements, to_kind, new_elements, capacity,
                     new_capacity, SKIP_WRITE_BARRIER, mode);
StoreObjectField(object, JSObject::kElementsOffset, new_elements);

当数组执行pop操作时，会判断pop后数组的容量，是否需要进行减容，如果容量大于等于length * 2 + 16，则进行收缩容量调整，否则用HOLES对象填充未被初始化的位置，elements_to_trim就是要裁剪的大小，需要根据length + 1和old_length判断是将空出的空间全部收缩掉还是只收缩一半。

// v8/src/elements.cc // line 783
if (2 * length + JSObject::kMinAddedElementsCapacity <= capacity) {
    // If more than half the elements won't be used, trim the array.
    // Do not trim from short arrays to prevent frequent trimming on
    // repeated pop operations.
    // Leave some space to allow for subsequent push operations.
    int elements_to_trim = length + 1 == old_length
                                ? (capacity - length) / 2
                                : capacity - length;
    isolate->heap()->RightTrimFixedArray(*backing_store, elements_to_trim);
    // Fill the non-trimmed elements with holes.
    BackingStore::cast(*backing_store)
        ->FillWithHoles(length,
                        std::min(old_length, capacity - elements_to_trim));
} else {
    // Otherwise, fill the unused tail with holes.
    BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);
}

上边提到的HOLES对象指的是数组中分配了空间，但是没有存放元素的位置，对于HOLES，在Fast Elements模式中有一个扩展，称为Fast Holey Elements模式。Fast Holey Elements模式适合于数组中的有空洞情况，即只有某些索引存有数据，而其他的索引都没有赋值的情况，此时没有赋值的数组索引将会存储一个特殊的值empty，这样在访问这些位置时就可以得到undefined。Fast Holey Elements模式与Fast Elements模式一样，会动态分配连续的存储空间，分配空间的大小由最大的索引值决定。定义数组时，如果没有设置容量，V8会默认使用Fast Elements模式实现，如果定义数组时进行了容量的指定，如上文中的new Array(100)，就会以Fast Holey Elements模式实现。
在Fast Elements模式下V8引擎还根据元素类型对数组类型做了细分用以优化数组，当全部元素都为整数型的话，那么这个数组的类型就被标记为PACKED_SMI_ELEMENTS。如果只存在整数型和浮点型的元素类型，那么这个数组的类型为PACKED_DOUBLE_ELEMENTS。除此以外，一个数组包含其它的元素，都被标记为PACKED_ELEMENTS。而这些数组类型并非一成不变，而是在运行时随时更改的，但是数组的类型只能从特定种类变更为普通种类。即初始为PACKED_SMI_ELEMENTS的数组，只能过渡为PACKED_DOUBLE_ELEMENTS或者PACKED_ELEMENTS。而PACKED_DOUBLE_ELEMENTS只能过渡为PACKED_ELEMENTS。至于初始就是PACKED_ELEMENTS类型的数组，就无法再过渡了，无法逆向过渡。而上述的这三种类型，都属于密集数组，与之相对应的，是稀疏数组，标记为HOLEY_ELEMENTS，稀疏数组同样具有三种类型，任何一种PACKED都可以过渡到HOLEY。PACKED_SMI_ELEMENTS可以转换为HOLEY_SMI_ELEMENTS，PACKED_DOUBLE_ELEMENTS可以转换为HOLEY_DOUBLE_ELEMENTS，PACKED_ELEMENTS可以转换为HOLEY_ELEMENTS。需要注意的是，虽然可以将数组转换为HOLEY模式，但是并不一定就代表着这个数组被转换为慢数组。

慢数组

慢数组是一种字典的内存形式。不用开辟大块连续的存储空间，节省了内存，但是由于需要维护这样一个HashTable，其效率会比快数组低，V8中是以Dictionary的结构实现的慢数组。

// v8/src/objects/dictionary.h // line 27
class Dictionary : public HashTable<Derived, Shape> {
    typedef HashTable<Derived, Shape> DerivedHashTable;

    public:
    typedef typename Shape::Key Key;
    // Returns the value at entry.
    Object ValueAt(int entry) {
        return this->get(DerivedHashTable::EntryToIndex(entry) + 1);
    }

    // Set the value for entry.
    void ValueAtPut(int entry, Object value) {
       this->set(DerivedHashTable::EntryToIndex(entry) + 1, value);
    }
    
    // Returns the property details for the property at entry.
    PropertyDetails DetailsAt(int entry) {
       return Shape::DetailsAt(Derived::cast(*this), entry);
    }

    // ...

}

类型转换

快数组转慢数组

快数组转换为慢数组主要有以下两种情况：

  • 当新容量大于等于3 * 3倍的扩容后的容量，会转变为慢数组。
  • 当加入的索引值index比当前容量capacity差值大于等于1024 时，也就是至少有1024个HOLEY时，即会转为慢数组，例如定义一个长度为1的数组arr然后使用arr[2000]=1赋值，此时数组就会被转换为慢数组。
// v8/src/objects/js-objects-inl.h // line 992
static inline bool ShouldConvertToSlowElements(JSObject object,
                                               uint32_t capacity,
                                               uint32_t index,
                                               uint32_t* new_capacity) {
  STATIC_ASSERT(JSObject::kMaxUncheckedOldFastElementsLength <=
                JSObject::kMaxUncheckedFastElementsLength);
  if (index < capacity) {
    *new_capacity = capacity;
    return false;
  }
  if (index - capacity >= JSObject::kMaxGap) return true; // 第二种转换
  *new_capacity = JSObject::NewElementsCapacity(index + 1);
  DCHECK_LT(index, *new_capacity);
  // TODO(ulan): Check if it works with young large objects.
  if (*new_capacity <= JSObject::kMaxUncheckedOldFastElementsLength ||
      (*new_capacity <= JSObject::kMaxUncheckedFastElementsLength &&
       ObjectInYoungGeneration(object))) {
    return false;
  }
  // If the fast-case backing storage takes up much more memory than a
  // dictionary backing storage would, the object should have slow elements.
  int used_elements = object->GetFastElementsUsage();
  uint32_t size_threshold = NumberDictionary::kPreferFastElementsSizeFactor *
                            NumberDictionary::ComputeCapacity(used_elements) *
                            NumberDictionary::kEntrySize;
  return size_threshold <= *new_capacity; // 第一种转换
}

// v8/src/objects/js-objects.h // line 738
// JSObject::kMaxGap 常量
// Maximal gap that can be introduced by adding an element beyond
// the current elements length.
static const uint32_t kMaxGap = 1024;

// v8/src/objects/dictionary.h // line 362
// NumberDictionary::kPreferFastElementsSizeFactor 常量
// JSObjects prefer dictionary elements if the dictionary saves this much
// memory compared to a fast elements backing store.
static const uint32_t kPreferFastElementsSizeFactor = 3;

// v8/src/objects/hash-table-inl.h // line 76
// NumberDictionary::ComputeCapacity(used_elements)
// NumberDictionary 继承于 Dictionary 再继承于 HashTable
// static
int HashTableBase::ComputeCapacity(int at_least_space_for) {
  // Add 50% slack to make slot collisions sufficiently unlikely.
  // See matching computation in HashTable::HasSufficientCapacityToAdd().
  // Must be kept in sync with CodeStubAssembler::HashTableComputeCapacity().
  int raw_cap = at_least_space_for + (at_least_space_for >> 1);
  int capacity = base::bits::RoundUpToPowerOfTwo32(raw_cap);
  return Max(capacity, kMinCapacity);
}

// v8/src/objects/dictionary.h // line 260
// NumberDictionary::kEntrySize 常量
// NumberDictionary 继承 Dictionary 传入 NumberDictionaryShape作为Shape 继承HashTable 
// HashTable 中定义 static const int kEntrySize = Shape::kEntrySize;
static const int kEntrySize = 3;

慢数组转快数组

当慢数组的元素可存放在快数组中且长度小于Smi::kMaxValue且对于快数组仅节省了50%的空间，则会转变为快数组。

// v8/src/objects/js-objects.cc // line 4523
static bool ShouldConvertToFastElements(JSObject object,
                                        NumberDictionary dictionary,
                                        uint32_t index,
                                        uint32_t* new_capacity) {
  // If properties with non-standard attributes or accessors were added, we
  // cannot go back to fast elements.
  if (dictionary->requires_slow_elements()) return false;

  // Adding a property with this index will require slow elements.
  if (index >= static_cast<uint32_t>(Smi::kMaxValue)) return false;

  if (object->IsJSArray()) {
    Object length = JSArray::cast(object)->length();
    if (!length->IsSmi()) return false;
    *new_capacity = static_cast<uint32_t>(Smi::ToInt(length));
  } else if (object->IsJSSloppyArgumentsObject()) {
    return false;
  } else {
    *new_capacity = dictionary->max_number_key() + 1;
  }
  *new_capacity = Max(index + 1, *new_capacity);

  uint32_t dictionary_size = static_cast<uint32_t>(dictionary->Capacity()) *
                             NumberDictionary::kEntrySize;

  // Turn fast if the dictionary only saves 50% space.
  return 2 * dictionary_size >= *new_capacity;
}

// v8/src/objects/smi.h // line 106
static constexpr int kMaxValue = kSmiMaxValue;

// v8/include/v8-internal.h // line 87
static constexpr intptr_t kSmiMaxValue = -(kSmiMinValue + 1);

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://v8.js.cn/blog/elements-kinds/
https://github.com/JunreyCen/blog/issues/10
https://juejin.im/post/5e1d919f5188254c3c275145
https://juejin.im/post/5df1e21bf265da33c24fe9f4
https://juejin.im/entry/5a9c0b606fb9a028d663a491
https://juejin.im/entry/59ae664d518825244d207196
https://blog.csdn.net/github_34708151/article/details/105463108
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Typed_arrays
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/ArrayBuffer
https://stackoverflow.com/questions/46526520/why-are-we-allowed-to-create-sparse-arrays-in-javascript