c++ - 批量分配库

Question

所以我目前正在重构一个巨大的函数:

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);

仍然有一些重复，但参数只输入一次。还有很多手工簿记。如果我能用较小的工厂 build 这个工厂就好了......

然后我的 haskell 大脑击中了我。我正在实现一个 应用仿函数 .这完全可以更好!

我需要做的就是编写一些工具来自动求和大小并并排运行构建函数:

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):

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 中的内存。总是一起分配/解除分配并为我批量分配。

如果没有，是否有这个想法(或其变体)的预先存在的实现，用于使用应用仿函数批量分配？

Answer 1

首先，我想就您的解决方案中的问题提供反馈:

你忽略对齐。依赖假设int和 float在您的系统上共享相同的对齐方式，您的特定用例可能“很好”。但是尝试添加一些 double进入混合，就会有 UB。由于未对齐的访问，您可能会发现您的程序在 ARM 芯片上崩溃。

new (buf) T[length]{};不幸的是bad and non-portable .简而言之:标准允许编译器保留初始 y给定存储的字节供内部使用。您的程序无法分配此 y系统上的字节数 y > 0 (是的，这些系统显然存在；据称 VC++ 就是这样做的)。
必须分配给 y很糟糕，但是让 array-placement-new 无法使用的原因是无法找出有多大 y直到实际调用新放置为止。在这种情况下真的没有办法使用它。

您已经意识到这一点，但为了完整起见:您不会破坏子缓冲区，因此如果您曾经使用过非平凡可破坏类型，那么将会有 UB。

解决方案:

分配额外 alignof(T) - 1每个缓冲区的字节数。将每个缓冲区的开头与 std::align 对齐.

您需要循环并使用新的非数组放置。从技术上讲，进行非数组放置 new 意味着在这些对象上使用指针算法具有 UB，但标准在这方面很愚蠢，我选择忽略它。 Here's关于这一点的语言律师讨论。据我了解，p0593r2提案包括对此技术性的解决方案。

添加与placement-new 调用相对应的析构函数调用(或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);
    }
};

A 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成员(member)const这可以说是很好，但我发现它涉及的样板文件比我喜欢的要多。

编译器会警告有 throw在声明为 noexcept 的函数中当构造函数不能抛出时。 g++ 和 clang++ 都不够聪明，无法理解当函数为 noexcept 时抛出永远不会发生。 .我想这可以通过使用部分特化来解决，或者我可以添加(非标准)指令来禁用警告。

buffer_clump_storage可以复制和分配。这涉及加载更多代码，我不希望需要它们。移动构造函数也可能是多余的，但至少它实现起来高效且简洁。