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

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

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

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

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

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

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

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

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

Улучшение пространственной локальности означает, что вы гарантируете, что каждая строка кеша будет использоваться полностью, как только она будет сопоставлена ​​с кешем. Когда мы рассмотрели различные стандартные эталонные тесты, мы увидели, что удивительная значительная часть из них не использует 100% выведенных строк кэша до того, как строки кэша будут выseleniumы.

Улучшение использования кеш-строки помогает в трех аспектах:

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

Общие методы:

  • Используйте меньшие типы данных
  • Организуйте свои данные, чтобы избежать выравнивания отверстий (сортировка ваших элементов структуры путем уменьшения размера является одним из способов)
  • Остерегайтесь стандартного динамического распределителя памяти, который может вводить отверстия и распространять ваши данные в памяти по мере их прогрева.
  • Убедитесь, что все смежные данные фактически используются в горячих циклах. В противном случае рассмотрите разбиение структур данных на горячие и холодные компоненты, чтобы горячие контуры использовали горячие данные.
  • избегайте алгоритмов и структур данных, которые демонстрируют нерегулярные шаблоны доступа, и предпочитают линейные структуры данных.

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

Современный процессор: часто есть один или несколько аппаратных префетов . Они тренируются по промахам в кеше и пытаются выявить закономерности. Например, после нескольких промахов к последующим строкам кэша, prefetcher hw начнет извлекать строки кэша в кеш, предвосхищая потребности приложения. Если у вас есть шаблон обычного доступа, предварительный набор аппаратных средств обычно выполняет очень хорошую работу. И если ваша программа не отображает обычные шаблоны доступа, вы можете улучшить ее, добавив инструкции предварительной выборки самостоятельно.

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

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

Слияние петель, которые касаются одних и тех же данных ( loop fusion ), и использование методов перезаписи, известных как тайлинг или блокирование, все стараются избежать дополнительных извлечений памяти.

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

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

Я не могу поверить, что на это больше нет ответов. Во всяком случае, один classический пример – итерация многомерного массива «наизнанку»:

pseudocode for (i = 0 to size) for (j = 0 to size) do something with ary[j][i] 

Причина, по которой этот кеш неэффективен, заключается в том, что современные процессоры будут загружать линию кэша с «близкими» адресами памяти из основной памяти при доступе к одному адресу памяти. Мы выполняем итерацию через «j» (внешние) строки в массиве во внутреннем цикле, поэтому для каждой поездки через внутренний цикл линия кэша будет выгружена и загружена линией адресов, которая находится рядом с [ j] [i]. Если это будет изменено на эквивалент:

 for (i = 0 to size) for (j = 0 to size) do something with ary[i][j] 

Он будет работать намного быстрее.

Я рекомендую прочитать статью из 9 статей. Каждый программист должен знать о памяти Ульриха Дреппера, если вам интересно, как взаимодействуют память и программное обеспечение. Он также доступен в виде 104-страничного PDF-файла .

Разделы, особенно имеющие отношение к этому вопросу, могут быть частью 2 (кэши CPU) и частью 5 (что могут сделать программисты – оптимизация кеша).

Основные правила на самом деле довольно просты. Там, где становится сложно, как они применяются к вашему коду.

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

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

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

Простым примером является обход 2D-массива, который показал ответ 1800-х годов. Если вы пересекаете его по строке за раз, вы читаете память последовательно. Если вы сделаете это по столбцу, вы прочтете одну запись, затем перейдете в совершенно другое место (начало следующей строки), прочитайте одну запись и снова прыгаете. И когда вы, наконец, вернетесь к первой строке, она больше не будет в кеше.

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

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

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

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

Помимо шаблонов доступа к данным, основным фактором в кэшировании кода является размер данных. Меньше данных означает, что он больше вписывается в кеш.

Это в основном фактор с структурами данных с выравниванием по памяти. «Обычная» мудрость гласит, что структуры данных должны быть выровнены на границах слов, потому что ЦПУ может получить доступ только к целым словам, а если слово содержит более одного значения, вам необходимо выполнить дополнительную работу (чтение-изменение-запись вместо простой записи) , Но кеши могут полностью аннулировать этот аргумент.

Аналогично, булевский массив Java использует весь байт для каждого значения, чтобы позволить напрямую работать с отдельными значениями. Вы можете уменьшить размер данных в 8 раз, если вы используете фактические биты, но тогда доступ к отдельным значениям становится намного сложнее, требуя операции сдвига бит и маски (class BitSet делает это для вас). Однако из-за эффектов кеша это может быть значительно быстрее, чем при использовании булева [], когда массив большой. IIRC Я однажды добился ускорения в 2 или 3 раза.

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

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

  1. Это дает процессору возможность читать вперед, например, спекулятивно класть больше памяти в кеш, к которому будет доступен доступ позже. Это чтение вперед дает огромный прирост производительности.

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

