Making std::vector allocate aligned memory

Question

Is it possible to make std::vector of custom structs allocate aligned memory for further processing with SIMD instructions? If it is possible to do with Allocator, does anyone happen to have such an allocator he could share?

Intertwist

did you check to see if the standard allocator already does that for you? – Denomination

@rhalbersma: I don't think it does, it doesn't take alignment parameter. – Intertwist

no what I mean is: does your STL implementation already align memory for you? Did you compute the memory address of v.begin() and check whether it starts at a multiple of X bytes? even though you can't explicily configure alignment, the std::allocator might already help you with that. – Denomination

@rhalbersma: I believe it aligns on 4B (32 bit) boundary, but I need 128 bit alignment. – Intertwist

@VioletGiraffe: more likely it aligns on an 8 byte boundry. – Clariceclarie

possible duplicate of How is a vector's data aligned? – Shantae

Note that with C++17, std::vector<__m256> automatically allocates memory with a 32 byte alignment :-) – Zoosporangium

@MarcGlisse: good to know, thanks! – Intertwist

@MarcGlisse Can you convert your comment to an answer so I can upvote it ? – Eunuchize

Answer 1

Starting in C++17, just use std::vector<__m256i> or with any other aligned type. There's aligned version of operator new, it is used by std::allocator for aligned types (as well as by plain new-expression, so new __m256i[N] is also safe starting in C++17).

There's a comment by @MarcGlisse saying this, making this an answer to make it more visible.

Gazo

Answer 2

Edit: I removed the inheritance of std::allocator as suggested by GManNickG and made the alignment parameter a compile time thing.

I recently wrote this piece of code. It's not tested as much as I would like it so go on and report errors. :-)

enum class Alignment : size_t
{
    Normal = sizeof(void*),
    SSE    = 16,
    AVX    = 32,
};


namespace detail {
    void* allocate_aligned_memory(size_t align, size_t size);
    void deallocate_aligned_memory(void* ptr) noexcept;
}


template <typename T, Alignment Align = Alignment::AVX>
class AlignedAllocator;


template <Alignment Align>
class AlignedAllocator<void, Align>
{
public:
    typedef void*             pointer;
    typedef const void*       const_pointer;
    typedef void              value_type;

    template <class U> struct rebind { typedef AlignedAllocator<U, Align> other; };
};


template <typename T, Alignment Align>
class AlignedAllocator
{
public:
    typedef T         value_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;

    typedef std::true_type propagate_on_container_move_assignment;

    template <class U>
    struct rebind { typedef AlignedAllocator<U, Align> other; };

public:
    AlignedAllocator() noexcept
    {}

    template <class U>
    AlignedAllocator(const AlignedAllocator<U, Align>&) noexcept
    {}

    size_type
    max_size() const noexcept
    { return (size_type(~0) - size_type(Align)) / sizeof(T); }

    pointer
    address(reference x) const noexcept
    { return std::addressof(x); }

    const_pointer
    address(const_reference x) const noexcept
    { return std::addressof(x); }

    pointer
    allocate(size_type n, typename AlignedAllocator<void, Align>::const_pointer = 0)
    {
        const size_type alignment = static_cast<size_type>( Align );
        void* ptr = detail::allocate_aligned_memory(alignment , n * sizeof(T));
        if (ptr == nullptr) {
            throw std::bad_alloc();
        }

        return reinterpret_cast<pointer>(ptr);
    }

    void
    deallocate(pointer p, size_type) noexcept
    { return detail::deallocate_aligned_memory(p); }

    template <class U, class ...Args>
    void
    construct(U* p, Args&&... args)
    { ::new(reinterpret_cast<void*>(p)) U(std::forward<Args>(args)...); }

    void
    destroy(pointer p)
    { p->~T(); }
};


template <typename T, Alignment Align>
class AlignedAllocator<const T, Align>
{
public:
    typedef T         value_type;
    typedef const T*  pointer;
    typedef const T*  const_pointer;
    typedef const T&  reference;
    typedef const T&  const_reference;
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;

