Data Structures & AlgorithmsArray Memory Model & Contiguous Storage

Array Memory Model & Contiguous Storage

LevelBeginner

Duration55 mins

TopicArray Memory Model & Contiguous Storage

2 / 4

Contiguous Memory Allocation and Its Implications

The Deeper Story of Array Allocation

In the previous page, we established that arrays live in contiguous memory. But how does that contiguous block get allocated? What happens when you request an array of a million elements? And what are the consequences of requiring a single unbroken stretch of memory?

These questions take us from the logical model of arrays into the pragmatic reality of memory management—a domain where theoretical efficiency meets the messy constraints of real hardware, operating systems, and concurrent programs fighting for resources.

What You Will Learn

By the end of this page, you will understand the mechanics of contiguous memory allocation, the critical differences between stack and heap allocation, how fragmentation threatens array allocation, and why these details matter for designing reliable, high-performance systems.

What 'Contiguous Allocation' Actually Means

When we say an array requires "contiguous allocation," we mean the entire array—from the first element to the last—must occupy a single, uninterrupted region of memory. This isn't a preference; it's a requirement for the address formula to work.

The requirements for contiguous allocation:

Single block — The memory manager must find or create a region large enough to hold all elements.
No internal gaps — Within that block, elements are packed tightly. There's no "empty space" between arr[5] and arr[6].
Exclusive ownership — Once allocated to an array, that memory region belongs to the array until freed. Other allocations cannot intrude.
Fixed position — The block stays at its base address. Moving it would require updating every reference to the array.

The Contiguity Constraint Is Non-Negotiable

Unlike linked structures where elements can be scattered across memory, arrays require finding a single block large enough for the entire allocation. This is fundamentally harder, especially as the requested size grows. A 1GB array needs a 1GB continuous region—no substitutes.

Why this constraint exists:

The constraint directly enables the O(1) addressing formula. If elements could be scattered, we'd need some form of indirection (like a table of pointers) to locate each element, adding overhead and complexity. The contiguity requirement is the price we pay for direct index-to-address arithmetic.

The allocator's challenge:

Memory allocators (whether the operating system or a runtime like the JVM or Python interpreter) must satisfy requests for contiguous blocks. If the system has 10GB of free memory but it's fragmented into 1000 separate 10MB chunks, a request for a 100MB array will fail—even though there's plenty of total free memory. This fragmentation problem is a central challenge in systems programming.

Stack vs. Heap Allocation

Arrays can be allocated in two fundamentally different regions of memory: the stack and the heap. Understanding this distinction is crucial for both performance and correctness.

The Stack:

The stack is a region of memory that grows and shrinks automatically as functions are called and return. It operates in LIFO (Last-In-First-Out) order—the most recent allocation is always freed first.

Stack-allocated arrays:

Size must be known at compile time (in most languages)
Allocation is extremely fast (just move a pointer)
Automatically deallocated when function returns
Limited total size (typically a few MB)
Cannot be resized or returned from a function

Stack Allocation Example
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void processData() {
    // Stack-allocated array - size known at compile time
    int localArray[100];
    
    // localArray exists only while processData() is running
    for (int i = 0; i < 100; i++) {
        localArray[i] = i * 2;
    }
    
    // When processData() returns, localArray is automatically
    // deallocated (the stack frame is popped)
}
 
// WARNING: Never return a pointer to a stack-allocated array!
int* badFunction() {
    int arr[10];
    return arr;  // UNDEFINED BEHAVIOR - arr is gone after return
}

The Heap:

The heap is a larger, more flexible memory region. Allocations can be any size (up to available memory), persist beyond function boundaries, and be freed explicitly when no longer needed.

Heap-allocated arrays:

Size can be determined at runtime
Allocation is slower (memory manager must find a suitable block)
Must be explicitly freed (or garbage collected)
Can be much larger than stack arrays
Can be resized (via reallocation)
Can be returned from functions safely

Heap Allocation Example
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdlib.h>
 
int* createArray(int size) {
    // Heap-allocated array - size can be runtime value
    int* arr = (int*)malloc(size * sizeof(int));
    
    if (arr == NULL) {
        // Allocation failed - not enough contiguous memory
        return NULL;
    }
    
    for (int i = 0; i < size; i++) {
        arr[i] = i * 2;
    }
    
    // Safe to return - arr persists beyond this function
    return arr;
}
 
void useArray() {
    int* myArray = createArray(1000000);  // 1 million elements
    
    if (myArray != NULL) {
        // Use the array...
        
        // When done, we MUST free it to avoid memory leak
        free(myArray);
        myArray = NULL;  // Good practice: null the pointer
    }
}

