subroute.
Beginner9 min readlive prototype

First Fit

Scan from the start, grab the first hole big enough. The fast, simple default — and where fragmentation begins.

Overview

What this concept solves

First Fit is the simplest allocation policy that actually works well. Keep a list of free holes in memory. When a request for n bytes arrives, walk the list from the beginning and hand back the *first hole that is at least n bytes. If the hole is bigger than needed, carve off the front, give that to the request, and leave the remainder as a smaller free hole. If you reach the end without finding one, the allocation fails — even if the total free space exceeds n*.

That last sentence is the whole drama of dynamic allocation. Free memory is rarely contiguous; it's a patchwork of holes left behind as variable-sized objects come and go. A request can fail not because memory is exhausted but because no single hole is large enough. This is external fragmentation, and every sequential-fit strategy is really just a different bet about how to keep the holes usable.

First Fit's bet is the laziest possible one: don't think, just take the first thing that fits. It sounds careless, but decades of study (and Knuth's own simulations) found it's one of the best general policies — fast because it stops scanning early, and it tends to leave larger holes toward the end of memory where bigger requests can still land.

Mechanics

How it works

The scan-and-split loop

  1. Walk the free list from the start. Visit each hole in address order, skipping reserved regions.
  2. Stop at the first hole that fits. The instant you find a hole of size ≥ the request, you're done scanning — no need to look further. This early stop is why First Fit is fast.
  3. Split the hole. Give the request the front of the hole. If anything is left over, that remainder becomes a new, smaller free hole sitting right after the allocation.
  4. Or fail. If the scan reaches the end with no hole big enough, the request fails — report external fragmentation, even though free memory in total may dwarf the request.

The free list, and why order matters

Allocators keep free holes in a linked list. First Fit traditionally keeps that list sorted by address, so the scan always starts at low memory. A consequence: small allocations pile up near the front, and the front of memory slowly fills with little holes the scan has to step over every time — the average scan gets longer as the heap ages. (A variant, Next Fit, fixes exactly this by resuming where the last scan left off.)

Splitting creates the fragments

Every time a hole is bigger than the request, the leftover becomes a new hole. Over thousands of allocations, big holes get whittled into smaller and smaller pieces. The allocator isn't doing anything wrong — splitting is unavoidable when requests don't exactly match holes — but it's the mechanism by which a healthy heap slowly fragments.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

Memory is a strip of reserved regions and free holes. A process arrives needing some space; First Fit scans the holes left to right and grabs the first one big enough, splitting it and leaving the remainder free. Step through with Prev / Next / Auto. Scenario 1 · Four-process run uses the canonical workload shared across all four fit strategies — watch whether the big 600K hole survives for P4. Scenario 2 · The sliver trap shows where First Fit's speed pays off.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Run the four-process workload

On scenario 1 · Four-process run, step through with Next. Watch First Fit place P1 (212K) in the 500K hole — the first that fits — even though tighter holes exist. By the time P4 (426K) arrives, the holes have been split down and P4 fails, despite plenty of total free memory. Note the 'Free' stat staying high while the allocation still fails: that's external fragmentation in one screen.

try 02

Compare against Best Fit on the same input

This exact workload is shared by all four fit pages. Remember First Fit's result (P4 fails, 3 of 4 placed), then open the Best Fit page and run scenario 1 there. Best Fit places all four — because First Fit spent the 500K hole on P1 while Best Fit saved larger holes. Same input, different policy, different outcome.

try 03

See where First Fit wins — the sliver trap

Switch to scenario 2 · The sliver trap and step through. Here First Fit places all three requests, while Best Fit (try it on its page) fails the small final request. First Fit's habit of grabbing the first roomy hole leaves a usable leftover; Best Fit's precision manufactures slivers too small to use. Use Restart and Auto to replay both.

In practice

When to use it — and what you give up

When First Fit is the right call

  • You want a simple, fast general-purpose allocator — First Fit is the sensible default. It's easy to implement, it stops scanning early, and in practice it performs about as well as the more elaborate fits.
  • Allocation latency matters more than squeezing out the last byte — early termination keeps the common case cheap.
  • Your workload is a mix of sizes — First Fit handles variety gracefully and tends to preserve large holes at higher addresses for the occasional big request.
  • Be cautious when the front of memory fills with tiny holes — scan time creeps up as the heap ages. If you see that, reach for Next Fit (resume the scan) or a segregated free list (bucket holes by size).

Real-world note

Production malloc implementations don't run a naive single-list First Fit, but the idea is everywhere: glibc's allocator, for instance, uses size-segregated bins and within them does a fit search. First Fit (and its cousin Next Fit) is the conceptual core you'd reach for inside a custom arena, a simple embedded allocator, or a teaching implementation.

Pros

  • Fast — stops at the first match instead of scanning the whole list.
  • Simple to implement and reason about.
  • Performs well in practice — empirically competitive with or better than Best Fit on real workloads.
  • Preserves large holes at higher addresses for bigger requests that arrive later.

Cons

  • External fragmentation — splitting leaves the heap dotted with holes that may be too small to reuse.
  • Front-loading — small holes accumulate near the start, lengthening the average scan as the heap ages.
  • No size awareness — it may carve a big hole for a small request when a tighter hole sat further along (the problem Best Fit tries to solve).
  • Worst-case O(n) scan over the free list per allocation.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

first-fit.ts
interface Hole { start: number; size: number; }

/** First Fit: return the first hole large enough, splitting it. */
function firstFitAlloc(holes: Hole[], request: number): number | null {
  for (let i = 0; i < holes.length; i++) {
    const hole = holes[i];
    if (hole.size >= request) {        // first one that fits — stop here
      const addr = hole.start;
      const leftover = hole.size - request;
      if (leftover === 0) {
        holes.splice(i, 1);            // exact fit: remove the hole
      } else {
        hole.start += request;         // shrink the hole from the front
        hole.size = leftover;          // remainder stays free
      }
      return addr;                     // address handed to the request
    }
  }
  return null;                         // external fragmentation: no single hole fits
}

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What does First Fit do the moment it finds a hole large enough for the request?

question 02 / 03

A request for 426K fails even though 959K is free in total. What is this called?

question 03 / 03

Why do small holes tend to accumulate near the start of memory under First Fit?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Memory Allocation