Почему для производительности массива важна локальность кеша?

Ответ 1

См. мой ответ о пространственной и временной локализации.

В частности, массивы являются смежными блоками памяти, поэтому большие куски из них будут загружены в кеш при первом доступе. Это делает его сравнительно быстрым для доступа к будущим элементам массива. Связанные списки, с другой стороны, необязательно находятся в смежных блоках памяти и могут привести к большему количеству промахов в кеше, что увеличивает время, необходимое для доступа к ним.

Рассмотрим следующие возможные макеты памяти для массива 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, нам снова придется перейти в память.

Ответ 2

Как правило, при использовании массива вы получаете доступ к элементам, которые находятся рядом друг с другом. Это особенно актуально при последовательном доступе к массиву.

Когда вы обращаетесь к памяти, ее куски кэшируются на разных уровнях. Кэш-память относится к вероятности последовательных операций, находящихся в кеше и, следовательно, быстрее. В массиве вы максимизируете вероятность доступа к последовательному элементу в кеш.

Со списками, например, не гарантируется, что элементы, которые появляются последовательно в списке, фактически расположены рядом друг с другом в памяти. Это означает меньшее количество обращений к кешу и ухудшение производительности.