Dynamic arrays

A block of memory cannot grow where it stands. To make room, take a bigger block and copy everything across. How much bigger? Watch why the answer is twice.

⋯16static bool grow(struct vec *v, size_t new_cap)17{18    int *p = malloc(new_cap * sizeof *p);19    if (p == NULL)20        return false;21    for (size_t i = 0; i < v->len; i++) {22        p[i] = v->data[i];23        copies++;24    }25    free(v->data);26    v->data = p;27    v->cap = new_cap;28    return true;29}30 31bool vec_push(struct vec *v, int x)32{33    if (v->len == v->cap) {34        size_t new_cap = v->cap == 0 ? 1 : 2 * v->cap;35        if (!grow(v, new_cap))36            return false;37    }38    v->data[v->len] = x;39    v->len++;40    return true;41}

Growing a block

A block from malloc has the size it was asked for, and the memory just after it may belong to something else. A list that must keep growing, read from a file of unknown length, say, has to move: allocate a bigger block, copy the elements across, free the old one. The copies are the cost.

How much bigger matters more than it seems. Grow by a fixed amount and the copies pile up as the square of the length. Grow by doubling and they stay below twice the length: each append costs a constant on average, even though a few of them cost a large copy.

The code and its cost

Grow, step by step

struct vec {
    int *data;
    size_t len, cap;
};

static bool grow(struct vec *v, size_t new_cap)
{
    int *p = malloc(new_cap * sizeof *p);
    if (p == NULL)
        return false;
    for (size_t i = 0; i < v->len; i++) {
        p[i] = v->data[i];
        copies++;
    }
    free(v->data);
    v->data = p;
    v->cap = new_cap;
    return true;
}

bool vec_push(struct vec *v, int x)
{
    if (v->len == v->cap) {
        size_t new_cap = v->cap == 0 ? 1 : 2 * v->cap;
        if (!grow(v, new_cap))
            return false;
    }
    v->data[v->len] = x;
    v->len++;
    return true;
}

The vec starts as { NULL, 0, 0 }. On the first push there is no old block: free(NULL) does nothing. Pushing 1 to 32 grows the block at lengths 0, 1, 2, 4, 8 and 16, copying 0 + 1 + 2 + 4 + 8 + 16 = 31 elements, and the program prints 32 pushes, capacity 32, 31 copies.

realloc

int *p = realloc(v->data, new_cap * sizeof *p);

realloc does what grow spells out: if the block can be extended where it stands, it extends it; if not, it allocates a new block, copies the bytes across and frees the old one. vec-realloc.c, the same program with realloc, prints 32 pushes, capacity 32. Either way, the block may have moved, so any pointer into the old block is invalid afterwards, even if this time it happened not to move.

Doubling against adding 4

With doubling, the copies are 1 + 2 + 4 + … up to the last capacity below n, which is less than 2n. So n appends cost O(n) copies in all, and O(1) each on average. That average over a whole run is the amortised cost: most appends cost one write, a few cost a large copy, and the large ones are rare because each comes after twice as many cheap ones as the last.

Growing by a fixed k cells instead copies k + 2k + 3k + … about n²/(2k) elements, O(n²). vec-add-four.c grows by 4 and copies 4 + 8 + … + 28 = 112 elements for the same 32 pushes. Its staircase passes the line 2n at the 17th push, 40 copies against 34, and pulls away. A fixed step wastes less space, but it pays for that in time.

Shrinking

A vec that empties can give memory back by halving its block. Halve when it is a quarter full, not half full. At exactly half, one push grows the block and the next pop shrinks it again, and every step costs a full copy.

Worked example

A thousand pushes. Doubling copies 1 + 2 + 4 + … + 512 = 1,023 elements. Adding 4 copies 4 + 8 + … + 996 = 124,500.

A binary counter. Counting from 0 to 16 in binary flips 31 bits in 16 increments. Half of them flip one bit; the one to 8 flips four and the one to 16 flips five. The average stays under 2, the same pattern as the copies: a few expensive steps paid for by many cheap ones.

A stale pointer.

int *first = &data[0];
int *bigger = realloc(data, 2 * sizeof *bigger);
...
printf("first = %d\n", *first);

stale-pointer.c keeps first across a realloc. In the plain build, realloc happened to grow the block where it stood, and the program printed first = 10. Reading *first is undefined behaviour even so: after realloc the old pointer must not be used, whether or not the block moved, and the 10 was luck. The sanitiser build moves every block, and stops with heap-use-after-free, a read of 4 bytes through first. gcc warns too: first may be used after realloc.

Shrinking at half. Start with capacity 16 and length 16. A push grows the block to 32, copying 16; a pop leaves 16 of 32, half full, and shrinking copies 16 back. Push, pop, push, pop: thrash.c prints 16, 32, 48, 64, 80 and 96 copies after six steps.

Two checks. How many copies for 9 pushes by doubling? (15: growth at lengths 0, 1, 2, 4 and 8.) Right after a doubling, at most how much of the capacity is unused? (Just under half.)

Where it’s used

Standard libraries. The growable lists of most languages are dynamic arrays that grow by a constant factor, often 2 or 1.5.

Reading unknown amounts. A program reading a file or a network stream of unknown length appends to a buffer that doubles as it fills.

Stacks and tables. The array stack of Chapter 8 can drop its fixed capacity this way, and hash tables grow by rehashing into a bigger table on the same principle.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.