7
\$\begingroup\$

During Jonathan Blow's video where he muses about a games-focused programming language, he presents C++ code that allocates a single big block of memory and has N pointers into that block. The purpose being to avoid heap allocating N blocks of memory for N arrays.

That code looked to me like it could use some genericity... so I first came up with the following where we would allocate three arrays into a single block of memory:

using memory_block = std::unique_ptr<char[]>;

template<typename A, typename B, typename C>
memory_block block_allocate(A*& p, size_t a, B*& q, size_t b, C*& r, size_t c)
{
    memory_block z = std::make_unique<char[]>(a * sizeof(A) + b * sizeof(B) + c * sizeof(C));

    p = reinterpret_cast<A*>(z.get());
    q = reinterpret_cast<B*>(p + a);
    r = reinterpret_cast<C*>(q + c);

    return z;
}

Improving for any number of arrays gives us:

using memory_block = std::unique_ptr<char[]>;

namespace detail
{
    template<typename T>
    size_t block_size(T* const, size_t const n)
    {
        return sizeof(T) * n;
    }

    template<typename T, typename U, typename... Args>
    size_t block_size(T* const t, size_t const m, U* const u, size_t const n, Args&&... args)
    {
        return block_size(t, m) + block_size(u, n, args...);
    }

    template<typename T, typename U>
    void block_assign(T* const p, size_t const offset, U*& u, size_t const)
    {
        u = reinterpret_cast<U*>(p + offset);
    }

    template<typename T, typename U, typename... Args>
    void block_assign(T* const p, size_t const offset, U*& u, size_t const n, Args&&... args)
    {
        block_assign(p, offset, u, n);
        block_assign(u, n, args...);
    }
}

template<typename T, typename... Args>
memory_block block_allocate(T*& t, size_t const n, Args&&... args)
{
    memory_block b = std::make_unique<char[]>(detail::block_size(t, n, args...));

    detail::block_assign(b.get(), 0, t, n, args...);

    return b;
}

It's understood that Jonathan's Blow's desire is for a language solution to this problem and not the library solution that I present but I had fun coming up with it nonetheless.

So, after simple testing the code appears to behave as expected but do you see something missing that would make production-ready?

\$\endgroup\$
2
\$\begingroup\$

Memory alignment requirements is something often forgotten when implementing custom memory allocation strategies. Each native type has a minimum alignment required for its starting memory address, consequently, structured types will inherit the requirement from its members. std::aligned_storage and std::aligned_union are a good example on that. Also refer to: How to allocate aligned memory only using the standard library?

Operator new and malloc are guaranteed to always return a starting address that is aligned for the most demanding type available (like 16 bytes for a __m128 vector type), so memory returned by those system allocators will be suitable to store such objects and homogeneous arrays of them. The problem with mixing objects with different alignment requirements in the same memory block is that if one item or chunk of items in this mixed array breaks the alignment, whatever follows will be misaligned, so you run the risk of getting memory access errors at the CPU level when touching that memory.

Your block allocator has that problem, since it accepts generic types, so you need to fix it in order to have a robust implementation that can allocate anything. To do that, you just have to increment each pointer to an aligned address, and also add an extra overhead to the parent block, in account of that. Something like the following:

void * aligned_ptr(void * ptr, std::size_t alignment)
{
    // Cast to integer and align the address:
    std::uintptr_t uintPtr = reinterpret_cast<std::uintptr_t>(ptr);
    std::uintptr_t alignedPtr = (uintPtr + (alignment - 1)) & ~(alignment - 1); // Power-of-two alignment assumed!

    // Re-cast to void*, validate and return:
    void * userPtr = reinterpret_cast<void *>(alignedPtr);
    assert(is_aligned_ptr(userPtr, alignment));
    return userPtr;
}

std::size_t aligned_size(std::size_t size, std::size_t alignment)
{
    // Add the minimum extra needed to the size for pointer alignment.
    // This size can then be used to malloc() some memory
    // and then have the pointer aligned with aligned_ptr().
    return size + (alignment - 1);
};

block block_allocate(A*& pA, std::size_t nA, B*& pB, std::size_t nB, C*& pC, std::size_t nC)
{
    auto sizeBlockA = aligned_size(nA * sizeof(A), alignof(A));
    auto sizeBlockB = aligned_size(nB * sizeof(B), alignof(B));
    auto sizeBlockC = aligned_size(nC * sizeof(C), alignof(C));

    block blk = alloc_bytes(sizeBlockA + sizeBlockB + sizeBlockC);

    pA = reinterpret_cast<A*>(aligned_ptr(blk.ptr, alignof(A))); // if allocated with new, already aligned, but doesn't harm checking either...
    pB = reinterpret_cast<B*>(aligned_ptr(blk.ptr + sizeBlockA, alignof(B)));
    pC = reinterpret_cast<C*>(aligned_ptr(blk.ptr + sizeBlockA + sizeBlockB, alignof(C)));

    return blk;
}

Please note that the above example was not tested, but hopefully gives you a good idea of the procedure.


Other little things:

Instead of returning a plain unique_ptr to the memory, I'd suggest augmenting the pointer with a small structure that has some extra context, like the total size of the memory. This is oftentimes useful for debugging and profiling (the block type I invented above):

struct block
{
    std::unique_ptr<std::uint8_t[]> ptr;
    std::size_t size;
};

Or you might modify it to use of a std::vector. It is certainly possible, but might be overkill, since the block is not meant to be resized.

Very minor nitpicking, but notice that I use the std:: prefix in the extended integer types like size_t? That's the correct usage, since they are members of the standard namespace in C++. It works without because shared C headers expose them globally, but a pure C++ compiler is not required to provide that.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the detailed explanation. I understand the issue. (And thanks for leaving the fixed generic solution up as an exercise for me! :) ) \$\endgroup\$ – screwnut Dec 2 '15 at 23:47
  • \$\begingroup\$ So I updated my code. I used std::align which you did not mention but I figured did what I needed (and more). Any reason you left it out? \$\endgroup\$ – screwnut Dec 3 '15 at 19:09
  • \$\begingroup\$ @screwnut I could lie to you and say that I wrote that function to show how it's done, but the true is that I completely overlooked std::align :) I had the impression there was some other function besides aligned_storage/union, but couldn't find it, so thanks for mentioning it! \$\endgroup\$ – glampert Dec 3 '15 at 19:16

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.