ARTICLE

Memory allocation is a software abstraction over physical constraints.

A systems note on how allocation APIs hide layout, locality, fragmentation, and hardware realities.

Published January 17, 2024

Systems
OS
Memory

A call to malloc looks almost trivial. The program provides a size, the allocator returns an address, and a new region of memory appears to exist:

void *buffer = malloc(4096);

From the program’s perspective, the operation is complete. It now owns a contiguous range of addresses that can be read from and written to according to the rules of the language.

Physically, however, very little may have happened. The allocator might have reused an old block, split a larger free region, extended one of its internal arenas, requested additional virtual pages from the operating system, or merely reserved an address range that will not receive physical backing until the program touches it.

The returned pointer hides nearly everything that determines the real cost of the allocation. It does not reveal whether the pages are resident in RAM, where the physical frames are located, which NUMA node owns them, how the block aligns with cache lines, how much allocator metadata surrounds it, or whether the allocation has increased fragmentation elsewhere in the heap.

Memory allocation is therefore not the creation of storage. It is a software agreement about ownership and addressability, implemented over hardware that has finite capacity, fixed access granularities, non-uniform latency, physical distance, and strict layout constraints.

Allocation Does Not Create Memory

The simplest mental model of allocation is that the operating system finds a fresh sequence of physical bytes and hands it directly to the process. General-purpose systems rarely work this way because physical memory is not exposed directly to ordinary programs.

A user-space allocator usually manages regions of virtual address space that it has previously obtained from the operating system. It divides these regions into blocks, records which blocks are available, and returns addresses within them when the program requests storage.

The operating system separately manages virtual pages and physical page frames. An allocated virtual page may currently be backed by RAM, mapped to a file, shared with another process, represented by a common zero page, moved to secondary storage, or reserved without any physical frame assigned to it.

The relationship can be represented as:

\text{allocation request} \rightarrow \text{allocator block} \rightarrow \text{virtual pages} \rightarrow \text{physical frames}

These layers describe different things. An allocator block represents software ownership, a virtual page represents an address-translation unit, and a physical frame represents actual hardware storage.

For an allocation of $S$ bytes and a page size of $P$ , the number of virtual pages involved is approximately:

N_{\text{pages}} = \left\lceil \frac{S}{P} \right\rceil

Reserving those virtual pages does not necessarily allocate the same number of physical frames immediately. Many systems delay physical allocation until the process first accesses each page, which allows an allocation to succeed before all of its physical cost has been paid.

The returned pointer is therefore a promise that an address range belongs to the process. It is not proof that every byte in that range currently exists in physical memory.

Virtual Memory Creates the Illusion of Contiguity

Most pointers used by application software contain virtual addresses rather than physical addresses. Before the processor can access the requested data, the virtual address must be translated through the page-table system or through a cached translation stored in the translation lookaside buffer.

A virtual address can be viewed as a virtual page number combined with an offset inside that page:

A_{\text{virtual}} = \text{virtual page number} + \text{page offset}

Address translation replaces the virtual page number with a physical frame number while preserving the offset:

A_{\text{physical}} = \text{physical frame number} + \text{page offset}

This indirection allows a program to observe one continuous address range even when its physical pages are scattered throughout RAM. Four consecutive virtual pages might map to physical frames numbered (812), (107), (4091), and (56), yet the program can still traverse them using ordinary pointer arithmetic.

The allocation is therefore contiguous only within the process’s virtual address space. At the hardware level, it may be distributed across memory banks, channels, cache sets, physical regions, or even NUMA nodes.

This distinction allows the operating system to provide isolation, flexible placement, sparse mappings, shared libraries, memory-mapped files, and demand paging. It also means that the apparent shape of an allocation can differ radically from its physical layout.

A Pointer Is a Name, Not a Physical Location

Programmers frequently treat a pointer as though it identifies one permanent place in the machine. In reality, a pointer identifies a virtual location whose physical backing may change while the virtual address remains unchanged.

The operating system may migrate a page between NUMA nodes, reclaim it temporarily, write it to secondary storage, replace it during copy-on-write, or remap it to another physical frame. None of these changes necessarily alter the pointer visible to the application.

This separation between address identity and physical location is one of the foundations of modern operating systems. It gives software stable names while allowing the kernel to rearrange the physical resources beneath those names.

The abstraction is powerful, but it hides topology. Two pointers separated by only a few bytes virtually may still participate in accesses whose latency depends on cache state, translation state, page residency, and physical placement.

