First Fit Allocation Strategy - Memory Allocation Strategies | OneNoughtOne

Operating SystemsAllocation Strategies

Memory Allocation Strategies

LevelIntermediate

Duration90 mins

TopicAllocation Strategies

1 / 5

First Fit Allocation Strategy

The Allocation Decision

When a process requests memory from the operating system, the memory manager faces a deceptively simple question: Which free block should satisfy this request? In a system using variable partitioning, multiple holes (free memory blocks) of varying sizes typically exist throughout physical memory. The algorithm used to select among these holes profoundly impacts system performance, memory utilization, and fragmentation characteristics.

First Fit is the most intuitive and historically significant memory allocation strategy. It answers the selection question with elegant simplicity: allocate the first hole that is large enough to satisfy the request. This seemingly trivial decision has far-reaching implications that we will explore in comprehensive detail.

What You Will Learn

By the end of this page, you will understand the First Fit algorithm at a deep level—its implementation, time complexity, memory traversal patterns, fragmentation behavior, and why it remains the default choice in many real-world memory allocators. You will be able to trace its execution, analyze its performance characteristics, and understand its theoretical foundations.

Algorithm Definition and Core Mechanics

First Fit is elegantly defined: scan the list of free memory blocks from the beginning and allocate the first block that is large enough to satisfy the request. If the selected block is larger than needed, it is split—the requested portion is allocated to the process, and the remainder stays in the free list as a smaller hole.

Formal Algorithm Specification

Let us formalize the algorithm precisely:

Input: A request for n bytes of memory
Data Structure: A linked list (or array) of free blocks, where each block has a start_address and size
Process:
- Traverse the free list from the beginning (lowest address or list head)
- For each block B with size S:
  - If S >= n: Select this block for allocation
  - If S > n: Split the block—allocate n bytes, return remainder (S - n) to free list
  - If S == n: Remove block entirely from free list
- If no suitable block found: Return allocation failure (out of memory)
Output: Starting address of allocated memory, or NULL/error on failure

first_fit.c
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef struct FreeBlock {
    size_t start_address;
    size_t size;
    struct FreeBlock* next;
} FreeBlock;
 
FreeBlock* free_list_head = NULL;
 
/**
 * First Fit Memory Allocation
 * 
 * Searches the free list from the beginning and allocates
 * the first block that can satisfy the request.
 * 
 * @param requested_size: Number of bytes to allocate
 * @return: Starting address of allocated block, or NULL on failure
 */
void* first_fit_allocate(size_t requested_size) {
    if (requested_size == 0) {
        return NULL;
    }
    
    FreeBlock* current = free_list_head;
    FreeBlock* previous = NULL;
    
    // Traverse free list from the beginning
    while (current != NULL) {
        if (current->size >= requested_size) {
            // Found a suitable block - this is THE first fit
            void* allocated_address = (void*)current->start_address;
            
            if (current->size > requested_size) {
                // Split the block: allocate requested, keep remainder
                current->start_address += requested_size;
                current->size -= requested_size;
            } else {
                // Exact fit: remove block from free list entirely
                if (previous == NULL) {
                    free_list_head = current->next;
                } else {
                    previous->next = current->next;
                }
                // In practice: return current to block pool or free()
            }
            
            return allocated_address;
        }
        
        // Move to next block
        previous = current;
        current = current->next;
    }
    
    // No suitable block found - memory exhausted
    return NULL;
}

Implementation Subtlety: Block Ordering

The behavior of First Fit depends critically on how the free list is ordered. If blocks are maintained in address order (lowest to highest), First Fit tends to allocate from lower memory addresses first, leaving larger blocks at higher addresses. If blocks are maintained in insertion order (most recently freed at head), behavior changes dramatically. Most implementations use address ordering for predictability and to facilitate coalescing of adjacent free blocks.

Time and Space Complexity Analysis

Understanding the computational complexity of First Fit is essential for predicting system behavior under various workloads.

Time Complexity

Worst Case: O(n) where n is the number of free blocks

In the worst case, First Fit must traverse the entire free list before finding a suitable block (or determining that none exists). This occurs when:

The requested size is larger than most free blocks
Suitable blocks are located near the end of the list
Memory is highly fragmented with many small blocks

Best Case: O(1)

The best case occurs when the first block in the free list is large enough to satisfy the request. This is remarkably common in practice, especially with address-ordered free lists where:

The first (lowest address) block tends to be large initially
Memory patterns often create suitable blocks near the list head

Average Case: O(n/2) → O(n)

