Pointer-stable Dynamic Arrays

Using Virtual Memory to Avoid Pointer Invalidation and Unpredictable Reallocation Costs in Dynamic Arrays

Dynamic arrays, as traditionally taught in computer science, reallocate memory when new elements are appended to the end. This has some undesirable effects when doing systems-level programming:

1. The performance of the append operation is unpredictable. Appending an element is often very fast, but sometimes it causes the entire underlying block of memory to be reallocated.

2. After this reallocation occurs, any pointer or reference to an element inside the dynamic array is invalidated.

Data structures that implicitly invalidate pointers make it more difficult to verify the correctness of a program, since most pointer-related bugs stem from assuming a pointer is valid when it isn’t.

This article presents a data structure that preserves the nice properties of classic dynamic arrays — O(1) random access, tightly packed elements, etc. — while completely avoiding the problems of memory reallocation.

---

---

Analyzing Static Arrays

Static arrays (i.e., arrays that never grow in size) are very fast and simple to reason about. If the maximum number of elements has a clear upper bound, a static array can be used in place of a dynamically allocated array.

typedef struct {
  uint32_t data;
} ArrayElement;

#define MAX_COUNT 8192
ArrayElement static_array[MAX_COUNT];
U32 count = 0;

// suballocate from static array
void AppendElement(ArrayElement new_element) {
  assert(count < MAX_COUNT);
  static_array[count] = new_element;
  count += 1;
}

This method is a fairly typical pattern in C programming: memory is over-allocated into a buffer upfront, and any dynamic allocation is essentially an index or slice into that buffer.

While using static arrays comes with the obvious limitation that the amount of memory needed has to be known ahead of time, it also fixes two of the aforementioned problems with dynamic arrays:

1. The base pointer address never changes and is valid throughout the lifetime of the program, meaning that pointers taken to elements within the array are never invalidated.

2. Appending an element is always a fast O(1) operation.

Static arrays break down when the number of potential elements in the array is unpredictable. Even if the array only stores a few elements, memory for the maximum number of potential elements must still be allocated. On the other hand, if the array needs to store a very large number of elements, predicting the correct maximum capacity can be difficult.

But what if this were a false dichotomy? The problem with many classic CS data structures is that they assume a malloc/free style of memory allocation, which is far from the only way of doing things. In the next section, we’ll look at some tricks with virtual memory that allow more flexibility when designing data structures with contiguous memory layouts.

Arrays Backed by Virtual Memory

Instead of trying to pre-compute what size a statically-allocated array should be, what if it were simply as large as possible?

If a computer has 16GB of available RAM, a natural maximum size of any data structure is 16GB. There is a point where enough memory can be statically allocated to handle any realistic use case.

#define KB(n) ((n) * 1024ULL)
#define MB(n) (KB(n) * 1024ULL)
#define GB(n) (MB(n) * 1024ULL)
#define TB(n) (GB(n) * 1024ULL)

// For sake of example: this may not actually compile
uint8_t large_array[GB(16)] = {0};

What may be surprising is that when the program starts executing, the operating system and compiler are not obligated to allocate any memory for an array whatsoever. It’s only when the array is written to that the data in the array starts getting mapped to physical memory.¹²

// operating system implicitly allocates memory when a static array is written to
large_array[0] = 0x1;

This effectively means that static arrays, just like dynamically heap-allocated arrays, automatically grow in size on an as-needed basis.

This can be proved more methodically by using an OS API that returns the total amount of memory physically mapped to RAM.

// Windows
uint64_t GetAmountOfPhysicallyMappedMemory() {
  PROCESS_MEMORY_COUNTERS pmc = {0};
  GetProcessMemoryInfo(GetCurrentProcess(), &pmc, sizeof(pmc));
  return pmc.WorkingSetSize;
}

The implicit allocation can be measured by reading the total amount of memory physically mapped to RAM before and after writing one byte to a static array.

uint64_t before = GetAmountOfPhysicallyMappedMemory();

large_array[0] = 0x1;

uint64_t after = GetAmountOfPhysicallyMappedMemory();
uint64_t change_in_memory_use = after - before; // change_in_memory_use is 4096

On x64, writing 0x1 to any location in a zero-initialized static array causes an implicit allocation of 4096 bytes. This is due to how memory works in modern operating systems.

The linear address space that a program sees is subdivided into 4KB sections, each one mapping to a different 4KB range on physical hardware. The 4KB sections are referred to as pages. This mapping is known as virtual memory.

Virtual memory works by dividing memory into fixed-size chunks called pages. Each page maps a range of virtual addresses to a physical one. Image credit: Computer Organization and Design RISC-V Edition

