Как выравнивать данные?
Современные процессоры не такие же, как те процессоры, на которых разрабатывали язык Си. В новых процессорах огромные кеши, которые состоят из «строк», и данные в них пересылаются целиковыми строками (это моя гипотеза), по крайней мере уж очищаются-то точно строками.
«This enables several tricks, like making sure neighboring elements of an array never share the same cache line with each other (which may speed up certain kinds of concurrent code).»
Так или иначе, для данных сегодня очень полезно быть выровненными на границу 8 байт (при 64-х битной архитектуре вроде x86_64), или даже на границу 16-ти байт (стек вроде так просят выравнивать). «The choice of both Windows x64 and x86-64 System V to maintain 16-byte stack alignment». С мотивацией, что «некоторые типы данных, такие как SSE- и AVX-векторы, требуют выравнивания по границе 16 байт для корректной работы».
В спецификации языка Си возможность выравнивания типов на границу появилась начиная с C11.
«alignment of any given struct or union type is required by the ISO C standard to be at least a perfect multiple of the lowest common multiple of the alignments of all of the members of the struct or union in question.»
Мне надо, чтобы экземпляры структуры всегда выравнивались на границу 16 байт (в стеке и в куче). Как мне этого добиваться?
Пункт 7.15 стандарта C11:
7.15 Alignment <stdalign.h>
1 The header <stdalign.h> defines four macros.
2 The macro
alignas
expands to _Alignas; the macro
alignof
expands to _Alignof.
3 The remaining macros are suitable for use in #if preprocessing directives. They are
_ _alignas_is_defined
and
_ _alignof_is_defined
which both expand to the integer constant 1.
В C11, вы можете использовать ключевое слово alignas для установки выравнивания структуры.
alignas(16) struct MyStruct {
// поля структуры
};
«Для выделения памяти для таких типов данных следует использовать функции aligned_alloc и подобные». И тут начинаются разброд и шатание:
-
C11
void * aligned_alloc (size_t alignment, size_t size)
-
POSIX
int posix_memalign (void **memptr, size_t alignment, size_t size)
В GCC, для выравнивания структур и объединений, можно использовать атрибут __attribute__((aligned(n))). Но непонятно, требование по выравниванию применятся к самой структуре в целом, или к каждому полю в ней (думал, что второе, а на самом деле оказалось, что первое).
To specify multiple attributes, separate them by commas within the double parentheses: for example, __attribute__ ((aligned (16), packed)). Ну ок, а в C11 как добится такого же эффекта (выравнивание + packed)?
В LLVM реализация стандарта C11 тоже должна быть.
Ещё есть пункт 7.19 с типом max_align_t
7.19 Common definitions <stddef.h>
1 The header <stddef.h> defines the following macros and declares the following types.
Some are also defined in other headers, as noted in their respective subclauses.
2 The types are
...
max_align_t
which is an object type whose alignment is as great as is supported by the implementation in all contexts;
Отсюда, насколько я понимаю, если мне надо выравнивание не менее чем на 16 байтов, использовать malloc в коде нельзя (только aligned_alloc, возможно с alignof).
Я это всё потому пишу, что наткнулся на github-е на фрагмент кода, и мне захотелось сделать по-аналогии, только выравнивать не на 4 байта, а на 16. Наличие четырёх битов позволило бы мне в них закодировать не только разницу в глубине/высоте поддеревьев, но и количество дочерних узлов (два, один, или ни одного). Зная, что в листе нет дочерних, можно выделять под него меньше памяти, а листов в дереве чуть ли не половина от всех узлов.
Стоит ли заморачиваться именно с такой структурой дерева (для экономии памяти), если всё равно результат будут размещать в докере и потеряют много ресурсов в других местах, а предварительная оптимизация - зло? Может быть уже кто-то готовый код написал, никто не видел?
А что, если бы это был не Си, а какой-нибудь Rust?
«Один из способов управления выравниванием в Rust - использование атрибута #[repr(C)]. Этот атрибут гарантирует, что структура данных будет представлена в памяти так, как если бы она была написана на C. Это означает, что порядок и размер полей структуры будут соответствовать тому, что определено в C, и выравнивание будет соответствовать стандартам C»
«использование атрибута #[repr(align(16))] может привести к неэффективному использованию памяти, так как компилятор будет добавлять дополнительные заполнения в структуру, чтобы удовлетворить требование выравнивания.»
