16

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

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

4

3 回答 3

28

简短的回答是：是的，有区别。固定长度列表在 CPU 和内存方面的开销都低于可变长度列表。

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

现在更详细地了解当前的实现：

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

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

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

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

于 2013-04-11T18:19:31.393 回答
14

如果 dart2js 知道列表的长度，它可以在循环内内联列表长度。常量列表具有在编译时已知的静态长度。

考虑一下这个 Dart 代码：

final List fruits = const ['apples', 'oranges'];

main() {
  for (var i = 0; i < fruits.length; i++) {
    print(fruits[i]);
  }
}

dart2js 可以发出：

$.main = function() {
  for (var i = 0; i < 2; ++i)
    $.Primitives_printString($.toString$0($.List_apples_oranges[i]));
};

注意i < 2，列表长度是内联的！

于 2013-04-11T17:24:53.907 回答
14

VM 在固定长度列表之上实现了可增长列表。在最好的情况下，这意味着一个可增长的列表会导致大约 3 个指针的损失（一个用于类描述，一个用于固定长度列表，一个用于长度）。

但是，为了避免在增长时复制过多，可增长列表的容量通常大于所需长度。据我所知，当空间不足时，可增长列表的内部存储空间会增加一倍。这意味着您最终可以获得两倍的所需内存。

性能方面取决于：如果您在紧密循环中运行列表，VM 可以内联指向嵌套列表的指针并使用该列表：

var list = foo();
var sum = 0;
for (int i = 0; i < list.length; i++) {
  sum += list[i];  // The internal pointer can be hoisted outside the loop.
}

这是可能的，因为 VM 可以看到列表的长度无法更改。从概念上讲，这变成：

var list = foo();
var sum = 0;
_check_that_list_is_growable_list_ // Because we have seen this type before.
int _list_length_ = list.length;
List _fixed_list_ = list._internal_fixed_list;
for (int i = 0; i < _list_length_; i++) {
  sum += _fixed_list_[i];
}

请注意，循环外的任何函数调用都会使假设无效（因为该函数可能会更改可增长列表的长度），然后循环会运行得更慢。

于 2013-04-11T17:50:33.030 回答