Every Allocation Is Larger Than Its Payload

When a program requests $n$ bytes, the allocator usually consumes more than exactly $n$ bytes. Additional space may be needed for block headers, free-list links, alignment padding, size-class rounding, security canaries, guard regions, or page-level bookkeeping.

A simplified model of the real allocation cost is:

S_{\text{actual}} = S_{\text{requested}} + S_{\text{metadata}} + S_{\text{padding}}

Many allocators organise small blocks into fixed size classes. A request is rounded upward to the smallest class that can contain it:

S_{\text{class}} = \min {c \mid c \geq S_{\text{requested}}}

The unused space inside the selected class is internal fragmentation:

F_{\text{internal}} = S_{\text{class}} - S_{\text{requested}}

For example, a request for (33) bytes might be served using a (48)-byte block. The application receives enough usable space, but (15) bytes of the allocator’s block remain unavailable to other objects.

The allocation interface hides this difference because managing every requested byte as a separately shaped object would be expensive. Allocators gain speed and simplicity by operating at coarser granularities, and those granularities inevitably create waste.

Alignment Is Hardware Geometry Exposed Through Software

Objects cannot always begin at arbitrary byte addresses. Many scalar, vector, and hardware-specific data types must be placed at addresses divisible by a particular alignment value.

For an object requiring alignment $k$ , its address $A$ must satisfy:

A \bmod k = 0

An object requiring (16)-byte alignment must therefore begin at an address for which:

A \bmod 16 = 0

If the allocator’s current position is not sufficiently aligned, it must move forward and leave unused padding before the object. Aligning an address $x$ upward to alignment $a$ gives:

x_{\text{aligned}} = \left\lceil \frac{x}{a} \right\rceil a

The resulting padding is:

P = x_{\text{aligned}} - x

Alignment is often presented as a language or application binary interface rule, but its origin is physical. Processors access memory through buses, cache lines, vector lanes, and load-store units that work most efficiently, and sometimes only correctly, when data is placed at suitable boundaries.

The program requests an object of a particular type. The allocator must fit that object into the access geometry of the machine.

Fragmentation Is the Cost of Arbitrary Lifetimes

Dynamic allocation allows objects of different sizes to be created and destroyed in almost any order. This flexibility removes the simple lifetime structure found in stack allocation and replaces it with a continuously changing set of occupied and free intervals.

Internal fragmentation occurs when an allocated block is larger than the requested payload. If a (33)-byte object occupies a (48)-byte block, the internal waste is:

F_{\text{internal}} = 48 - 33 = 15

Its storage utilisation is:

U = \frac{33}{48}

External fragmentation occurs when enough free memory exists in total, but the free memory is divided into blocks that cannot satisfy a larger contiguous request. If the free blocks have sizes $f_1, f_2, \ldots, f_n$ , the total free capacity is:

F_{\text{total}} = \sum_{i=1}^{n} f_i

The largest immediately available allocation is limited by:

S_{\text{max}} = \max_i f_i

It is therefore possible for a request of size $S$ to fail even when:

F_{\text{total}} \geq S

because no individual free region satisfies:

S_{\text{max}} \geq S

The system has enough free capacity numerically, but that capacity does not have the required shape. Allocation is not simply the management of a number of unused bytes; it is the management of intervals, boundaries, and placement constraints.

Free Memory Is Not a Single Meaningful Number

Operating systems often report a quantity called free or available memory. While useful, this number cannot completely describe whether a future allocation will succeed or how efficiently it can be served.

The system may have substantial free memory spread across many small regions, concentrated on the wrong NUMA node, unavailable for large pages, or tied up in pages that cannot easily be moved. Some memory may be reclaimable from caches, while other pages may be pinned by devices or kernel subsystems.

For most user-space allocations, physical contiguity is unnecessary because virtual memory can map scattered physical frames into a contiguous virtual range. Hardware devices, direct-memory-access buffers, huge pages, and some kernel structures may require stronger physical layout guarantees.

A machine can therefore have gigabytes of unused memory and still fail to provide one sufficiently large physically contiguous region. The capacity exists, but the required physical geometry does not.

Allocators Trade Space for Time

No allocator can simultaneously minimise allocation latency, metadata overhead, fragmentation, contention, and memory retention for every possible workload. Allocator design is therefore an exercise in choosing which costs to prioritise.

