Встраивание полей структур

Дмитрий
Дмитрий

Cтруктура данных Object в данном примере (на x64) занимает 32 байта:

struct Container {
    void *data;     // 8
    uint16_t size;  // 8, из которых используется 2
};
 
struct Object {
    uint64_t id;     // 8
    Container list;  // 16, из которых используется 10
    uint16_t flags;  // 8, из которых используется 2
};

Её можно переписать вот так:

struct Object {
    uint64_t id;    // 8     void *data;     // 8     uint16_t size;  // 2     uint8_t flags;  // 1 };

Тогда её размер уменьшится на 25%, до 24 байт (а на 32 битной системе размер уменьшится еще больше - на 33%, с 24 байт до 16 байт). Но данный вариант требует ручного дублирования Container во всех структурах. Предлагаю в качестве решения обозначать структуру как встраиваемую:

 

inline struct Container {
    void *data;     // 8
    uint16_t size;  // 8, из которых используется 2
};
 
struct Object {
    uint64_t id;     // 8
    Container list;  // 16, из которых используется 11, свои поля + flags
    uint16_t flags;
};

В данном примере сообщается, что структура Container никак не использует области памяти, к которым у неё нет явного доступа (последние 6 байт), и может быть безопасно встроена в другую структуру, которая, в свою очередь, может использовать данную память под свои поля. При этом сохраняется выравнивание полей по границе кратной своему же размеру, но уменьшается объем потребляемой памяти и, соответственно, количество промахов кэша.
Альтернативный вариант:

 

struct Container {
    void *data;     // 8
    uint16_t size;  // 8, из которых используется 2
};
 
struct Object {
    uint64_t id;     // 8
    inline Container list;  // 16, из которых используется 11, свои поля + flags
    uint16_t flags;
};
7
рейтинг
26 комментариев
yndx-antoshkka
Стоит поисследовать проблему и понять почему это не делается автоматически. Если разумных причин нет - разрешить компиляторам так делать по умолчанию.
yndx-antoshkka
Павел Корозевцев
yndx-antoshkka, если начать делать по умолчанию, сломается бинарная совместимость со старым кодом.
Павел Корозевцев
yndx-antoshkka
Павел Корозевцев, да сломается.

Но мне кажется что оптимизация сильно хорошая и было бы неплохо, чтобы стандарт C++ позволял её делать. А уж какие из компиляторов будут её реализовывать и когда (и будут ли вообще) - это их дело.

Нужно поисследовать этот вопрос подробнее
yndx-antoshkka
Дмитрий
yndx-antoshkka, размер перечисления задается только вручную (начиная с c++11), иначе будет int. Никакого автоматического выведения не сделали, а тоже была бы неплохая оптимизация.
Дмитрий
yndx-antoshkka
Дмитрий, поясните вашу мысль. Я немного не понимаю о чём вы.
yndx-antoshkka
Дмитрий
yndx-antoshkka, мне кажется ситуация аналогична. Размер enum фиксирован - 4 байта (тип int), что излишне в ряде случаев. В с++11 могли сделать автоматический вывод размера перечисления основываясь на количестве и значениях его полей. Но так не сделали, а ввели альтернативный синтаксис для объявления перечисления с явным заданием типа (размера). Я полагаю тоже руководствовались бинарной совместимостью.
Дмитрий
Andrey Davydov
Давайте рассмотрим такой код:
void assign(Container & dest, Container const & src)
{
dest = src;
}

void foo(Object o, Container c)
{
assign(o.list, c);
}
Компилятор не имеет права скомпилировать assign как memcpy(&dst, &src, sizeof(Container)). Кажется это довольно сильное ограничение. Не лучше ли стандартизовать аттрибут packed (#pragma pack в MSVC), чтобы можно было реализовать Ваш пример следующим образом?
#include <cstdint>

static_assert(sizeof(void*) == 8);

struct [[gnu::packed]] alignas(2) Container
{
void * data;
std::uint16_t size;
};

static_assert(sizeof(Container) == 10);
static_assert(alignof(Container) == 2);

struct Object
{
std::uint64_t id;
Container list;
std::uint16_t flags;
};

static_assert(sizeof(Object) == 24);

При этом, если мы не хотим уплотнять Object, то этого можно достичь так:
struct Object
{
std::uint64_t id;
Container list;
alignas(8) std::uint16_t flags;
};

static_assert(sizeof(Object) == 32);
Andrey Davydov
Дмитрий
Скомпилировать assign как memcpy(&dst, &src, sizeof(Container)) не может. Но я отметил что inline должен обозначать что структура Container никак не использует области памяти, к которым у неё нет явного доступа (в примере последние 6 байт). Поэтому компилятор свободно может сделать так: memcpy(&dst, &src, sizeof(Container)-6), или проще: memcpy(&dst, &src, 10).
Дмитрий
Andrey Davydov
Дмитрий, а чем такое хитрое определение "структура никак не использует области памяти к которым у нее нет явного доступа" лучше чем просто ограничить размер структуры (что достигается в моем примере через атрибут packed)?
Andrey Davydov
Дмитрий
Andrey Davydov, дело в выравнивании. Обычно поля структур выравнены по границе кратной своему же размеру. Не знаю актуально ли оно на сегодня, но все компиляторы его производят и данное правило будет нарушено.
Дмитрий
dmitriy@izvolov.ru
Идея хорошая, но — согласен с комментариями — требуется более глубокая проработка.
dmitriy@izvolov.ru
Сергей Прейс
Проблема в совместимости - необходимо обеспечить бинарную совместимость структур между кодами от разных компиляторов, поэтому "А уж какие из компиляторов будут её реализовывать и когда (и будут ли вообще) - это их дело" - не вариант. Более того, придется прописать как в точности встраивание структур будет работать.
Кроме того, "встраиваемость" накладывает определенные ограничения на компилятор и может иметь негативный эффект на производительность. Например, сейчас компилятор имеет право записывать 4 байта вместо 2х в size если это будет быстрее на целевой архитектуре, но если на структуре написано inline то это недопустимо - структура может содержать данные из другой структуры, которые будут испорчены таким образом. В частности при копировании структур нельзя будет делать bulk copy, придется делать field-by-filed.
Сергей Прейс
Дмитрий
Сергей Прейс, бинарная совместимость обеспечивается, ситуация аналогична enum. При копировании структур делать bulk copy можно во всех случаях, т.к. речи о перестановке полей или нарушении выравнивания не идет. Встраиваемость негативный эффект может иметь, а может не иметь. Я склоняюсь к мнению что описанного негативного эффекта не будет в принципе. Однозначно можно сказать что потребление памяти и количество кэш-промахов снизится. Далее сам программист в конкретной ситуации должен решать применять или нет.
Дмитрий
Сергей Прейс
Дмитрий, про enum не понял аналогию. Для обычных структур в стандарте строго прописано размещение полей и это обеспечивает бинарную совместимость. Всякие [[gnu::packed]] нарушают эту совместимость - если один компилятор (сс1) поддерживает gnu::packed а другой компилятор (сс2) не поддерживает gnu::packed и проигнорирует атрибут, то структура пришедшая от сс1 к сс2 как параметр вызова (при чем не важно по ссылке или по значению) будет интерпретирована неправильно. То же и в обратную сторону, то же и с предложенной идеей - точное размещение полей структур должно полностью совпадать и его надо будет точно специфицировать.

И нет, bulk copy делать нельзя. Рассмотрим такой код.

struct Container {
void *data; // 8
uint16_t size; // 8, из которых используется 2
};

struct Object {
uint64_t id; // 8
inline Container list; // 16, из которых используется 11, свои поля + flags
uint16_t flags;
};

void make_container(void* data, uint16_t size) {
return {data, size};
}

void make_object(uint64_t id, uint16_t flags, uint_16 size, Generator gen) {
Object o;
o.id = id;
o.flags = flags;
Container c = make_container(gen(size), size);
o.list = c; // Будем считать, что это копирование останется в коде
}

Присваивание o.list = c; нельзя сделать через bulk copy (memcpy(o.list, c, sizeof(Container)) - можно было бы сделать через один SSE регистр двумя простыми инструкциями) - внутри o.list размещено поле flags и при bulk copy оно будет затерто.

На некоторых платформах негативные эффекты точно будут. Потребление памяти и количество промахов по кэшу могут снизиться, но могут возникнуть проблемы с partial register stall, store forwarding и т.п. К сожалению программисты далеко не всегда понимают возможные низкоуровневые проблемы.
Сергей Прейс
Сергей Прейс
Поправлюсь - согласен с yndx-antoshkka - размещение полей структур описано в ABI а не в стандарте языка. И это делает аналогию с enum еще менее понятной.
Сергей Прейс
Дмитрий
Сергей Прейс, одни компиляторы поддерживают enum Example : uint8_t { ... }, другие нет. Одни компиляторы будут поддерживать inline struct Container { ... }, другие нет. И в том, и в другом случае при отсутствии поддержки код просто не соберется. Поясните, в чем же все таки разница?
Отмечу что в предложении про [[gnu::packed]] и нарушение выравнивания ничего не говорится в принципе. Выравнивание сохраняется.
Дмитрий
Сергей Прейс
Если не соберется - это нормально. Я отвечал на вот этот комментарий "А уж какие из компиляторов будут её реализовывать и когда (и будут ли вообще) - это их дело."

Про выравнивание я понимаю, но дело не только в нем. Чтобы была можно было передавать структуру между функциями собранными разными компиляторами эта структура должна пониматься ими обоими абсолютно одинаково (должны совпадать не просто выравнивания, а смещения полей от начала структуры и размер всей структуры). В предложении меняются и смещения и размеры, а значит требуется их точное описание при чем, как правильно отметил yndx-antoshkka менять придется не только стандарт, но и ABI.

>> Обычно поля структур выравнены по границе кратной своему же размеру.
>> Не знаю актуально ли оно на сегодня, но все компиляторы его производят
>> и данное правило будет нарушено.
Правило актуально - оно часть ABI и оно имеет два полезных свойства: оно фиксирует как точно должны размещаться поля в структурах и при этом позволяет эффективную и безпроблемную реализацию операций над структурами. Эффективность достигается не только за счет собственно выравнивания, но и за счет снижения гранулярности операций (использование доступов большего размера). Ну и на части платформ (Sparc, Xeon Phi первого поколения) нарушение натурального выравнивания (выравнивания на размер доступа) при доступе к памяти может приводить к аппаратным ошибкам.
Сергей Прейс
Дмитрий
Сергей Прейс, в таком случае выравнивание сохраняется, здесь проблем нет. А по поводу передачи структуры между функциями я предложил решение ниже - если она встраивается, то её как объекта быть не должно, иначе действительно много проблем.
Дмитрий
yndx-antoshkka
Поисследовал:

* Стандарт С++ позволяет такую оптимизацию:

[basic.align]

The alignment required for a type might be different when it is used as the type of a complete object and when it is used as the type of a subobject.

[ Example:

struct B { long double d; };
struct D : virtual B { char c; };

When D is the type of a complete object, it will have a subobject of type B, so it must be aligned appropriately for a long double. If D appears as a subobject of another object that also has B as a virtual base class, the B subobject might be part of a different subobject, reducing the alignment requirements on the D subobject.

— end example ]


* GCC использует Itanium ABI gcc.gnu.org/onlinedocs/libstdc++/manual/abi.html
* Itanium ABI описывает alignment для классов refspecs.linuxbase.org/cxxabi-1.83.html#class-types
* Для примеров близких к вашим, GCC и CLANG сейчас генерируют очень похожий код в обоих случаях (см вторую половину) godbolt.org/g/ztHZnn . Другими словами, можно проводить такую оптимизацию, но надо поэкспериментировать с типами и перепроверить, что для unsigned типов переполнение будет работать одинаково в обоих случаях.

Итого: если хочется увидеть из коробки такую оптимизацию, то нужно убедить в её целесообразности разработчиков Itanium ABI и дополнить Itanium ABI.
yndx-antoshkka
Сергей Прейс
yndx-antoshkka,
боюсь даже представить как передается по ссылке D для которого выполнено "appears as a subobject of another object that also has B as a virtual base class, the B subobject might be part of a different subobject, reducing the alignment requirements on the D subobject". В вызываемой функции D is the type of a complete object со всеми вытекающими, так что передать простой указатель на подобъект D не получится. Подозреваю, что в месте вызова возникнет временный объект типа D в него соберут подобъект и передадут на него ссылку в вызов при возврате случится копирование данных из времянки. Впрочем это поведение не зависит от выравнивания, так что определенная оптимизация по памяти будет иметь место, а бинарная совместимость будет обеспечена необходимостью описанного выше преобразования.
Сергей Прейс
yndx-antoshkka
Есть у кого желание заняться улучшением Itanium ABI?
yndx-antoshkka
Дмитрий
Там, где копирование встроенного объекта делается так: memcpy(&dst, &src, sizeof(Container)), будет ошибка. При том ошибка неявная и трудноуловимая, особенно для незнающего.
Предлагаю для решения данной проблемы запретить прямой доступ к объектам встраиваемых структур, превратить их во что-то вроде namespace. А доступ к его полям и методам сделать с явным указанием, что объекта не существует, он встроен:
Object testObject;
testObject.id; // Можно
testObject.list; // Нельзя, такого объекта нет
testObject.list::size; // Можно.
Взять адрес list него нельзя, передать по ссылке тоже нельзя и т.д., а его поля приобрели имена list::size и list::data. Таким образом проблема будет решена.
А в подобных случаях: std::vector<Container> или std::vector<Container*> доступ оставить, т.к. объект Container не встроен и действительно существует сам по себе.
Дмитрий
alexey.i.salmin
Эта проблема известна под названием "overlaying tail padding". Itanium ABI изначально не оговаривал этот вопрос явно, что привело к разным реализациям: g++ упаковывал структуры, а icc нет. Вот тред про g++: gcc.gnu.org/ml/gcc/2002-08/msg00874.html

Когда это обнаружилось, вопрос вынесли на обсуждение рабочей группы ABI. Решение -- явно запретить переиспользование tail padding. itanium-cxx-abi.github.io/cxx-abi/cxx-closed.html#A31 . После этого в g++ привели реализацию в соответствие с ABI.

Так что, шансы того, что "компиляторы будут делать это автоматически" равны нулю.

Насчет нового ключевого слова -- идея интересная, но тут главный вопрос: чему равен sizeof(Container)? Если 6, то их нельзя класть в массив. Если 8, то нельзя будет делать memset(&container, 0, sizeof(container)) -- это не только компиляторы делают. Единственное решение, которое я вижу -- вообще не считать Container типом данных, а чем-то вроде нэймспейса, как предлагают ниже. Если хочешь использовать inline структуру -- обязательно должен обернуть ее в полноценный тип. В таком виде можно попробовать довести идею до ума, но удобство использования страдает.
alexey.i.salmin
alexey.i.salmin
Добавлю: ближайшая аналогия -- это bit fields. Поле в структуре есть, но адрес брать нельзя.
Если продолжить эту идею, то можно объявлять Container как обычно, а inline писать в точке использования, будет даже понятнее. Но "инлайнить" можно будет только POD структуры: адрес брать нельзя, т.е. this использовать нельзя, нетривиальный конструктор копирования использовать нельзя и т.д.
alexey.i.salmin
yndx-antoshkka
alexey.i.salmin, спасибо большое за ссылки!

По поводу ключевого слова - с такими ограничениями не хочется вводить новую конструкцию. Предлагаю подождать принятия метаклассов open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0707r0.pdf . С ними можно будет написать метакласс делающий эту оптимизацию (как-то вот так):

$class tail_opt { constexpr {
for (auto m : $this.classes())
for (auto m : $b.variables())
-> { m; }
}};
yndx-antoshkka
Дмитрий
alexey.i.salmin, sizeof(Container) менять нельзя, это нарушит выравнивание. Рассматривать нужно ситуацию встраивания, когда сам объект пропадает. std::vector<Container> к этой ситуации не относится.
yndx-antoshkka, тут без вариантов, автоматически не выйдет. И потом не всегда всё необходимо встраивать, иногда требуется чтобы объект сохранился, для передачи его куда-то... Многие моменты в метаклассах меня смущают, но я согласен, это вполне решение.
Дмитрий
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).