On average, First Fit must scan roughly half the free list. However, the constant factor is typically small because the early termination property means many allocations complete quickly.

First Fit Complexity Analysis
Scenario	Time Complexity	When It Occurs
Best Case	O(1)	First block satisfies request
Average Case	O(n)	Suitable block found mid-list
Worst Case	O(n)	Must scan entire list or no block found
Amortized (real workloads)	~O(1) to O(log n)	Early termination common in practice

Space Complexity

O(n) for the free list data structure, where n is the number of free blocks.

Each free block requires a small constant amount of metadata:

Start address (pointer or size_t): 4-8 bytes
Block size: 4-8 bytes
Next pointer (for linked list): 4-8 bytes

Total overhead per block: typically 12-24 bytes on modern systems.

Fragmentation Impact on Complexity

A critical observation: as external fragmentation increases, the number of free blocks increases, and allocation time degrades. This creates a negative feedback loop:

First Fit splits blocks, creating more (smaller) blocks
More blocks means longer search times
Longer searches mean slower allocation
System performance degrades progressively

This phenomenon motivates the use of more sophisticated data structures (binary trees, segregated lists) in production allocators.

The Hidden Cost of Linear Search

While O(n) might seem acceptable, consider a system with thousands of free blocks. Each allocation requiring a linear scan through thousands of entries creates substantial overhead. Real-time systems with strict latency requirements often cannot tolerate this variability—the worst-case allocation time may violate timing constraints even if average performance is acceptable.

Memory Traversal and Search Patterns

The search pattern of First Fit has profound implications for memory layout and fragmentation. Understanding these patterns is crucial for systems programmers.

Address-Ordered Traversal

When the free list is maintained in ascending address order (the most common implementation), First Fit exhibits a front-loading allocation pattern:

Allocations preferentially consume blocks at lower memory addresses
Higher memory addresses tend to accumulate larger, unused blocks
The "front" of memory becomes increasingly fragmented over time
The "back" of memory remains relatively pristine

This creates a characteristic fragmentation gradient across the address space.

Converting Mermaid diagram...

The Front-End Fragmentation Problem

The front-loading pattern creates a well-known problem: the front of memory becomes increasingly fragmented with small, often unusable blocks, while the back retains larger blocks. This has several consequences:

Positive Effects:

Large blocks are preserved for large allocation requests
Memory near the top of the address space remains contiguous
Coalescing opportunities exist in the back portion

Negative Effects:

Small allocations must wade through fragmented front-end debris
Search times steadily increase as fragmentation accumulates
Cache locality suffers as allocations scatter across memory
The free list grows longer, consuming more metadata space

Temporal Locality Considerations

First Fit's traversal pattern interacts with processor cache behavior:

The free list itself must be traversed, causing cache misses
Allocated blocks near the front of memory may have better cache locality due to address clustering
However, fragmentation disrupts this as allocations interleave with free blocks

Address Order vs. LIFO Order

Some allocators use a LIFO (Last-In-First-Out) free list where recently freed blocks are placed at the head. This improves cache locality (recently freed memory is 'hot' in cache) but sacrifices address ordering, making coalescing more complex. The choice between address order and LIFO order represents a fundamental design trade-off.

Block Splitting Mechanics and Minimum Block Size

Block splitting is fundamental to how First Fit operates. When a free block larger than the request is selected, the allocator must decide how to handle the surplus.

The Splitting Decision

Given a free block of size B and a request for size R where B > R:

Option 1: Always Split

Allocate exactly R bytes
Return (B - R) bytes to the free list
Maximizes memory utilization
May create tiny, unusable fragments

Option 2: Conditional Split with Minimum Block Size

Define a MIN_BLOCK_SIZE (e.g., 16 bytes)
Only split if (B - R) >= MIN_BLOCK_SIZE
Otherwise, allocate the entire block B
Trades some internal fragmentation for reduced external fragmentation

Option 3: Threshold-Based Allocation

Define a waste threshold (e.g., 25% of request)
Split only if (B - R) > threshold
More sophisticated heuristic balancing both fragment types

block_splitting.c
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
31
32
#define MIN_BLOCK_SIZE 32  // Minimum viable free block size
 
/**
 * Allocate from a free block with intelligent splitting
 * 
 * Implements minimum block size constraint to prevent
 * creation of tiny, unusable fragments.
 */