Stack vs. Heap Array Allocation
Characteristic	Stack Allocation	Heap Allocation
Speed	Extremely fast (pointer bump)	Slower (search for free block)
Size flexibility	Fixed at compile time	Dynamic at runtime
Max size	Small (1-8 MB typical)	Large (up to available RAM)
Lifetime	Function scope only	Until explicitly freed
Fragmentation risk	None (LIFO deallocation)	High with many allocations
Memory leaks	Impossible	Possible if not freed
Thread safety	Each thread has own stack	Shared, requires care

Heap Allocation Mechanics

When you request a heap-allocated array, a complex process occurs behind the scenes. Understanding this process reveals why allocation has costs and can fail.

The allocation process:

Request arrives — Your program calls malloc(n) or equivalent, requesting n bytes of contiguous memory.
Allocator searches — The memory allocator searches its data structures for a free block of at least n bytes.
Block selection — Various strategies exist: first-fit (take the first suitable block), best-fit (take the smallest suitable block), or more sophisticated approaches.
Block preparation — If the found block is larger than needed, it may be split. Metadata is updated to track the allocation.
Address returned — The base address of the allocated block is returned to your program.
Failure case — If no suitable contiguous block exists, allocation fails (returning NULL in C, throwing OutOfMemoryError in Java, etc.).

Allocator Overhead

Memory allocators typically store metadata alongside each allocation—at minimum, the block size. This means requesting 100 bytes might actually consume 104 or 108 bytes. Large allocations have proportionally tiny overhead; many small allocations have significant overhead.

Why heap allocation is slower:

Search time — Finding a suitable block requires traversing free lists or other data structures.
Synchronization — In multi-threaded programs, the heap is shared. Allocations may require locks to prevent corruption.
Bookkeeping — Updating metadata (block sizes, free lists) adds overhead.
Potential system calls — If the heap needs to grow, the allocator must request more memory from the operating system.

When allocation fails:

Contrary to popular belief, running out of memory doesn't always mean RAM is exhausted. For arrays, the most common cause is fragmentation—plenty of total free memory, but no single contiguous block large enough for the requested array.

Common Causes of Allocation Failure

•External fragmentation — Free memory is scattered in blocks too small to satisfy the request.
•Memory exhaustion — Total free memory is genuinely insufficient.
•Per-process limits — Operating system limits on process memory have been reached.
•Address space limits — On 32-bit systems, the virtual address space (4GB) may be exhausted before physical RAM.
•Heap corruption — A bug has damaged allocator metadata, causing it to malfunction.

Memory Fragmentation

Fragmentation is the nemesis of contiguous allocation. It occurs when free memory becomes broken into many small, non-adjacent pieces. For arrays—which require contiguous blocks—fragmentation can be catastrophic.

Types of fragmentation:

External Fragmentation:

Free memory exists but is scattered in pieces too small to satisfy a request.

Memory state (X = used, . = free):
XXXX....XXX...XXXXX....XX..XXXX....XXX

Total free: 20 units
Largest contiguous free: 4 units
Request for 10 units: FAILS

Despite 20 units of free memory, no array larger than 4 units can be allocated.

Internal Fragmentation:

Allocated blocks are larger than requested, wasting space within the block.

Requested: 100 bytes
Allocated: 128 bytes (next power of 2, common strategy)
Wasted: 28 bytes

This wasted space cannot be used for other allocations and accumulates with many small allocations.

Fragmentation Creeps In Over Time

Fragmentation often isn't visible in short tests. A server running for months with varied allocation patterns may slowly fragment memory until a previously-successful allocation fails. This is why long-running systems require careful memory management and monitoring.

How arrays are particularly vulnerable:

Size variability — Arrays come in all sizes. A pattern of allocating and freeing different-sized arrays creates irregular gaps.
No partial satisfaction — Unlike some data structures that can use scattered memory, arrays need the full block. 99% of the needed space is as useless as 0%.
Long-lived allocations — Arrays often persist for extended periods, creating "anchors" that prevent compaction of surrounding free space.
Growth patterns — Dynamic arrays that double in size create progressively larger allocations, increasing the chance of fragmentation-induced failure.

Strategies to Mitigate Fragmentation

•Object pools — Pre-allocate a pool of fixed-size objects; reuse instead of allocating/freeing.
•Slab allocators — Group allocations by size class to reduce external fragmentation.
•Compacting garbage collectors — Some runtimes can move allocations to defragment the heap.
•Memory arenas — Allocate a large block upfront and sub-allocate from it; free the entire arena at once.
•Conservative sizing — Allocate arrays with some slack to avoid frequent resizing.

