189
Consider fragmentation for each of those data structures:
• For linked lists, fragmentation efficiency depends on the node size. If
it is small enough, then high internal fragmentation can be expected.
During node allocation, every allocator will return memory with a
certain alignment that will likely be different than the node size.
• Using dynamic array results in fewer memory allocations, but every
allocation will have a different size (most implementations double
the previous one), which results in a higher external fragmentation.
• Using a segment vector, the size of a segment is fixed, so every allocation
has the same size. This practically eliminates external fragmentation
because we can allocate a new one for each freed segment.
1
Atomicity and Consistency
Guaranteeing consistency requires the proper ordering of stores and making sure data
is stored persistently. To make an atomic store bigger than 8 bytes, you must use some
additional mechanisms. This section describes several mechanisms and discusses their
memory and time overheads. For the time overhead, the focus is on analyzing the number
of flushes and memory barriers used because they have the biggest impact on performance.
Transactions
One way to guarantee atomicity and consistency is to use transactions (described in
detail in Chapter 7). Here we focus on how to design a data structure to use transactions
efficiently. An example data structure that uses transactions is described in the “Sorted
Array with Versioning” section later in this chapter.
Transactions are the simplest solution for guaranteeing consistency. While using
transactions can easily make most operations atomic, two items must be kept in mind.
First, transactions that use logging always introduce memory and time overheads.
Second, in the case of undo logging, the memory overhead is proportional to the size of
data you modify, while the time overhead depends on the number of snapshots. Each
snapshot must be persisted prior to the modification of snapshotted data.
1
Using the libpmemobj allocator, it is also possible to easily lower internal fragmentation by using
allocation classes (see Chapter 7).
Chapter 11 Designing Data struCtures for persistent MeMory
Consider fragmentation for each of those data structures:
• For linked lists, fragmentation efficiency depends on the node size. If
it is small enough, then high internal fragmentation can be expected.
During node allocation, every allocator will return memory with a
certain alignment that will likely be different than the node size.
• Using dynamic array results in fewer memory allocations, but every
allocation will have a different size (most implementations double
the previous one), which results in a higher external fragmentation.
• Using a segment vector, the size of a segment is fixed, so every allocation
has the same size. This practically eliminates external fragmentation
because we can allocate a new one for each freed segment.
1
Atomicity and Consistency
Guaranteeing consistency requires the proper ordering of stores and making sure data
is stored persistently. To make an atomic store bigger than 8 bytes, you must use some
additional mechanisms. This section describes several mechanisms and discusses their
memory and time overheads. For the time overhead, the focus is on analyzing the number
of flushes and memory barriers used because they have the biggest impact on performance.
Transactions
One way to guarantee atomicity and consistency is to use transactions (described in
detail in Chapter 7). Here we focus on how to design a data structure to use transactions
efficiently. An example data structure that uses transactions is described in the “Sorted
Array with Versioning” section later in this chapter.
Transactions are the simplest solution for guaranteeing consistency. While using
transactions can easily make most operations atomic, two items must be kept in mind.
First, transactions that use logging always introduce memory and time overheads.
Second, in the case of undo logging, the memory overhead is proportional to the size of
data you modify, while the time overhead depends on the number of snapshots. Each
snapshot must be persisted prior to the modification of snapshotted data.
1
Using the libpmemobj allocator, it is also possible to easily lower internal fragmentation by using
allocation classes (see Chapter 7).
Chapter 11 Designing Data struCtures for persistent MeMory