6
\$\begingroup\$

I want to use an std::array, but am operating on sufficiently large arrays that stack allocation is not reasonable (and fails using default stack size). I also needed a function that performed much like std::transform, but always in-place. The issue is that many of these transformations change the "type". All of these types, in my usage, are simply the same templated type with different non-type template arguments associated with them. I don't want to have many arrays allocated to move data through the system because these type changes, only when a copy is strictly necessary.

To that end, I wrote a pretty crappy implementation of both by wrapping std::unique_ptr and std::array.

template <typename T, size_t SZ, typename Deleter = std::default_delete<T>>
class unique_heap_array {
private: // members
    std::unique_ptr<std::array<T, SZ>> p {nullptr};
public:  // pointer member types
    using deleter_type              = typename decltype(p)::deleter_type;
    using element_type              = typename decltype(p)::element_type;
    using element_pointer_type      = typename decltype(p)::pointer;
public:  // array member types
    using value_type                = typename element_type::value_type;
    using size_type                 = typename element_type::size_type;
    using difference_type           = typename element_type::difference_type;
    using reference                 = typename element_type::reference;
    using const_reference           = typename element_type::const_reference;
    using pointer                   = typename element_type::pointer;
    using const_pointer             = typename element_type::const_pointer;
    using iterator                  = typename element_type::iterator;
    using const_iterator            = typename element_type::const_iterator;
    using reverse_iterator          = typename element_type::reverse_iterator;
    using const_reverse_iterator    = typename element_type::const_reverse_iterator;
public:  // pointer member function
    auto get_deleter() const noexcept                   { return p.get_deleter(); }
    explicit operator bool() const noexcept             { return p; }
    auto borrow_ptr() const noexcept                    { return p.get(); }
    auto release_ptr() noexcept                         { return p.release(); }
    void reset_ptr(element_pointer_type ptr) noexcept   { p.reset(ptr); }
    void reset_ptr(std::nullptr_t ptr) noexcept         { p.reset(ptr); }
    void reset_ptr() noexcept                           { p.reset(new element_type); }
    void swap(unique_heap_array& other) noexcept        { p.swap(other.p); }
public:  // array members functions
    auto at(size_type i)                                { return p->at(i); }
    auto at(size_type i) const                          { return p->at(i); }
    auto operator[](size_type i)                        { return (*p)[i]; }
    auto operator[](size_type i) const                  { return (*p)[i]; }
    auto begin()                                        { return p->begin(); }
    auto begin() const                                  { return p->begin(); }
    auto cbegin() const                                 { return p->cbegin(); }
    auto end()                                          { return p->end(); }
    auto end() const                                    { return p->end(); }
    auto cend() const                                   { return p->cend(); }
    auto rbegin()                                       { return p->rbegin(); }
    auto rbegin() const                                 { return p->rbegin(); }
    auto crbegin() const                                { return p->crbegin(); }
    auto rend()                                         { return p->rend(); }
    auto rend() const                                   { return p->rend(); }
    auto crend() const                                  { return p->crend(); }
    auto data() const                                   { return p->data(); }
    constexpr bool empty() const noexcept               { return SZ == 0; }
    constexpr auto size() const noexcept                { return SZ; }
    constexpr auto max_size() const noexcept            { return SZ; }
    void fill(const T& value)                           { p->fill(value); }
public:  // constructors
    unique_heap_array()                                 { reset_ptr(); }
    unique_heap_array(std::nullptr_t)                   { }
    unique_heap_array(element_pointer_type ptr)         { reset_ptr(ptr); }
public:  // copy and move constructiona and assignment
    unique_heap_array(const unique_heap_array<T, SZ, Deleter>&)                             = delete;
    unique_heap_array(unique_heap_array<T, SZ, Deleter>&&)                                  = default;
    unique_heap_array<T, SZ, Deleter>& operator=(const unique_heap_array<T, SZ, Deleter>&)  = delete;
    unique_heap_array<T, SZ, Deleter>& operator=(unique_heap_array<T, SZ, Deleter>&&)       = default;
public:  // destructor
    ~unique_heap_array() = default;
public:  // inplace data and type transformation
    template <typename O, typename OutTypeDeleter = std::default_delete<O>, typename F>
    auto transform(F&& func)
    {
        static_assert((sizeof(O) == sizeof(T)) &&
                      (alignof(O) <= alignof(T)),
                      "input and output types are not compatible");
        auto res = unique_heap_array<O, SZ, OutTypeDeleter>(reinterpret_cast<std::array<O, SZ>*>(borrow_ptr()));
        std::transform(begin(), end(), res.begin(), func);
        release_ptr();
        return res;
    }
    template <typename O, typename OutTypeDeleter = std::default_delete<O>, typename F, typename T2, typename Deleter2>
    auto transform(F&& func, const unique_heap_array<T2, SZ, Deleter2>& other)
    {
        static_assert((sizeof(O) == sizeof(T)) &&
                      (alignof(O) <= alignof(T)),
                      "input and output types are not compatible");
        auto res = unique_heap_array<O, SZ, OutTypeDeleter>(reinterpret_cast<std::array<O, SZ>*>(borrow_ptr()));
        std::transform(begin(), end(), other.begin(), res.begin(), func);
        release_ptr();
        return res;
    }
};

