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

Наконец добрался до реализации диагностики в анализаторе Viva64, выявляющей структуры с неоптимальным расположением полей\. До этого сдерживало отсутствие в библиотеке VivaCore поддержки вычисления типов для мелких типов данных, таких как ST\_CHAR, ST\_SHORT\. Ранее все типы, размером меньше 32\-бит назывались ST\_LESS\_INT\. Так что пользователям библиотеки есть смысл скачать обновленную версию VivaCore\. В последнее время там многое поменялась\.

Но вернемся собственно к проверке оптимальности расположения данных в структурах\. Говорить я буду применительно к Visual C\+\+\. Вы знаете, что данные в структурах в языке Си\+\+ выравниваются таким образом, чтобы обеспечить более эффективный к ним доступ\. Кстати, некоторые микропроцессоры вообще не могут напрямую обращаться к не выровненным данным и компилятору приходится генерировать специальный код для обращения к таким данным\. Те же микропроцессоры, которые могут обращаться к не выровненным данным, все равно делают это намного менее эффективно\. Поэтому компилятор Си\+\+ оставляет пустые ячейки между полями структур, чтобы обеспечить их выравнивание по адресам машинных слов и тем самым ускорить к ним обращение\. Можно отключить выравнивание, используя специальные директивы \#pragma, чтобы сократить объем используемой памяти, но нас этот вариант сейчас не интересует\. Часто можно значительно сократить объем расходуемой памяти, простым изменением порядка полей в структуре, без потери производительности\.

Рассмотрим следующую структуру:

```cpp
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 в конец структуры, как показано ниже:

```cpp
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 не выравнивается\. Размер структуры выравнивается до размера, кратному размеру его максимального элемента\. Поясним это выравнивание на примере:

```cpp
struct ABCD
 {
  size_t m_a;
  char m_b;
 };
```

Элементы займут 8 \+ 1 \= 9 байт\. Но если размер структуры будет 9 байт, то если мы захотим создать массив структур ABCD\[2\], то поле m\_a второй структуры будет лежать по не выровненному адресу\. Вследствие этого компилятор дополнит структуру 7 пустыми байтами до размера 16 байт\.

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

```cpp
struct MyStruct
{
  int m_int;
  size_t m_size_t;
  short m_short;
  void *m_ptr;
  char m_char;
};
```

и простой сортировкой последовательности полей по убыванию размера:

```cpp
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:

```cpp
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];
  ...
};
```