subroute.
Intermediate9 min readlive prototype

Next Fit

First Fit with a memory: resume scanning where you stopped last time, wrapping around the end.

Overview

What this concept solves

Next Fit is a small but pointed tweak to First Fit. First Fit always begins its scan at the start of memory, which means the front holes get visited — and split — over and over, while the average scan grows longer as the heap ages. Next Fit fixes this by keeping a roving pointer: it resumes each scan from wherever the last allocation landed, and only wraps back to the beginning if it hits the end without finding a fit.

The effect is that allocations spread out across memory rather than piling up at the front. The pointer sweeps forward like a clock hand, distributing requests around the address space. Each allocation is still 'first fit from the current position,' so it keeps First Fit's early-stop speed — but the starting point moves, so no single region bears the full scan burden.

Whether that's better depends on the workload. Spreading reduces the front-loading pathology and can shorten scans, but it also scatters allocations, which can hurt locality and sometimes fragments memory more evenly (and thus more pervasively). On the shared four-process workload Next Fit ends up with the same failure as First Fit — but a different heap shape, which is the real lesson.

Mechanics

How it works

The roving pointer

  1. Start where you left off. Begin scanning from the saved bookmark — the position of the most recent allocation — not from the start of memory.
  2. Take the first hole that fits, just like First Fit, scanning forward.
  3. Wrap around. If you reach the end of memory without a fit, continue from address 0 and scan up to the bookmark. Only after a full loop with no fit does the request fail.
  4. Move the bookmark. When you place the request, save its position as the new starting point for the next allocation.

Why wrap-around matters

The wrap is what keeps Next Fit correct: without it, holes behind the pointer would be invisible and the allocator could fail spuriously while free space sat unused at low addresses. The scan is therefore a full circular sweep — at most O(n) — that just happens to start at the bookmark instead of at zero.

The trade for spreading

Spreading allocations around memory has a cost: it tends to leave free space distributed in many medium holes rather than consolidated. Some studies find Next Fit fragments slightly worse than First Fit because it doesn't give low-address holes a chance to be refilled and coalesced. It also scatters related allocations, which can reduce cache and page locality.

Interactive prototype

Run it. Break it. Tune it.

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

About this simulation

Next Fit is First Fit with a memory: it keeps a bookmark at the last allocation and resumes scanning from there, wrapping around the end of memory back to the start. The '↻ resume here' marker shows where the next scan begins. Scenario 1 · Four-process run shows allocations spreading forward instead of clustering at the front. Scenario 2 · The sliver trap shows the rolling pointer still finding a home for the small final request.

Hands-on

Try these on your own

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

try 01

Follow the bookmark

On scenario 1 · Four-process run, step through and watch the '↻ resume here' marker. P1 (212K) is placed and the bookmark lands on it; P2's scan then resumes from there rather than restarting at address 0. Notice how each allocation pushes the bookmark forward — the scan never goes back to the front unless it wraps.

try 02

Compare the heap shape to First Fit

Run scenario 1 to the end. Like First Fit, Next Fit fails P4 (426K) — 3 of 4 placed — but the arrangement of allocations is different: they're spread further across memory instead of clustered near the front. Open the First Fit page, run the same scenario, and compare where each process ended up. Same input, same failure, different shape.

try 03

Watch a wrap-around

Switch to scenario 2 · The sliver trap and step through. After the first two requests push the bookmark toward the end, the small final request resumes from there, finds no fit ahead, and wraps back to the start to land in the leftover near address 0. Watch for the 'Reached the end of memory — wrap back' narration. Use Restart and Auto to replay the sweep.

In practice

When to use it — and what you give up

When Next Fit fits

  • The front of memory keeps filling with small holes under First Fit — Next Fit's roving start avoids re-scanning that congested region every time.
  • You want allocations spread evenly across the address space rather than concentrated at the front.
  • Allocation speed matters and the free list is long — resuming mid-list keeps the common scan short.
  • Be wary if locality matters — scattering related allocations across memory can hurt cache/page behavior; and the fragmentation profile is sometimes worse than plain First Fit. Measure on your workload.

A common building block

The roving-pointer idea shows up well beyond classic free-list allocators — it's the same insight behind the Clock page-replacement algorithm (a hand sweeping circularly through frames) and behind bump-pointer allocators that advance through an arena. 'Resume where you stopped, wrap when you reach the end' is a broadly reusable pattern.

Pros

  • Avoids front-loading — doesn't repeatedly re-scan and split the low-address holes.
  • Fast — keeps First Fit's early stop; the average scan can be shorter than First Fit's on an aged heap.
  • Even distribution — allocations spread across the whole address space.
  • Simple — one extra saved pointer on top of First Fit.

Cons

  • Can fragment more evenly (and thus more pervasively) than First Fit on some workloads.
  • Hurts locality — related allocations get scattered around memory.
  • Still external fragmentation — wrapping doesn't conjure a hole big enough; large requests can still fail.
  • Outcome depends on history — the same request can land in different places depending on where the bookmark is.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

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

class NextFit {
  private last = 0; // roving bookmark: index to resume from

  alloc(holes: Hole[], request: number): number | null {
    const n = holes.length;
    for (let step = 0; step < n; step++) {
      const i = (this.last + step) % n;   // resume at bookmark, wrap with %
      if (holes[i].size >= request) {     // first fit from current position
        const addr = holes[i].start;
        const leftover = holes[i].size - request;
        if (leftover === 0) holes.splice(i, 1);
        else { holes[i].start += request; holes[i].size = leftover; }
        this.last = i;                    // save bookmark for next time
        return addr;
      }
    }
    return null;                          // full loop, no fit: fail
  }
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

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

question 01 / 03

How does Next Fit differ from First Fit?

question 02 / 03

Why must Next Fit wrap around to the start of memory?

question 03 / 03

On the four-process workload, how does Next Fit's result compare to First Fit's?

0/3 answered

Was this concept helpful?

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

Back to Memory Allocation