template <typename T, size_t SZ, typename Deleter>
bool operator==(const unique_heap_array<T, SZ, Deleter>& a, const unique_heap_array<T, SZ, Deleter>& b)
{
    return *a.borrow_ptr() == *b.borrow_ptr();
}

template <typename T, size_t SZ, typename Deleter>
bool operator!=(const unique_heap_array<T, SZ, Deleter>& a, const unique_heap_array<T, SZ, Deleter>& b)
{
    return *a.borrow_ptr() != *b.borrow_ptr();
}

template <typename T, size_t SZ, typename Deleter>
bool operator<(const unique_heap_array<T, SZ, Deleter>& a, const unique_heap_array<T, SZ, Deleter>& b)
{
    return *a.borrow_ptr() < *b.borrow_ptr();
}

template <typename T, size_t SZ, typename Deleter>
bool operator<=(const unique_heap_array<T, SZ, Deleter>& a, const unique_heap_array<T, SZ, Deleter>& b)
{
    return *a.borrow_ptr() <= *b.borrow_ptr();
}

template <typename T, size_t SZ, typename Deleter>
bool operator>(const unique_heap_array<T, SZ, Deleter>& a, const unique_heap_array<T, SZ, Deleter>& b)
{
    return *a.borrow_ptr() > *b.borrow_ptr();
}

template <typename T, size_t SZ, typename Deleter>
bool operator>=(const unique_heap_array<T, SZ, Deleter>& a, const unique_heap_array<T, SZ, Deleter>& b)
{
    return *a.borrow_ptr() >= *b.borrow_ptr();
}

template <std::size_t i, typename T, size_t SZ, typename Deleter>
auto get(unique_heap_array<T, SZ, Deleter>& p) { return std::get<i>(*p.borrow_ptr()); }

template <std::size_t i, typename T, size_t SZ, typename Deleter>
auto get(const unique_heap_array<T, SZ, Deleter>& p) { return std::get<i>(*p.borrow_ptr()); }

The transform function works by reinterpreting the array as the output type, performing an std::transform on the array in-place, then invalidating the input pointer afterward, returning the output type array created from the stolen pointer.

Example usage using similar types:

#include <cstdint>


template <int FracSize_>
struct FixedFractional {
    static constexpr auto FracSize = FracSize_;
    int64_t value;
};

template <int OutFracSize, int InFracSize>
FixedFractional<OutFracSize> resize(FixedFractional<InFracSize> a)
{
    if (InFracSize < OutFracSize) {
        return {a.value << (OutFracSize - InFracSize)};
    } else {
        return {a.value >> (InFracSize - OutFracSize)};
    }
}

template <int AFracSize, int BFracSize>
auto operator+ (FixedFractional<AFracSize> a, FixedFractional<BFracSize> b)
{
    constexpr auto ResFracSize = std::max(AFracSize, BFracSize);
    auto resVal = resize<ResFracSize>(a).value + resize<ResFracSize>(b).value;
    return FixedFractional<ResFracSize> {resVal};
}

int main()
{
    auto a = unique_heap_array<FixedFractional<6>, 100'000>();
    auto unaryXfer = [](decltype(a[0]) t) { return resize<4>(t); };
    auto b = a.transform<decltype(unaryXfer(a[0]))>(unaryXfer);
    // a is released, further usage is a seg fault
    // b uses a's memory where it stores the resized integers from a
    auto c = unique_heap_array<FixedFractional<12>, 100'000>();
    auto binaryXfer = [](decltype(c[0]) t, decltype(b[0]) v) { return t + v; };
    auto d = c.transform<FixedFractional<decltype(binaryXfer(c[0], b[0]))::FracSize>>(binaryXfer, b);
    // c is now released
    // d uses c's memory to store the piecewise addition of b and c
}
\$\endgroup\$
  • \$\begingroup\$ Can you include an example type transformation? I suspect the best option may be to adjust your types and then use a vector. \$\endgroup\$ – sudo rm -rf slash Nov 11 '19 at 3:49
  • \$\begingroup\$ The types cannot be "adjusted" without moving the bounds to runtime which completely trashes performance. And correct me if I'm wrong, std::vector code won't generate SIMD instructions due to the runtime size. Performance is a REQUIREMENT, hence the effort. \$\endgroup\$ – ktb Nov 11 '19 at 4:14
  • \$\begingroup\$ The compiler can generate SIMD on a vector. godbolt.org/z/75C5xS. You could also consider std::valarray \$\endgroup\$ – sudo rm -rf slash Nov 11 '19 at 5:03
  • \$\begingroup\$ The variable s in the example is not defined within the scope of the example and possibly makes this question off-topic due to Lack of Concrete Context. Instead of the 2 line example could you provide a test case that actually runs? \$\endgroup\$ – pacmaninbw Nov 11 '19 at 15:32
  • \$\begingroup\$ Thanks for posting an example. Are you sure you need to store the FracSize as a static member of each fraction? Why not store it (possibly as a static contexpr member) of the array type? \$\endgroup\$ – sudo rm -rf slash Nov 11 '19 at 22:03