A first-fit allocator selects the first free block large enough to satisfy a request. It can be straightforward and fast, but its placement choices may gradually produce poor fragmentation patterns.

A best-fit allocator searches for the smallest block that can hold the request. This may reduce immediate leftover space, but searching can be slower and may produce many tiny fragments that are difficult to reuse.

Segregated free-list allocators organise available blocks by size class. They can serve common allocation sizes quickly, although class rounding creates internal fragmentation and unused blocks may remain trapped within underutilised classes.

A buddy allocator rounds requests to powers of two:

B = 2^{\lceil \log_2 S \rceil}

The waste for a request of size $S$ is:

F = B-S

Buddy systems make splitting and merging efficient because adjacent blocks have predictable relationships. Their regular structure simplifies coalescing, but power-of-two rounding can consume substantially more memory than the application requested.

Arena allocators make a different trade-off. They place objects sequentially inside a reserved region, making allocation approximately a pointer increment:

p_{\text{new}} = p_{\text{current}} + S_{\text{aligned}}

Individual objects are not usually freed separately. Instead, the entire arena is discarded when all of its objects are no longer needed, providing extremely low overhead when object lifetimes naturally form a common region.

The source-level API may always appear to perform the same operation. The policy beneath it determines whether allocation is a simple local update or a complex search through shared global state.

Allocation Time Is Not Uniform

A source-level allocation call looks as though it should have a predictable cost. The same line of code, however, can take very different execution paths depending on the allocator’s internal state.

A fast allocation may find a suitable block in a thread-local cache, remove it from a list, and return immediately. A slow allocation may require splitting a larger block, acquiring locks, requesting pages from the operating system, modifying page tables, faulting in physical memory, zeroing pages, or reclaiming memory from other parts of the system.

Under favourable conditions, allocation may behave approximately like an $O(1)$ operation. Under pressure, its latency may depend on search length, lock contention, virtual-memory operations, physical-page availability, and kernel reclaim activity.

This distinction is especially important in real-time systems. A low average allocation time is not enough when a rare slow path can violate a strict response-time deadline.

The abstraction hides variability from the source code. It cannot guarantee that the underlying physical work is equally cheap every time.

Freeing Memory Does Not Necessarily Return It

Calling free tells the allocator that a block is no longer owned by the application. It does not necessarily cause the surrounding pages to be returned immediately to the operating system.

Returning every small block directly to the kernel would require frequent system calls, mapping changes, and page-management work. General-purpose allocators therefore retain freed blocks in free lists, thread-local caches, slabs, or arenas so that later requests can reuse them efficiently.

This creates three different measurements:

M_{\text{application}} \neq M_{\text{allocator}} \neq M_{\text{resident}}

The application’s live objects may occupy one amount of memory, the allocator may retain a larger virtual region, and the operating system may keep only part of that region resident in RAM. None of these figures alone describes the complete memory state of the process.

Suppose one page contains (64) small objects and (63) of them are freed. If the final object remains live, the allocator may be unable to release the page even though most of its contents are unused.

The live payload might be only:

S_{\text{live}} = S_{\text{object}}

while the retained physical granularity remains:

S_{\text{retained}} = P

This does not necessarily indicate a memory leak. It is often the result of a mismatch between small object lifetimes and page-sized resource ownership.

Object Lifetimes Determine Reclaimability

Allocation behaviour is influenced not only by object size but also by how long objects survive. Mixing short-lived temporary objects with long-lived persistent objects can leave large regions mostly empty but impossible to release.

Consider an allocation order containing long-lived objects $L$ and short-lived objects $S$ :

L,\ S,\ S,\ S,\ L,\ S,\ S,\ L

After the temporary objects are freed, the layout becomes:

L,\ -,\ -,\ -,\ L,\ -,\ -,\ L

Most of the region is now unused, but the surviving objects prevent the allocator from releasing the surrounding pages. This effect is sometimes described as lifetime fragmentation.

Region-based allocation, object pools, and generational garbage collectors improve this behaviour by grouping objects with similar expected lifetimes. When all objects in a region become dead together, the entire region can be reclaimed without individually examining or merging its internal blocks.

If a region contains $n$ objects but can be discarded by resetting one pointer, its reclamation cost can approach:

T_{\text{region free}} \approx O(1)

The advantage is not only faster deallocation. Grouping related lifetimes preserves useful physical structure and makes whole pages easier to return or reuse.

