В следующем блоге есть утверждение о преимуществах массивов по связанным спискам:
Массивы имеют лучшую локальность кэша, что может существенно повлиять на производительность.
Что это значит? Я не понимаю, как локальность кэша может обеспечить огромное преимущество в производительности.
См. мой ответ о пространственной и временной локализации.
В частности, массивы являются смежными блоками памяти, поэтому большие куски из них будут загружены в кеш при первом доступе. Это делает его сравнительно быстрым для доступа к будущим элементам массива. Связанные списки, с другой стороны, необязательно находятся в смежных блоках памяти и могут привести к большему количеству промахов в кеше, что увеличивает время, необходимое для доступа к ним.
Рассмотрим следующие возможные макеты памяти для массива data и связанного списка l_data больших структур
Address Contents | Address Contents
ffff 0000 data[0] | ffff 1000 l_data
ffff 0040 data[1] | ....
ffff 0080 data[2] | ffff 3460 l_data->next
ffff 00c0 data[3] | ....
ffff 0100 data[4] | ffff 8dc0 l_data->next->next
| ffff 8e00 l_data->next->next->next
| ....
| ffff 8f00 l_data->next->next->next->next
Если бы мы захотели пропустить этот массив, первый доступ к ffff 0000 потребовал бы, чтобы мы перешли в память для извлечения (очень медленная операция в цикле процессора). Однако после первого доступа остальная часть массива будет находиться в кеше, а последующие обращения будут намного быстрее. В связанном списке первый доступ к ffff 1000 также потребует от нас перехода в память. К сожалению, процессор будет кэшировать память, расположенную непосредственно вокруг этого места, скажем, вплоть до ffff 2000. Как вы можете видеть, это фактически не захватывает ни один из других элементов списка, а это значит, что когда мы перейдем к доступу l_data->next, нам снова придется перейти в память.
Как правило, при использовании массива вы получаете доступ к элементам, которые находятся рядом друг с другом. Это особенно актуально при последовательном доступе к массиву.
Когда вы обращаетесь к памяти, ее куски кэшируются на разных уровнях. Кэш-память относится к вероятности последовательных операций, находящихся в кеше и, следовательно, быстрее. В массиве вы максимизируете вероятность доступа к последовательному элементу в кеш.
Со списками, например, не гарантируется, что элементы, которые появляются последовательно в списке, фактически расположены рядом друг с другом в памяти. Это означает меньшее количество обращений к кешу и ухудшение производительности.