performance - 在 Dart 中使用定长列表有性能优势吗？

Question

我想知道使用固定长度列表而不是动态长度列表是否有性能(CPU、内存)优势。

我认为在大多数语言中，固定长度列表只是一个指针数组，而动态长度列表是一些更复杂的数据结构，如链表，显然速度较慢。

Answer 1

简短的回答是:是的，有区别。与可变长度列表相比，固定长度列表在 CPU 和内存方面的开销更低。

请注意:我纯粹是从 VM 的角度回答这个问题，所以这仅适用于在 Dart VM 上运行的代码。在使用 dart2js 编译后使用 JS 执行运行时，其他规则适用。

现在有更多关于当前实现的细节:

当您在 Dart 中持有对可变长度列表的引用时，您将拥有对保持当前长度的对象的引用和对实际数据的引用。实际数据是一个固定长度的列表，具有足够的容量来容纳元素。通常，此后备存储的容量大于容纳所需长度元素所严格需要的容量。这让我们可以快速 add大部分时间都是元素。

如果您现在使用 [] 访问此可变长度列表中的元素或 []= ，然后实现必须首先对可变长度列表进行长度检查，然后读取对后备存储的引用并从后备存储中访问所请求的元素。一个简单的实现需要在访问后备存储之前发出另一个长度检查，但是有几个优化是 VM 的优化编译器执行的: 避免了冗余长度检查，假设将固定长度的数组对象用作后备存储避免类型检查，然后整个序列在调用站点内联。尽管如此，在您实际获取数据之前，代码确实有两个相关负载。

由于固定长度对象的数据内联在对象内，因此可以避免相关负载。类似地，优化编译器内联通用访问模式并尝试删除冗余长度检查。

就内存开销而言，固定长度列表仅消耗将所有元素放入单个对象所需的内存。相反，可变长度列表需要两个对象，并且在后备存储中几乎总是有一些剩余容量。在当前实现中，这可能是显着的内存开销。当后备存储容量满时 add被调用，然后后备存储的大小加倍，并且在添加额外元素之前，所有当前元素都被复制到新的后备存储中。不过，这可能会在 future 发生变化。