Heap Layout Becomes Cache Behaviour

An allocator chooses addresses, and those addresses determine which objects share cache lines. If the cache-line size is $C$ , the line containing address $A$ can be identified conceptually as:

L(A) = \left\lfloor \frac{A}{C} \right\rfloor

Two objects share a cache line when their addresses fall within the same line-sized interval. This can improve locality when the objects are consumed together, because one line transfer brings both objects into the cache.

The same placement can be harmful when different processor cores repeatedly modify the objects. Although the program regards the values as independent, the coherence system transfers ownership at cache-line granularity.

The number of cache lines touched by an object of size $S$ depends on both its size and its starting offset $O$ :

N_{\text{lines}} = \left\lceil \frac{S+O}{C} \right\rceil

An unfortunate starting position may cause an object to cross an extra cache-line boundary. The allocation API exposes the address but does not describe the surrounding cache geometry or the communication cost created by that placement.

Small Allocations Can Have Large Physical Costs

A program may allocate millions of tiny objects because each allocation appears independent and conceptually inexpensive. The physical cost can be much larger than the logical payload suggests.

Each small object may require allocator metadata, alignment padding, pointer fields, cache-line capacity, address translations, and separate traversal loads. Individually allocated objects are also more likely to be scattered across pages than elements stored in one contiguous array.

For a cache line of size $C$ and a compact record of size $R$ , the ideal number of records carried by each line is:

N = \left\lfloor \frac{C}{R} \right\rfloor

Contiguous storage can therefore amortise one cache-line transfer across several records. A pointer-based structure may instead fetch an entire line to use only one small node.

An array calculates the address of element $i$ directly:

A_i = A_0+iS

A linked structure must load each next address from the current object:

A_{i+1} = \text{memory}[A_i+\text{next offset}]

The second access is dependent on the completion of the first. The next address cannot be requested until the current node arrives, which limits parallelism and makes memory latency difficult to hide.

The allocation interface permits both representations. The hardware strongly favours layouts that are dense, predictable, and reusable.

The Heap Is Also a Translation Workload

Every memory access must be translated from a virtual address to a physical one. The translation lookaside buffer caches recent translations, but it has limited capacity.

If the page size is $P$ and the TLB can hold $E$ relevant entries, its approximate coverage is:

C_{\text{TLB}} = EP

A tightly packed data structure uses relatively few pages. For $N$ objects of size $S$ , the page count is approximately:

N_{\text{pages}} = \left\lceil \frac{NS}{P} \right\rceil

A scattered heap can place those objects across many more pages. In a pathological layout, one small object might be accessed on each page, causing the useful payload to remain small while the translation working set becomes enormous.

When the TLB misses, the processor must perform a page-table walk. Since page tables are themselves stored in memory, the machine may generate several additional memory accesses merely to determine where the original data is located.

A poor allocation layout can therefore cause substantial traffic before the processor even begins retrieving the requested object.

Large Pages Exchange Translation Cost for Allocation Granularity

Larger pages increase the amount of memory represented by each TLB entry:

C_{\text{TLB}} = E P_{\text{large}}

This can reduce translation misses for large, densely used working sets. Numerical applications, databases, and virtual machines may benefit when their memory is accessed broadly enough to justify the larger mappings.

Large pages also create coarser allocation units. A sparsely used large page can waste physical memory, may be harder to allocate under fragmentation, and can increase the cost of page migration or copy-on-write.

The trade-off can be expressed as fewer translations in exchange for less flexible physical allocation. Large pages are therefore not free performance; they replace one form of overhead with another.

NUMA Makes Memory Geographical

In a non-uniform memory access system, the latency and bandwidth of an access depend on the relationship between the executing processor and the physical location of the page. Memory is no longer one uniform pool from the perspective of performance.

The access time becomes a function of placement:

T_{\text{access}} = f(\text{processor node},\text{memory node})

A local access may use a nearby memory controller, while a remote access must cross a socket or node interconnect. Both operations use the same pointer syntax, but they produce different physical journeys.

Many operating systems use first-touch placement, assigning a physical page near the processor that first writes to it. An application may allocate a large array on one thread and initialise it on another, causing the initialising thread to determine the eventual physical placement.

If later computation runs on a different node, the program may continuously access remote memory. The allocator selected the virtual address range, but thread scheduling and initialisation determined the physical geography.

The source code says only that memory was allocated. The hardware cares about which processor caused each page to become real.

