JS Arrays如何在内部调整大小？

Question

所以我一直在尝试在JS中实现一个集合类型的类(类似于在C#中找到的List),它具有一些自定义功能.我也希望它有所优化(我已经阅读了一些关于如何正确使用JS Arrays的文章).所以我想我自己"如果我们没有为数组定义一个初始大小,我们不断向它添加对象,在内部它必须为每个插入分配一个新的大小,这必须很慢.我可以通过分配来避免这种情况我自己的新尺寸(改变阵列长度),有点类似于在CSharp中完成的尺寸,每当达到最大容量时尺寸加倍(我知道这不是微不足道但它是一个开始)"

我试图实现这个想法,发现它慢了(慢10倍):

//This simplified approach of my implementation is faster...
var array = [];
var counter = 0;
function addItem(newItem) {
    array[++counter] = newItem;
}

//..than this version that resizes the array when a limit is reached
var array = [];
array.length = INITIAL_SIZE;
/*
 Alternatively
 var array = new Array(INITIAL_SIZE);
*/
var counter = 0;
function addItem(newItem) {
    if( CheckCapacity(counter + 1) ) { //Function that checks if the maximum size is reached and if it is, change the array.length to the new size
        array[++counter] = newItem;
    }
}

在测试之前,我想,"因为当我调用CheckCapacity(计数器+ 1)时,我有一个新的数组大小,内部它(JS数组)与第一个函数相比不需要做太多的操作因为我确保有空间可用,超过必要的",即第二个函数上的数组[++ counter] = newItem line应该比第一个函数中的相同更快.我甚至使用了不同的数组,其中包含预先计算出的大小的数据; 它仍然较慢.

那么回到我的问题,JS Array的实现如何分配必要的大小？我是否正确地假设没有太多可以加快这个过程的速度？对我来说,有意义的是,每次添加新项目时,拥有一个动态分配更多内存的对象(JS数组)的缺点就是速度的损失(除非它实现了相当好的算法,但我不知道不知道,因此我的问题.

Answer 1

在Javascript中,Array是一种抽象.它是如何实现的(以及何时执行分配和调整大小)由Javascript引擎决定 - ECMAScript规范没有规定如何完成.因此,基本上没有确切的方法可以知道.

在实践中,Javascript引擎非常聪明地分配内存和确保不分配太多.在我看来,它们比C#复杂得多List- 因为Javascript引擎可以根据情况动态地改变底层数据结构.算法各不相同,但大多数人会考虑阵列中是否有"漏洞":

var array = [];
array[0] = "foo"          // is a resizable array
array[1] = "bar"          // is a resizable array
array[2] = "baz"          // is a resizable array
array[1000000] = "hello"; // is now a hash table
console.log(array[1000000]) // "hello"

如果您正常使用数组并使用从零开始的连续键,则没有"漏洞",并且大多数Javascript引擎将通过使用可调整大小的数组数据结构来表示Javascript数组.现在考虑第四个任务,我创造了一个大约一百万的所谓"洞"(洞跨越插槽3-999999).事实证明,Javascript引擎足够聪明,不会为这个巨大的漏洞分配大约100万个内存插槽.它检测到我们有一个洞,它现在将使用Dictionary/hash-table(如数据结构)(它使用二进制搜索树,其中键被散列)来表示Javascript数组,以节省空间.它不会存储空间的孔,只有四个映射:(0, "foo"),(1, "bar"),(2, "baz"),(1000000, "hello").

不幸的是,现在访问数组的引擎速度较慢,因为它现在必须计算哈希值并遍历树.当没有漏洞时,我们使用可调整大小的阵列,我们有更快的访问时间,但是当我们有一个漏洞时,Array的性能会更慢.常见的术语是说Array是一个密集的数组,当它没有任何漏洞时(它使用一个可调整大小的数组=更好的性能),而Array是一个稀疏数组,当它有一个或多个漏洞时(它使用一个哈希) table =性能较慢).为了获得最佳性能,请尝试使用密集阵列.

现在结束,让我告诉你,以下是一个坏主意:

var array = new Array(1000000);
array[0] = "foo";               // is a hash table

上面的数组有一个大小约为1百万的漏洞(就像["foo", undefined, undefined, ... undefined]这样:),因此它使用散列表作为底层数据结构.所以实现自己调整大小是一个坏主意 - 它会创建一个漏洞并导致最差的性能而不是更好.你只是混淆了Javascript引擎.这是你的代码正在做的事情,你的数组总是有一个漏洞,因此使用哈希表作为底层数据结构; 与没有任何漏洞的数组(也就是代码的第一个版本)相比,性能更低.

我是否正确地假设没有太多可以加快这个过程的速度？

是的,关于预分配空间,用户方面几乎没有什么可做的.一般来说,为了加速Javascript数组,您希望避免创建稀疏数组(避免创建漏洞):

1. 不要预先分配使用new Array(size).而是"随着你的成长".引擎将计算出底层可调整大小的数组本身的大小.
2. 使用从0开始的连续整数键.不要从大整数开始.不要添加非整数的键(例如,不要使用字符串作为键).
3. 尽量不要删除数组中间的键(不要从索引为0的数组中删除索引为5的元素).
4. 不要转换为密集和稀疏数组(即不要重复添加和删除孔).引擎转换为可调整大小的数组与散列表表示之间存在开销.

[JS Arrays over C#Lists]的缺点是,每次添加新项目时,它们都会动态分配更多内存

不,不一定.当Javascript数组没有漏洞时,C#列表和Javascipt数组基本相同.两者都是可调整大小的数组 不同之处在于:

1. C#列表使用户可以更好地控制可调整大小的数组的行为.在Javascript中,你无法控制它 - 它在引擎内部.
2. C#列表允许用户预分配内存以获得更好的性能,而在Javascript中,您应该让引擎自动解决如何在底层可调整大小的阵列中预分配内存以获得更好的性能.