0
\$\begingroup\$

These are wrong. It doesn't make sense for operators on the array to succeed if the pointer is null. I would remove the constexpr and noexcept from the first three and access the array's member functions through the pointer so that it will segfault.

    constexpr bool empty() const noexcept               { return SZ == 0; }
    constexpr auto size() const noexcept                { return SZ; }
    constexpr auto max_size() const noexcept            { return SZ; }

The noexcept in this is wrong, all allocation can throw.

    void reset_ptr() noexcept                           { p.reset(new element_type); }

These constructors could be noexcept.

    unique_heap_array(std::nullptr_t)                   { }
    unique_heap_array(element_pointer_type ptr)         { reset_ptr(ptr); }

If you remove the Deleter parameter so that you don't have to potentially feed it to transform, you can deduce the output type and not have to require the user to determine the output type. You could probably find a way to support the deleter, but it's rarely used and even if defaulted you would still have to call it with the empty argument list transform<>(...), which some people find annoying. I would remove Deleter entirely from the class and the get_deleter method as well.

    template <typename F>
    auto transform(F&& func)
    {
        using O = decltype(func((*this)[0]));
        static_assert((sizeof(O) == sizeof(T)) &&
                      (alignof(O) <= alignof(T)),
                      "input and output types are not compatible");
        auto res = unique_heap_array<O, SZ>(reinterpret_cast<std::array<O, SZ>*>(borrow_ptr()));
        std::transform(begin(), end(), res.begin(), func);
        release_ptr();
        return res;
    }
    template <typename F, typename T2>
    auto transform(F&& func, const unique_heap_array<T2, SZ>& other)
    {
        using O = decltype(func((*this)[0], other[0]));
        static_assert((sizeof(O) == sizeof(T)) &&
                      (alignof(O) <= alignof(T)),
                      "input and output types are not compatible");
        auto res = unique_heap_array<O, SZ>(reinterpret_cast<std::array<O, SZ>*>(borrow_ptr()));
        std::transform(begin(), end(), other.begin(), res.begin(), func);
        release_ptr();
        return res;
    }
\$\endgroup\$
0
\$\begingroup\$

Now for something completely different!

I re-analyzed my problem and determined that I didn't really need to implement the above data structure. How my program works is that I have many modules (that change) that are connected together to perform operations on large arrays of data. Ideally, I want minimal memory usage for both performance and scalability, so I must reuse memory allocations in my calculations to store the temporary calculations that get sent from module to module, copying only when necessary.

The best solution to this problem is to allocate all the memory up front and give ownership of it to an entity that sits above all the modules that shuffles the data through the system. As the system runs through an iteration of data processing it gives handles to the memory locations it allocated to each of the modules for I/O. These handles claim no ownership. The handles can be initialized with a borrowed pointer, and then later invalidated in a call to transform. And only one "view" of the memory space should exist at a time, seeing as each view could be as a different type.

I found this example of a non-owning observer smart pointer written by Howard Hinnant in this proposal. They went on to modify it to add copy semantics, but the original implementation serves my purposes better.

struct no_delete {
    template <typename T>
    void operator() (T*) {}
};

template <typename T>
using unique_handle = std::unique_ptr<T, no_delete>;

template <typename T>
auto get_handle_to(T& a) {
    return unique_handle<T>(&a);
}

Transform can be as follows.

template <typename I, size_t SZ, typename F>
auto transform(unique_handle<std::array<I, SZ>>& in, F&& func)
{
    using O = decltype(func((*in)[0]));
    auto out = unique_handle<std::array<O, SZ>>(reinterpret_cast<std::array<O, SZ>*>(in.get()));
    std::transform(in->begin(), in->end(), out->begin(), func);
    in.release();
    return out;
}

template <typename I, size_t SZ, typename I2, typename F>
auto transform(unique_handle<std::array<I, SZ>>& in, const unique_handle<std::array<I2, SZ>>& in2, F&& func)
{
    using O = decltype(func((*in)[0], (*in2)[0]));
    auto out = unique_handle<std::array<O, SZ>>(reinterpret_cast<std::array<O, SZ>*>(in.get()));
    std::transform(in->begin(), in->end(), in2->begin(), out->begin(), func);
    in.release();
    return out;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.