void* allocate_with_split(FreeBlock* block, FreeBlock* prev, 
                          size_t requested_size) {
    void* allocated_address = (void*)block->start_address;
    size_t remaining = block->size - requested_size;
    
    if (remaining >= MIN_BLOCK_SIZE) {
        // Worth splitting: remainder is large enough to be useful
        block->start_address += requested_size;
        block->size = remaining;
        // Block stays in free list at same position
    } else {
        // Not worth splitting: allocate entire block
        // This causes internal fragmentation but prevents tiny fragments
        if (prev == NULL) {
            free_list_head = block->next;
        } else {
            prev->next = block->next;
        }
        // Note: we allocate block->size bytes, not requested_size
        // Caller may receive more memory than requested
    }
    
    return allocated_address;
}

Minimum Block Size Selection

Choosing the appropriate MIN_BLOCK_SIZE is a nuanced engineering decision:

Factors to Consider:

Metadata Overhead: If block metadata requires 24 bytes, a free block smaller than 24 bytes cannot exist (the metadata would consume the entire block)
Alignment Requirements: Memory must often be aligned to word boundaries (4 bytes), cache lines (64 bytes), or page boundaries (4096 bytes). MIN_BLOCK_SIZE should be at least the alignment requirement
Workload Characteristics: If the system frequently allocates small objects (8-16 bytes), MIN_BLOCK_SIZE should be low. If allocations are typically larger, higher thresholds are acceptable
Fragmentation Trade-off: Lower MIN_BLOCK_SIZE → more external fragmentation, less internal fragmentation. Higher MIN_BLOCK_SIZE → opposite trade-off

Typical Values in Practice:

Simple allocators: 16-32 bytes
Production allocators (glibc malloc): 16 bytes minimum, but complex binning
Page-level allocators: 4096 bytes (one page)

The Sliver Problem

Tiny leftover fragments (sometimes called 'slivers') are particularly insidious. They consume space in the free list, slow down searches, but are too small to satisfy any allocation request. Without minimum block size enforcement, slivers accumulate over time, degrading allocator performance even when substantial total free memory exists.

Fragmentation Behavior and Characteristics

Understanding how First Fit induces and manages fragmentation is essential for evaluating its suitability for different workloads.

External Fragmentation Analysis

First Fit tends to produce moderate external fragmentation—better than some strategies (like Worst Fit) and comparable to or slightly better than Best Fit in many workloads.

Why First Fit Handles External Fragmentation Reasonably Well:

Early Termination: By stopping at the first suitable block, First Fit avoids unnecessarily fragmenting larger blocks deeper in the list
Block Preservation: Large blocks at the end of the address space tend to survive longer, providing capacity for large future allocations
Natural Coalescing Opportunities: Adjacent allocations in the front of memory are likely freed together (temporal locality of deallocation), enabling efficient coalescing

The 50-Percent Rule Relevance:

Knuth's 50-percent rule states that under heavy allocation/deallocation workloads, free blocks approach 50% of the total blocks (free + allocated). First Fit, like other strategies, converges to this equilibrium, meaning approximately half of memory tracking overhead goes to free block management.

First Fit Fragmentation Advantages

•Preserves large blocks for large requests
•Front-loaded fragmentation is predictable
•Good locality of reference for allocated blocks
•Simpler coalescing in address-ordered lists
•Performance degrades gracefully, not catastrophically

First Fit Fragmentation Disadvantages

•Front of memory accumulates small fragments
•Search times increase as fragmentation grows
•May reject requests despite adequate total free memory
•Not optimal for minimizing fragmentation
•Sensitive to allocation/deallocation patterns

Empirical Fragmentation Studies

Extensive research since the 1970s has characterized First Fit's fragmentation behavior:

Knuth's Analysis (1973):

First Fit produces approximately 27% unusable memory due to fragmentation under random workloads
This is better than Worst Fit (~35%) and comparable to Best Fit (~25-27%)

Johnstone and Wilson (1998):

Studied real application traces rather than synthetic workloads
Found First Fit performs within 1% of Best Fit for most applications
Real workloads show less fragmentation than random workloads due to structure in allocation patterns

Modern Observations:

With sophisticated coalescing and minimum block sizes, First Fit achieves excellent memory utilization (typically >90% in well-tuned allocators)
The simple algorithm enables aggressive optimization of the hot path (frequent small allocations)

Implementation Variations and Optimizations

Production allocators rarely use textbook First Fit directly. Instead, they employ various optimizations that preserve First Fit semantics while improving performance.

Roving Pointer (Next Fit Connection)

A simple optimization: maintain a 'rover' pointer to the last examined block. Start each search from the rover position rather than the list head. This distributes fragmentation more evenly and reduces average search time.