Concurrent Allocation Trades Memory Efficiency for Scalability

A general-purpose allocator must support requests from multiple threads. A simple global allocator protected by one lock can become a serial bottleneck as the number of threads increases.

The total cost may be represented as:

T_{\text{alloc}} \approx T_{\text{local work}} + T_{\text{lock wait}}

Modern allocators reduce this contention using per-thread caches, multiple arenas, per-core structures, batched transfers, and carefully designed concurrent free lists. These techniques allow many requests to complete without touching one central data structure.

The trade-off is increased memory retention. Free blocks stored in one thread’s local cache may remain unavailable to another thread even when the second thread needs blocks of the same size.

The allocator sacrifices some global packing efficiency to obtain local speed. As with many systems designs, reducing communication requires duplicating or partitioning state.

Two threads may allocate logically independent objects and later modify them without any explicit sharing. If the allocator places those objects within the same cache line, the hardware coherence system treats the writes as conflicting ownership changes.

For cache-line size $C$ , two objects avoid sharing a line when:

\left\lfloor \frac{A_1}{C} \right\rfloor \neq \left\lfloor \frac{A_2}{C} \right\rfloor

Separating heavily written objects may require explicit alignment or padding. This increases memory consumption, but it can reduce invalidation traffic and improve parallel performance.

The important principle is that minimum storage size does not imply minimum execution cost. A physically larger layout may be faster because it respects the ownership granularity of the cache-coherence protocol.

Allocation Layout Also Affects Security

Allocator layout influences which objects become neighbours in memory and what happens after an object is released. A buffer overflow may corrupt adjacent application objects, allocator metadata, free-list links, size fields, function pointers, or authentication values.

Use-after-free errors are especially dangerous because the same address can represent different logical objects at different times. An address $A$ may initially refer to object $O_1$ :

A \rightarrow O_1

After $O_1$ is freed and the block is reused, the same address may refer to a different object:

A \rightarrow O_2

A stale pointer still contains the valid numerical address $A$ , but its ownership rights have expired. Ordinary hardware address translation does not understand this distinction.

Defensive allocators may use guard pages, quarantines, delayed reuse, randomised placement, memory tagging, encoded free-list pointers, or integrity canaries. These mechanisms increase time or space overhead because exposing and checking object-lifetime information requires additional machinery.

A pointer identifies where an access will occur. By itself, it does not prove that the access remains semantically valid.

Zeroed Memory Still Requires Physical Work

Fresh pages supplied to a process are generally required to appear zero-initialised so that data from another process cannot leak across protection boundaries. Clearing memory therefore represents genuine bandwidth consumption.

For a region of size $S$ , the amount of data written during explicit zeroing is approximately:

D_{\text{written}} = S

The minimum time is constrained by effective memory bandwidth:

T_{\text{zero}} \geq \frac{S}{B_{\text{write}}}

Operating systems can postpone this work through demand paging and shared zero pages. A large read-only range may initially map many virtual pages to one common physical page containing zeros.

When the process writes to a page, the system must provide a private physical frame and preserve the illusion that the page had always belonged exclusively to the process. The allocation call may therefore appear inexpensive because its cost has been deferred until first use.

The abstraction can move physical work to a later moment. It cannot remove the work entirely.

Demand Paging Turns First Access into Allocation

When physical pages are assigned lazily, the first access to each page can trigger a page fault. The processor enters the kernel, the operating system selects a physical frame, clears it if necessary, updates the page table, adjusts translation state, and restarts the faulting instruction.

A program may appear to perform a single store, but the machine performs a page-sized resource allocation event. For a buffer of size $S$ and page size $P$ , touching every page can produce approximately:

N_{\text{faults}} \approx \left\lceil \frac{S}{P} \right\rceil

This is why benchmarks that measure only the duration of malloc can be misleading. They may measure address-space reservation while excluding the later cost of supplying, clearing, and mapping the physical pages.

Allocation reserves ownership at one layer. First use may complete the transaction at another.

Overcommit Separates Reservation from Guarantee

Some operating systems permit processes to reserve more virtual memory than the system can simultaneously back with RAM and secondary storage. This policy is based on the observation that many reserved pages are never touched or are not active at the same time.

The committed virtual capacity may satisfy:

V_{\text{committed}} > R_{\text{physical}} + R_{\text{swap}}

