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

Мы получили те же 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>();
  // ^ Код выше при раскомментировании упадет с красивым сообщением
  // ...
}

// ...

int main() {
  // ...

  // Наш самодельный tuple blazing fast и уделывает
  // стандартный тупль в некоторых кейсах, так как std::tuple
  // не оптимизирует размещение членов в памяти
  assert(sizeof(tuple) == 16);
  assert(sizeof(std::tuple) == 24);
}