С++: оптимизирующий порядок переменных?

Ответ 1

Два вопроса здесь:

• Независимо от того, сохраняются ли определенные поля вместе, это оптимизация.
• Как это сделать на самом деле.

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

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

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

Обратите внимание, что здесь есть некоторые ошибки. Если вы используете атомные операции на основе процессора (которые обычно имеют атомарные типы в С++ 0x), вы можете обнаружить, что ЦП блокирует всю строку кэша, чтобы заблокировать это поле. Затем, если у вас несколько атомных полей близко друг к другу, с разными потоками, запущенными на разных ядрах и работающими в разных полях одновременно, вы обнаружите, что все эти атомарные операции сериализованы, потому что они блокируют одно и то же местоположение памяти, работая в разных областях. Если бы они работали в разных строках кэша, они бы работали параллельно и работали быстрее. Фактически, как указывает Глен (через Herb Sutter), в архитектуре с когерентным кешем это происходит даже без атомных операций и может полностью разрушить ваш день. Таким образом, местность ссылок не всегда является хорошей вещью, когда задействованы несколько ядер, даже если они разделяют кеш. Вы можете ожидать, что это будет по причине того, что промахи в кешах обычно являются источником потерянной скорости, но в вашем конкретном случае будут ужасно ошибочными.

Теперь, несмотря на различие между обычно используемыми и менее используемыми полями, чем меньше объект, тем меньше занимает память (и, следовательно, меньше кеша). Это хорошая новость по всему миру, по крайней мере, там, где у вас нет тяжелой конкуренции. Размер объекта зависит от полей в нем и от любого дополнения, которое должно быть вставлено между полями, чтобы гарантировать, что они правильно выровнены для архитектуры. С++ (иногда) помещает ограничения на порядок, какие поля должны появляться в объекте, в зависимости от того, какой порядок они объявлены. Это делается для упрощения программирования на низком уровне. Итак, если ваш объект содержит:

• int (4 байта, 4-выровненный)
• а затем char (1 байт, любое выравнивание)
• за которым следует int (4 байта, 4-выровненный)
• а затем char (1 байт, любое выравнивание)

то, скорее всего, это займет 16 байт в памяти. Размер и выравнивание int не одинаковы на каждой платформе, кстати, но 4 очень распространен, и это всего лишь пример.

В этом случае компилятор вставляет 3 байта заполнения перед вторым int, чтобы правильно выровнять его, и 3 байта заполнения в конце. Размер объекта должен быть кратным его выравниванию, так что объекты одного и того же типа могут быть смежными в памяти. То, что весь массив находится в C/С++, смежные объекты в памяти. Если бы структура была int, int, char, char, тогда один и тот же объект мог быть 12 байтов, потому что char не имеет требования к выравниванию.

Я сказал, что если int 4-aligned зависит от платформы: на ARM это абсолютно необходимо, так как неаудированный доступ вызывает аппаратное исключение. На x86 вы можете получить доступ к ints unligned, но он в целом медленнее и IIRC неатомный. Итак, компиляторы обычно (всегда?) 4-align ints на x86.

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

struct some_stuff {
    double d;   // I expect double is 64bit IEEE, it might not be
    uint64_t l; // 8 bytes, could be 8-aligned or 4-aligned, I don't know
    uint32_t i; // 4 bytes, usually 4-aligned
    int32_t j;  // same
    short s;    // usually 2 bytes, could be 2-aligned or unaligned, I don't know
    char c[4];  // array 4 chars, 4 bytes big but "never" needs 4-alignment
    char d;     // 1 byte, any alignment
};

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

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

Ответ 2

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

Выполнение этой задачи в многопоточной программе означает, что вы увеличите шансы "ложного обмена".

Ознакомьтесь с статьями Herb Sutters по теме здесь

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

Ответ 3

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

Ответ 4

У нас есть несколько разные рекомендации для членов здесь (цель ARM-архитектуры, в основном, 16-разрядный кодек THUMB по разным причинам):

• по требованию выравнивания (или, для новичков, "группа по размеру" обычно выполняет трюк)
• наименьшее из первых

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

Вторая пуля, однако, вытекает из небольшого 5-битного "немедленного" размера поля в байтах THUMB LDRB (Load Register Byte), LDRH (Load Register Halfword) и LDR (Load Register).

5 бит означает, что смещения 0-31 могут быть закодированы. Эффективно, предполагая, что "this" удобен в регистре (который обычно есть):

• 8-разрядные байты могут быть загружены в одну команду, если они существуют при этом + 0 через это + 31
• 16-битные полусловы, если они существуют при этом + 0 через это + 62;
• 32-битные машинные слова, если они существуют при этом + 0 через это + 124.

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

Если мы попадаем в литеральный пул, это больно: литеральный пул проходит через d-кеш, а не i-cache; это означает, по крайней мере, ценность кештинга нагрузок из основной памяти для первого доступа к литерному пулу, а затем множество потенциальных проблем выселения и недействительности между d-кешем и i-кешем, если литеральный пул не запускается в своем собственном кеше (т.е. если фактический код не заканчивается в конце строки кэша).

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

(Не говоря уже о том, что одна из вещей, которые мы делаем, чтобы избежать использования литерального пула, хранит все наши "глобалы" в одной таблице. Это означает, что один литеральный пул ищет "GlobalTable", а не множественный поиск для каждого глобального. Если вы действительно умны, возможно, вы сможете сохранить свой GlobalTable в какой-то памяти, к которой можно получить доступ, не загружая личную запись пула - это было .sbss?)

Ответ 5

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

- выравнивание по полям в структурах

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

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

- Смещение часто используемых полей в структуре

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

Некоторые архитектуры имеют ограниченное количество бит, доступных в инструкции для кодирования смещения для доступа к указателю, поэтому, если вы обращаетесь к полю, смещение которого превышает это количество бит, компилятору придется использовать несколько инструкций для формирования указателя на поле. Например, архитектура ARM Thumb имеет 5 бит для кодирования смещения, поэтому она может обращаться к полю размера слова в одной команде, только если это поле находится в пределах 124 байт от начала. Поэтому, если у вас есть большая структура, оптимизация, которую хотел бы иметь в виду встроенный инженер, - это разместить часто используемые поля в начале структуры структуры.

Ответ 6

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

Ответ 7

В С# порядок члена определяется компилятором, если вы не поместите атрибут [LayoutKind.Sequential/Explicit], который заставляет компилятор выложить структуру/класс так, как вы ему рассказываете.

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

Ответ 8

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

Ответ 9

hmmm, это звучит как очень сомнительная практика, почему компилятор не позаботится об этом?

Ответ 10

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

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

Я давно ушел от этой линии работы, но не так много изменилось, как они работают.

Ответ 11

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

 unsigned char a;
 unsigned char b;
 long c;

Большой беспорядок? без выравнивающих переключателей, операторы с малой памятью. и др., у нас будет неподписанный char, используя 64-битное слово на вашем DDR3-dimm, а другое 64-битное слово для другого, и все же неизбежное для долгого.

Итак, это выборка для каждой переменной.

Однако, упаковывая его или переупорядочивая его, вы получите одну выборку и одно маскирование ИМ, чтобы использовать символы без знака.

Таким образом, по скорости, на текущей 64-битной машине с памятью, выравниваниях, переупорядочениях и т.д., нет-nos. Я занимаюсь микроконтроллером, и там различия в упакованном/не упакованном состоянии по-разному заметны (речь идет о процессорах 10 Мбит/с, 8-битных словарных памяти)

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

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