Наконец добрался до реализации диагностики в анализаторе Viva64, выявляющей структуры с неоптимальным расположением полей. До этого сдерживало отсутствие в библиотеке VivaCore поддержки вычисления типов для мелких типов данных, таких как ST_CHAR, ST_SHORT. Ранее все типы, размером меньше 32-бит назывались ST_LESS_INT. Так что пользователям библиотеки есть смысл скачать обновленную версию VivaCore. В последнее время там многое поменялась.
Но вернемся собственно к проверке оптимальности расположения данных в структурах. Говорить я буду применительно к Visual C++. Вы знаете, что данные в структурах в языке Си++ выравниваются таким образом, чтобы обеспечить более эффективный к ним доступ. Кстати, некоторые микропроцессоры вообще не могут напрямую обращаться к не выровненным данным и компилятору приходится генерировать специальный код для обращения к таким данным. Те же микропроцессоры, которые могут обращаться к не выровненным данным, все равно делают это намного менее эффективно. Поэтому компилятор Си++ оставляет пустые ячейки между полями структур, чтобы обеспечить их выравнивание по адресам машинных слов и тем самым ускорить к ним обращение. Можно отключить выравнивание, используя специальные директивы #pragma, чтобы сократить объем используемой памяти, но нас этот вариант сейчас не интересует. Часто можно значительно сократить объем расходуемой памяти, простым изменением порядка полей в структуре, без потери производительности.
Рассмотрим следующую структуру:
struct MyStruct
{
bool m_bool;
char *m_pointer;
int m_int;
};На 32-битной системе эта структура займет 12 байт и сократить этот размер не представляется возможным. Каждое поле выровнено по границе 4 байта. Даже если m_bool перенести в конец, это ничего не изменит. Компилятор все равно сделает размер структуры кратным 4 байтам, для выравнивания таких структур в массивах.
В случае 64-битной сборки структура MyStruct займет уже 24 байта. Это понятно. В начале идет один байт под m_bool и 7 неиспользуемых байт для выравнивания, так как указатель занимает 8 байт и должен быть выровнен по границе 8 байт. Затем 4 байта для m_int и 4 неиспользуемых байта, для выравнивания структуры по границе 8 байт. К счастью дело можно легко поправить, переместив m_bool в конец структуры, как показано ниже:
struct MyStructOpt
{
char *m_pointer;
int m_int;
bool m_bool;
};Структура MyStructOpt займет уже не 24, а 16 байт. Весьма существенная экономия, если мы будем использовать, например, 10 миллионов элементов. В этом случае мы сэкономим 80 мегабайт памяти, но что еще более важно, можем повысить производительность. Если структур будет немного, то нет разницы, какого они размера. Доступ будет происходить с одинаковой скоростью. Но когда элементов много, то начинает играть роль кеш, количество обращений к памяти и так далее. И можно с уверенностью утверждать, что обработка 160 мегабайт данных займет меньше времени, чем 240. Даже простой доступ ко всем элементам массива для чтения, уже будет более быстр.
Я знаю, что не всегда изменение последовательности полей в структурах возможно или удобно. Но если таких структур миллионы, то следует не пожалеть немного времени. Результат такой простой оптимизации, как изменение последовательности полей, может дать весьма впечатляющие результаты. Сейчас у меня нет чисел подтверждающих это, но возможно я приведу примеры в следующих заметках блога.
Вы, наверное, зададите вопрос, по каким правилам компилятор выравнивает данные. Я отвечу кратко, а если интересно познакомиться с этой темой более подробно, то отсылаю вас к книге Джеффри Рихтер - Создание эффективных WIN32-приложений с учетом специфики 64-разрядной версии Windows. Там этот вопрос, кажется, рассматривается достаточно подробно.
В целом правило выравнивание следующее: каждое поле выравнивается по адресу, кратному размеру данного поля. Поле типа size_t на 64-битной системе будет выровнено по границе 8 байт, int по границе 4 байта, short по границе 2 байта. Поля типа char не выравнивается. Размер структуры выравнивается до размера, кратному размеру его максимального элемента. Поясним это выравнивание на примере:
struct ABCD
{
size_t m_a;
char m_b;
};Элементы займут 8 + 1 = 9 байт. Но если размер структуры будет 9 байт, то если мы захотим создать массив структур ABCD[2], то поле m_a второй структуры будет лежать по не выровненному адресу. Вследствие этого компилятор дополнит структуру 7 пустыми байтами до размера 16 байт.
Может показаться сложным процесс оптимизации последовательности полей. Но можно предложить очень простой и очень эффективный способ. Достаточно расположить поля в порядке убывания их размера. Этого будет совершенно достаточно. В этом случае поля начнут располагаться без лишних зазоров. Например, возьмем следующую структуру размером 40 байт
struct MyStruct
{
int m_int;
size_t m_size_t;
short m_short;
void *m_ptr;
char m_char;
};и простой сортировкой последовательности полей по убыванию размера:
struct MyStructOpt
{
void *m_ptr;
size_t m_size_t;
int m_int;
short m_short;
char m_char;
};мы сделаем из нее структуру размером всего 24 байт.
Намного более нетривиальной задачей является найти эти самые структуры, которые следует модифицировать. Просматривать все struct и class дело достаточно неблагодарное и утомительное. Именно для этого я занялся добавлением в анализатор Viva64 правила для поиска подобных неэффективных структур (классов). Вдобавок анализатор будет проявлять некоторую интеллектуальность и не выдавать предупреждение на классы, являющимися наследниками других классов. Обычно такие объекты не создают миллионами. Т.е. хочется сделать, чтобы предупреждать о неэффективности класса MyPoint, но промолчать про неэффективность класса MyWindow:
class MyPoint {
bool m_isActive;
size_t m_x, m_y;
char m_color[3];
...
};
class MyWindow : public CWnd {
bool m_isActive;
size_t m_sizeX, m_ sizeY;
char m_color[3];
...
};