This is not the current version of the class.

Data representation 3: Layout and allocators

Overview

Last time, we examined the way C++ compilers assign sizes to objects, and the way they lay out compound objects in memory. We ended on a cliffhanger about alignment. This time we explain alignment in depth, and then describe an arena allocator, a purpose-built dynamic memory allocator that improves performance when many small objects are allocated and freed.

Mysterious struct sizes

datarep3/structs.cc
#include <cstdio>
#include "hexdump.hh"

int main() {
    struct {
        int a;
        int b;
        char c;
        char d;
    } s1 = {61, 62, 63, 64};

    struct {
        int a;
        char b;
        int c;
        char d;
    } s2 = {61, 62, 63, 64};

    hexdump_object(s1);
    hexdump_object(s2);
}

Alignments and compound types

Alignment and size

Struct rule

Struct example 1

struct s {     // <- Alignment = ?, Size = ?
               // <- Padding = ?
    int a;     // <- Alignment = 4, Offset = ?
               // <- Padding = ?
    char b;    // <- Alignment = 1, Offset = ?
               // <- Padding = ?
    int c;     // <- Alignment = 4, Offset = ?
               // <- Padding = ?
    char d;    // <- Alignment = 1, Offset = ?
               // <- Padding = ?
};

Struct example 1, completed

struct s {     // <- Alignment = 4, Size = 16
               // <- Padding = 0 (always)
    int a;     // <- Alignment = 4, Offset = 0 (always)
               // <- Padding = 0 (`b` is less aligned than `a`)
    char b;    // <- Alignment = 1, Offset = 4
               // <- Padding = 3 (recover alignment for `c`)
    int c;     // <- Alignment = 4, Offset = 8
               // <- Padding = 0
    char d;    // <- Alignment = 1, Offset = 12
               // <- Padding = 3 (recover alignment for `sizeof(s)`)
};

Struct rule, mathematically

Alignment and malloc

Performance and layout

datarep3/accessor.cc
// access 10M integers in up, down, or random order
unsigned long sum = 0;
unsigned long rand_sum = 0;

for (int i = 0; i != size; ++i) {
    int r = rand() % size;

    int idx;
    if (style == access_up) {
        idx = i;
    } else if (style == access_down) {
        idx = size - i - 1;
    } else if (style == access_random) {
        idx = r;
    }

    sum += v[idx];
    rand_sum += r;
}

Sequential faster than random

Performance consequences of memory allocation

datarep3/mb0.cc
// allocate and free nodes `noperations` times
long counter = 0;
for (unsigned i = 0; i != noperations; ++i) {
    int pos = random_node_index(randomness);
    if (n[pos] == nullptr) {
        n[pos] = new node;
        n[pos]->contents = counter;
        ++counter;
    } else {
        delete n[pos];
        n[pos] = nullptr;
    }
}

Memory arenas