Свет видел много любительских реализаций std::tuple
, и реализация своих велосипедов — наверное, действительно действенный способ обучения: вряд-ли можно сказать, что ты что-то по-настоящему понимаешь, если не можешь объяснить, как это что-то устроено.
Многие пытливые умы на протяжении десятилетий задавались вопросом: как же реализован std::tuple
, как мне реализовать свой тупль (кортеж)? [1]
И немало было дано на эти вопросы ответов и написано статей ([2]). Однако я берусь утверждать, что все они имеют один критический недостаток! Конкретнее, они все рассматривают в основном лишь один (и при этом неэффективный) способ реализации: с помощью множественного наследования или рекурсивного инстанцирования, имеющий в свой очередь множество своих недостатков, главный из которых — неэффективное использование памяти.
В то время как современный C++ позволяет реализовать тупль гораздо проще (без обилия шаблоноты) и эффективнее.
Design notes
Краеугольный камень этой идеи эффективной реализации — простой массив байт (далее — хранилище), размер которого будет достаточен для хранения всех членов тупля. Конечно, он налагает на нас требование подумать о выравнивании: члены имеют разные типы, имеющие разные требования к выравниванию, и мы должны будем учесть это при размещении их в хранилище.
Но как именно нам нужно размещать члены, чтобы получить максимальную эффективность по занимаемой памяти?
Предположим, имеем тип tuple<char, double, int>
— наивный вариант его размещения в памяти (см. рисунок и листинг ниже), в котором мы просто располагаем члены (с учетом выравнивания) один за другим в их исходном порядке, нам явно не подходит.
![Рисунок 1 — Наивный вариант размещения tuple<char, double, int> в памяти Рисунок 1 — Наивный вариант размещения tuple<char, double, int> в памяти](https://habrastorage.org/getpro/habr/upload_files/686/f6b/025/686f6b0258eb97563e276c417c007e42.png)
Листинг 1 — Наивный вариант размещения tuple<char, double, int> в памяти (если вам неудобно смотреть рисунки)
struct tuple /* size: 24, align: 8 */
{
char a; /* offset: 0, size: 1
char __padding[7]; size: 7 */
double b; /* offset: 8, size: 8 */
int c; /* offset: 16, size: 4
char __padding[4]; size: 4 */
};
Он требует 24 байт памяти в то время как эти же члены можно разместить гораздо более эффективно. Так, следующий вариант оптимален и требует всего 16 байт:
![Рисунок 2 — Один из оптимальных вариантов размещения tuple<char, double, int> в памяти Рисунок 2 — Один из оптимальных вариантов размещения tuple<char, double, int> в памяти](https://habrastorage.org/getpro/habr/upload_files/43c/bce/0b4/43cbce0b4b4360877a815036bd712f5f.png)
Листинг 2 — Один из оптимальных вариантов размещения tuple<char, double, int> в памяти
struct tuple /* size: 16, align: 8 */
{
double b; /* offset: 0, size: 8 */
char a; /* offset: 8, size: 1
char __padding[3]; size: 3 */
int c; /* offset: 12, size: 4 */
};
Но как нам для любого сочетания типов найти оптимальный вариант их размещения в памяти? Для этого существует алгоритм: достаточно просто отсортировать типы по их требованиям к выравниванию в убывающем порядке. В нашем случае, так как alignof(double) > alignof(int) > alignof(char)
, это будет выглядеть так:
![Рисунок 3 — Оптимальный вариант размещения tuple<char, double, int> в памяти Рисунок 3 — Оптимальный вариант размещения tuple<char, double, int> в памяти](https://habrastorage.org/getpro/habr/upload_files/4c0/a9b/9fe/4c0a9b9fe28587e17ef3347304c35dea.png)
Листинг 3 — Оптимальный вариант размещения tuple<char, double, int> в памяти
struct tuple /* size: 16, align: 8 */
{
double b; /* offset: 0, size: 8 */
int c; /* offset: 8, size: 4 */
char a; /* offset: 12, size: 1
char __padding[3]; size: 3 */
};
Мы получили те же 16 байт — это минимальный размер, который может иметь наш тупль с учетом требований к выраниванию.
С учетом высказанных соображений мы уже можем реализовать наш тупль на псевдокоде:
template <typename... T>
struct tuple {
constexpr tuple(T&&... args) {
/* Инициализируем хранилище */
1) Отсортировать типы T по их требованиям к выравниванию
2) Для каждого T:
2.1) Разместить его на требуемом месте в массиве
2.2) Инициализировать его соответствующим значением args
}
template <std::size_t I>
constexpr auto& get() noexcept {
1) Отсортировать типы T по их требованиям к выравниванию,
сохраняя информацию об их исходном индексе (относительно T...)
IOriginal
3) Получить тип TOriginal, имевший исходный индекс IOriginal
2) Получить информацию о смещении (=offset) внутри storage для
TOriginal
return *std::launder(reinterpret_cast<TOriginal*>(storage + offset))
}
private:
alignas(T...) std::byte storage[(sizeof(T) + ...)];
};
Звучит как что-то, требующее сложной шаблонной магии: «отсортировать типы» звучит страшно (даже с учетом того, что на самом деле для наших целей мы можем свести это к сортировке обычных объектов). И это действительно требует сложной шаблонной магии, если мы говорим о C++11, C++14 и даже о C++17.
Но с тех пор как значительно расширились возможности constexpr
, так и в языке появились такие приятные фичи как pack indexing (cppreference). Так что на деле всё будет выглядеть довольно просто и понятно. Приступим же к настоящей реализации.
Implementation
В качестве основы возьмем наш предыдущий листинг (из которого, конечно, уберем весь псевдокод) (godbolt):
#include <cstddef>
template <typename... T>
struct tuple {
constexpr tuple(T&&... args) { }
template <std::size_t I>
constexpr auto& get() noexcept { }
private:
alignas(T...) std::byte storage[(sizeof(T) + ...)];
};
// Corner case: пустой tuple
// Проще всего реализовать его как специализацию
template <>
struct tuple<> { };
Первое, что нам потребуется, чтобы реализовать конструктор — вспомогательный тип MemberInfo
, который мы будем использовать для хранения информации о каждом T
(каждом члене нашего тупля): его оригинальный индекс в T...
, выравнивание, размер и смещение относительно &storage[0]
(другим языком — то, где этот член в storage
будет расположен).
И вместе с этим же реализуем метод get_members_info
, заполняющий в компайл-тайме MemberInfo
для каждого T
(godbolt):
// ...
#include <utility>
#include <array>
#include <algorithm>
template <typename... T>
struct tuple {
// ...
private:
struct MemberInfo {
std::size_t original_idx;
std::size_t align;
std::size_t sizeof_;
std::size_t offset;
};
template <std::size_t... I>
consteval static auto get_members_info(std::index_sequence<I...> idx) {
// Для каждого T сохраняем его исходный индекс относительно T...,
// alignof и sizeof
std::array<MemberInfo, sizeof...(T)> res = {
MemberInfo { I, alignof(T), sizeof(T), 0 }...
};
// Сортируем полученный массив по требуемым выравниваниям, чтобы
// получить оптимальное размещение
std::sort(res.begin(), res.end(), [](const auto& lhs, const auto& rhs) {
return lhs.align > rhs.align;
});
// Считаем смещение относительно &storage[0] для каждого из членов
for (std::size_t idx = 1, size = res.size(); idx != size; ++idx) {
res[idx].offset = res[idx - 1].offset + res[idx - 1].sizeof_;
}
return res;
}
consteval static auto get_members_info() {
return get_members_info(std::make_index_sequence<sizeof...(T)>());
}
// ...
};
// ...
Теперь несложно реализовать и сам конструктор (godbolt):
// ...
#include <new>
template <typename... T>
struct tuple {
constexpr tuple(T&&... args) {
initialize_storage(std::make_index_sequence<sizeof...(T)>(), std::forward<T>(args)...);
}
// ...
private:
// ...
template <std::size_t... I>
constexpr auto initialize_storage(std::index_sequence<I...> idx, T&&... args) {
// Получаем всю необходимую нам информацию о членах
constexpr static auto info = get_members_info();
// Размещаем каждый член с помощью placement new в storage
// Обратите внимание: мы не можем написать T...[I] или args...[I],
// так как мы отсортировали члены по их выравниваниям
/// и на I-ой позиции в info может оказаться совсем другой член.
// Именно поэтому мы сохраняем в info original_idx
(
new (storage + info[I].offset)
T...[info[I].original_idx](
std::forward<T...[info[I].original_idx]>(
args...[info[I].original_idx]
)
),
...
);
}
// ...
};
// ...
И этот код мы уже можем начать покрывать тестами: в частности, удостоверимся, что наш тупль действительно оптимален по занимаемой памяти (сравнивая его размер с размером аналогичного std::tuple
) (godbolt):
#include <tuple>
#include <cassert>
#include <string>
// ...
int main() {
// Все эти assertы выполняются без ошибок
tuple<int, double> x1(1, 2.0);
assert(sizeof(x1) == sizeof(std::tuple<int, double>{}));
tuple<double, int> x2(2.0, 1);
assert(sizeof(x2) == sizeof(std::tuple<double, int>{}));
tuple<double, char, int, std::string> x3(2.0, 'A', 1, "ABC");
assert(sizeof(x3) == sizeof(std::tuple<double, char, int, std::string>));
}
Осталось реализовать лишь метод get<I>()
(вместе с тестами для него) (godbolt):
// ...
template <typename... T>
struct tuple {
// ...
template <std::size_t I>
constexpr auto& get() noexcept {
constexpr static auto info = get_members_info();
// Нас интересует один конкретный член: с original_idx == I
// В частности, нас интересует только его offset — он нам нужен для
// того, чтобы найти этот член в storage
constexpr auto it = std::find_if(info.begin(), info.end(), [](const auto& element) {
return element.original_idx == I;
});
if constexpr (it == info.end()) {
// Если его не оказалось — пользователь указал некорректный индекс
// Выводим красивое сообщение об ошибке
static_assert(false, "get<I>() access out of bounds");
} else {
// Иначе, пользуясь сохраненным offset, находим этот член в storage и
// возвращаем его
constexpr auto type = *it;
return *std::launder(reinterpret_cast<T...[I]*>(storage + type.offset));
}
}
// ...
};
// ...
int main() {
// Все эти assertы выполняются без ошибок
tuple<int, double> x1(1, 2.0);
assert(x1.get<0>() == 1 && x1.get<1>() == 2.0);
// ...
tuple<double, int> x2(2.0, 1);
assert(x2.get<0>() == 2.0 && x2.get<1>() == 1);
// ...
tuple<double, char, int, std::string> x3(2.0, 'A', 1, "ABC");
assert(x3.get<0>() == 2.0 && x3.get<1>() == 'A' && x3.get<2>() == 1 && x3.get<3>() == "ABC");
// x3.get<4>();
// ^ Код выше при раскомментировании упадет с красивым сообщением
// ...
}
И, конечно же, так как мы размещали объекты в памяти вручную (с помощью placement new), нам вручную же надо в деструкторе ~tuple
вызвать деструкторы для всех размещенных объектов. По аналогии с initialize_storage
, это можно реализовать следующим образом (godbolt):
// ...
template <typename... T>
struct tuple {
// ...
constexpr ~tuple() {
deinitialize_storage(std::make_index_sequence<sizeof...(T)>());
}
private:
// ...
template <std::size_t... I>
constexpr auto deinitialize_storage(std::index_sequence<I...> idx) {
// Получаем всю необходимую нам информацию о членах
constexpr static auto info = get_members_info();
// Вызываем деструктор каждого из членов, стараясь при этом
// не запутаться в индексах
(
std::launder(
reinterpret_cast<T...[info[I].original_idx]*>(
storage + info[I].offset
)
)->~T...[info[I].original_idx](),
...
);
}
Теперь мы великолепны! Наш самодельный тупль
Превосходит
std::tuple
по эффективности использования памяти. Взгляните сами на результаты тестов, приведенных ниже (godbolt).
// ...
int main() {
// ...
// Наш самодельный tuple blazing fast и уделывает
// стандартный тупль в некоторых кейсах, так как std::tuple
// не оптимизирует размещение членов в памяти
assert(sizeof(tuple<char, double, int>) == 16);
assert(sizeof(std::tuple<char, double, int>) == 24);
}
Чертовски быстр. Благодаря использованию
constexpr
иconsteval
большинство написанных нами строчек даже не появятся в бинарнике, так как будут исполнены в компайл-тайме.
Теперь вы знаете, как легко и эффективно реализовать тупль на собеседовании!
Опубликовано при поддержке C++ Moscow
Комментарии (29)
aol-nnov
11.08.2024 12:05+26тупль
кортеж же, ну!... :(
dyadyaSerezha
11.08.2024 12:05+3Не, тупль - это прекрасно! Я долго смеялся)
rukhi7
11.08.2024 12:05+3Только на звание маленько не дотягивает.
Реализуем эффективный тупль с помощью C++26
Надо было
Эффективно туплим с помощью C++26
tzlom
11.08.2024 12:05+3Идея интересная, но ваш кортеж (не тупль, пожалуйста) не constexpr
Прикольно было бы реализовать обёртку поверх стандартного кортежа, которая бы пересортировывала элементы, тогда она была бы и эффективной по памяти, и constexpr
Совсем прикольно было бы сделать это всё на С++11 (но не уверен что это возможно) :)
thuzz
11.08.2024 12:05Я, может быть, ретроград, но называть C++26 современным, по-моему, немного смело.
Шаг 1: Давайте придумаем и запустим в С++ фичу, чтобы было полегче реализовывать туплы!!!Шаг 2: Смотрите, как легко можно реализовывать туплы на современном C++, а вы и не знали!
(тем временем публика: "Горшочек, не вари...")
tzlom
11.08.2024 12:05+1Но если 26 это не современная версия, то какая же тогда современная?
thuzz
11.08.2024 12:05+2Кому как, мне, например (это очень субъективно) - взять стандарт с годом не больше текущего и вернуться ещё на один. В данном случае - с++20, хотя я стараюсь придерживаться 17.
Но уж во всяком случае не стандарт из будущего.
segment
11.08.2024 12:05Подскажите, а такое вообще используется в production коде? Это выглядит замысловато, чтобы разобраться в ней нужно неплохо так шарить в соответствующем стандарте. Реализация подобного, мне кажется, будет занимать приличное время. Тот, кто с этим кодом работает должен еще понять как эта штука работает и какие побочные эффекты существуют, разве нет?
rukhi7
11.08.2024 12:05+1насколько, например, я это понимаю, тупли это фактически анонимные структуры (или классы зависит от контекста и от компилятора). То что эта структура анонимная напрочь убивает возможность повторного использования логики которая привязана к некоторому конкретному типу этой тупли! То есть вы будете писать логику обработки определенного набора переменных снова и снова, потому что даже если вы сможете идентифицировать уже существующюю подобную логику, набор переменных вы должны формировать самостоятельно. Фактически это такой способ одновременно скрывать и размножать копи-паст в коде.
RichardMerlock
11.08.2024 12:05+1Это же целое сражение с ветряными мельницами! Зачем разрабатывать сортировку членов, если можно сразу нормально объявить на стадии написания кода?
artptr86
11.08.2024 12:05И более того, потом никому не придётся обалдевать с отладчиком, пытаясь разобраться в дампах памяти.
boldape
11.08.2024 12:05+5Так вы не сможете на стадии написания кода. Почему? Да просто замените дабл инт и чар на хз1, хз2 и хз3 и не забудьте о том, что в разных ревизиях их размеры тоже могут быть разными.
Там выше кто то на отладку жалуется, но целый Раст так делает из коробки вообще во всех структурах по умолчанию и всем норм, а на с++ значит не норм?
Kelbon
11.08.2024 12:05а на с++ значит не норм?
не норм, это кривое поведение раста
boldape
11.08.2024 12:05+2Это отличное поведение раста по умолчанию, когда надо с внешним миром взаимодействовать то там через атрибуты можно четко зафиксировать бинарный формат, а внутри всем больше нравится экономить память, а дебагер как то справляется с этим из коробки.
eao197
11.08.2024 12:05+2А точно ли здесь нужно использование
std::launder
?
Вроде бы объект типа T инстанциируется корректно, затем его тип не меняется, а кастинг изstd::byte*
вT*
полностью легален.ahabreader
11.08.2024 12:05+3P3006R1 говорит, что UB в такой конструкции сейчас есть:
alignas(T) std::byte storage[sizeof(T)]; ::new (&storage) T(); // ... T *ptr_ = reinterpret_cast<T*>(&storage); // UB
Он ссылается на понятие pointer-interconvertible (появилось в P0137R1). На всё это ведут комменты на stackoverflow.
Если шутят, что программирование на Rust - это борьба с компилятором, то надо шутить, что программирование на C++ - это борьба с оптимизатором (который в рамках стандарта может действовать по принципу "вижу UB - не вижу препятствий").
eao197
11.08.2024 12:05+2Да, есть такое дело.
Но ведь в C++23 завозятstd::start_lifetime_as
и, поскольку в статье речь идет о C++26, может бытьstd::start_lifetime_as
уместнее, чемstd::launder
?PS. На самом деле я сам не знаю, что правильно. До C++23 вроде как
std::launder
необходим хотя бы для очистки совести. На вот начиная с C++23...hiewpoint
11.08.2024 12:05std::start_lifetime_as нужен для создания объекта с состоянием уже хранящимся в байтах, где он будет размещен. А std::launder это отмывка указателя на ранее созданный объект, для которого в этом месте кода компилятором потеряна информация о типе хранящегося в этих байтах объекта. Разные же смыслы. У вас как раз launder нужен после того, как вы создали объекты через placement new, но типизированные указатели на них нигде не сохранили.
eao197
11.08.2024 12:05std::start_lifetime_as нужен для создания объекта с состоянием уже хранящимся в байтах, где он будет размещен.
Насколько я знаю,
start_lifetime_as
не создает объект, а говорит компилятору о том, что появился новый объект о котором компилятор ранее не знал (т.е. он не был создан через new, как локальная переменная на стеке или каким-то другим известным компилятором способом). Т.е. программист говорит компилятору: вот в этой области памяти сейчас есть объект, пожалуйста, поверь, что это так.В этой связи мне не понятно, чем область памяти, заполненная, например, чтением байт из файла или из пайпа, принципиально отличается от области памяти, в которой объект был ранее сконструирован через placement new.
У вас как раз launder нужен после того, как вы создали объекты через placement new, но типизированные указатели на них нигде не сохранили.
Я понимаю роль launder вот в таком сценарии: https://wandbox.org/permlink/wh0QVJSGhu41P0LH
И, насколько помню, именно для этого launder и создавался.Но вот другой сценарий: https://wandbox.org/permlink/wTISrxXoKMlw0PUv
(к сожалению, не удалось протестировать сstart_lifetime_as
, похоже, эту фичу пока еще в компилятор не завезли).Здесь
make_and_use_object
для конструирования объекта вызывает разные функторы. И вот после возврата из функтора что должно применяться --launder
илиstart_lifetime_as
? Ведь каждый из функторов заполняет переданный буфер по-разному?И для
launder
здесь, вроде как, места нет, т.к. не было ранее объектов Data, на которые у меня могли бы быть указатели, и эти объекты бы пересоздавались.В общем, я к тому, что после введения в язык
start_lifetime_as
стало не очень понятно в каком случае требуетсяlaunder
, а в какомstart_lifetime_as
.
Kelbon
11.08.2024 12:05+3Уж не этого я ожидал от эффективного тупла на С++26...
alignas(T...) std::byte storage[(sizeof(T) + ...)];
если у вас tuple<int32_t, char>, то размер будет 5, это неправильно (он должен быть 8)
Плюс ручная реализация конструктора, деструктора и операторов гораздо хуже чем встроенная от компилятора (по многим причинам), мув конструктора и копирования вообще не видно (по дефолту сгенерированный это уб)
И да, пользователю важно в каком порядке он передал типы, так что лучше их местами не менять. Можно отдельно сделать сортировку типов по размеру и алигменту, чтобы передать в их простой тупл, который не меняет ничего местамиqw1
11.08.2024 12:05то размер будет 5, это неправильно (он должен быть 8)
Хорошее замечанение. Если это так, то серьёзная ошибка. Я проверил на godbolt, размер 8.
Видимо, когда компилятор видитalignas
перед массивом, он корректирует егоsizeof
до этого выравнивания.
Panzerschrek
11.08.2024 12:05Сортировать члены кортеже - так себе идея. Кому надо, тот изначально отсортирует, а остальным же такая сортировка может создать неожиданности в отладке.
qw1
11.08.2024 12:05+1Статью можно рассматривать как упражнение в метапрограммировании.
В случае, когда надо сохранить порядок полей, можно вернуться к std::tuple.
Пример, когда порядок полей важен, это синтаксис инициализации. Например, определённый порядок полей "красиво" вписывается в логику предметной области, а поменять его ради оптимального хранения в памяти - каждый раз глаз будет спотыкаться.
qw1
Троеточие в арифметическом выражении выглядит как псевдокод. Но ведь компилируется!