Note: This optimization transforms First Fit into Next Fit, which we cover in detail later.

Segregated Free Lists

Modern allocators like glibc malloc, jemalloc, and tcmalloc use size-segregated free lists:

Maintain separate free lists for different size classes (e.g., 16 bytes, 32 bytes, 64 bytes, ...)
Allocations are routed to the appropriate size class
Within each class, First Fit (or exact fit) is used
Dramatically reduces search time: O(1) to find the right list, O(1) or O(k) within the list

segregated_first_fit.c
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define NUM_SIZE_CLASSES 32
#define SIZE_CLASS_SHIFT 4  // Minimum block = 16 bytes
 
// Segregated free lists: one list per size class
FreeBlock* segregated_lists[NUM_SIZE_CLASSES];
 
/**
 * Map allocation size to size class index
 * Size classes: 16, 32, 64, 128, ... bytes
 */
int size_to_class(size_t size) {
    if (size <= 16) return 0;
    // Log2 calculation to find size class
    int class = 0;
    size_t s = size >> SIZE_CLASS_SHIFT;
    while (s > 1) {
        s >>= 1;
        class++;
    }
    return (class < NUM_SIZE_CLASSES) ? class : NUM_SIZE_CLASSES - 1;
}
 
/**
 * Segregated First Fit allocation
 * 
 * Routes request to appropriate size class, then applies
 * First Fit within that class's free list.
 */
void* segregated_first_fit(size_t requested_size) {
    int class = size_to_class(requested_size);
    
    // Search this class and larger classes
    for (int c = class; c < NUM_SIZE_CLASSES; c++) {
        FreeBlock* block = segregated_lists[c];
        FreeBlock* prev = NULL;
        
        while (block != NULL) {
            if (block->size >= requested_size) {
                // Found first fit in this size class
                return allocate_and_maybe_split(block, prev, 
                                                 requested_size, c);
            }
            prev = block;
            block = block->next;
        }
    }
    
    return NULL;  // No suitable block in any class
}

Binary Tree Organization

For systems with many free blocks, a balanced binary tree (AVL, red-black) ordered by address provides O(log n) First Fit:

Use in-order traversal to maintain address ordering
At each node, track the maximum free size in the subtree
Navigate to find the first (lowest address) block meeting size requirement
This is the approach used in some kernel allocators

Bitmap-Based First Fit

For fixed-size block systems (like page frame allocators), bitmaps provide extremely fast First Fit:

Each bit represents one block (0 = free, 1 = allocated)
Hardware instructions (find-first-zero) locate free blocks in O(1)
Memory overhead is minimal (1 bit per block)
Cache-efficient scanning of free block status

This approach is used extensively in:

Page frame allocators in Linux, Windows, BSD kernels
Ext4 file system block allocation
Memory-mapped file region management

The Art of Practical Allocation

Real-world allocators combine multiple strategies. For example, glibc malloc uses: exact-fit bins for common sizes, First Fit within bins, Best Fit for large allocations, and mmap() for very large allocations. Understanding the pure algorithms enables appreciation of these hybrid designs.

Real-World Applications and Usage

First Fit's simplicity and acceptable performance make it the default choice in many contexts.

Operating System Kernel Allocators

Linux Kernel:

The buddy system uses a form of First Fit within each order's free list
SLUB (the default slab allocator) uses First Fit for per-CPU partial slabs
The page allocator scans zone lists with First Fit semantics

Windows Kernel:

The segment heap uses segregated First Fit for smaller allocations
The NT heap manager historically used First Fit for coalesced blocks

User-Space Memory Allocators

glibc malloc (ptmalloc2):

Uses First Fit within unsorted bins
Employs Best Fit for large bins (sorted by size)
Demonstrates that pure strategies are rarely used alone

jemalloc (used by Firefox, Facebook):

Uses First Fit for selecting runs within arenas
Emphasizes per-thread caching to reduce contention

