Как написать код, который лучше всего использует кэш процессора для повышения производительности?

Question

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

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

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

3. Существуют ли какие-либо программные конструкции (если for, switch, break, goto, ...), поток кода (для if, if внутри for и т.д. ...), за которым следует следовать / избежать в этом вопросе?

Я с нетерпением жду возможности услышать индивидуальный опыт, связанный с созданием эффективного кеш-кода в целом. Это может быть любой язык программирования (C, C ++, Assembly, ...), любая аппаратная цель (ARM, Intel, PowerPC, ...), любая ОС (Windows, Linux, Symmbian, ...) и т. Д. .

Разнообразие поможет лучше понять его.

Answer 1

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

Предлагаю почитать про Оптимизацию, на этом сайте есть несколько хороших ответов. С точки зрения книг, я рекомендую Компьютерные системы: Перспектива программиста , в которой есть небольшой текст о правильном использовании кэша.

(b.t.w - как бы плохо ни был промах кеша, еще хуже - если программа пейджинговая с жесткого диска ...)

Answer 2

Кэш размещается в «строках кэша», и (реальная) память считывается и записывается в блоки такого размера.

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

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

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

Answer 3

Я могу ответить (2), сказав, что в мире C ++ связанные списки могут легко уничтожить кэш процессора. Массивы являются лучшим решением, где это возможно. Не знаю, применимо ли это к другим языкам, но легко представить, что возникнут те же проблемы.

Answer 4

Помимо выравнивания вашей структуры и полей, если ваша структура, если выделена куча, вы можете использовать распределители, которые поддерживают выравниваемые выделения; как _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); в противном случае у вас может быть случайный ложный обмен; помните, что в Windows куча по умолчанию имеет 16-байтовое выравнивание.

Answer 5

Напишите вашу программу, чтобы взять минимальный размер. Вот почему не всегда хорошая идея использовать оптимизацию -O3 для GCC. Это занимает больший размер. Часто -Os так же хорошо, как -O2. Все зависит от используемого процессора. YMMV.

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

Чтобы помочь вам лучше использовать временную / пространственную локальность команд, вы можете изучить, как ваш код преобразуется в сборку. Например:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

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