The operating system is effectively making a statistical assumption that all reservations will not become active simultaneously. This improves utilisation but weakens the intuitive meaning of a successful allocation.

A non-null pointer may confirm that a virtual range was reserved. It may not constitute an unconditional guarantee that every future page write can be backed under all possible system states.

The allocator reports local success to one process. The operating system continues managing the global risk created by all processes together.

Memory Pressure Reveals the Hidden Machinery

When a system has abundant unused memory, allocation and access abstractions remain relatively convincing. Under pressure, the physical limits become visible through rising latency and unpredictable behaviour.

The operating system may reclaim file-cache pages, write dirty data to storage, migrate pages, compact physical memory, reduce kernel caches, or terminate processes. A previously resident page may be removed and later restored through a major page fault.

The pointer and load instruction remain unchanged throughout these events. Their execution time changes because memory latency is not purely a property of the instruction or address.

Access cost is an outcome of current cache state, translation state, physical placement, residency, contention, and global resource pressure. The software abstraction provides stable syntax over an unstable physical environment.

Garbage Collection Changes the Interface, Not the Constraint

Managed runtimes replace explicit calls to free with automatic reclamation. This removes some ownership decisions from application code, but the runtime must still determine which objects remain live and when their storage may be reused.

A tracing collector examines the reachable object graph. Under a simplified model, tracing time is related to the amount of live data:

T_{\text{trace}} = O(L)

where $L$ is the live object volume.

Copying collectors move surviving objects into new regions. This compacts memory and can improve locality, but it generates traffic proportional to the amount of data copied:

D_{\text{copy}} \propto L

Generational collectors exploit the tendency of many objects to die young. New objects can be allocated using fast bump-pointer regions, and large groups of dead objects can be reclaimed together.

These benefits require write barriers, remembered sets, tracing work, relocation support, extra memory headroom, and pause-management mechanisms. Garbage collection does not eliminate memory management; it changes which layer performs it and when its costs become visible.

Compaction Exchanges Bandwidth for Free Space

External fragmentation can be reduced by relocating live objects so that scattered free regions become one large contiguous area. A fragmented layout such as:

L,\ -,\ L,\ -,\ -,\ L

can be compacted into:

L,\ L,\ L,\ -,\ -,\ -

This improves packing but requires reading and writing the live objects. For a live data volume $L$ , the resulting movement is at least proportional to:

D_{\text{compact}} = O(L)

Native allocators usually cannot relocate arbitrary live objects because raw pointers may be stored anywhere in the program. The allocator cannot reliably locate and update every reference.

Managed runtimes can move objects because they control or understand references. This ability improves compaction and locality, but it introduces runtime machinery and may require indirect access or pointer-update pauses.

Stable addresses simplify programming. Movable addresses simplify memory management, and the system must choose how much of each property it is willing to sacrifice.

Address Stability Restricts Placement

Once a native allocator returns a pointer, the object is generally expected to remain at that virtual address until it is released. This makes location part of the object’s software-visible identity.

The allocator cannot freely relocate the object to improve packing, place related objects together, or consolidate free regions. The operating system may migrate the underlying physical page because the virtual address can remain unchanged, but moving an object within the virtual heap would invalidate every raw pointer to it.

Handle-based systems add indirection:

\text{handle} \rightarrow \text{object address} \rightarrow \text{object}

The runtime can move the object and update the handle table, preserving the handle’s identity. Every access may then require an extra lookup, potentially increasing latency and cache pressure.

Direct pointers make ordinary access efficient. Handles provide greater placement freedom, demonstrating again that abstraction and physical control cannot both be maximised without cost.

Data Structures Are Physical Allocation Policies

Selecting a data structure determines not only algorithmic complexity but also how memory is allocated, grouped, and traversed. A linked list represents dynamic insertion elegantly, but normally requires separate nodes and dependent pointer loads.

A dynamic array stores elements contiguously and occasionally increases its capacity geometrically:

C_{n+1} = gC_n

where $g > 1$ is the growth factor.

Its unused capacity is:

F = C-N

where $C$ is capacity and $N$ is the current element count.

This unused capacity is deliberate. It reduces the frequency of reallocations and preserves contiguous access, trading additional space for better amortised growth and cache locality.

Hash tables use a similar trade-off. Their load factor is:

\alpha = \frac{N}{M}

where $N$ is the number of stored entries and $M$ is the bucket count.

