190
It is recommended to use a data-oriented approach when designing a data structure
for persistent memory. The idea is to store data in such a way that its processing by the
CPU is cache friendly. Imagine having to store a sequence of 1000 records that consist of
2 integer values. This has two approaches: Either use two arrays of integers as shown in
Listing 11-1, or use one array of pairs as shown in Listing 11-2. The first approach is SoA
(Structure of Arrays), and the second is AoS (Array of Structures).
Listing 11-1. SoA layout approach to store data
struct soa {
int a[1000];
int b[1000];
};
Listing 11-2. AoS layout approach to store data
std::pair aos_records[1000];
Depending on the access pattern to the data, you may prefer one solution over the
other. If the program frequently updates both fields of an element, then the AoS solution
is better. However, if the program only updates the first variable of all elements, then the
SoA solution works best.
For applications that use volatile memory, the main concerns are usually cache
misses and optimizations for single instruction, multiple data (SIMD) processing. SIMD
is a class of parallel computers in Flynn’s taxonomy,
2
which describes computers with
multiple processing elements that simultaneously perform the same operation on
multiple data points. Such machines exploit data-level parallelism, but not concurrency:
There are simultaneous (parallel) computations but only a single process (instruction) at
a given moment.
While those are still valid concerns for persistent memory, developers must consider
snapshotting performance when transactions are used. Snapshotting one contiguous
memory region is always better then snapshotting several smaller regions, mainly due to
the smaller overhead incurred by using less metadata. Efficient data structure layout that
takes these considerations into account is imperative for avoiding future problems when
migrating data from DRAM-based implementations to persistent memory.
2
For a full definition of SIMD, see https://en.wikipedia.org/wiki/SIMD.
Chapter 11 Designing Data struCtures for persistent MeMory
It is recommended to use a data-oriented approach when designing a data structure
for persistent memory. The idea is to store data in such a way that its processing by the
CPU is cache friendly. Imagine having to store a sequence of 1000 records that consist of
2 integer values. This has two approaches: Either use two arrays of integers as shown in
Listing 11-1, or use one array of pairs as shown in Listing 11-2. The first approach is SoA
(Structure of Arrays), and the second is AoS (Array of Structures).
Listing 11-1. SoA layout approach to store data
struct soa {
int a[1000];
int b[1000];
};
Listing 11-2. AoS layout approach to store data
std::pair
Depending on the access pattern to the data, you may prefer one solution over the
other. If the program frequently updates both fields of an element, then the AoS solution
is better. However, if the program only updates the first variable of all elements, then the
SoA solution works best.
For applications that use volatile memory, the main concerns are usually cache
misses and optimizations for single instruction, multiple data (SIMD) processing. SIMD
is a class of parallel computers in Flynn’s taxonomy,
2
which describes computers with
multiple processing elements that simultaneously perform the same operation on
multiple data points. Such machines exploit data-level parallelism, but not concurrency:
There are simultaneous (parallel) computations but only a single process (instruction) at
a given moment.
While those are still valid concerns for persistent memory, developers must consider
snapshotting performance when transactions are used. Snapshotting one contiguous
memory region is always better then snapshotting several smaller regions, mainly due to
the smaller overhead incurred by using less metadata. Efficient data structure layout that
takes these considerations into account is imperative for avoiding future problems when
migrating data from DRAM-based implementations to persistent memory.
2
For a full definition of SIMD, see https://en.wikipedia.org/wiki/SIMD.
Chapter 11 Designing Data struCtures for persistent MeMory