Is there a performance benefit in using fixed-length lists in Dart?

Question

I was wondering if there's a performance (CPU, Memory) benefit in using fixed-length lists instead of dynamic-length lists.

I think in most languages fixed-length list is just an array of pointers while dynamic-length lists is some more complicated data structure like linked list which is obviously slower.

Answer 1

The short answer is: Yes, there is a difference. Fixed-length lists have lower overhead both in CPU and memory than variable-length lists.

Please note: I am answering this purely from the VM perspective, so this applies only to code running on the Dart VM. When running using JS execution after compilation with dart2js other rules apply.

---

Now a bit more detail about the current implementation:

When you hold a reference to a variable-length list in Dart, you have a reference to an object which maintains the current length and a reference to the actual data. The actual data is a fixed-length list with enough capacity to hold the elements. Usually this backing store has more capacity than is strictly needed to hold the required length elements. This allows us to quickly add elements most of the time.

If you now access elements in this variable-length list using [] or []=, then the implementation has to first do the length check against the variable-length list, then it reads the reference to the backing store out and accesses the requested element from the backing store. A naive implementation would need to emit another length check before accessing the backing store, but there are several optimizations that the VM's optimizing compiler performs: The redundant length check is avoided, a fixed-length array object is assumed to be used as the backing store avoiding a type check and then this whole sequence is inlined at the call site. Still, the code does have two dependent loads before you actually get at the data.

As the data for fixed-length objects is inlined within the object the dependent load can be avoided. Similarly the optimizing compiler inlines the common access patterns and tries to remove redundant length checks.

As far as memory overhead is concerned the fixed-length list consumes only as much memory as is needed to fit all elements into a single object. On the contrary a variable-length list needs two objects and almost always has some capacity left over in the backing store. This can be a significant memory overhead in the current implementation. When the backing store is at capacity when add is called, then the size of the backing store is doubled and all current elements are copied to the new backing store before the extra element can be added. This will likely change in the future though.

Answer 2

dart2js can inline list length inside of loops, if it knows the list's length. Const lists have a static length known at compile time.

Consider this Dart code:

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

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

dart2js can emit:

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

Notice i < 2, the list length is inlined!

Answer 3

The VM implements growable lists on top of fixed-length lists. In the best case this means that a growable list incurs a penalty of ~3 pointers (one for the class-description, one to the fixed-length list, and one for the length).

However, to avoid too much copying when growing, the capacity of the growable list is usually greater than the needed length. As far as I know, a growable list doubles its internal storage when it runs out of space. This means that you can end up with twice the needed memory.

Performance-wise it depends: if you run through a list in a tight loop the VM can inline the pointer to the nested list and work with that one:

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.
}

This is possible because the VM can see that the length of the list cannot change. Conceptually this becomes:

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

Note that any function call out of the loop would invalidate the assumption (because the function could change the growable list's length) and then the loop would run slower.