Lower load factors consume more memory but can reduce collisions and lookup work. B-trees use relatively large nodes to increase the number of keys obtained from each cache line or storage page, reducing the number of distant accesses needed during traversal.

These structures are not merely mathematical organisations of values. They are concrete proposals for placing and moving data through a memory hierarchy.

Big-O Memory Does Not Describe Physical Cost

Two programs may both use (O $n$ ) logical memory while generating entirely different behaviour in the allocator and hardware. One may reserve a single contiguous array, while the other performs $n$ independent heap allocations.

Their asymptotic capacity is the same, but they differ in metadata overhead, fragmentation, allocation latency, cache utilisation, translation footprint, pointer traffic, and deallocation cost.

A more complete memory model distinguishes several quantities:

M_{\text{payload}}, \quad M_{\text{reserved}}, \quad M_{\text{resident}}, \quad M_{\text{transferred}}

A program might contain (100) MB of useful data, reserve (140) MB because of size classes and fragmentation, retain (120) MB in physical memory, and transfer several gigabytes while repeatedly traversing the structure.

Memory complexity describes how capacity grows. It does not describe the shape, location, or movement of that capacity.

The Cheapest Allocation Is Often the One Avoided

Dynamic allocation is necessary when object size, lifetime, or ownership cannot be predicted conveniently. It should not be treated as physically free simply because its interface is short.

Avoiding an allocation can remove allocator metadata, free-list operations, fragmentation, synchronisation, page faults, and unpredictable slow paths. Objects can sometimes be stored on the stack, embedded inside parent objects, placed in fixed-capacity containers, or drawn from reusable pools.

Stack allocation is efficient because object lifetimes follow a nested order. Allocating $S$ bytes may be approximated as:

SP_{\text{new}} = SP_{\text{old}} - S_{\text{aligned}}

Deallocation reverses the pointer adjustment when the function returns. No general search is needed because the lifetime discipline preserves a simple structure.

The limitation is that stacks cannot naturally represent arbitrary ownership graphs, unbounded objects, or values that must outlive their creating function. General-purpose heap allocation is complex because arbitrary lifetimes destroy the structure that makes stack allocation simple.

Pools Replace a General Problem with a Narrow One

A pool allocator reserves storage for objects of one known size or a small set of sizes. Allocation can often remove one slot from a free list, making both allocation and deallocation approximately constant time.

Fixed-size slots avoid block splitting and simplify coalescing. They can reduce metadata, improve locality, and make performance more predictable.

The cost is reduced generality. A pool designed for (64)-byte objects cannot efficiently satisfy arbitrary multi-kilobyte requests, and unused slots remain reserved even when another part of the program requires memory.

Pool allocation becomes efficient because the software provides information that a general allocator does not have. Once size and lifetime patterns become constrained, the physical placement problem becomes easier to solve.

Allocation and Ownership Are One Problem

The allocator must determine when a region may be reused. That decision is fundamentally an ownership question rather than a question about the numerical address alone.

Manual memory management relies on program logic to determine when no valid references remain. Reference counting tracks the number of owners and releases an object when:

R=0

Tracing garbage collection determines ownership through reachability. Region-based systems assign objects to a shared lifetime, while linear and affine type systems restrict how references may be copied or consumed.

All of these methods answer the same physical question: when may these bytes safely be assigned a new meaning? Deallocation does not destroy the memory cells; it transfers the right to reuse them.

Memory Leaks Strand Physical Capacity

A memory leak occurs when storage remains allocated even though the program can no longer use it productively. The bytes have not disappeared, but the allocator still considers them owned.

If a program leaks $r$ bytes per operation, the accumulated leak after $n$ operations is:

M_{\text{leaked}} = rn

Even a tiny repeated leak can therefore produce unbounded memory growth in a long-running process. The allocator cannot recover the storage because the software has lost the information required to declare it reusable.

A leak is best understood as capacity whose ownership state no longer matches its semantic usefulness. Physical memory becomes stranded behind incorrect software accounting.

Out of Memory Is Not One Physical Condition

An allocation may fail because the process lacks sufficient virtual address space, the system lacks commit capacity, the heap is fragmented, a container limit has been reached, a requested alignment cannot be satisfied, or the kernel cannot find sufficiently contiguous physical pages.

These conditions can all appear to the application as a null pointer, error code, exception, or process termination. The interface compresses several distinct failures into one software-visible result.

