Viva64 для оптимизации структур данных

16 Фев 2009

Автор: Андрей Карпов

Наконец добрался до реализации диагностики в анализаторе 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];
  ...
};

#Cpp #64bit