tcmalloc (Google's allocator):

Thread-caching with First Fit for span allocation
Optimized for high allocation rates in multithreaded programs

First Fit in Production Systems
System/Allocator	Where First Fit Is Used	Why First Fit
Linux Buddy Allocator	Within each order's free list	Simplicity, O(1) common case
glibc malloc	Unsorted bin allocation	Speed for recent frees
FreeBSD UMA (slab)	Zone selection	Cache efficiency
Ext4 Block Allocator	Block group scanning	Locality of allocation
JVM G1 Garbage Collector	Region selection	Predictable latency

Embedded and Real-Time Systems

First Fit is particularly popular in embedded systems due to:

Predictable worst-case: O(n) is bounded and analyzable
Low code complexity: Smaller code footprint for resource-constrained devices
No dynamic data structures: Can be implemented with static arrays
Deterministic: No randomization that could affect timing analysis

However, for hard real-time systems, even O(n) worst-case may be unacceptable, motivating specialized allocators like TLSF (Two-Level Segregated Fit) that achieve O(1) with First Fit semantics.

Summary: The First Fit Strategy

We have explored First Fit comprehensively—from its elegant simplicity to its nuanced real-world behavior. Let us consolidate the essential points:

Key Takeaways

•Definition: First Fit allocates the first block large enough to satisfy the request, scanning from the beginning of the free list
•Time Complexity: O(n) worst case, but often O(1) in practice due to early termination
•Fragmentation: Produces moderate external fragmentation with characteristic front-loading pattern
•Block Splitting: Requires minimum block size enforcement to prevent useless slivers
•Traversal Pattern: Address-ordered lists create predictable allocation patterns but accumulate front-end fragments
•Optimizations: Segregated lists, binary trees, and bitmaps can dramatically improve performance while preserving First Fit semantics
•Real-World Use: Remains the default or component strategy in most production allocators due to simplicity and acceptable performance

What's Next:

Now that we understand First Fit, we will examine Best Fit—a strategy that trades search time for potentially better memory utilization by always selecting the smallest sufficient block.

Page Complete

You now have a deep understanding of the First Fit allocation strategy—its algorithm, complexity, fragmentation behavior, implementation variations, and real-world applications. This knowledge forms the foundation for comparing allocation strategies and understanding modern memory allocator design.

1 / 5

Loading learning content...

Operating SystemsAllocation Strategies

Memory Allocation Strategies

LevelIntermediate

Duration90 mins

TopicAllocation Strategies

1 / 5

First Fit Allocation Strategy

The Allocation Decision

What You Will Learn

Algorithm Definition and Core Mechanics

Formal Algorithm Specification

Let us formalize the algorithm precisely:

Input: A request for n bytes of memory
Data Structure: A linked list (or array) of free blocks, where each block has a start_address and size
Process:
- Traverse the free list from the beginning (lowest address or list head)
- For each block B with size S:
  - If S >= n: Select this block for allocation
  - If S > n: Split the block—allocate n bytes, return remainder (S - n) to free list
  - If S == n: Remove block entirely from free list
- If no suitable block found: Return allocation failure (out of memory)
Output: Starting address of allocated memory, or NULL/error on failure

first_fit.c
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef struct FreeBlock {
    size_t start_address;
    size_t size;
    struct FreeBlock* next;
} FreeBlock;
 
FreeBlock* free_list_head = NULL;
 
/**
 * First Fit Memory Allocation
 * 
 * Searches the free list from the beginning and allocates
 * the first block that can satisfy the request.
 * 
 * @param requested_size: Number of bytes to allocate
 * @return: Starting address of allocated block, or NULL on failure
 */
void* first_fit_allocate(size_t requested_size) {
    if (requested_size == 0) {
        return NULL;
    }
    
    FreeBlock* current = free_list_head;
    FreeBlock* previous = NULL;
    
    // Traverse free list from the beginning
    while (current != NULL) {
        if (current->size >= requested_size) {
            // Found a suitable block - this is THE first fit
            void* allocated_address = (void*)current->start_address;
            
            if (current->size > requested_size) {
                // Split the block: allocate requested, keep remainder
                current->start_address += requested_size;
                current->size -= requested_size;
            } else {
                // Exact fit: remove block from free list entirely
                if (previous == NULL) {
                    free_list_head = current->next;
                } else {
                    previous->next = current->next;
                }
                // In practice: return current to block pool or free()
            }
            
            return allocated_address;
        }
        
        // Move to next block
        previous = current;
        current = current->next;
    }
    
    // No suitable block found - memory exhausted
    return NULL;
}

Implementation Subtlety: Block Ordering

Time and Space Complexity Analysis

Understanding the computational complexity of First Fit is essential for predicting system behavior under various workloads.

Time Complexity

Worst Case: O(n) where n is the number of free blocks

In the worst case, First Fit must traverse the entire free list before finding a suitable block (or determining that none exists). This occurs when:

The requested size is larger than most free blocks
Suitable blocks are located near the end of the list
Memory is highly fragmented with many small blocks

Best Case: O(1)

The best case occurs when the first block in the free list is large enough to satisfy the request. This is remarkably common in practice, especially with address-ordered free lists where:

The first (lowest address) block tends to be large initially
Memory patterns often create suitable blocks near the list head

Average Case: O(n/2) → O(n)

On average, First Fit must scan roughly half the free list. However, the constant factor is typically small because the early termination property means many allocations complete quickly.

First Fit Complexity Analysis
Scenario	Time Complexity	When It Occurs
Best Case	O(1)	First block satisfies request
Average Case	O(n)	Suitable block found mid-list
Worst Case	O(n)	Must scan entire list or no block found
Amortized (real workloads)	~O(1) to O(log n)	Early termination common in practice

Space Complexity

O(n) for the free list data structure, where n is the number of free blocks.

Each free block requires a small constant amount of metadata:

Start address (pointer or size_t): 4-8 bytes
Block size: 4-8 bytes
Next pointer (for linked list): 4-8 bytes

Total overhead per block: typically 12-24 bytes on modern systems.

Fragmentation Impact on Complexity

A critical observation: as external fragmentation increases, the number of free blocks increases, and allocation time degrades. This creates a negative feedback loop:

First Fit splits blocks, creating more (smaller) blocks
More blocks means longer search times
Longer searches mean slower allocation
System performance degrades progressively

This phenomenon motivates the use of more sophisticated data structures (binary trees, segregated lists) in production allocators.

The Hidden Cost of Linear Search

Memory Traversal and Search Patterns

The search pattern of First Fit has profound implications for memory layout and fragmentation. Understanding these patterns is crucial for systems programmers.

Address-Ordered Traversal

When the free list is maintained in ascending address order (the most common implementation), First Fit exhibits a front-loading allocation pattern:

Allocations preferentially consume blocks at lower memory addresses
Higher memory addresses tend to accumulate larger, unused blocks
The "front" of memory becomes increasingly fragmented over time
The "back" of memory remains relatively pristine

This creates a characteristic fragmentation gradient across the address space.

Converting Mermaid diagram...

The Front-End Fragmentation Problem

Positive Effects:

Large blocks are preserved for large allocation requests
Memory near the top of the address space remains contiguous
Coalescing opportunities exist in the back portion

Negative Effects:

Small allocations must wade through fragmented front-end debris
Search times steadily increase as fragmentation accumulates
Cache locality suffers as allocations scatter across memory
The free list grows longer, consuming more metadata space

Temporal Locality Considerations

First Fit's traversal pattern interacts with processor cache behavior:

The free list itself must be traversed, causing cache misses
Allocated blocks near the front of memory may have better cache locality due to address clustering
However, fragmentation disrupts this as allocations interleave with free blocks

Address Order vs. LIFO Order

Block Splitting Mechanics and Minimum Block Size

Block splitting is fundamental to how First Fit operates. When a free block larger than the request is selected, the allocator must decide how to handle the surplus.

The Splitting Decision

Given a free block of size B and a request for size R where B > R:

Option 1: Always Split

Allocate exactly R bytes
Return (B - R) bytes to the free list
Maximizes memory utilization
May create tiny, unusable fragments

Option 2: Conditional Split with Minimum Block Size

Define a MIN_BLOCK_SIZE (e.g., 16 bytes)
Only split if (B - R) >= MIN_BLOCK_SIZE
Otherwise, allocate the entire block B
Trades some internal fragmentation for reduced external fragmentation

Option 3: Threshold-Based Allocation

Define a waste threshold (e.g., 25% of request)
Split only if (B - R) > threshold
More sophisticated heuristic balancing both fragment types

block_splitting.c
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
31
32
#define MIN_BLOCK_SIZE 32  // Minimum viable free block size
 
/**
 * Allocate from a free block with intelligent splitting
 * 
 * Implements minimum block size constraint to prevent
 * creation of tiny, unusable fragments.
 */
void* allocate_with_split(FreeBlock* block, FreeBlock* prev, 
                          size_t requested_size) {
    void* allocated_address = (void*)block->start_address;
    size_t remaining = block->size - requested_size;
    
    if (remaining >= MIN_BLOCK_SIZE) {
        // Worth splitting: remainder is large enough to be useful
        block->start_address += requested_size;
        block->size = remaining;
        // Block stays in free list at same position
    } else {
        // Not worth splitting: allocate entire block
        // This causes internal fragmentation but prevents tiny fragments
        if (prev == NULL) {
            free_list_head = block->next;
        } else {
            prev->next = block->next;
        }
        // Note: we allocate block->size bytes, not requested_size
        // Caller may receive more memory than requested
    }
    
    return allocated_address;
}

Minimum Block Size Selection

Choosing the appropriate MIN_BLOCK_SIZE is a nuanced engineering decision:

Factors to Consider:

Metadata Overhead: If block metadata requires 24 bytes, a free block smaller than 24 bytes cannot exist (the metadata would consume the entire block)
Alignment Requirements: Memory must often be aligned to word boundaries (4 bytes), cache lines (64 bytes), or page boundaries (4096 bytes). MIN_BLOCK_SIZE should be at least the alignment requirement
Workload Characteristics: If the system frequently allocates small objects (8-16 bytes), MIN_BLOCK_SIZE should be low. If allocations are typically larger, higher thresholds are acceptable
Fragmentation Trade-off: Lower MIN_BLOCK_SIZE → more external fragmentation, less internal fragmentation. Higher MIN_BLOCK_SIZE → opposite trade-off

Typical Values in Practice:

Simple allocators: 16-32 bytes
Production allocators (glibc malloc): 16 bytes minimum, but complex binning
Page-level allocators: 4096 bytes (one page)

The Sliver Problem

Fragmentation Behavior and Characteristics

Understanding how First Fit induces and manages fragmentation is essential for evaluating its suitability for different workloads.

External Fragmentation Analysis

First Fit tends to produce moderate external fragmentation—better than some strategies (like Worst Fit) and comparable to or slightly better than Best Fit in many workloads.

Why First Fit Handles External Fragmentation Reasonably Well:

Early Termination: By stopping at the first suitable block, First Fit avoids unnecessarily fragmenting larger blocks deeper in the list
Block Preservation: Large blocks at the end of the address space tend to survive longer, providing capacity for large future allocations
Natural Coalescing Opportunities: Adjacent allocations in the front of memory are likely freed together (temporal locality of deallocation), enabling efficient coalescing

The 50-Percent Rule Relevance:

First Fit Fragmentation Advantages

•Preserves large blocks for large requests
•Front-loaded fragmentation is predictable
•Good locality of reference for allocated blocks
•Simpler coalescing in address-ordered lists
•Performance degrades gracefully, not catastrophically

First Fit Fragmentation Disadvantages

•Front of memory accumulates small fragments
•Search times increase as fragmentation grows
•May reject requests despite adequate total free memory
•Not optimal for minimizing fragmentation
•Sensitive to allocation/deallocation patterns

Empirical Fragmentation Studies

Extensive research since the 1970s has characterized First Fit's fragmentation behavior:

Knuth's Analysis (1973):

First Fit produces approximately 27% unusable memory due to fragmentation under random workloads
This is better than Worst Fit (~35%) and comparable to Best Fit (~25-27%)

Johnstone and Wilson (1998):

Studied real application traces rather than synthetic workloads
Found First Fit performs within 1% of Best Fit for most applications
Real workloads show less fragmentation than random workloads due to structure in allocation patterns

Modern Observations:

With sophisticated coalescing and minimum block sizes, First Fit achieves excellent memory utilization (typically >90% in well-tuned allocators)
The simple algorithm enables aggressive optimization of the hot path (frequent small allocations)

Implementation Variations and Optimizations

Production allocators rarely use textbook First Fit directly. Instead, they employ various optimizations that preserve First Fit semantics while improving performance.

Roving Pointer (Next Fit Connection)

Note: This optimization transforms First Fit into Next Fit, which we cover in detail later.

Segregated Free Lists

Modern allocators like glibc malloc, jemalloc, and tcmalloc use size-segregated free lists:

Maintain separate free lists for different size classes (e.g., 16 bytes, 32 bytes, 64 bytes, ...)
Allocations are routed to the appropriate size class
Within each class, First Fit (or exact fit) is used
Dramatically reduces search time: O(1) to find the right list, O(1) or O(k) within the list

segregated_first_fit.c
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define NUM_SIZE_CLASSES 32
#define SIZE_CLASS_SHIFT 4  // Minimum block = 16 bytes
 
// Segregated free lists: one list per size class
FreeBlock* segregated_lists[NUM_SIZE_CLASSES];
 
/**
 * Map allocation size to size class index
 * Size classes: 16, 32, 64, 128, ... bytes
 */
int size_to_class(size_t size) {
    if (size <= 16) return 0;
    // Log2 calculation to find size class
    int class = 0;
    size_t s = size >> SIZE_CLASS_SHIFT;
    while (s > 1) {
        s >>= 1;
        class++;
    }
    return (class < NUM_SIZE_CLASSES) ? class : NUM_SIZE_CLASSES - 1;
}
 
/**
 * Segregated First Fit allocation
 * 
 * Routes request to appropriate size class, then applies
 * First Fit within that class's free list.
 */
void* segregated_first_fit(size_t requested_size) {
    int class = size_to_class(requested_size);
    
    // Search this class and larger classes
    for (int c = class; c < NUM_SIZE_CLASSES; c++) {
        FreeBlock* block = segregated_lists[c];
        FreeBlock* prev = NULL;
        
        while (block != NULL) {
            if (block->size >= requested_size) {
                // Found first fit in this size class
                return allocate_and_maybe_split(block, prev, 
                                                 requested_size, c);
            }
            prev = block;
            block = block->next;
        }
    }
    
    return NULL;  // No suitable block in any class
}

Binary Tree Organization

For systems with many free blocks, a balanced binary tree (AVL, red-black) ordered by address provides O(log n) First Fit:

Use in-order traversal to maintain address ordering
At each node, track the maximum free size in the subtree
Navigate to find the first (lowest address) block meeting size requirement
This is the approach used in some kernel allocators

Bitmap-Based First Fit

For fixed-size block systems (like page frame allocators), bitmaps provide extremely fast First Fit:

Each bit represents one block (0 = free, 1 = allocated)
Hardware instructions (find-first-zero) locate free blocks in O(1)
Memory overhead is minimal (1 bit per block)
Cache-efficient scanning of free block status

This approach is used extensively in:

Page frame allocators in Linux, Windows, BSD kernels
Ext4 file system block allocation
Memory-mapped file region management

The Art of Practical Allocation

Real-World Applications and Usage

First Fit's simplicity and acceptable performance make it the default choice in many contexts.

Operating System Kernel Allocators

Linux Kernel:

The buddy system uses a form of First Fit within each order's free list
SLUB (the default slab allocator) uses First Fit for per-CPU partial slabs
The page allocator scans zone lists with First Fit semantics

Windows Kernel:

The segment heap uses segregated First Fit for smaller allocations
The NT heap manager historically used First Fit for coalesced blocks

User-Space Memory Allocators

glibc malloc (ptmalloc2):

Uses First Fit within unsorted bins
Employs Best Fit for large bins (sorted by size)
Demonstrates that pure strategies are rarely used alone

jemalloc (used by Firefox, Facebook):

Uses First Fit for selecting runs within arenas
Emphasizes per-thread caching to reduce contention

tcmalloc (Google's allocator):

Thread-caching with First Fit for span allocation
Optimized for high allocation rates in multithreaded programs

First Fit in Production Systems
System/Allocator	Where First Fit Is Used	Why First Fit
Linux Buddy Allocator	Within each order's free list	Simplicity, O(1) common case
glibc malloc	Unsorted bin allocation	Speed for recent frees
FreeBSD UMA (slab)	Zone selection	Cache efficiency
Ext4 Block Allocator	Block group scanning	Locality of allocation
JVM G1 Garbage Collector	Region selection	Predictable latency

Embedded and Real-Time Systems

First Fit is particularly popular in embedded systems due to:

Predictable worst-case: O(n) is bounded and analyzable
Low code complexity: Smaller code footprint for resource-constrained devices
No dynamic data structures: Can be implemented with static arrays
Deterministic: No randomization that could affect timing analysis

However, for hard real-time systems, even O(n) worst-case may be unacceptable, motivating specialized allocators like TLSF (Two-Level Segregated Fit) that achieve O(1) with First Fit semantics.

Summary: The First Fit Strategy

We have explored First Fit comprehensively—from its elegant simplicity to its nuanced real-world behavior. Let us consolidate the essential points:

Key Takeaways

•Definition: First Fit allocates the first block large enough to satisfy the request, scanning from the beginning of the free list
•Time Complexity: O(n) worst case, but often O(1) in practice due to early termination
•Fragmentation: Produces moderate external fragmentation with characteristic front-loading pattern
•Block Splitting: Requires minimum block size enforcement to prevent useless slivers
•Traversal Pattern: Address-ordered lists create predictable allocation patterns but accumulate front-end fragments
•Optimizations: Segregated lists, binary trees, and bitmaps can dramatically improve performance while preserving First Fit semantics
•Real-World Use: Remains the default or component strategy in most production allocators due to simplicity and acceptable performance

What's Next:

Now that we understand First Fit, we will examine Best Fit—a strategy that trades search time for potentially better memory utilization by always selecting the smallest sufficient block.

Page Complete

1 / 5