Является ли массив массивов кэшем локальным?

Question

Если массив

[1,2,3,4,5,6] 

существует в непрерывном блоке памяти, делает массив массивов

[[1,2,3],[4,5,6]] 

обязательно имеет то же расположение кэша?

Answer 1

В массиве массивов, массивы себя будут обладать теми же свойствами локальности, что и массив элементов, потому что этот случай ничем не отличается - здесь «элементы» представляют собой массивы. Однако, независимо от того, являются ли элементы каждого вспомогательного массива смежными в памяти элементам другого подматрица, зависит от реализации подматриц.

Поскольку вы не указали язык, я буду использовать синтаксис C++ для демонстрации, но это в основном языковой агностик, поскольку он касается аспектов аппаратного обеспечения. Если ваш массив массивов эквивалентен C++ std::vector<std::vector<int>> - который представляет собой гибкий контейнер контейнеров, который может расти/сокращаться по мере необходимости, каждый std::vector будет смежным в памяти по отношению к другим, но std::vector не содержит элементов. Скорее, это оболочка вокруг динамически выделенного массива, обычно содержащая несколько указателей на базовые данные. Это означает, что каждая обертка будет непрерывной, но элементы не обязательно будут. Вот это live demo, демонстрирующее это.

Однако рассмотрим случай, когда ваш массив массивов - это std::array<std::array<int,3>,2> - это просто массив из 2 элементов, где каждый элемент представляет собой массив фиксированного размера, 3, int. A std::array - это обертка вокруг массива C фиксированного размера, который не распределяется динамически, в отличие от его аналога std::vector. В этом случае вы получаете то же свойство локальности, что и для случая std::vector - каждый std::array смежн с передышкой на других, но здесь вы также получаете что-то большее. Поскольку std::array фактически содержит базовые данные, а не только несколько указателей на него, элементы каждой подматрицы также смежны относительно друг друга. Это тоже можно увидеть here.

То, что это сводится к аппаратной перспективе, - это просто то, как ваши объекты закладываются в память. В первом случае каждая оболочка смежна, но данных нет, потому что обертки просто содержат указатели на данные. В последнем случае каждая обертка является непрерывной, а также данные, потому что каждая обертка фактически содержит данные.

Возможно, если вы укажете, на каком языке вы ссылаетесь, я могу помочь вам в вашем конкретном случае.