Virtual Memory and Arrays

Modern operating systems use virtual memory to provide each process with its own address space. This abstraction layer affects how array allocation works in practice.

The virtual memory abstraction:

Each process sees a clean, linear address space (typically 0 to 2⁴⁸ or larger).
The OS maps virtual addresses to physical RAM behind the scenes.
Physical memory can be fragmented; virtual memory appears contiguous.
Pages (typically 4KB) are the unit of mapping.

Implications for arrays:

Contiguity is in the virtual space — An array appears contiguous to your program, but the underlying physical pages may be scattered. This is fine—your program only sees virtual addresses.
Lazy allocation — Many systems don't map physical memory until pages are actually accessed. A 1GB array allocation might not immediately consume 1GB of RAM.
Overcommit — Some operating systems allow allocating more virtual memory than physical RAM exists, relying on the fact that not all allocations will be fully used. This can lead to out-of-memory conditions when memory is actually accessed.

Virtual Memory Is Your Friend

Virtual memory means you can often allocate larger arrays than you might expect. Physical fragmentation is the OS's problem, not yours. However, accessing the memory still requires physical RAM—virtual memory isn't infinite, and touching all elements of a huge array still requires real resources.

Page faults and performance:

When an array element is accessed for the first time (in a lazy allocation system), a page fault occurs:

The program attempts to access an unmapped virtual address.
The CPU traps to the operating system.
The OS allocates a physical page and updates the page table.
The program resumes, unaware of the interruption.

Page faults are expensive (thousands of CPU cycles). Sequential array access causes minimal page faults (each page serves many accesses). Random access in a large array can cause frequent page faults if the working set doesn't fit in RAM.

Physical vs. Virtual Memory for Arrays
Aspect	Physical Memory View	Virtual Memory View (Your Program)
Contiguity	May be scattered across RAM	Always contiguous
Fragmentation	Handled by OS	Invisible to program
Allocation size limit	Total physical RAM	Virtual address space (huge)
Speed	Direct access	Translation via page tables
Overcommit	N/A	Possible; risks OOM on access

Cache Implications of Contiguous Layout

One of the greatest practical benefits of contiguous array storage is cache friendliness. Understanding this requires knowing how CPU caches work.

The cache hierarchy:

Modern CPUs have multiple levels of cache between the processor and main memory:

L1 Cache: ~32KB, ~4 cycles latency
L2 Cache: ~256KB, ~12 cycles latency
L3 Cache: ~8MB (shared), ~40 cycles latency
Main Memory (RAM): ~100+ cycles latency

When you access memory, the CPU doesn't fetch just the requested byte—it fetches an entire cache line (typically 64 bytes). This line is stored in the cache, making subsequent accesses to nearby addresses extremely fast.

Why contiguous arrays benefit:

Cache Advantages of Arrays

•Spatial locality — When you access arr[i], arr[i+1] through arr[i+15] (for 4-byte integers) are likely already in cache because they're on the same cache line.
•Predictable access patterns — Sequential traversal is highly predictable; CPUs can prefetch upcoming cache lines before they're needed.
•Minimal cache misses — With 64-byte cache lines and 4-byte integers, traversing an array causes a cache miss only once every 16 elements.
•Hardware prefetching — Modern CPUs detect sequential access patterns and automatically prefetch data, eliminating even those periodic misses.

The performance impact:

The difference between cached and uncached access is enormous—often 10x to 100x. This means:

Sequential array traversal: ~1-2 cycles per element (cached)
Random array access (large array): ~100+ cycles per access (frequent cache misses)

This explains why algorithms that access arrays sequentially often outperform theoretically equivalent algorithms with random access patterns, even if Big O analysis suggests similar performance.

The Linked List Comparison

In contrast to arrays, linked list nodes can be scattered throughout memory. Each node access may be a cache miss, adding ~100 cycles of latency. This is why arrays often outperform linked lists for traversal, even though both are O(n)—the constants differ dramatically due to cache behavior.

Memory Alignment

Alignment refers to placing data at memory addresses that are multiples of certain values. This detail affects both performance and correctness of array access.

Why alignment matters:

Hardware requirements — Many CPUs require or strongly prefer that multi-byte values be aligned. A 4-byte integer should be at an address divisible by 4; an 8-byte double at an address divisible by 8.
Performance — Misaligned access may work but require multiple memory operations, halving (or worse) performance.
Atomicity — Aligned loads/stores are often atomic; misaligned ones may not be, causing race conditions in concurrent code.

How arrays are aligned:

