Главная » C++ » Библиотека для пакетного размещения

Библиотека для пакетного размещения

В настоящее время я выполняю рефакторинг гигантской функции:

int giant_function(size_t n, size_t m, /*... other parameters */) {
int x[n]{};
float y[n]{};
int z[m]{};
/* ... more array definitions */

И когда я нахожу группу связанных определений с дискретной функциональностью, группирую их в определение класса:

class V0 {
std::unique_ptr<int[]> x;
std::unique_ptr<float[]> y;
std::unique_ptr<int[]> z;
public:
V0(size_t n, size_t m)
: x{new int[n]{}}
, y{new float[n]{}}
, z{new int[m]{}}
{}
// methods...
}

Реорганизованная версия неизбежно становится более читабельной, но одна вещь, которую я считаю менее удовлетворительной, — это увеличение количества выделений.

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

class V1 {
int* x;
float* y;
int* z;
public:
V1(size_t n, size_t m) {
char *buf = new char[n*sizeof(int)+n*sizeof(float)+m*sizeof(int)];
x = (int*) buf;
buf += n*sizeof(int);
y = (float*) buf;
buf += n*sizeof(float);
z = (int*) buf;
}
// methods...
~V0() { delete[] ((char *) x); }
}

Мало того, что этот подход включает в себя много ручного (читай: подверженного ошибкам) ​​бухгалтерии, но его большой грех в том, что он не поддается компоновке.

Если я хочу иметь V1 значение и W1 значение в стеке, то это
одно распределение каждого для их закулисных ресурсов. Еще проще, я бы хотел выделить V1 и ресурсы, на которые он указывает в одном распределении, и я не могу сделать это с этим подходом.

Первоначально это привело меня к двухпроходному подходу — один проход для расчета необходимого пространства, затем одно гигантское распределение, затем другой проход для выделения распределения и инициализации структур данных.

class V2 {
int* x;
float* y;
int* z;
public:
static size_t size(size_t n, size_t m) {
return sizeof(V2) + n*sizeof(int) + n*sizeof(float) + m*sizeof(int);
}
V2(size_t n, size_t m, char** buf) {
x = (int*) *buf;
*buf += n*sizeof(int);
y = (float*) *buf;
*buf += n*sizeof(float);
z = (int*) *buf;
*buf += m*sizeof(int);
}
}
// ...
size_t total = ... + V2::size(n,m) + ...
char* buf = new char[total];
// ...
void*  here = buf;
buf += sizeof(V2);
V2* v2 = new (here) V2{n, m, &buf};

Однако этот подход имел много повторений на расстоянии, что создает проблемы в долгосрочной перспективе. Вернувшись с завода избавился от этого:

class V3 {
int* const x;
float* const y;
int* const z;
V3(int* x, float* y, int* z) : x{x}, y{y}, z{z} {}
public:
class V3Factory {
size_t const n;
size_t const m;
public:
Factory(size_t n, size_t m) : n{n}, m{m};
size_t size() {
return sizeof(V3) + sizeof(int)*n + sizeof(float)*n + sizeof(int)*m;
}
V3* build(char** buf) {
void * here = *buf;
*buf += sizeof(V3);
x = (int*) *buf;
*buf += n*sizeof(int);
y = (float*) *buf;
*buf += n*sizeof(float);
z = (int*) *buf;
*buf += m*sizeof(int);
return new (here) V3{x,y,z};
}
}
}
// ...
V3::Factory v3factory{n,m};
// ...
size_t total = ... + v3factory.size() + ...
char* buf = new char[total];
// ..
V3* v3 = v3factory.build(&buf);

Все еще некоторое повторение, но параметры получают только один раз. И еще много ручной бухгалтерии. Было бы хорошо, если бы я мог построить этот завод из небольших заводов …

А потом мой мозг на хаскеле ударил меня. Я осуществлял Аппликативный Функтор. Это может быть лучше!

Все, что мне нужно было сделать, это написать некоторые инструменты для автоматического суммирования размеров и параллельного запуска функций сборки:

namespace plan {

template <typename A, typename B>
struct Apply {
A const a;
B const b;
Apply(A const a, B const b) : a{a}, b{b} {};

template<typename ... Args>
auto build(char* buf, Args ... args) const {
return a.build(buf, b.build(buf + a.size()), args...);
}

size_t size() const {
return a.size() + b.size();
}

Apply(Apply<A,B> const & plan) : a{plan.a}, b{plan.b} {}
Apply(Apply<A,B> const && plan) : a{plan.a}, b{plan.b} {}

template<typename U, typename ... Vs>
auto operator()(U const u, Vs const ... vs) const {
return Apply<decltype(*this),U>{*this,u}(vs...);
}

auto operator()() const {
return *this;
}
};
template<typename T>
struct Lift {
template<typename ... Args>
T* build(char* buf, Args ... args) const {
return new (buf) T{args...};
}
size_t size() const {
return sizeof(T);
}
Lift() {}
Lift(Lift<T> const &) {}
Lift(Lift<T> const &&) {}

template<typename U, typename ... Vs>
auto operator()(U const u, Vs const ... vs) const {
return Apply<decltype(*this),U>{*this,u}(vs...);
}

auto operator()() const {
return *this;
}
};

template<typename T>
struct Array {
size_t const length;
Array(size_t length) : length{length} {}
T* build(char* buf) const {
return new (buf) T[length]{};
}
size_t size() const {
return sizeof(T[length]);
}
};

template <typename P>
auto heap_allocate(P plan) {
return plan.build(new char[plan.size()]);
}

}

Теперь я могу изложить свой класс довольно просто:

class V4 {
int* const x;
float* const y;
int* const z;

public:
V4(int* x, float* y, int* z) : x{x}, y{y}, z{z} {}

static auto plan(size_t n, size_t m) {
return plan::Lift<V4>{}(
plan::Array<int>{n},
plan::Array<float>{n},
plan::Array<int>{m}
);
}
};

И использовать его за один проход:

V4* v4;
W4* w4;
std::tie{ ..., v4, w4, .... } = *plan::heap_allocate(
plan::Lift<std::tie>{}(
// ...
V4::plan(n,m),
W4::plan(m,p,2*m+1),
// ...
)
);

Он не идеален (помимо прочего, мне нужно добавить код для отслеживания деструкторов и heap_allocate вернуть std::unique_ptr это вызывает их всех), но прежде чем я пошел дальше по кроличьей норе, я подумал, что должен проверить уже существующее искусство.

Насколько я знаю, современные компиляторы могут быть достаточно умными, чтобы признать, что память в V0 всегда распределяется / освобождается вместе и пакетное распределение для меня.

Если нет, то существует ли ранее существовавшая реализация этой идеи (или ее разновидности) для пакетного размещения с аппликативным функтором?

3

Решение

Во-первых, я хотел бы предоставить отзыв о проблемах с вашими решениями:

  1. Вы игнорируете выравнивание. Опираясь на предположение, что int а также float используйте такое же выравнивание в вашей системе, ваш конкретный вариант использования может быть «хорошим». Но попробуйте добавить немного double в микс и будет UB. Вы можете обнаружить сбой вашей программы на чипах ARM из-за невыровненного доступа.

  2. new (buf) T[length]{}; к сожалению плохой и непереносимый. Короче говоря: Стандарт позволяет компилятору зарезервировать начальный y байты данного хранилища для внутреннего использования. Ваша программа не может выделить это y байт в системах, где y > 0 (и да, эти системы, очевидно, существуют; VC ++ делает это якобы).

    Необходимость выделить на y это плохо, но то, что делает размещение массива новым непригодным, является неспособность выяснить, насколько большой y пока размещение не называется новым Там действительно нет способа использовать его для этого случая.

  3. Вы уже знаете об этом, но для полноты: вы не разрушаете подбуферы, поэтому, если вы когда-либо будете использовать нетривиально разрушаемый тип, тогда будет UB.

Решения:

  1. Выделить дополнительно alignof(T) - 1 байты для каждого буфера. Совместите начало каждого буфера с std::align,

  2. Вы должны зациклить и использовать размещение без массива new. Технически, выполнение размещения без массива new означает, что использование арифметики с указателями на этих объектах имеет UB, но стандарт просто глуп в этом отношении, и я предпочитаю его игнорировать. Вот языковая адвокатская дискуссия об этом. Насколько я понимаю, p0593r2 Предложение включает в себя решение этой технической задачи.

  3. Добавьте вызовы деструктора, соответствующие новым вызовам размещения (или static_assert что должны использоваться только тривиально разрушаемые типы). Обратите внимание, что поддержка нетривиального уничтожения повышения необходимость исключительной безопасности. Если построение одного буфера вызывает исключение, то суббуферы, которые были сконструированы ранее, должны быть уничтожены. Такую же осторожность нужно соблюдать, когда конструктор бросает один элемент после того, как некоторые из них уже созданы.

Я не знаю предшествующего уровня техники, но как насчет последующего уровня техники? Я решил сделать удар по этому вопросу немного под другим углом. Имейте в виду, однако, что это не требует тестирования и может содержать ошибки.

buffer_clump шаблон для создания / уничтожения объектов во внешнем необработанном хранилище и вычисления выровненных границ каждого подпуфера:

#include <cstddef>
#include <memory>
#include <vector>
#include <tuple>
#include <cassert>
#include <type_traits>
#include <utility>

// recursion base
template <class... Args>
class buffer_clump {
protected:
constexpr std::size_t buffer_size() const noexcept { return 0; }
constexpr std::tuple<> buffers(char*) const noexcept { return {}; }
constexpr void construct(char*) const noexcept { }
constexpr void destroy(const char*) const noexcept {}
};

template<class Head, class... Tail>
class buffer_clump<Head, Tail...> : buffer_clump<Tail...> {
using tail = buffer_clump<Tail...>;
const std::size_t length;

constexpr std::size_t size() const noexcept
{
return sizeof(Head) * length + alignof(Head) - 1;
}

constexpr Head* align(char* buf) const noexcept
{
void* aligned = buf;
std::size_t space = size();
assert(std::align(
alignof(Head),
sizeof(Head) * length,
aligned,
space
));
return (Head*)aligned;
}

constexpr char* next(char* buf) const noexcept
{
return buf + size();
}

static constexpr void
destroy_head(Head* head_ptr, std::size_t last)
noexcept(std::is_nothrow_destructible<Head>::value)
{
if constexpr (!std::is_trivially_destructible<Head>::value)
while (last--)
head_ptr[last].~Head();
}

public:
template<class... Size_t>
constexpr buffer_clump(std::size_t length, Size_t... tail_lengths) noexcept
: tail(tail_lengths...), length(length) {}

constexpr std::size_t
buffer_size() const noexcept
{
return size() + tail::buffer_size();
}

constexpr auto
buffers(char* buf) const noexcept
{
return std::tuple_cat(
std::make_tuple(align(buf)),
tail::buffers(next(buf))
);
}

void
construct(char* buf) const
noexcept(std::is_nothrow_default_constructible<Head, Tail...>::value)
{
Head* aligned = align(buf);
std::size_t i;
try {
for (i = 0; i < length; i++)
new (&aligned[i]) Head;
tail::construct(next(buf));
} catch (...) {
destroy_head(aligned, i);
throw;
}
}

constexpr void
destroy(char* buf) const
noexcept(std::is_nothrow_destructible<Head, Tail...>::value)
{
tail::destroy(next(buf));
destroy_head(align(buf), length);
}
};

buffer_clump_storage шаблон, который использует buffer_clump создать подбуферы в контейнер RAII.

template <class... Args>
class buffer_clump_storage {
const buffer_clump<Args...> clump;
std::vector<char> storage;

public:
constexpr auto buffers() noexcept {
return clump.buffers(storage.data());
}

template<class... Size_t>
buffer_clump_storage(Size_t... lengths)
: clump(lengths...), storage(clump.buffer_size())
{
clump.construct(storage.data());
}

~buffer_clump_storage()
noexcept(noexcept(clump.destroy(nullptr)))
{
if (storage.size())
clump.destroy(storage.data());
}

buffer_clump_storage(buffer_clump_storage&& other) noexcept
: clump(other.clump), storage(std::move(other.storage))
{
other.storage.clear();
}
};

Наконец, класс, который может быть выделен как автоматическая переменная и предоставляет именованные указатели на подбуферы buffer_clump_storage:

class V5 {
// macro tricks or boost mpl magic could be used to avoid repetitive boilerplate
buffer_clump_storage<int, float, int> storage;

public:
int* x;
float* y;
int* z;
V5(std::size_t xs, std::size_t  ys, std::size_t zs)
: storage(xs, ys, zs)
{
std::tie(x, y, z) = storage.buffers();
}
};

И использование:

int giant_function(size_t n, size_t m, /*... other parameters */) {
V5 v(n, n, m);
for(std::size_t i = 0; i < n; i++)
v.x[i] = i;

В случае, если вам нужно только сгруппированное распределение и не столько возможность назвать группу, это прямое использование позволяет избежать практически всего:

int giant_function(size_t n, size_t m, /*... other parameters */) {
buffer_clump_storage<int, float, int> v(n, n, m);
auto [x, y, z] = v.buffers();

Критика моей собственной работы:

  • Я не стал делать V5 члены const что, возможно, было бы неплохо, но я обнаружил, что в нем больше шаблонов, чем я бы предпочел.
  • Компиляторы предупредят, что есть throw в функции, которая объявлена noexcept когда конструктор не может бросить. Ни g ++, ни clang ++ не были достаточно умны, чтобы понять, что бросок никогда не произойдет, когда функция noexcept, Я думаю, что это можно обойти, используя частичную специализацию, или я мог бы просто добавить (нестандартные) директивы, чтобы отключить предупреждение.
  • buffer_clump_storage могут быть сделаны копируемыми и назначаемыми. Это предполагает загрузку большего количества кода, и я не ожидал бы, что он понадобится. Конструктор перемещения также может быть лишним, но по крайней мере он эффективен и лаконичен в реализации.
1

Другие решения

Других решений пока нет …

Источник
Web-Answers © 2024 Наверх