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