When you allocate an array, the runtime ensures:

The base address is aligned to the element type's requirement.
Elements are sized (with padding if necessary) to maintain alignment of subsequent elements.
The overall block size accounts for any alignment padding.

Alignment Effects
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
 
// This struct has 1 + 4 = 5 bytes of data
// But sizeof might be 8 due to alignment padding
struct Example {
    char c;     // 1 byte
    // 3 bytes padding (to align next int)
    int n;      // 4 bytes, must be at 4-byte boundary
};
 
int main() {
    printf("Size of char: %zu\n", sizeof(char));        // 1
    printf("Size of int: %zu\n", sizeof(int));          // 4
    printf("Size of Example: %zu\n", sizeof(struct Example));  // 8, not 5!
    
    // Array of these structs
    struct Example arr[3];
    
    // Each element is 8 bytes apart, ensuring all ints are aligned
    printf("Address of arr[0]: %p\n", (void*)&arr[0]);
    printf("Address of arr[1]: %p\n", (void*)&arr[1]);
    printf("Address of arr[2]: %p\n", (void*)&arr[2]);
    
    return 0;
}

Alignment Is Handled Automatically

In most programming, you don't need to think about alignment—the compiler and allocator handle it. But when working with binary file formats, network protocols, or doing low-level optimization, understanding alignment is essential. Incorrect assumptions about struct sizes are a common source of bugs.

Implications for array indexing:

Because elements are uniformly sized (including alignment padding), the address formula still works:

address(arr[i]) = base_address + i × sizeof(element)

The sizeof operator accounts for padding, so the formula remains valid. This is why you should always use sizeof rather than manually computing sizes—the compiler knows about alignment; your mental calculation probably doesn't.

The Resizing Problem

The contiguity constraint creates a fundamental challenge: arrays cannot grow in place. If you need a larger array, you must allocate a new block and copy all elements.

Why in-place growth is impossible:

Current state:
[ARRAY (10 elements)] [OTHER_DATA] [MORE_DATA] [...]

Want to grow to 20 elements:
[ARRAY (10 elements)] [OTHER_DATA] [MORE_DATA] [...]
                     ↑
                     Can't extend here - memory is occupied

The memory immediately after your array likely contains other allocations. You can't simply claim that space.

The reallocation process:

Allocate a new, larger contiguous block elsewhere.
Copy all existing elements from old block to new block.
Free the old block.
Update the array reference to point to the new block.

Resizing Is Expensive

Copying n elements is O(n) work. If you grow an array one element at a time, each addition is O(n), making n insertions O(n²). This is why dynamic arrays typically double in size when they grow—trading memory for amortized O(1) insertions. We'll explore this strategy in depth in the Static vs. Dynamic Arrays module.

Array Resizing
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdlib.h>
#include <string.h>
 
int* growArray(int* oldArray, int oldSize, int newSize) {
    // 1. Allocate new, larger block
    int* newArray = (int*)malloc(newSize * sizeof(int));
    if (newArray == NULL) return NULL;
    
    // 2. Copy existing elements
    memcpy(newArray, oldArray, oldSize * sizeof(int));
    
    // 3. Free old block
    free(oldArray);
    
    // 4. Return new block (caller must use this address now!)
    return newArray;
}
 
// Usage
void example() {
    int* arr = (int*)malloc(10 * sizeof(int));
    // ... fill arr with data ...
    
    // Need more space
    arr = growArray(arr, 10, 20);  // Note: arr pointer changes!
    
    // Old arr address is now INVALID - the memory is freed
}

Critical implication—pointer invalidation:

When an array is resized, its base address changes. Any pointers or references to the old array become dangling pointers—they point to freed memory. This is a source of many bugs:

Other code holding the old pointer won't know it moved.
Accessing via the old pointer is undefined behavior.
The old memory might be reused for something else, causing silent corruption.

This is why many languages (Java, Python, Go) hide array resizing behind abstractions that automatically update references.

How Languages Handle Array Allocation

Different programming languages provide different levels of abstraction over array memory allocation. Understanding these differences helps you write more effective code in each language.

Array Allocation Across Languages
Language	Static Arrays	Dynamic Arrays	Memory Management
C	Stack or malloc()	Manual realloc()	Manual free()
C++	Stack or new[]	std::vector (auto-resize)	Manual delete[] or RAII
Java	Always heap (new[])	ArrayList (auto-resize)	Garbage collected
Python	N/A	list (auto-resize)	Garbage collected
JavaScript	N/A	Array (auto-resize)	Garbage collected
Rust	Stack arrays	Vec<T> (auto-resize)	Ownership system
Go	Stack or heap	slices (auto-resize)	Garbage collected

