栈
栈是一种先进后出的数据结构,而队列是一种先进先出的数据结构,在JS中数组即是栈又是队列
数组
一种最基础的数据结构，每种编程语言都有，它编号从 0 开始，代表一组连续的储存结构，用来储存同一种类型的数据
它的这种特定的存储结构（连续存储空间存储同一类型数据）决定了:
优点
- 随机访问：可以通过下标随机访问数组中的任意位置上的数据,根据下标随机访问的时间复杂度为 O(1)
缺点
- 对数据的删除和插入不是很友好, 时间复杂度为 O(n)
JavaScript 数组的内存占用
FixedArray的内存占用大小为length * kPointerSize,64位的操作系统上，一个指针为8个字节，所以一个长度是1的数组它的大小将是8个字节
var arr = new Array(1000);
// 不会为1000个元素申请内存空间, 不会输出
arr.forEach((item)=>{console.info(item)});
var arr2 = [undefined, undefined];
// 输入两个undefined
arr2.forEach((item)=>{console.info(item)})
JavaScript 中，数组可以保存不同类型值
// 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)
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
};
JSArray 继承于 JSObject ，也就是说JS数组就是一个对象,底层就是个 Map ，key 为0，1，2，3这种索引，value 就是数组的元素,数组的index其实是字符串,从注释上看，它有两种存储方式：
- fast：存储结构是 FixedArray ，并且数组长度 <= elements.length() ，push 或 pop 时可能会伴随着动态扩容或减容
- slow：存储结构是 HashTable（哈希表），并且数组下标作为 key
fast 模式下数组在源码里面叫 FastElements ，而 slow 模式下的叫做 SlowElements
1、压紧的（Packed）
例如 ['a', 'b', 'c'] 这样的数组长度为3，数组索引0、1、2均有值，那么就认为是Packed
**** 2、有洞的（Holey）****
对于 ['a',,,'d'] 这样的数组，长度为4，但是索引1、2位置并没有进行初始化赋值，那么就认为是Holey。当数组出现了较大空洞的时候，内存明显是被浪费了。
3、快数组（FastElements)
FixedArray 是 V8 实现的一个类似于数组的类，它表示一段连续的内存，可以使用索引直接定位。新创建的空数组默认就是快数组。当数组满（数组的长度达到数组在内存中申请的内存容量最大值）的时候，继续 push 时， JSArray 会进行动态的扩容，以存储更多的元素
所有的数组初始化的时候默认都是快数组模式
4、慢数组（SlowElements
慢数组以哈希表的形式存储在内存空间里，它不需要开辟连续的存储空间，但需要额外维护一个哈希表，与快数组相比，性能相对较差
3、什么时候会从 fast 转变为 slow
// src/objects/js-objects.h
static const uint32_t kMaxGap = 1024;
// src/objects/dictionary.h
// JSObjects prefer dictionary elements if the dictionary saves this much
// memory compared to a fast elements backing store.
static const uint32_t kPreferFastElementsSizeFactor = 3;
// src/objects/js-objects-inl.h
// If the fast-case backing storage takes up much more memory than a dictionary
// backing storage would, the object should have slow elements.
// static
static inline bool ShouldConvertToSlowElements(uint32_t used_elements,uint32_t new_capacity) {
uint32_t size_threshold = NumberDictionary::kPreferFastElementsSizeFactor *
NumberDictionary::ComputeCapacity(used_elements) *
NumberDictionary::kEntrySize;
// 快数组新容量是扩容后的容量3倍之多时，也会被转成慢数组
return size_threshold <= new_capacity;
}
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;
}
// 当加入的索引值（例如例3中的2000）比当前容量capacity 大于等于 1024时，
// 返回true，转为慢数组
if (index - capacity >= JSObject::kMaxGap) return true;
// NewElementsCapacity就是进行扩容
*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;
}
// GetFastElementsUsage 来获取原来的数组中非空洞的元素数量乘以 kPreferFastElementsSizeFactor(值为3) 与 kEntrySize (值为2),与新的容量长度进行对比，如果小于新的容量长度，那么就转换为慢数组
return ShouldConvertToSlowElements(object.GetFastElementsUsage(),*new_capacity);
}
所以，当处于以下情况时，快数组在扩容之后会被转变为慢数组：
- 当加入的索引值 index 比当前容量 capacity 差值大于等于 1024 时（index - capacity >= 1024）
- 快数组新容量是扩容后的容量 3 倍之多时
- 扩容之后的非空洞元素数量 * kPreferFastElementsSizeFactor * kEntrySize 小于新容量的大小的时候
// 从上面的代码可以看到，当设置 99998 的时候，索引小于当前容量的时候，返回值为false
const a = new Array(99999);
a[99998] = undefined;
// 当设置 99999 这个索引的值的时候，因为超出了原来的FixedArray容量，那么就会进行扩容,扩容的算法（v8/src/objects/js-objects.h#L540）为容量 + 容量 /2 + 16，那么原来 99999 的容量就会扩容放大到 15万,然后会执行 GetFastElementsUsage 来获取原来的数组中非空洞,乘以 kPreferFastElementsSizeFactor(值为3) 与 kEntrySize (值为2) ，与新的容量长度进行对比，如果小于新的容量长度，那么就转换为慢数组
// 下面的代码非空洞元素数量为0，计算后的乘积也为0，因此小于15万的新数组长度，于是数组转换为了慢数组，使用了Dictionary进行数据的存储，从而节省了大量的内存
const b = new Array(99999);
b[99999] = undefined;
4、什么时候会从 slow 转变为 fast
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();
// smi在64位平台为 -2^31到2^31 -1, 在32位平台为-2^30到2^30 -1,如果数组长度不在smi之间则不转换
if (!length.IsSmi()) return false;
*new_capacity = static_cast<uint32_t>(Smi::ToInt(length));
} else if (object.IsJSArgumentsObject()) {
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;
}
所以，当处于以下情况时，快数组会被转变为慢数组：
- 如果数组长度在smi之间并且慢数组比快数组节省 50% 的空间则进行转换
let a = [1,2];
// 在 1030 的位置上面添加一个值，会造成多于 1024 个空洞，数组会使用为 Dictionary 模式来实现
a[1030] = 1;
// 往 200-1029 这些位置上赋值填补空洞，此时快数组占用空间1030 * 8, 慢数组占用空间 829 * 8,慢数组不再比快数组节省 50% 的空间,此时转换为快数组
for (let i = 200; i < 1030; i++) {
a[i] = i;
}
JavaScript 中，数组的动态扩容与减容（FastElements）
默认空数组初始化大小为 4
// Number of element slots to pre-allocate for an empty array.
static const int kPreallocatedArrayElements = 4;
判断是否进行扩容
在 JavaScript 中，当数组执行 push 操作时，一旦发现数组内存不足，将进行扩容
在 Chrome 源码中， push 的操作是用汇编实现的，在 c++ 里嵌入的汇编，以提高执行效率，并且在汇编的基础上用 c++ 封装了一层，在编译执行的时候，会将这些 c++ 代码转成汇编代码
// js-objects.h
static const uint32_t kMinAddedElementsCapacity = 16;
// code-stub-assembler.cc
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);
}
所以扩容后新容量计公式为：
new_capacity = old_capacity /2 + old_capacity + 16;
即老的容量的 1.5 倍加上 16 。初始化为 4 个，当 push 第 5 个的时候，容量将会变成
new_capacity = 4 / 2 + 4 + 16 = 22
接着申请一块这么大的内存，把老的数据拷过去，把新元素放在当前 length 位置，然后将数组的 length + 1，并返回 length
所以，扩容可以分为以下几步：
- push 操作时，发现数组内存不足
- 申请 new_capacity = old_capacity /2 + old_capacity + 16 那么长度的内存空间
- 将数组拷贝到新内存中
- 把新元素放在当前 length 位置
- 数组的 length + 1
- 返回 length
判断是否进行减容
if (2 * length <= capacity) {
// If more than half the elements won't be used, trim the array.
isolate->heap()->RightTrimFixedArray(*backing_store, capacity - length);
} else {
// Otherwise, fill the unused tail with holes.
BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);
}
所以，当数组 pop 后，如果数组容量大于等于 length 的 2 倍，则进行容量调整，使用 RightTrimFixedArray 函数，计算出需要释放的空间大小，做好标记，等待 GC 回收；如果数组容量小于 length 的 2 倍，则用 holes 对象填充
所以，减容可以分为以下几步：
- pop 操作时，获取数组 length
- 获取 length - 1 上的元素（要删除的元素）
- 数组 length - 1
- 判断数组的总容量是否大于等于 length - 1 的 2 倍
是的话，使用 RightTrimFixedArray 函数，计算出需要释放的空间大小，并做好标记，等待 GC 回收
不是的话，用 holes
参考文章
