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

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

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

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

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

Design notes

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

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

Предположим, имеем тип tuple — наивный вариант его размещения в памяти (см. рисунок и листинг ниже), в котором мы просто располагаем члены (с учетом выравнивания) один за другим в их исходном порядке, нам явно не подходит.

Рисунок 1 — Наивный вариант размещения tuple<char, double, int> в памяти» /></p>

<p>Рисунок 1 — Наивный вариант размещения tuple<char, double, int> в памяти</p><p>Листинг 1 — Наивный вариант размещения tuple<char, double, int> в памяти (если вам неудобно смотреть рисунки)</p>

<div><pre><code class=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> в памяти» /></p>

<p>Рисунок 2 — Один из оптимальных вариантов размещения tuple<char, double, int> в памяти</p><p>Листинг 2 — Один из оптимальных вариантов размещения tuple<char, double, int> в памяти</p>

<div><pre><code class=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> в памяти» /></p>

<p>Рисунок 3 — Оптимальный вариант размещения tuple<char, double, int> в памяти</p><p>Листинг 3 — Оптимальный вариант размещения tuple<char, double, int> в памяти</p>

<div><pre><code class=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 
struct tuple {
    constexpr tuple(T&&... args) {
      /* Инициализируем хранилище */
      1) Отсортировать типы T по их требованиям к выравниванию
      2) Для каждого T:
        2.1) Разместить его на требуемом месте в массиве
        2.2) Инициализировать его соответствующим значением args
    }

    template 
    constexpr auto& get() {
      1) Отсортировать типы T по их требованиям к выравниванию,
         сохраняя информацию об их исходном индексе (относительно T...)
         IOriginal
      3) Получить тип TOriginal, имевший исходный индекс IOriginal
      2) Получить информацию о смещении (=offset) внутри storage для
         TOriginal
      return *std::launder(reinterpret_cast(storage + offset))
    }
private:
    alignas(T...) std::byte storage[(sizeof(T) + ...)];
};

Звучит как что-то, требующее сложной шаблонной магии: «отсортировать типы» звучит страшно (даже с учетом того, что на самом деле для наших целей мы можем свести это к сортировке обычных объектов). И это действительно требует сложной шаблонной магии, если мы говорим о C++11, C++14 и даже о C++17.

Но с тех пор как значительно расширились возможности constexpr, так и в языке появились такие приятные фичи как pack indexing (cppreference). Так что на деле всё будет выглядеть довольно просто и понятно. Приступим же к настоящей реализации.

Implementation

В качестве основы возьмем наш предыдущий листинг (из которого, конечно, уберем весь псевдокод) (godbolt):

#include 

template 
struct tuple {
  constexpr tuple(T&&... args) { }
  
  template 
  constexpr auto& get() { }
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 
#include 
#include 

template 
struct tuple {
  // ...
private:
  struct MemberInfo {
    std::size_t original_idx;
    std::size_t align;
    std::size_t sizeof_;
    std::size_t offset;
  };

  template 
  consteval static auto get_members_info(std::index_sequence idx) {
    // Для каждого T сохраняем его исходный индекс относительно T...,
    // alignof и sizeof
    std::array 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());
  }
  // ...
};

// ...

Теперь несложно реализовать и сам конструктор (godbolt):

// ...

#include 

template 
struct tuple {
  constexpr tuple(T&&... args) {
    initialize_storage(std::make_index_sequence(), std::forward(args)...);
  }
  // ...
private:
  // ...
  template 
  constexpr auto initialize_storage(std::index_sequence 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](args...[info[I].original_idx]),
      ...
    );
  }
  // ...
};

// ...

И этот код мы уже можем начать покрывать тестами: в частности, удостоверимся, что наш тупль действительно оптимален по занимаемой памяти (сравнивая его размер с размером аналогичного std::tuple) (godbolt):

#include 
#include 
#include 

// ...

int main() {
  // Все эти assertы выполняются без ошибок
  tuple x1(1, 2.0);
  assert(sizeof(x1) == sizeof(std::tuple{}));
  
  tuple x2(2.0, 1);
  assert(sizeof(x2) == sizeof(std::tuple{}));
  
  tuple x3(2.0, 'A', 1, "ABC");
  assert(sizeof(x3) == sizeof(std::tuple));
}

Осталось реализовать лишь метод get() (вместе с тестами для него) (godbolt):

// ...

template 
struct tuple {
  // ...
  template 
  constexpr auto& get() {
    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() access out of bounds");
    } else {
      // Иначе, пользуясь сохраненным offset, находим этот член в storage и
      // возвращаем его
      constexpr auto type = *it;
      return *std::launder(reinterpret_cast(storage + type.offset));
    }
  }
  // ...
};

// ...

int main() {
  // Все эти assertы выполняются без ошибок
  tuple x1(1, 2.0);
  assert(x1.get<0>() == 1 && x1.get<1>() == 2.0);
  // ...

  tuple x2(2.0, 1);
  assert(x2.get<0>() == 2.0 && x2.get<1>() == 1);
  // ...
  
  tuple 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>();
  // ^ Код выше при раскомментировании упадет с красивым сообщением
  // ...
}

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

  1. Превосходит std::tuple по эффективности использования памяти. Взгляните сами на результаты тестов, приведенных ниже (godbolt).

// ...

int main() {
  // ...

  // Наш самодельный tuple blazing fast и уделывает
  // стандартный тупль в некоторых кейсах, так как std::tuple
  // не оптимизирует размещение членов в памяти
  assert(sizeof(tuple) == 16);
  assert(sizeof(std::tuple) == 24);
}
  1. Чертовски быстр. Благодаря использованию constexpr и consteval большинство написанных нами строчек даже не появятся в бинарнике, так как будут исполнены в компайл-тайме.

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

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

© Habrahabr.ru