Мне было интересно, есть ли преимущество производительности (CPU, Memory) в использовании списков фиксированной длины вместо списков динамической длины.
Я думаю, что в большинстве языков список фиксированной длины - это всего лишь массив указателей, в то время как списки динамической длины - это более сложная структура данных, такая как связанный список, который, очевидно, медленнее.
Короткий ответ: Да, есть разница. Списки фиксированной длины имеют более низкие издержки как в ЦП, так и в памяти, чем списки переменной длины.
Обратите внимание: я отвечаю на это исключительно с точки зрения VM, так что это относится только к коду, запущенному на Dart VM. При запуске с использованием JS-исполнения после компиляции с помощью dart2js применяются другие правила.
Теперь немного подробнее о текущей реализации:
Когда вы держите ссылку на список переменной длины в Dart, у вас есть ссылка на объект, который поддерживает текущую длину и ссылку на фактические данные. Фактические данные представляют собой список фиксированной длины с достаточной емкостью для хранения элементов. Обычно этот резервный магазин имеет большую емкость, чем это необходимо для хранения элементов требуемой длины. Это позволяет нам быстро add элементы большую часть времени.
Если вы теперь обращаетесь к элементам в этом списке переменной длины, используя [] или []=, тогда реализация должна сначала выполнить проверку длины в списке переменной длины, затем она считывает ссылку на хранилище резервных копий и обращается к запрашиваемому элементу из хранилища резервных копий. Наивная реализация должна будет исправить другую проверку длины перед доступом к хранилищу резервных копий, но есть несколько оптимизаций, которые выполняет компилятор оптимизации VM: избыточная проверка длины исключена, предполагается, что объект массива с фиксированной длиной используется как хранилище резервных копий избегая проверки типа, а затем вся эта последовательность встраивается на сайт вызова. Тем не менее, код действительно имеет две зависимые нагрузки, прежде чем вы действительно получите данные.
Поскольку данные для объектов фиксированной длины встроены в объект, можно избежать зависимой нагрузки. Подобным образом оптимизирующий компилятор строит общие шаблоны доступа и пытается удалить избыточные проверки длины.
Что касается служебных данных памяти, список фиксированной длины потребляет только столько памяти, сколько необходимо для установки всех элементов в один объект. Напротив, список переменной длины требует двух объектов и почти всегда имеет некоторую пропускную способность, оставшуюся в хранилище резервных копий. Это может быть значительным накладным объемом памяти в текущей реализации. Когда хранилище резервных копий находится в состоянии, когда вызывается add, размер хранилища резервных копий удваивается, и все текущие элементы копируются в новый резервный магазин перед добавлением дополнительного элемента. Вероятно, это изменится в будущем.
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.
}
Это возможно, потому что виртуальная машина может видеть, что длина списка не может измениться. Концептуально это становится:
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];
}
Обратите внимание, что любая функция, вызываемая из цикла, приведет к аннулированию предположения (поскольку функция может изменить длину растущего списка), а затем цикл будет работать медленнее.
dart2js может содержать длину строки внутри петель, если она знает длину списка. Списки Const имеют статическую длину, известную во время компиляции.
Рассмотрим этот код Дарта:
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, длина списка встраивается!