在Dart中使用固定长度列表是否有性能优势？

Question

我想知道使用固定长度列表而不是动态长度列表是否有性能(CPU,内存)的好处.

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

Answer 1

简短的回答是:是的,存在差异.固定长度列表在CPU和内存中的开销低于可变长度列表.

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

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

在Dart中保存对可变长度列表的引用时,您可以引用一个维护当前长度的对象和对实际数据的引用.实际数据是固定长度列表,具有足够的容量来容纳元素.通常,此后备存储具有比保持所需长度元素所严格需要的容量更多的容量.这允许我们在大多数时间快速添加元素.

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

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

就内存开销而言,固定长度列表仅消耗所需的内存以使所有元素适合单个对象.相反,可变长度列表需要两个对象,并且几乎总是在后备存储中保留一些容量.这可能是当前实现中的重要内存开销.当后备存储在调用add时处于容量时,则后备存储的大小加倍,并且在添加额外元素之前,所有当前元素都将复制到新的后备存储.尽管如此,这可能会在未来发生变化.

Answer 2

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];
}

请注意,循环中的任何函数调用都会使假设无效(因为函数可能会更改可增长列表的长度),然后循环运行速度会变慢.

Answer 3

如果dart2js知道列表的长度,它可以在循环内部列出长度.Const列表在编译时具有已知的静态长度.

考虑这个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,列表长度是内联的!