Реализуем эффективный тупль с помощью C++26

Свет видел много любительских реализаций std::tuple, и реализация своих велосипедов — наверное, действительно действенный способ обучения: вряд-ли можно сказать, что ты что-то по-настоящему понимаешь, если не можешь объяснить, как это что-то устроено.

Многие пытливые умы на протяжении десятилетий задавались вопросом: как же реализован std::tuple, как мне реализовать свой тупль (кортеж)? [1]

И немало было дано на эти вопросы ответов и написано статей ([2]). Однако я берусь утверждать, что все они имеют один критический недостаток! Конкретнее, они все рассматривают в основном лишь один (и при этом неэффективный) способ реализации: с помощью множественного наследования или рекурсивного инстанцирования, имеющий в свой очередь множество своих недостатков, главный из которых — неэффективное использование памяти.

В то время как современный C++ позволяет реализовать тупль гораздо проще (без обилия шаблоноты) и эффективнее.

Design notes

Краеугольный камень этой идеи эффективной реализации — простой массив байт (далее — хранилище), размер которого будет достаточен для хранения всех членов тупля. Конечно, он налагает на нас требование подумать о выравнивании: члены имеют разные типы, имеющие разные требования к выравниванию, и мы должны будем учесть это при размещении их в хранилище.

Но как именно нам нужно размещать члены, чтобы получить максимальную эффективность по занимаемой памяти?

Предположим, имеем тип 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 байт:

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), это будет выглядеть так:

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](),
      ...
    );
  }

Теперь мы великолепны! Наш самодельный тупль

1. Превосходит 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);
}

2. Чертовски быстр. Благодаря использованию constexpr и consteval большинство написанных нами строчек даже не появятся в бинарнике, так как будут исполнены в компайл-тайме.

Теперь вы знаете, как легко и эффективно реализовать тупль на собеседовании!

Опубликовано при поддержке C++ Moscow