Оптимизация членского порядка переменной в C++
Я столкнулся с той же проблемой. «Перезагрузка моего iPhone» сработала для меня.
10 ответов
Здесь две проблемы:
- Является ли сохранение вместе определенных полей вместе оптимизацией.
- Как это сделать на самом деле.
Причина, по которой это может помочь, заключается в том, что Память загружается в кэш ЦП кусками, называемыми «строками кеша». Это требует времени, и, вообще говоря, чем больше строк кэша загружено для вашего объекта, тем больше времени это занимает. Кроме того, для освобождения места из кэша выбрасывается все больше других вещей, что непредсказуемо замедляет другой код.
Размер строки кэша зависит от процессора. Если он велик по сравнению с размером ваших объектов, то очень немногие объекты будут охватывать границу строки кэша, поэтому вся оптимизация не имеет значения. В противном случае вам может сойти с рук только часть вашего объекта в кеше, а остальная часть в основной памяти (или, возможно, кеш-памяти L2). Хорошо, если ваши наиболее распространенные операции (те, которые обращаются к часто используемым полям) используют как можно меньше кеша для объекта, поэтому группировка этих полей вместе дает вам больше шансов на то, что это произойдет.
Общий принцип называется «месторасположение». Чем ближе друг к другу разные адреса памяти, к которым обращается ваша программа, тем больше у вас шансов добиться хорошего поведения кеша. Часто бывает сложно предсказать производительность заранее: разные модели процессоров одной и той же архитектуры могут вести себя по-разному, многопоточность означает, что вы часто не знаете, что будет в кэше и т. Д. Но можно поговорить о том, что скорее всего произойдет в большинстве случаев. Если вы хотите знать что-нибудь, обычно вам нужно это измерить.
Обратите внимание, что здесь есть некоторые подводные камни. Если вы используете атомарные операции на базе ЦП (которые обычно используются атомарными типами в C ++ 0x), то вы можете обнаружить, что ЦП блокирует всю строку кэша, чтобы заблокировать поле. Затем, если у вас есть несколько атомарных полей, расположенных близко друг к другу, с разными потоками, работающими на разных ядрах и одновременно работающими с разными полями, вы обнаружите, что все эти атомарные операции сериализованы, потому что все они блокируют одно и то же место в памяти, даже если они ' повторно работают на разных месторождениях. Если бы они работали с разными строками кэша, они бы работали параллельно и работали быстрее. Фактически, как указывает в своем ответе Глен (через Херба Саттера), в архитектуре с когерентным кешем это происходит даже без атомарных операций и может полностью испортить вам жизнь. Таким образом, местоположение ссылки не обязательно хорошо, когда задействовано несколько ядер, даже если они совместно используют кеш. Вы можете ожидать этого на том основании, что промахи в кэше обычно являются источником потери скорости, но это ужасно неправильно в вашем конкретном случае.
Теперь, помимо различия между часто используемыми и менее используемыми полями, меньшие тем меньше памяти (и, следовательно, меньше кеша) он занимает. Это довольно хорошие новости для всех, по крайней мере, если у вас нет серьезных споров. Размер объекта зависит от полей в нем и от любого заполнения, которое должно быть вставлено между полями, чтобы гарантировать, что они правильно выровнены для архитектуры. C ++ (иногда) накладывает ограничения на порядок, в котором поля должны появляться в объекте, в зависимости от порядка, в котором они объявлены. Это сделано для упрощения низкоуровневого программирования. Итак, если ваш объект содержит:
- int (4 байта, с выравниванием по 4)
- , за которым следует char (1 байт, любое выравнивание)
- , за которым следует int (4 байта, с выравниванием по 4)
- , за которым следует символ (1 байт, любое выравнивание)
, то есть вероятность, что это займет 16 байт в памяти. Между прочим, размер и выравнивание int не одинаковы на каждой платформе, но 4 очень распространено, и это всего лишь пример.
В этом случае компилятор вставит 3 байта заполнения перед вторым int , чтобы правильно выровнять его, и 3 байта заполнения в конце. Размер объекта должен быть кратным его выравниванию, чтобы объекты одного типа могли размещаться в памяти рядом. Вот и все, что есть массив в C / C ++, смежные объекты в памяти. Если бы структура была int, int, char, char, тогда тот же объект мог быть 12 байтов, потому что char не требует выравнивания.
Я сказал, что то, является ли int 4-выровненным, зависит от платформы: в ARM это обязательно должно быть, поскольку невыровненный доступ вызывает аппаратное исключение. На x86 вы можете получить доступ к ints без выравнивания, но обычно он медленнее и IIRC неатомарен. Таким образом, компиляторы обычно (всегда?) Выравнивают целые числа на x86 по 4.
Практическое правило при написании кода, если вы заботитесь об упаковке, - смотреть на требования выравнивания каждого члена структуры. Затем упорядочьте поля с наиболее выровненными типами сначала, затем со следующими наименьшими типами и так далее до членов без требования к выравниванию. Например, если я пытаюсь написать переносимый код, я могу придумать следующее:
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 или long long, лучше всего предположить, что она выровнена по 8. Иногда вы ошибаетесь, но большую часть времени будете правы.
Обратите внимание, что игровые программисты, такие как ваш блоггер, часто знают все о своем процессоре и оборудовании, и поэтому им не нужно гадать. Они знают размер строки кэша, они знают размер и выравнивание каждого типа, и они знают правила компоновки структуры, используемые их компилятором (для типов POD и не-POD). Если они поддерживают несколько платформ, то при необходимости они могут использовать особый случай для каждой из них. Они также тратят много времени на размышления о том, какие объекты в их игре выиграют от улучшения производительности, и с помощью профилировщиков выясняют, где находятся реальные узкие места. Но даже в этом случае неплохо иметь несколько практических правил, которые вы применяете независимо от того, нужно это объекту или нет. Если это не сделает код неясным, два хороших правила - «помещать часто используемые поля в начало объекта» и «сортировать по требованию выравнивания».
В зависимости от типа программы, которую вы запускаете, этот совет может привести к повышению производительности или может резко замедлить работу.
Выполнение этого в многопоточной программе означает, что вы собирается увеличить шансы «ложного обмена».
Прочтите статьи Херба Саттерса на эту тему здесь
Я уже говорил об этом раньше и буду повторять. Единственный реальный способ добиться реального увеличения производительности - это измерить ваш код и использовать инструменты для определения реального узкого места, вместо того, чтобы произвольно изменять что-то в вашей кодовой базе.
Это один из способов оптимизации размера рабочего набора . Есть хорошая статья Джона Роббинса о том, как можно ускорить производительность приложения за счет оптимизации размера рабочего набора. Конечно, это включает в себя тщательный отбор наиболее частых вариантов использования, которые конечный пользователь может выполнять с приложением.
У нас здесь немного другие рекомендации для участников (цель архитектуры ARM, в основном 16-битный кодогенератор THUMB по разным причинам):
- группировка по требованиям выравнивания (или, для новичков, «группировка по размер "обычно помогает)
- сначала наименьший
" группировать по выравниванию "в некоторой степени очевиден и выходит за рамки этого вопроса; он избегает заполнения, использует меньше памяти и т. д.
Второй пункт, однако, проистекает из небольшого 5-битного «непосредственного» размера поля в THUMB LDRB (байт регистра загрузки), LDRH (полуслова регистра загрузки) и LDR Инструкции (Загрузить регистр).
5 битов означают, что могут быть закодированы смещения 0–31. Фактически, если предположить, что "this" удобно в регистре (что обычно и есть):
- 8-битные байты могут быть загружены в одну инструкцию, если они существуют с этого + 0 по этот + 31
- 16-битные полуслова, если они существуют с этого + 0 по этот + 62;
- 32-битная машина слова, если они существуют в диапазоне от + 0 до +124.
Если они выходят за пределы этого диапазона, необходимо сгенерировать несколько инструкций: либо последовательность ADD с немедленными элементами для накопления соответствующего адреса в регистре, либо еще хуже , загрузка из литерального пула в конце функции.
Если мы попадаем в литеральный пул, это повредит: буквальный пул проходит через d-кеш, а не i-кеш; это означает, по крайней мере, загрузку из основной памяти в кэш-строку для первого доступа к литеральному пулу, а затем множество потенциальных проблем с вытеснением и недействительностью между d-кешем и i-кешем, если литеральный пул не запускается в собственном кэше линия (т.е. Одна из вещей, которые мы делаем, чтобы избежать буквального использования пула, - хранить все наши «глобальные переменные» в одной таблице. Это означает один поиск в пуле букв для «GlobalTable», а не несколько поисков для каждой глобальной таблицы. Если вы действительно умен, вы могли бы сохранить свою GlobalTable в какой-нибудь памяти, к которой можно было бы получить доступ, не загружая буквальную запись пула - это был .sbss?)
Одна из вещей, которые мы делаем, чтобы избежать буквального использования пула, - хранить все наши «глобальные переменные» в одной таблице. Это означает один поиск в пуле букв для «GlobalTable», а не несколько поисков для каждой глобальной таблицы. Если вы действительно умен, вы могли бы сохранить свою GlobalTable в какой-нибудь памяти, к которой можно было бы получить доступ, не загружая буквальную запись пула - это был .sbss?)Ну, первый член не нуждается в добавлении смещения к указателю для доступа к нему.
В C # порядок элементов определяется компилятором, если вы не укажете атрибут [LayoutKind.Sequential / Explicit], который заставляет компилятор размещать структуру / класс так, как вы указываете это к.
Насколько я могу судить, компилятор, кажется, минимизирует упаковку при выравнивании типов данных в их естественном порядке (т.е. 4 байта int начинаются с 4 байтовых адресов).
Я сосредотачиваюсь на производительности, скорости выполнения, а не на использовании памяти. Компилятор без какого-либо оптимизирующего переключателя отобразит область хранения переменных, используя тот же порядок объявлений в коде. Представьте себе
unsigned char a;
unsigned char b;
long c;
Большой беспорядок? без переключателей выравнивания, операции с низким объемом памяти. и др., у нас будет беззнаковый символ, использующий 64-битное слово в вашем DDR3 dimm, и другое 64-битное слово для другого, и все же неизбежное на долгое время.
Итак, это выборка для каждой переменной.
Однако упаковка или переупорядочивание приведет к тому, что одна выборка и одно маскирование AND смогут использовать беззнаковые символы.
Таким образом, с точки зрения скорости на текущей 64-битной машине с памятью слов выравнивается, повторные заказы и т. д. запрещены. Я занимаюсь микроконтроллерами, и там различия в упакованном / незапакованном виде действительно заметны (речь идет о процессорах <10MIPS, 8-битной памяти слов).
С другой стороны, давно известно, что инженерные усилия, необходимые для настройки кода для повышения производительности кроме того, что вам предписывает хороший алгоритм, и то, что компилятор может оптимизировать, часто приводит к сжиганию резины без каких-либо реальных эффектов. Это и кусок синтаксически dubius-кода только для записи.
Последний шаг вперед в оптимизации, который я видел (в uPs, не думаю, что это выполнимо для приложений для ПК), - это скомпилировать вашу программу как один модуль, иметь компилятор оптимизирует его (гораздо более общее представление о скорости / разрешении указателя / упаковке памяти и т. д.), а компоновщик убирает не вызываемые библиотечные функции, методы и т. д.
Теоретически это могло бы уменьшить промахи в кэше, если у вас есть большие объекты. Но обычно лучше группировать элементы одного размера вместе, чтобы получить более плотную упаковку памяти.
Я очень сомневаюсь, что любые улучшения в CPU - возможно, читаемость. Вы можете оптимизировать исполняемый код, если обычно выполняемые базовые блоки, которые выполняются в данном кадре, находятся в одном наборе страниц. Это та же идея, но он не знает, как создавать базовые блоки в коде. Я предполагаю, что компилятор размещает функции в том порядке, в котором он их видит, без оптимизации, чтобы вы могли попытаться объединить общие функции.
Попробуйте запустить профилировщик / оптимизатор. Сначала вы компилируете с некоторыми опциями профилирования, а затем запускаете свою программу. Как только профилированный exe будет завершен, он сбросит некоторую профилированную информацию. Возьмите этот дамп и прогоните его через оптимизатор в качестве входных данных.
Я не занимался этой работой в течение многих лет, но мало что изменило то, как они работают.
Это та же идея, но он не знает, как создавать базовые блоки в коде. Я предполагаю, что компилятор размещает функции в том порядке, в котором он их видит, без оптимизации, чтобы вы могли попытаться объединить общие функции.Попробуйте запустить профилировщик / оптимизатор. Сначала вы компилируете с некоторыми опциями профилирования, а затем запускаете свою программу. Как только профилированный exe будет завершен, он сбросит некоторую профилированную информацию. Возьмите этот дамп и прогоните его через оптимизатор в качестве входных данных.
Я не занимался этой работой в течение многих лет, но мало что изменило то, как они работают.
Это та же идея, но он не знает, как создавать базовые блоки в коде. Я предполагаю, что компилятор размещает функции в том порядке, в котором он их видит, без оптимизации, чтобы вы могли попытаться объединить общие функции.Попробуйте запустить профилировщик / оптимизатор. Сначала вы компилируете с некоторыми опциями профилирования, а затем запускаете свою программу. Как только профилированный exe будет завершен, он сбросит некоторую профилированную информацию. Возьмите этот дамп и прогоните его через оптимизатор в качестве входных данных.
Я не занимался этой работой в течение многих лет, но мало что изменило то, как они работают.
Как только профилированный exe будет завершен, он сбросит некоторую профилированную информацию. Возьмите этот дамп и прогоните его через оптимизатор в качестве входных данных.Я не занимался этой работой в течение многих лет, но мало что изменило то, как они работают.
Как только профилированный exe будет завершен, он сбросит некоторую профилированную информацию. Возьмите этот дамп и прогоните его через оптимизатор в качестве входных данных.Я не занимался этой работой в течение многих лет, но мало что изменило то, как они работают.
Вы можете просто использовать curl и regexp для получения результатов, но Google поймает вас, очистив результаты, если вы делать много вызовов (и возвращать поддельные результаты), поэтому у вас должна быть полная поддержка заголовков.
даже несмотря на то, что процессоры, используемые во многих встраиваемых системах, даже не имеют кеша.- Выравнивание памяти полей в структурах
Многие программисты хорошо понимают, что такое выравнивание, поэтому я не буду вдаваться в подробности здесь.
На большинстве архитектур ЦП к полям в структуре для повышения эффективности необходимо обращаться при собственном выравнивании. Это означает, что если вы смешиваете поля разного размера, компилятор должен добавить отступы между полями, чтобы обеспечить правильность требований к выравниванию. Поэтому для оптимизации памяти, используемой структурой, важно помнить об этом и располагать поля таким образом, чтобы за самыми большими полями следовали поля меньшего размера, чтобы свести к минимуму требуемое заполнение. Если конструкция должна быть «упакована» для предотвращения заполнения, доступ к невыровненным полям требует больших затрат времени выполнения, поскольку компилятор должен получить доступ к невыровненным полям, используя серию обращений к меньшим частям поля вместе со сдвигами и масками для сборки значения поля в регистре.
- Смещение часто используемых поля в структуре
Еще одно соображение, которое может быть важным для многих встроенных систем, - наличие часто используемых полей в начале структуры.
Некоторые архитектуры имеют ограниченное количество бит, доступных в инструкции для кодирования смещения для доступа к указателю, поэтому, если вы обращаетесь к полю, смещение которого превышает это количество битов, компилятор должен будет использовать несколько инструкций для формирования указателя на поле. Например, архитектура ARM Thumb имеет 5 бит для кодирования смещения, поэтому он может получить доступ к полю размером со слово в одной инструкции, только если поле находится в пределах 124 байтов от начала. Итак, если у вас большая структура, оптимизация, которую может захотеть иметь в виду встроенный инженер, - это разместить часто используемые поля в начале макета структуры.