What the abstractions hide:

Automatic resizing — High-level languages make arrays appear infinitely growable. Under the hood, they're still reallocating and copying when capacity is exceeded.
Garbage collection — You don't explicitly free arrays, but the GC must track allocations, potentially causing pauses when it runs.
Bounds checking — Many languages automatically check array bounds on every access. This prevents bugs but adds overhead.
Reference semantics — In Java/Python/JS, array variables hold references to heap-allocated arrays. Assignment copies the reference, not the array itself.

The underlying reality is the same:

No matter the language, arrays require contiguous memory. The abstractions hide but don't eliminate the costs. A Python list that grows by one element at a time is still doing O(n) copies internally—you just don't see it happening.

Abstraction Awareness

Higher-level languages make array usage easier but can hide performance implications. If you're hitting performance issues with array operations in any language, understanding the underlying memory model helps you diagnose and fix them—even if you never write malloc() yourself.

Summary: The Allocation Story

We've explored the deep implications of contiguous memory allocation—the design choice that makes arrays both powerful and constrained.

Key Takeaways

•Contiguous means unbroken — Arrays require a single continuous block; partial satisfaction is useless.
•Stack vs. heap matters — Stack allocation is fast but limited and scoped; heap allocation is flexible but slower and requires management.
•Fragmentation threatens arrays — Scattered free memory is worthless for large array allocations.
•Virtual memory helps — The OS provides a contiguous virtual view even if physical memory is fragmented.
•Caches love contiguity — Sequential array access is dramatically faster than random access due to cache line prefetching.
•Alignment ensures efficiency — Elements are spaced to meet hardware requirements, affecting true element size.
•Resizing means copying — Arrays cannot grow in place; reallocation requires copying all elements to a new block.
•Languages hide but don't eliminate costs — High-level abstractions make allocation easier but the underlying realities remain.

What's next:

Now that we understand how arrays are stored and allocated, we'll examine how this layout enables the O(1) random access that makes arrays so powerful. We'll see the exact address calculation in action and understand why this constant-time access is the defining characteristic of the array data structure.

Page Complete

You now understand the allocation mechanics behind arrays—from the heap/stack decision to fragmentation challenges to cache effects. This knowledge is essential for writing performant code and debugging memory-related issues. Next, we'll explore index-based access and address calculation in detail.

2 / 4

Loading learning content...

Data Structures & AlgorithmsArray Memory Model & Contiguous Storage

Array Memory Model & Contiguous Storage

LevelBeginner

Duration55 mins

TopicArray Memory Model & Contiguous Storage

2 / 4

Contiguous Memory Allocation and Its Implications

The Deeper Story of Array Allocation

What You Will Learn

What 'Contiguous Allocation' Actually Means

The requirements for contiguous allocation:

Single block — The memory manager must find or create a region large enough to hold all elements.
No internal gaps — Within that block, elements are packed tightly. There's no "empty space" between arr[5] and arr[6].
Exclusive ownership — Once allocated to an array, that memory region belongs to the array until freed. Other allocations cannot intrude.
Fixed position — The block stays at its base address. Moving it would require updating every reference to the array.

The Contiguity Constraint Is Non-Negotiable

Why this constraint exists:

The allocator's challenge:

Stack vs. Heap Allocation

Arrays can be allocated in two fundamentally different regions of memory: the stack and the heap. Understanding this distinction is crucial for both performance and correctness.

The Stack:

Stack-allocated arrays:

Size must be known at compile time (in most languages)
Allocation is extremely fast (just move a pointer)
Automatically deallocated when function returns
Limited total size (typically a few MB)
Cannot be resized or returned from a function

Stack Allocation Example
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void processData() {
    // Stack-allocated array - size known at compile time
    int localArray[100];
    
    // localArray exists only while processData() is running
    for (int i = 0; i < 100; i++) {
        localArray[i] = i * 2;
    }
    
    // When processData() returns, localArray is automatically
    // deallocated (the stack frame is popped)
}
 
// WARNING: Never return a pointer to a stack-allocated array!
int* badFunction() {
    int arr[10];
    return arr;  // UNDEFINED BEHAVIOR - arr is gone after return
}

The Heap:

The heap is a larger, more flexible memory region. Allocations can be any size (up to available memory), persist beyond function boundaries, and be freed explicitly when no longer needed.

Heap-allocated arrays:

Size can be determined at runtime
Allocation is slower (memory manager must find a suitable block)
Must be explicitly freed (or garbage collected)
Can be much larger than stack arrays
Can be resized (via reallocation)
Can be returned from functions safely