The operating system can be forced to map two virtual pages to physical memory if a program writes two non-zero bytes that are exactly 4096 bytes away from each other.

uint64_t start = GetAmountOfPhysicallyMappedMemory();

large_array[0] = 0x1;
large_array[4096] = 0x1;

uint64_t end = GetAmountOfPhysicallyMappedMemory();
uint64_t change_in_memory_use = end - start; // change_in_memory_use is 8192
uint64_t mapped_pages = change_in_memory_use / 4096ull; // 2 pages mapped to physical memory

While most CPUs natively support a page size of 4KB, it’s important to note that this varies depending on CPU architecture.³ Both Linux and Windows, for example, support large pages, which increases the page size up to 1 or 2MB if the underlying processor supports it.

In addition to allocating pages implicitly, the OS also exposes APIs that give programs direct control over virtual memory. This will be the subject of the next section.

Virtual Memory OS Calls

On Windows, the primary function for allocating virtual memory is called VirtualAlloc. Memory can be allocated in a straightforward way by doing the following:

// equivalent to malloc(KB(64))
void *ptr = VirtualAlloc(0, KB(64), MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);

VirtualAlloc takes a set of flags as the third argument. When both MEM_RESERVE and MEM_COMMIT are set, it works like any other memory allocator, except that VirtualAlloc allocates pages directly from the operating system, bypassing the heap.

The second argument takes the size of the allocation. Since virtual memory is divided into 4KB pages, allocations are always a multiple of 4KB. In practice, Windows rounds this up further to 64KB due to backwards compatibility reasons.⁴

When only the MEM_RESERVE flag is set, VirtualAlloc reserves a pointer address for future use, without actually allocating any memory.

// 64KB of pointer address space is reserved for future use, but no memory is allocated
void *ptr = VirtualAlloc(0, KB(64), MEM_RESERVE, PAGE_READWRITE);

The program can call VirtualAlloc again with previously-reserved pointer address as the first argument. Setting the MEM_COMMIT flag converts the pointer from being reserved-only to an active pointer the program can read and write to.

// the previously reserved-only pointer can now be read from/written to
VirtualAlloc(ptr, KB(64), MEM_COMMIT, PAGE_READWRITE);
*(uint32_t *)ptr = 0x1;

The allocation of pointer addresses and the underlying physical memory can be completely decoupled, which allows the program to use memory in a very flexible way.

Another surprising aspect of virtual memory is that it’s possible to reserve several terabytes of pointer address space at once, even if the total amount of physical RAM on the computer is far less than that.

// reserve a terabyte of virtual address space
void *ptr = VirtualAlloc(0, TB(1), MEM_RESERVE, PAGE_READWRITE);

This is possible because reserving pointer address space has relatively little cost. It only guarantees that future calls to VirtualAlloc won’t return a pointer within the reserved range.

It should be noted that virtual address space, while abundant for the needs of most software, does have a limit. A 64-bit process on Windows has a virtual address space limit of 128 terabytes.⁵

While VirtualAlloc is Windows-specific, the same concept applies to almost any modern operating system. The equivalent functionality is available on Linux through the mmap and mprotect syscalls.

