Какова интуиция, лежащая в основе структур данных, не обращающих внимания на кэш?
Я понимаю, что означает кеш выражения. Но мне было интересно, есть ли какое-нибудь простое объяснение того, как можно спроектировать структуры данных, которые могут оптимально использовать кеш, не зная размеров кеша.
Не могли бы вы дать такое объяснение, желательно с (простым) примером?
2 ответа
Даже такой знакомый алгоритм, как быстрая сортировка, несколько забывает о кеше (но не оптимально). Напомним, что это работает путем разбиения массива, а затем повторения на каждой стороне раздела. В конце концов, он работает с вложенным массивом, который помещается в кэш, и, таким образом, больше не будет промахов кеша, пока он не завершит этот массив и перейдет к другому. Это свойство, которое мы ищем.
Сравните это с сортировкой вставок, которая (если использовать технический термин) постоянно появляется повсюду. Таким образом, помимо необходимости вставки сортировки для перемещения O(n^2) элементов, она также сильно пропускает кэш при использовании больших массивов.
Быстрая сортировка является некоторым способом от оптимального, все же. Каждая отдельная фаза раздела не разделяет и не рекурсирует - она выполняет длинный последовательный прогон памяти, переполняющей кэш. Потенциально это произойдет несколько раз, прежде чем размер подмассива станет достаточно маленьким, и мы начнем побеждать, поэтому мы не минимизируем количество пропусков кэша.
Основная интуиция заключается в том, что если вы рекурсивно разбиваете набор данных, с которым работаете, в какой-то момент (обычно довольно быстро) вы достигнете размера, который 1) помещается в кеш, а 2) заполняет по крайней мере половину кеша (при условии каждого разделения из набора данных (по крайней мере, приблизительно) пополам).