Heap Allocation Example
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdlib.h>
 
int* createArray(int size) {
    // Heap-allocated array - size can be runtime value
    int* arr = (int*)malloc(size * sizeof(int));
    
    if (arr == NULL) {
        // Allocation failed - not enough contiguous memory
        return NULL;
    }
    
    for (int i = 0; i < size; i++) {
        arr[i] = i * 2;
    }
    
    // Safe to return - arr persists beyond this function
    return arr;
}
 
void useArray() {
    int* myArray = createArray(1000000);  // 1 million elements
    
    if (myArray != NULL) {
        // Use the array...
        
        // When done, we MUST free it to avoid memory leak
        free(myArray);
        myArray = NULL;  // Good practice: null the pointer
    }
}

Stack vs. Heap Array Allocation
Characteristic	Stack Allocation	Heap Allocation
Speed	Extremely fast (pointer bump)	Slower (search for free block)
Size flexibility	Fixed at compile time	Dynamic at runtime
Max size	Small (1-8 MB typical)	Large (up to available RAM)
Lifetime	Function scope only	Until explicitly freed
Fragmentation risk	None (LIFO deallocation)	High with many allocations
Memory leaks	Impossible	Possible if not freed
Thread safety	Each thread has own stack	Shared, requires care

Heap Allocation Mechanics

When you request a heap-allocated array, a complex process occurs behind the scenes. Understanding this process reveals why allocation has costs and can fail.

The allocation process:

Request arrives — Your program calls malloc(n) or equivalent, requesting n bytes of contiguous memory.
Allocator searches — The memory allocator searches its data structures for a free block of at least n bytes.
Block selection — Various strategies exist: first-fit (take the first suitable block), best-fit (take the smallest suitable block), or more sophisticated approaches.
Block preparation — If the found block is larger than needed, it may be split. Metadata is updated to track the allocation.
Address returned — The base address of the allocated block is returned to your program.
Failure case — If no suitable contiguous block exists, allocation fails (returning NULL in C, throwing OutOfMemoryError in Java, etc.).

Allocator Overhead

Why heap allocation is slower:

Search time — Finding a suitable block requires traversing free lists or other data structures.
Synchronization — In multi-threaded programs, the heap is shared. Allocations may require locks to prevent corruption.
Bookkeeping — Updating metadata (block sizes, free lists) adds overhead.
Potential system calls — If the heap needs to grow, the allocator must request more memory from the operating system.

When allocation fails:

Common Causes of Allocation Failure

•External fragmentation — Free memory is scattered in blocks too small to satisfy the request.
•Memory exhaustion — Total free memory is genuinely insufficient.
•Per-process limits — Operating system limits on process memory have been reached.
•Address space limits — On 32-bit systems, the virtual address space (4GB) may be exhausted before physical RAM.
•Heap corruption — A bug has damaged allocator metadata, causing it to malfunction.

Memory Fragmentation

Types of fragmentation:

External Fragmentation:

Free memory exists but is scattered in pieces too small to satisfy a request.

Memory state (X = used, . = free):
XXXX....XXX...XXXXX....XX..XXXX....XXX

Total free: 20 units
Largest contiguous free: 4 units
Request for 10 units: FAILS

Despite 20 units of free memory, no array larger than 4 units can be allocated.

Internal Fragmentation:

Allocated blocks are larger than requested, wasting space within the block.

Requested: 100 bytes
Allocated: 128 bytes (next power of 2, common strategy)
Wasted: 28 bytes

This wasted space cannot be used for other allocations and accumulates with many small allocations.

Fragmentation Creeps In Over Time

How arrays are particularly vulnerable:

Size variability — Arrays come in all sizes. A pattern of allocating and freeing different-sized arrays creates irregular gaps.
No partial satisfaction — Unlike some data structures that can use scattered memory, arrays need the full block. 99% of the needed space is as useless as 0%.
Long-lived allocations — Arrays often persist for extended periods, creating "anchors" that prevent compaction of surrounding free space.
Growth patterns — Dynamic arrays that double in size create progressively larger allocations, increasing the chance of fragmentation-induced failure.

Strategies to Mitigate Fragmentation

•Object pools — Pre-allocate a pool of fixed-size objects; reuse instead of allocating/freeing.
•Slab allocators — Group allocations by size class to reduce external fragmentation.
•Compacting garbage collectors — Some runtimes can move allocations to defragment the heap.
•Memory arenas — Allocate a large block upfront and sub-allocate from it; free the entire arena at once.
•Conservative sizing — Allocate arrays with some slack to avoid frequent resizing.