// Reserve
void *ptr = mmap(NULL, KB(64), PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

// Commit
mprotect(ptr, KB(64), PROT_READ | PROT_WRITE);

Virtual Memory-Backed Array Implementation in C

Using the tricks of virtual memory, we can create a dynamic array that never invalidates pointers and avoids the heap allocator altogether.

A standard implementation would:

1. Reserve a large amount of address space, far more than the array could ever possibly use.

2. When an element is about to be appended, commit more virtual pages if necessary.

3. Append the element and increase the count by one.

At a minimum, this data structure will need to store a base pointer, the element count, and the amount of memory that has been allocated by VirtualAlloc using MEM_COMMIT.

typedef struct {
  ArrayElement *base_ptr;
  uint64_t element_count;
  uint64_t committed;
} VirtualArray;

To initialize the array, we reserve a large section of virtual address space. The base pointer is set to the beginning of the reserved region.

VirtualArray CreateVirtualArray() {
  VirtualArray result = {0};
  // assumes the array won't store more than 16GB of data
  result.base_ptr = VirtualAlloc(0, GB(16), MEM_RESERVE, PAGE_READWRITE);
  result.element_count = 0;
  result.committed = 0;
  return result;
}

When the virtual array is created, the base pointer technically points to invalid memory. Virtual memory lets us defer allocation until memory is actually needed.

void AppendElement(VirtualArray *array, ArrayElement element) {
  uint64_t new_size = (array->element_count + 1) * sizeof(ArrayElement);

  // check if more virtual pages need to be committed
  if (new_size > array->committed) {
    void *commit_ptr = (void *)((uint8_t *)array->base_ptr + array->committed);

    // allocate virtual pages for next 64KB section
    VirtualAlloc(commit_ptr, KB(64), MEM_COMMIT, PAGE_READWRITE);
    array->committed += KB(64);
  }

  array->base_ptr[array->element_count] = element;
  array->element_count += 1;
}

The append operation of a virtual memory-backed array does not require copying or reallocating data. Instead, it simply sets a region of pre-reserved pointer address space as active for reads and writes. This same technique can be generalized beyond typed arrays.

Linear Allocators

Virtual memory tricks work well with custom allocators, the simplest of which is a linear allocator.

A linear allocator is effectively a stack of bytes that can push and pop from the end. It only needs to store a base pointer, a byte offset, and a total capacity. The offset is bumped forward with each allocation. If the offset ever becomes greater than the total capacity, the allocator has run out of memory.

typedef struct {
  void *base_ptr;
  uint64_t bytes_allocated;
  uint64_t capacity;
} LinearAllocator;

static void *LinearAllocatorPush(LinearAllocator *allocator, uint64_t size) {
  if (allocator->bytes_allocated + size > allocator->capacity) {
    return NULL;
  }
  void *result = (uint8_t *)allocator->base_ptr + allocator->bytes_allocated;
  allocator->bytes_allocated += size; // increment by size
  return result;
}

// free a pointer returned from LinearAllocatorPush
static void LinearAllocatorPop(LinearAllocator *allocator, void *ptr) {
  uintptr_t current_ptr = (uintptr_t)allocator->base_ptr + allocator->bytes_allocated;
  uint64_t bytes_deallocated = (uint64_t)(current_ptr - ptr);
  memset(ptr, 0, bytes_deallocated);
  allocator->bytes_allocated -= bytes_deallocated;
}

The problem is that it might not be possible to know what the total capacity should be ahead of time. In this case, we can use virtual memory to first reserve a large section of pointer address space and only commit as necessary.

typedef struct {
  void *base_ptr;
  uint64_t bytes_allocated;
  uint64_t committed;
  uint64_t reserved;
} LinearAllocator;

static LinearAllocator CreateLinearAllocator() {
  LinearAllocator result = {0};
  // reserve large pool of memory up front
  result.base_ptr = VirtualAlloc(0, GB(16), MEM_RESERVE, PAGE_READWRITE);
  result.bytes_allocated = 0;
  result.committed = 0;
  result.reserved = GB(16);
  return result;
}

uint64_t RoundUp(uint64_t value, uint64_t multiple) {
  return ((value + (multiple - 1)) / multiple) * multiple;
}

static void *LinearAllocatorPush(LinearAllocator *allocator, uint64_t size) {

  assert(allocator->bytes_allocated + size < allocator->reserved);

  void *result = (uint8_t *)allocator->base_ptr + allocator->bytes_allocated;
  allocator->bytes_allocated += size;

  if (allocator->bytes_allocated > allocator->committed) {
    void *commit_ptr = (void *)((uint8_t *)allocator->base_ptr + allocator->committed);

    // it's possible that more than one page needs to be allocated, depending on the input size
    uint64_t commit_size = RoundUp(allocator->bytes_allocated - allocator->committed, KB(64));
    VirtualAlloc(commit_ptr, commit_size, MEM_COMMIT, PAGE_READWRITE);
    allocator->committed += commit_size;
  }

  return result;
}

Optimized linear allocators are just one example of what becomes possible when memory allocation is decoupled from the heap. More complex allocators can be built using the same virtual memory techniques.

Conclusion

Many classic data structures rely on a heap-based allocation strategy. Revisiting that assumption with virtual memory can lead to simpler, faster, and more correct alternatives.

This article showed that both dynamic arrays and linear allocators can be made more efficient by first reserving a large pool of memory and only committing virtual pages as necessary. Virtual memory techniques apply to many other data structures as well.

As with everything, there are trade-offs when using virtual memory in this way. Virtual address space, while abundant for the needs of most software, is limited. When used deliberately, however, it can be an incredibly useful tool.

---

1. https://devblogs.microsoft.com/oldnewthing/20091002-00/?p=16513

2. https://devblogs.microsoft.com/oldnewthing/20170512-00/?p=96146

3. https://devblogs.microsoft.com/oldnewthing/20210510-00/?p=105200

4. https://devblogs.microsoft.com/oldnewthing/20031008-00/?p=42223

5. https://learn.microsoft.com/en-us/windows-hardware/drivers/gettingstarted/virtual-address-spaces