Dynamic arrays: memory and performance optimization for developers

Optimizing Dynamic Arrays: Memory Management Strategies for Developers

Dynamic arrays are a core data structure, but their performance often suffers from poor memory management. The main culprit is reallocation, which can turn an O(1) insertion into O(n). Let's dive into practical optimization strategies, from growth factors to capacity reservation and small vector optimizations.

The Reallocation Problem and Exponential Growth

A naive dynamic array implementation that grows by one element on each overflow leads to disastrous performance. Inserting 1000 elements requires 1000 reallocations and copying 500,500 elements. The fix? Exponential capacity growth, typically doubling.

void add_message(log_buffer_t *buf, const char *msg) {
    if (buf->size >= buf->capacity) {
        buf->capacity = buf->capacity ? buf->capacity * 2 : 16;
        buf->messages = realloc(buf->messages, 
                               buf->capacity * sizeof(char*));
    }
    buf->messages[buf->size++] = strdup(msg);
}

Results for 1000 elements:

• Reallocations: 7 (vs. 1000).
• Copied elements: ~2000 (vs. 500,500).
• Speedup: 60x.

Over-allocation strategies to cut latency are used across systems:

• String builders (like StringBuilder) avoid O(n²) concatenation.
• TCP network buffers reduce system calls.
• Memory allocators use size classes to fight fragmentation.
• Database logs pre-allocate in blocks to minimize disk I/O.

Growth Factor Implementation and Analysis

A basic C dynamic array includes a data pointer, size, and capacity. The critical vector_push function checks for reallocation.

Choosing a growth factor balances speed and memory use:

• 2× growth: Standard (std::vector, Python lists). Fast (bit-shift friendly), minimizes reallocs, but wastes up to 50% memory.
• 1.5× growth: Used in some libs (e.g., folly). More memory-efficient (~33% waste), but more reallocs.
• φ (1.618): Theoretical sweet spot.

Benchmark growing to 1M elements:

• 1.5×: 34 reallocs, 1.5 MB peak memory, 12 ms.
• 2×: 20 reallocs, 2 MB peak memory, 8 ms.

Recommendation: Use 2× when memory is plentiful for top speed.

Shrinking Capacity and Reservations

Auto-shrinking on deletions can cause performance thrashing if size hovers near thresholds. Shrinking when size < capacity / 2 triggers frequent reallocs.

Best practices:

• Hysteresis: Shrink only when size < capacity / 4 for a buffer zone.
• Explicit shrink: Offer a shrink_to_fit for manual control.

Reserve upfront if you know the final size to skip reallocs entirely.

vector_reserve(&v, 1000);
for (int i = 0; i < 1000; i++) {
    vector_push(&v, i); // No reallocs
}

Benchmark (1000 elements):

• No reserve: 7 reallocs, 45 µs.
• Reserved: 1 realloc, 12 µs (3.75x faster).

Small Vector Optimization

For tiny vectors, heap allocation overhead dominates. The solution: small vector optimization—store the first N elements inline.

#define SMALL_SIZE 16
typedef struct {
    int small_data[SMALL_SIZE]; // Inline storage
    int *data;                  // Heap pointer on overflow
    size_t size;
    size_t capacity;
} small_vector_t;

Pros:

• Zero allocations for ≤16 elements.
• Better cache locality.
• Blazing fast for small collections.

Cons:

• Larger struct size.
• Copy overhead on heap transition.

Key Takeaways

• Exponential growth (2× factor) drops amortized insert cost from O(n) to O(1).
• Reserving known sizes eliminates reallocs and boosts speed dramatically.
• Auto-shrinking is often harmful; prefer hysteresis or manual methods.
• Small vector optimization kills allocation overhead for tiny collections.
• Growth factor choice trades speed for memory efficiency.

— Editorial Team