Virtual Memory and Arrays

Modern operating systems use virtual memory to provide each process with its own address space. This abstraction layer affects how array allocation works in practice.

The virtual memory abstraction:

Each process sees a clean, linear address space (typically 0 to 2⁴⁸ or larger).
The OS maps virtual addresses to physical RAM behind the scenes.
Physical memory can be fragmented; virtual memory appears contiguous.
Pages (typically 4KB) are the unit of mapping.

Implications for arrays:

Contiguity is in the virtual space — An array appears contiguous to your program, but the underlying physical pages may be scattered. This is fine—your program only sees virtual addresses.
Lazy allocation — Many systems don't map physical memory until pages are actually accessed. A 1GB array allocation might not immediately consume 1GB of RAM.
Overcommit — Some operating systems allow allocating more virtual memory than physical RAM exists, relying on the fact that not all allocations will be fully used. This can lead to out-of-memory conditions when memory is actually accessed.

Virtual Memory Is Your Friend

Page faults and performance:

When an array element is accessed for the first time (in a lazy allocation system), a page fault occurs:

The program attempts to access an unmapped virtual address.
The CPU traps to the operating system.
The OS allocates a physical page and updates the page table.
The program resumes, unaware of the interruption.

Physical vs. Virtual Memory for Arrays
Aspect	Physical Memory View	Virtual Memory View (Your Program)
Contiguity	May be scattered across RAM	Always contiguous
Fragmentation	Handled by OS	Invisible to program
Allocation size limit	Total physical RAM	Virtual address space (huge)
Speed	Direct access	Translation via page tables
Overcommit	N/A	Possible; risks OOM on access

Cache Implications of Contiguous Layout

One of the greatest practical benefits of contiguous array storage is cache friendliness. Understanding this requires knowing how CPU caches work.

The cache hierarchy:

Modern CPUs have multiple levels of cache between the processor and main memory:

L1 Cache: ~32KB, ~4 cycles latency
L2 Cache: ~256KB, ~12 cycles latency
L3 Cache: ~8MB (shared), ~40 cycles latency
Main Memory (RAM): ~100+ cycles latency

Why contiguous arrays benefit:

Cache Advantages of Arrays

•Spatial locality — When you access arr[i], arr[i+1] through arr[i+15] (for 4-byte integers) are likely already in cache because they're on the same cache line.
•Predictable access patterns — Sequential traversal is highly predictable; CPUs can prefetch upcoming cache lines before they're needed.
•Minimal cache misses — With 64-byte cache lines and 4-byte integers, traversing an array causes a cache miss only once every 16 elements.
•Hardware prefetching — Modern CPUs detect sequential access patterns and automatically prefetch data, eliminating even those periodic misses.

The performance impact:

The difference between cached and uncached access is enormous—often 10x to 100x. This means:

Sequential array traversal: ~1-2 cycles per element (cached)
Random array access (large array): ~100+ cycles per access (frequent cache misses)

This explains why algorithms that access arrays sequentially often outperform theoretically equivalent algorithms with random access patterns, even if Big O analysis suggests similar performance.

The Linked List Comparison

Memory Alignment

Alignment refers to placing data at memory addresses that are multiples of certain values. This detail affects both performance and correctness of array access.

Why alignment matters:

Hardware requirements — Many CPUs require or strongly prefer that multi-byte values be aligned. A 4-byte integer should be at an address divisible by 4; an 8-byte double at an address divisible by 8.
Performance — Misaligned access may work but require multiple memory operations, halving (or worse) performance.
Atomicity — Aligned loads/stores are often atomic; misaligned ones may not be, causing race conditions in concurrent code.

How arrays are aligned:

When you allocate an array, the runtime ensures:

The base address is aligned to the element type's requirement.
Elements are sized (with padding if necessary) to maintain alignment of subsequent elements.
The overall block size accounts for any alignment padding.

Alignment Effects
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
 
// This struct has 1 + 4 = 5 bytes of data
// But sizeof might be 8 due to alignment padding
struct Example {
    char c;     // 1 byte
    // 3 bytes padding (to align next int)
    int n;      // 4 bytes, must be at 4-byte boundary
};
 
int main() {
    printf("Size of char: %zu\n", sizeof(char));        // 1
    printf("Size of int: %zu\n", sizeof(int));          // 4
    printf("Size of Example: %zu\n", sizeof(struct Example));  // 8, not 5!
    
    // Array of these structs
    struct Example arr[3];
    
    // Each element is 8 bytes apart, ensuring all ints are aligned
    printf("Address of arr[0]: %p\n", (void*)&arr[0]);
    printf("Address of arr[1]: %p\n", (void*)&arr[1]);
    printf("Address of arr[2]: %p\n", (void*)&arr[2]);
    
    return 0;
}