Even successful allocation may not guarantee successful future access on a system using memory overcommit. Reservation, commitment, residency, and physical contiguity are separate resources.

“Out of memory” is therefore not one universal hardware state. It is the point at which a particular promise about capacity, placement, or backing can no longer be honoured.

Allocation Is a Placement Decision

Every allocation implicitly answers several questions. The system must determine how much space to reserve, where the virtual interval should appear, which physical pages should eventually back it, and how those pages should be positioned relative to processors and devices.

These choices influence latency, bandwidth, cache behaviour, translation pressure, coherence traffic, fragmentation, and energy consumption. The allocation’s size affects its allocator class, while its address determines cache-line neighbours and its physical node determines access distance.

Its lifetime determines whether surrounding pages can be reclaimed. Its ownership rules determine whether it can be relocated, compacted, or safely reused.

The source-level allocation request is small. Its placement consequences extend across the entire memory hierarchy.

Allocation Is an Online Scheduling Problem

An allocator decides which available region should satisfy each incoming request. In this sense, it schedules objects into space while lacking reliable knowledge about the future.

When placing an object, it usually does not know how long the object will live, which other objects will be accessed alongside it, which thread will use it, whether neighbouring blocks will soon be released, or whether the object’s size will later change.

The problem resembles online bin packing because requests arrive over time and placement decisions must be made without complete future information. Stable addresses also prevent the allocator from freely rearranging live objects after making an imperfect decision.

Fragmentation is therefore not always evidence of a careless allocator. Some waste is the natural result of serving arbitrary sizes and lifetimes through online decisions under incomplete information.

The Abstraction Is Still Necessary

It is easy to criticise allocation APIs because they hide the machine’s physical structure. Without that abstraction, however, every ordinary program would need to reason directly about page frames, memory banks, NUMA topology, translation tables, cache-line ownership, device accessibility, and concurrent free-space management.

A library can request storage without knowing which operating system, processor, memory configuration, or workload will host it. This separation makes portable and modular software possible.

The cost is that simple source code can produce expensive physical behaviour. An API that makes memory appear uniform cannot also communicate every property of placement, locality, residency, and contention.

The solution is not to abandon allocation abstractions. It is to recognise when a workload has become sensitive to the realities those abstractions conceal.

Systems Programming Begins Where the Abstraction Leaks

At the source level, allocation is presented as:

pointer = allocate(size);

The physical process is closer to:

\text{size} \rightarrow \text{alignment} \rightarrow \text{size class} \rightarrow \text{heap region} \rightarrow \text{virtual pages} \rightarrow \text{physical frames} \rightarrow \text{NUMA node} \rightarrow \text{cache lines}

Each transition can introduce latency, waste, movement, or contention. Most applications do not need to control every layer, but performance-sensitive software must recognise when the general-purpose policy no longer matches the workload.

A database may use page-oriented arenas, while a game engine may use one allocator per frame. A network service may use object pools, a compiler may store syntax trees in regions, and a real-time system may forbid general heap allocation after startup.

A NUMA-aware program may partition memory by worker, while a numerical application may use aligned contiguous arrays and parallel first-touch initialisation. These designs differ in implementation but pursue the same goal: make software ownership and access patterns resemble the physical structure of the machine.

Conclusion

Memory allocation appears to be an API for obtaining bytes. In reality, it is an agreement negotiated across the application, allocator, operating system, virtual-memory subsystem, cache hierarchy, coherence network, and physical memory hardware.

The application requests a logical object, and the allocator finds a suitable virtual interval. The operating system manages pages, the memory manager supplies physical frames, the processor translates addresses, and the cache hierarchy moves the relevant lines toward the executing core.

A pointer hides this entire chain. That concealment makes programming practical, but it also encourages the false idea that all allocated memory is equivalent.

Two objects with the same requested size can have different alignment, fragmentation cost, cache placement, translation footprint, NUMA distance, residency, reclaimability, and security properties. Their source-level types may be identical while their physical costs differ substantially.

The allocation API describes ownership, but not placement. It describes addressability, but not locality, and it describes capacity without describing the journey required to reach that capacity.

Memory allocation is a software abstraction over physical constraints because the hardware cannot provide arbitrary, perfectly packed, uniformly fast storage. It provides cache lines, pages, frames, banks, channels, translation entries, finite bandwidth, and physical distance.

The allocator’s job is to make those constraints look like a pointer. The systems programmer’s job is to remember that the constraints never disappeared.