    typedef std::true_type propagate_on_container_move_assignment;

    template <class U>
    struct rebind { typedef AlignedAllocator<U, Align> other; };

public:
    AlignedAllocator() noexcept
    {}

    template <class U>
    AlignedAllocator(const AlignedAllocator<U, Align>&) noexcept
    {}

    size_type
    max_size() const noexcept
    { return (size_type(~0) - size_type(Align)) / sizeof(T); }

    const_pointer
    address(const_reference x) const noexcept
    { return std::addressof(x); }

    pointer
    allocate(size_type n, typename AlignedAllocator<void, Align>::const_pointer = 0)
    {
        const size_type alignment = static_cast<size_type>( Align );
        void* ptr = detail::allocate_aligned_memory(alignment , n * sizeof(T));
        if (ptr == nullptr) {
            throw std::bad_alloc();
        }

        return reinterpret_cast<pointer>(ptr);
    }

    void
    deallocate(pointer p, size_type) noexcept
    { return detail::deallocate_aligned_memory(p); }

    template <class U, class ...Args>
    void
    construct(U* p, Args&&... args)
    { ::new(reinterpret_cast<void*>(p)) U(std::forward<Args>(args)...); }

    void
    destroy(pointer p)
    { p->~T(); }
};

template <typename T, Alignment TAlign, typename U, Alignment UAlign>
inline
bool
operator== (const AlignedAllocator<T,TAlign>&, const AlignedAllocator<U, UAlign>&) noexcept
{ return TAlign == UAlign; }

template <typename T, Alignment TAlign, typename U, Alignment UAlign>
inline
bool
operator!= (const AlignedAllocator<T,TAlign>&, const AlignedAllocator<U, UAlign>&) noexcept
{ return TAlign != UAlign; }

The implementation for the actual allocate calls is posix only but you can extent that easily.

void*
detail::allocate_aligned_memory(size_t align, size_t size)
{
    assert(align >= sizeof(void*));
    assert(nail::is_power_of_two(align));

    if (size == 0) {
        return nullptr;
    }

    void* ptr = nullptr;
    int rc = posix_memalign(&ptr, align, size);

    if (rc != 0) {
        return nullptr;
    }

    return ptr;
}


void
detail::deallocate_aligned_memory(void *ptr) noexcept
{
    return free(ptr);
}

Needs C++11, btw.

Herein

I don't think you need to or should inherit from <strike>std::exception<></strike>std::allocator<>. – Stettin

@GManNickG, perhaps you meant allocator? :) – Guildsman

@avakar: Whoa, didn't even notice I wrote that! – Stettin

@GManNickG: Thanks I'll put it onto my todo list. – Herein

The old one was better, there's no way I can compile this in VS 2010 :) – Intertwist

I used the std::allocator as a reference but removed most of the ifdefs and stuff... Might be it only works with clang... – Herein

Undefined nail::is_power_of_two – Amphioxus

@shoosh: That's not hard to implement. E. g. graphics.stanford.edu/~seander/… – Intertwist

Answer 3

In the upcoming version 1.56, the Boost library will include Boost.Align. Among other memory alignment helpers it provides boost::alignment::aligned_allocator, which can be used a drop-in replacement for std::allocator and allows you to specify an alignment. See the documentation on https://boostorg.github.io/align/

Patently

It's good to know, but personally I find boost quite a pain to integrate into my projects (those libraries that are not header-only). – Intertwist

I agree, integrating boost can be a bit of a pain. However, Boost.Align is header-only and also only depends on other header-only libraries AFAICS. – Patently

It is now available: boost.org/doc/libs/1_56_0/libs/core/doc/html/index.html – Necklace

Answer 4

Yes, it should be possible. If you put this question on google then you will get lots of sample code, below is some promising results:

https://bitbucket.org/marten/alignedallocator/wiki/Home

http://code.google.com/p/mastermind-strategy/source/browse/trunk/src/util/aligned_allocator.hpp?r=167

https://gist.github.com/1471329

Klaxon