Alignment Is Handled Automatically

Implications for array indexing:

Because elements are uniformly sized (including alignment padding), the address formula still works:

address(arr[i]) = base_address + i × sizeof(element)

The Resizing Problem

The contiguity constraint creates a fundamental challenge: arrays cannot grow in place. If you need a larger array, you must allocate a new block and copy all elements.

Why in-place growth is impossible:

Current state:
[ARRAY (10 elements)] [OTHER_DATA] [MORE_DATA] [...]

Want to grow to 20 elements:
[ARRAY (10 elements)] [OTHER_DATA] [MORE_DATA] [...]
                     ↑
                     Can't extend here - memory is occupied

The memory immediately after your array likely contains other allocations. You can't simply claim that space.

The reallocation process:

Allocate a new, larger contiguous block elsewhere.
Copy all existing elements from old block to new block.
Free the old block.
Update the array reference to point to the new block.

Resizing Is Expensive

Array Resizing
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdlib.h>
#include <string.h>
 
int* growArray(int* oldArray, int oldSize, int newSize) {
    // 1. Allocate new, larger block
    int* newArray = (int*)malloc(newSize * sizeof(int));
    if (newArray == NULL) return NULL;
    
    // 2. Copy existing elements
    memcpy(newArray, oldArray, oldSize * sizeof(int));
    
    // 3. Free old block
    free(oldArray);
    
    // 4. Return new block (caller must use this address now!)
    return newArray;
}
 
// Usage
void example() {
    int* arr = (int*)malloc(10 * sizeof(int));
    // ... fill arr with data ...
    
    // Need more space
    arr = growArray(arr, 10, 20);  // Note: arr pointer changes!
    
    // Old arr address is now INVALID - the memory is freed
}

Critical implication—pointer invalidation:

When an array is resized, its base address changes. Any pointers or references to the old array become dangling pointers—they point to freed memory. This is a source of many bugs:

Other code holding the old pointer won't know it moved.
Accessing via the old pointer is undefined behavior.
The old memory might be reused for something else, causing silent corruption.

This is why many languages (Java, Python, Go) hide array resizing behind abstractions that automatically update references.

How Languages Handle Array Allocation

Different programming languages provide different levels of abstraction over array memory allocation. Understanding these differences helps you write more effective code in each language.

Array Allocation Across Languages
Language	Static Arrays	Dynamic Arrays	Memory Management
C	Stack or malloc()	Manual realloc()	Manual free()
C++	Stack or new[]	std::vector (auto-resize)	Manual delete[] or RAII
Java	Always heap (new[])	ArrayList (auto-resize)	Garbage collected
Python	N/A	list (auto-resize)	Garbage collected
JavaScript	N/A	Array (auto-resize)	Garbage collected
Rust	Stack arrays	Vec<T> (auto-resize)	Ownership system
Go	Stack or heap	slices (auto-resize)	Garbage collected

What the abstractions hide:

Automatic resizing — High-level languages make arrays appear infinitely growable. Under the hood, they're still reallocating and copying when capacity is exceeded.
Garbage collection — You don't explicitly free arrays, but the GC must track allocations, potentially causing pauses when it runs.
Bounds checking — Many languages automatically check array bounds on every access. This prevents bugs but adds overhead.
Reference semantics — In Java/Python/JS, array variables hold references to heap-allocated arrays. Assignment copies the reference, not the array itself.

The underlying reality is the same:

Abstraction Awareness

Summary: The Allocation Story

We've explored the deep implications of contiguous memory allocation—the design choice that makes arrays both powerful and constrained.

Key Takeaways

•Contiguous means unbroken — Arrays require a single continuous block; partial satisfaction is useless.
•Stack vs. heap matters — Stack allocation is fast but limited and scoped; heap allocation is flexible but slower and requires management.
•Fragmentation threatens arrays — Scattered free memory is worthless for large array allocations.
•Virtual memory helps — The OS provides a contiguous virtual view even if physical memory is fragmented.
•Caches love contiguity — Sequential array access is dramatically faster than random access due to cache line prefetching.
•Alignment ensures efficiency — Elements are spaced to meet hardware requirements, affecting true element size.
•Resizing means copying — Arrays cannot grow in place; reallocation requires copying all elements to a new block.
•Languages hide but don't eliminate costs — High-level abstractions make allocation easier but the underlying realities remain.

What's next:

Page Complete

2 / 4