21
\$\begingroup\$

After learning more about memory alignment and how it can impact processor data access, I tried to find something in the standard that offers proper memory alignment inside blocks of raw memory that will be used to hold heterogeneous types. With no luck, I had to come up with a solution.

The problem

Assuming we have some variadic template of the form: \$T_0, T_1, ..., T_{n - 1}, T_n\$:

We can't just construct \$T_n\$ at offset sizeof( \$T_{n-1}\$ ) because they would be in an unaligned address. Example, for the list <char, int> and std::aligned_storage_t<8, 4> storage, doing:

::new ( &storage ) char{}; // OK; can go into any address in terms of alignment
::new ( &storage + sizeof( char ) ) int{}; // now misaligned!

This would look like so in memory:

bytes:    [  0  ][  1  ][  2  ][  3  ][  4  ]
contents: [ c_0 ][ i_0 ][ i_1 ][ i_2 ][ i_3 ]

Which is clearly unaligned for int. For an int that follows a char to be properly aligned, it should look like this in memory:

bytes:    [  0  ][  1  ][  2  ][  3  ][  4  ][  5  ][  6  ][  7  ]
contents: [ c_0 ][ pad ][ pad ][ pad ][ i_0 ][ i_1 ][ i_2 ][ i_3 ]

This is exactly what your compiler does when you declare a class in order to maintain alignment:

struct my_type         ----         struct my_type
{                      ----         {
    char c;            ----             char c;
    int i;             ----             char padding[ 3 ]; // courtesy of the compiler
};                     ----             int i;
                       ----         };

Solution

For some variadic template, I present a way to automatically generate offsets into aligned memory for the respective types in the variadic template. This allows me to in-place construct types while maintaining proper address alignment so that performance is optimal.

The program generates a compile-time offset map, where the \$n\$th offset is added to the starting address of the std::aligned_storage_t<> where the types will reside in order to in-place construct the \$n\$th type at its properly aligned memory address.

TL;DR: I do what the compiler does for classes (as above), but for std::aligned_storage_t<>.

Advantages

  • std::tuple<> instance creation and access can bog down compile time. The proposed functionality can be used to implement a non-recursive tuple definition or any other variant-like type with static memory (see usage example for basic implementation).

  • Does not consume any more memory than an instance of std::tuple<> with the same variadic template.

  • Everything is done at compile-time. Accessing memory locations with constant offsets should be fast.

Implementation

Usage of std::index_sequence<> and other related classes should be replaced by non-recursive implementations (such as my very own found here) in order to decrease compilation time.

1. Calculating the offsets and total memory required

The calculate_offsets() function returns a std::array<> containing the offsets, where the value at index \$i\$ maps to the offset for \$T_i\$. The total required size is stored in the final position in the array.

#include <array>
#include <cstddef>
#include <utility>

template<std::size_t align, class... Ts, std::size_t... is>
constexpr auto calculate_offsets( std::index_sequence<is...> ) noexcept
{
    static_assert( sizeof...( Ts ) == sizeof...( is ),
        "invalid std::index_sequence<is...>; sizeof...( Ts ) != sizeof...( is )" );

    constexpr std::size_t alignments[] = { alignof( Ts )... };
    constexpr std::size_t sizes[] = { sizeof( Ts )... };

    std::size_t offsets[ sizeof...( Ts ) ] = {};
    std::size_t memory_used{ 0 };

    for ( std::size_t i{ 0 }, multiplier{ 1 }; i < sizeof...( Ts ); ++i )
    {
        while ( memory_used % alignments[ i ] != 0 )
            ++memory_used;

        offsets[ i ] = memory_used;
        memory_used += sizes[ i ];

        if ( memory_used > multiplier * align )
            ++multiplier;
    }

    while ( memory_used % align != 0 )
        ++memory_used;

    return std::array<std::size_t, sizeof...( Ts ) + 1>
    {
        offsets[ is ]..., memory_used
    };
}

2. Providing simple access to the generated values

The simple make_aligned_offsets<> type provides a simple interface for getting the information generated by calculate_offsets().

template<std::size_t align, class... Ts>
struct make_aligned_offsets
{
    static constexpr std::array<std::size_t, sizeof...( Ts ) + 1> map
    {
        calculate_offsets<align, Ts...>( std::make_index_sequence<sizeof...( Ts )>{} )
    };

    static constexpr std::size_t size{ map[ sizeof...( Ts ) ] };
    static constexpr std::size_t alignment{ align };
};

Sample usage

In this sample, usage, I demonstrate how to use the functionality to properly receive aligned addresses for the respective types. As before, usage of std::tuple<> and std::tuple_elemet_t<> should be replaced by non-recursive implementations to increase compilation speed.

#include <tuple>
#include <cstdint>
#include <cassert>
#include <algorithm>

template<class... Ts>
class multitype_storage
{
private:
    using tuple_t = std::tuple<Ts...>;
    using info_t = make_aligned_offsets<std::max( { alignof( Ts )... } ), Ts...>;
    std::aligned_storage_t<info_t::size, info_t::alignment> m_data;

public:
    template<std::size_t i>
    constexpr decltype( auto ) get() noexcept
    {
        return *reinterpret_cast<std::tuple_element_t<i, tuple_t>*>(
            reinterpret_cast<char*>( &m_data ) + info_t::map[ i ] );
    }
};

int main()
{
    multitype_storage<double, int, char, float> storage;

    assert( ( (std::intptr_t) &storage.get<0>() ) % alignof( double ) == 0 );
    assert( ( (std::intptr_t) &storage.get<1>() ) % alignof( int ) == 0 );
    assert( ( (std::intptr_t) &storage.get<2>() ) % alignof( char ) == 0 );
    assert( ( (std::intptr_t) &storage.get<3>() ) % alignof( float ) == 0 );
}
\$\endgroup\$
2
\$\begingroup\$

I only see one easy speedup:

while ( memory_used % align != 0 )
     ++memory_used;

Why do multiple divisions? Just do a single division, get the remainder, and then add the appropriate amount to memory_used

int remainder = memory_used % align;
if (remainder != 0)
    memory_used += align - remainder;
\$\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.