Какова интуиция, лежащая в основе структур данных, не обращающих внимания на кэш?

Question

Я понимаю, что означает выражение кеш, забывающий .Но мне было интересно, есть ли какое-нибудь простое объяснение того, как можно спроектировать структуры данных, которые могут оптимально использовать кеш, не зная размеров кеша.

Не могли бы вы дать такое объяснение, желательно с (легкий) пример?

Answer 1

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

Сравните это с сортировкой вставок, которая (если использовать технический термин) постоянно появляется повсюду.Таким образом, помимо необходимости вставки сортировки для перемещения O (n ^ 2) элементов, она также сильно пропускает кэш при использовании больших массивов.

Быстрая сортировка - это, однако, путь от оптимального.Каждая отдельная фаза раздела не разделяет и не рекурсирует - она ​​выполняет длинный последовательный прогон памяти, переполняющей кэш.Потенциально это произойдет несколько раз, прежде чем размер подмассива станет достаточно маленьким, и мы начнем побеждать, поэтому мы не минимизируем количество пропусков кэша.

Answer 2

Основная интуиция заключается в том, что если вы рекурсивно разделите набор данных, с которым работаете, в какой-то момент (обычно довольно быстро) вы достигнете размера, который 1) помещается в кеш, а 2) заполняет по крайней мере половину кеша ( при условии, что каждый раздел набора данных (по крайней мере приблизительно) пополам).