Замечание к «classическому примеру» пользователя 1800 INFORMATION (слишком долго для комментария)

Я хотел проверить разницу во времени для двух итерационных порядков («outter» и «inner»), поэтому я сделал простой эксперимент с большим 2D-массивом:

 measure::start(); for ( int y = 0; y < N; ++y ) for ( int x = 0; x < N; ++x ) sum += A[ x + y*N ]; measure::stop(); 

и второй случай, когда петли for меняются местами.

Более медленная версия («x first») составляла 0,88 сек, а более быстрая - 0,06 сек. Это сила кеширования 🙂

Я использовал gcc -O2 и все же петли не были оптимизированы. Комментарий Рикардо о том, что «большинство современных компиляторов могут понять это сами», не выполняется

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

Таким образом, во время цикла физики данные физики обрабатывались в порядке массива с использованием векторной математики. Объекты игры использовали свой идентификатор объекта как индекс в различных массивах. Это не был указатель, потому что указатели могут стать недействительными, если необходимо переместить массивы.

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

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

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

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

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

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

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

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

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

Я предлагаю прочитать о Оптимизации, есть несколько хороших ответов на этом сайте. Что касается книг, я рекомендую в Computer Systems: «Перспектива программиста», в которой есть тонкий текст о правильном использовании кеша.

(btw – так же плохо, как прошивка кэш-памяти, есть еще хуже – если программа пейджинговая с жесткого диска …)

Было много ответов на общие советы, такие как выбор структуры данных, шаблон доступа и т. Д. Здесь я хотел бы добавить еще один шаблон проектирования кода, называемый программным конвейером, который использует активное управление кешем.

Идея заимствована из других методов конвейерной обработки, например, для конвейерной обработки команд процессора.

Этот тип шаблона лучше всего относится к процедурам, которые

  1. может быть разбит на разумные несколько подэтапов, S [1], S [2], S [3], … время выполнения которых примерно сопоставимо с временем доступа к ОЗУ (~ 60-70 нс).
  2. принимает пакет ввода и выполняет вышеупомянутые несколько шагов для получения результата.

Давайте рассмотрим простой случай, когда есть только одна подпроцедура. Обычно код хотел бы:

 def proc(input): return sub-step(input)) 

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

 def batch_proc(inputs): results = [] for i in inputs: // avoids code cache miss, but still suffer data(inputs) miss results.append(sub-step(i)) return res 

Однако, как было сказано ранее, если выполнение шага примерно совпадает с временем доступа к ОЗУ, вы можете еще больше улучшить код:

 def batch_pipelined_proc(inputs): for i in range(0, len(inputs)-1): prefetch(inputs[i+1]) # work on current item while [i+1] is flying back from RAM results.append(sub-step(inputs[i-1])) results.append(sub-step(inputs[-1])) 

Поток выполнения будет выглядеть так:

  1. prefetch (1) запрашивает CPU для предварительной выборки ввода [1] в кеш, где команда prefetch берет сами P-циклы и возвращает, а в фоновом входе [1] поступает в кеш после циклов R.
  2. works_on (0) холодный промах на 0 и работает на нем, который принимает M
  3. prefetch (2) выдает другую выборку
  4. works_on (1), если P + R <= M, то входы [1] должны находиться в кеше уже до этого шага, таким образом, избежать промаха в кеше данных
  5. works_on (2)

Может быть больше шагов, тогда вы можете проектировать многоступенчатый конвейер, если совпадение времени шагов и латентности доступа к памяти совпадет, вы будете испытывать недостаток в кэше кода / данных. Однако этот процесс необходимо настроить во многих экспериментах, чтобы выяснить правильную группировку шагов и время предварительной выборки. Благодаря своим требуемым усилиям он видит большее применение в обработке данных с высокой производительностью / пакетным streamом. Хороший пример производственного кода можно найти в проекте конвейера DPQK QoS Enqueue: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Глава 21.2.4.3. Enqueue Pipeline.

Дополнительная информация может быть найдена:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

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

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

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

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

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

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

  • Как планируется x86 uops?
  • Лучший способ изменить строку
  • Android ListView Refresh Single Row
  • Самый эффективный код для первых 10000 простых чисел?
  • Получить экземпляр нового объекта из типа
  • Выполнение стресс-теста в веб-приложении?
  • Эффективность отражения Java
  • Какой был бы самый быстрый метод тестирования на простоту Java?
  • Как ускорить алгоритм A * при больших пространственных масштабах?
  • MySQL загружает данные infile - ускорение?
  • Кто-нибудь действительно эффективно реализовал Fibonacci-Heap?
  • Давайте будем гением компьютера.