Allocation-Free and Cache-Friendly Code

A hot path is the code that runs for every message or event, so its cost is paid millions of times per second. This lesson combines techniques taught earlier into one practice: the hot path allocates nothing after warmup, touches memory in order, and never blocks. After it, a reader can measure allocation per operation, remove it, and explain why each change lowers tail latency.

Technique	Removes	Taught in detail in
Allocation measurement	Guessing	This lesson
Primitive collections	Boxing, entry objects	Primitive Collections
Pools and mutable holders	Per-message objects	This lesson
Flyweights over buffers	Decoded objects	ByteBuffer and Direct Buffers
Reused text buffers	`String` creation in logging	This lesson
Arrays of primitives	Pointer chasing	CPU Caches and Locality
Busy spinning and affinity	Wake-up delay, migration	Processes, Threads, and Scheduling
Single writer	Contention	Ring Buffers and Lock-Free Queues

The reason to avoid allocation is the garbage collector: fewer allocated bytes means fewer young collections and fewer pauses (GC Fundamentals). Escape analysis removes some allocations automatically, but only when the JIT can prove the object does not escape (Escape Analysis), so the result has to be measured.

Example 1: measuring bytes per operation

com.sun.management.ThreadMXBean extends the standard java.lang.management.ThreadMXBean with getThreadAllocatedBytes(long id), which returns the bytes a thread has allocated on the heap so far. Reading it before and after a loop and dividing by the iteration count gives bytes per operation. A warmup loop first lets the JIT compile the code, because interpreted code allocates where compiled code may not.

Java

import java.lang.management.ManagementFactory;

public class AllocMeter {
    static final com.sun.management.ThreadMXBean MX =
            (com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean();

    static long allocated() {
        return MX.getThreadAllocatedBytes(Thread.currentThread().threadId());
    }

    static long sink;

    static void boxed(int n) {
        for (int i = 0; i < n; i++) {
            Long v = Long.valueOf(i * 1_000L);   // outside the -128..127 cache
            sink += v.hashCode();
            consume(v);
        }
    }

    static Object last;
    static void consume(Object o) { last = o; }  // the object escapes to a field

    static void primitive(int n) {
        for (int i = 0; i < n; i++) {
            long v = i * 1_000L;
            sink += Long.hashCode(v);
        }
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        for (int w = 0; w < 20; w++) { boxed(n); primitive(n); }

        long before = allocated();
        boxed(n);
        long boxedBytes = allocated() - before;

        before = allocated();
        primitive(n);
        long primBytes = allocated() - before;

        System.out.println("boxed bytes/op: " + Math.round((double) boxedBytes / n));
        System.out.println("primitive bytes/op: " + Math.round((double) primBytes / n));
    }
}

Output

boxed bytes/op: 24
primitive bytes/op: 0

Each Long outside the cache is a 24-byte object: a 12-byte header plus 8 bytes of value is 20 bytes, rounded up to the 8-byte object alignment (see Object Layout). Storing it in a static field makes it escape, so the JIT cannot remove it. The primitive loop allocates nothing. The same meter is used in every example below.

Example 2: boxing and iterators in collections

A HashMap<Integer, Long> allocates a node per new key and a Long per updated value outside the cache. Iterating with for-each allocates an Iterator unless escape analysis removes it. A primitive map from fastutil stores keys and values in int[] and long[] arrays and updates in place.

Java

import it.unimi.dsi.fastutil.ints.Int2LongOpenHashMap;
import java.lang.management.ManagementFactory;
import java.util.HashMap;
import java.util.Map;

public class PositionMaps {
    static final com.sun.management.ThreadMXBean MX =
            (com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean();
    static long allocated() { return MX.getThreadAllocatedBytes(Thread.currentThread().threadId()); }

    static final Map<Integer, Long> boxed = new HashMap<>();
    static final Int2LongOpenHashMap prim = new Int2LongOpenHashMap(1024);

    static void fillBoxed(int n) {
        for (int i = 0; i < n; i++) boxed.merge(i & 511, 1_000L, Long::sum);
    }

    static void fillPrim(int n) {
        for (int i = 0; i < n; i++) prim.addTo(i & 511, 1_000L);
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        for (int w = 0; w < 20; w++) { fillBoxed(n); fillPrim(n); }

        long b = allocated();
        fillBoxed(n);
        long boxedBytes = allocated() - b;
        b = allocated();
        fillPrim(n);
        long primBytes = allocated() - b;

        System.out.println("HashMap<Integer,Long> bytes/op: " + Math.round((double) boxedBytes / n));
        System.out.println("Int2LongOpenHashMap bytes/op: " + Math.round((double) primBytes / n));
        System.out.println("same total for key 7: " + (boxed.get(7) == prim.get(7)));
    }
}

Output

HashMap<Integer,Long> bytes/op: 60
Int2LongOpenHashMap bytes/op: 0
same total for key 7: true

The keys 0..511 are not all inside the Integer cache (-128..127), and the sums are far outside the Long cache, so each merge call allocates three objects: the Long for the argument 1_000L (24 bytes), the Long for the new sum (24 bytes), and an Integer key for 384 of the 512 keys (16 bytes, 12 on average). That is the 60 bytes per operation. addTo changes a long slot in the value array. The primitive map was sized for 1,024 entries up front, so it never resizes during the run.

Example 3: pools and mutable value holders

A mutable value holder is a class with settable fields that is filled, used, and cleared instead of being created for each message. A pool keeps a fixed number of holders and hands them out. On a single thread, the pool is a plain array used as a stack, with no locks.

Java

import java.lang.management.ManagementFactory;

public class OrderPool {
    static final com.sun.management.ThreadMXBean MX =
            (com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean();
    static long allocated() { return MX.getThreadAllocatedBytes(Thread.currentThread().threadId()); }

    static final class Order {          // mutable holder
        long id; long price; int qty; boolean buy;
        Order set(long id, long price, int qty, boolean buy) {
            this.id = id; this.price = price; this.qty = qty; this.buy = buy; return this;
        }
        void clear() { id = 0; price = 0; qty = 0; buy = false; }
    }

    static final class Pool {           // single-threaded, fixed capacity
        private final Order[] free;
        private int top;
        Pool(int capacity) {
            free = new Order[capacity];
            for (int i = 0; i < capacity; i++) free[i] = new Order();
            top = capacity;
        }
        Order acquire() {
            if (top == 0) throw new IllegalStateException("pool exhausted");
            return free[--top];
        }
        void release(Order o) { o.clear(); free[top++] = o; }
        int available() { return top; }
    }

    static long notional;

    static void handle(Pool pool, int n) {
        for (int i = 0; i < n; i++) {
            Order o = pool.acquire().set(i, 10_000 + (i & 7), 5, (i & 1) == 0);
            notional += o.price * o.qty;
            pool.release(o);
        }
    }

    public static void main(String[] args) {
        Pool pool = new Pool(64);
        int n = 1_000_000;
        for (int w = 0; w < 20; w++) handle(pool, n);
        notional = 0;

        long b = allocated();
        handle(pool, n);
        long bytes = allocated() - b;

        System.out.println("bytes/op: " + Math.round((double) bytes / n));
        System.out.println("notional: " + notional);
        System.out.println("all returned: " + (pool.available() == 64));
    }
}

Output

bytes/op: 0
notional: 50017500000
all returned: true

A pool has costs that a reader states with it: a holder that is used after release sees another message's data, and a leak (no release) empties the pool. Pools pay off for objects that live across calls; a short-lived object that never escapes is often removed by escape analysis, and pooling it only adds code.

Example 4: a flyweight over a buffer

A flyweight is one reusable object that reads fields directly from a buffer at an offset, so decoding a message creates no objects. The same instance is moved over each message with wrap. The buffer is a direct ByteBuffer, as taught in ByteBuffer and Direct Buffers.

Java

import java.lang.management.ManagementFactory;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;

public class TradeFlyweight {
    static final com.sun.management.ThreadMXBean MX =
            (com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean();
    static long allocated() { return MX.getThreadAllocatedBytes(Thread.currentThread().threadId()); }

    static final int SIZE = 24;         // id 8, price 8, qty 4, side 1, pad 3

    static final class TradeView {
        private ByteBuffer buf;
        private int base;
        TradeView wrap(ByteBuffer buf, int offset) { this.buf = buf; this.base = offset; return this; }
        long id()    { return buf.getLong(base); }
        long price() { return buf.getLong(base + 8); }
        int qty()    { return buf.getInt(base + 16); }
        boolean buy() { return buf.get(base + 20) == 1; }
    }

    public static void main(String[] args) {
        int count = 4096;
        ByteBuffer buf = ByteBuffer.allocateDirect(count * SIZE).order(ByteOrder.LITTLE_ENDIAN);
        for (int i = 0; i < count; i++) {
            int o = i * SIZE;
            buf.putLong(o, i).putLong(o + 8, 100 + i % 10).putInt(o + 16, 1 + i % 3).put(o + 20, (byte) (i & 1));
        }

        TradeView view = new TradeView();
        long buyQty = 0;
        for (int w = 0; w < 2_000; w++) buyQty += scan(view, buf, count);

        long b = allocated();
        buyQty = scan(view, buf, count);
        long bytes = allocated() - b;

        System.out.println("buy quantity: " + buyQty);
        System.out.println("bytes per message: " + Math.round((double) bytes / count));
    }

    static long scan(TradeView view, ByteBuffer buf, int count) {
        long sum = 0;
        for (int i = 0; i < count; i++) {
            view.wrap(buf, i * SIZE);
            if (view.buy()) sum += view.qty();
        }
        return sum;
    }
}

Output

buy quantity: 4095
bytes per message: 0

The view holds only a reference and an offset. Fixed offsets are what make this possible; Binary Protocols covers how such layouts are designed, and SBE generates flyweights like this from a schema (Agrona, Aeron, SBE, and Chronicle).

Example 5: string-free logging and pre-sizing

String concatenation allocates a String and its byte[] for every log line. A reused StringBuilder with enough capacity appends numbers and characters without allocating, and the text is copied into a pre-allocated byte array that a background thread or an off-heap buffer would write out. Pre-sizing also matters for collections: an ArrayList that grows copies its array at each growth step.

Java

import java.lang.management.ManagementFactory;
import java.util.ArrayList;

public class QuietLogging {
    static final com.sun.management.ThreadMXBean MX =
            (com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean();
    static long allocated() { return MX.getThreadAllocatedBytes(Thread.currentThread().threadId()); }

    static final StringBuilder line = new StringBuilder(128);
    static final byte[] out = new byte[128];
    static int lastLength;
    static String lastString;

    static void logConcat(long id, long price) {
        lastString = "fill id=" + id + " px=" + price;
    }

    static void logReused(long id, long price) {
        line.setLength(0);
        line.append("fill id=").append(id).append(" px=").append(price);
        int len = line.length();
        for (int i = 0; i < len; i++) out[i] = (byte) line.charAt(i);   // ASCII only
        lastLength = len;
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        for (int w = 0; w < 20; w++) {
            for (int i = 0; i < n; i++) { logConcat(i, 10_050); logReused(i, 10_050); }
        }

        long b = allocated();
        for (int i = 0; i < n; i++) logConcat(i, 10_050);
        long concat = allocated() - b;

        b = allocated();
        for (int i = 0; i < n; i++) logReused(i, 10_050);
        long reused = allocated() - b;

        System.out.println("concat bytes/line > 0: " + (concat / n > 0));
        System.out.println("reused bytes/line: " + Math.round((double) reused / n));
        System.out.println("last line: " + new String(out, 0, lastLength));

        b = allocated();
        ArrayList<Object> grown = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) grown.add(line);
        long grownBytes = allocated() - b;

        b = allocated();
        ArrayList<Object> sized = new ArrayList<>(100_000);
        for (int i = 0; i < 100_000; i++) sized.add(line);
        long sizedBytes = allocated() - b;

        System.out.println("growing list allocates more: " + (grownBytes > sizedBytes));
    }
}

Output

concat bytes/line > 0: true
reused bytes/line: 0
last line: fill id=999999 px=10050
growing list allocates more: true

The concatenated line's size depends on the digits of id, so the example prints a check rather than a number. ArrayList grows by half its size each time (newCapacity = old + old >> 1 in ArraysSupport.newLength), so filling it from empty allocates and copies a chain of arrays, while the pre-sized list allocates one array.

Example 6: a cache-friendly layout

An array of objects stores references; each element is a separate heap object that may sit anywhere. An array of primitives per field, called a structure of arrays, stores values next to each other, so a scan reads consecutive cache lines and the hardware prefetcher can predict them (CPU Caches and Locality). The example prints sums, not times, because timing depends on the machine.

Java

public class Layouts {
    record Quote(long price, int size) {}

    static final class QuoteColumns {       // structure of arrays
        final long[] price; final int[] size;
        QuoteColumns(int n) { price = new long[n]; size = new int[n]; }
    }

    public static void main(String[] args) {
        int n = 1 << 16;
        Quote[] objects = new Quote[n];
        QuoteColumns cols = new QuoteColumns(n);
        for (int i = 0; i < n; i++) {
            objects[i] = new Quote(100 + i % 50, 1 + i % 9);
            cols.price[i] = 100 + i % 50;
            cols.size[i] = 1 + i % 9;
        }

        long a = 0;
        for (Quote q : objects) a += q.price() * q.size();
        long c = 0;
        for (int i = 0; i < n; i++) c += cols.price[i] * cols.size[i];

        System.out.println("array of objects: " + a);
        System.out.println("structure of arrays: " + c);
        System.out.println("bytes of price data in columns: " + (long) n * Long.BYTES);
    }
}

Output

array of objects: 40794014
structure of arrays: 40794014
bytes of price data in columns: 524288

Both layouts compute the same value. The difference is in memory traffic: each Quote costs a 4-byte reference plus a 24-byte object, while the columns cost 12 bytes per quote with no headers and no indirection. JMH is the tool for timing the two scans on a given machine.

Example 7: busy spinning and the single writer

A thread that waits by blocking (LockSupport.park, wait) gives up the CPU, and waking it costs microseconds of scheduler work. A busy-spinning thread loops on a volatile read instead and calls Thread.onSpinWait() (Java 9), which on x86 emits a PAUSE instruction that lowers power use and avoids a memory-order pipeline flush when the value changes. The single-writer principle says each variable has exactly one thread that writes it; here the producer alone writes published and the consumer alone writes consumed, so neither needs CAS.

Java

import java.util.concurrent.atomic.AtomicLong;

public class SpinHandoff {
    static final long[] slots = new long[1024];
    static final AtomicLong published = new AtomicLong(-1);  // written by producer only
    static final AtomicLong consumed = new AtomicLong(-1);   // written by consumer only

    public static void main(String[] args) throws InterruptedException {
        int messages = 1_000_000;

        Thread consumer = new Thread(() -> {
            long sum = 0;
            for (long seq = 0; seq < messages; seq++) {
                while (published.get() < seq) Thread.onSpinWait();
                sum += slots[(int) (seq & 1023)];
                consumed.lazySet(seq);                         // release store
            }
            System.out.println("consumer sum: " + sum);
        });
        consumer.start();

        for (long seq = 0; seq < messages; seq++) {
            while (seq - consumed.get() > 1024) Thread.onSpinWait();   // wait for space
            slots[(int) (seq & 1023)] = seq;
            published.lazySet(seq);
        }
        consumer.join();
        long expected = (long) messages * (messages - 1) / 2;
        System.out.println("expected sum: " + expected);
    }
}

Output

consumer sum: 499999500000
expected sum: 499999500000

This is the ring buffer from Ring Buffers and Lock-Free Queues reduced to its sequences. lazySet is a release store, which is enough because each counter has one writer (VarHandle, Access Modes, and Fences). A spinning thread holds a full core at 100% even when idle, so it is used only on machines with spare isolated cores. Idle strategies that back off from spinning to yielding to parking are shown in the next lesson.

Thread affinity pins a thread to one CPU so it is not migrated and its caches stay warm. The JDK has no API for it. Linux offers taskset and isolcpus at the process level (Processes, Threads, and Scheduling). The OpenHFT Java-Thread-Affinity library (net.openhft.affinity) calls sched_setaffinity for the current thread; it is not on this course's class path, so the sketch below is not compiled.

Java

// Not compiled: OpenHFT Affinity is not on the checker's class path.
try (AffinityLock lock = AffinityLock.acquireLock()) {   // reserves a free core
    runEventLoop();                                      // runs pinned to that core
}

Example 8: an allocation-free order handler

The last example combines the techniques: a flyweight decodes orders from a direct buffer, a primitive map holds net positions per instrument, a reused builder formats an audit line, and the meter checks that steady state allocates nothing.

Java

import it.unimi.dsi.fastutil.ints.Int2LongOpenHashMap;
import java.lang.management.ManagementFactory;
import java.nio.ByteBuffer;

public class OrderHandler {
    static final com.sun.management.ThreadMXBean MX =
            (com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean();
    static long allocated() { return MX.getThreadAllocatedBytes(Thread.currentThread().threadId()); }

    static final int SIZE = 16;            // instrument 4, qty 4, price 8

    static final class OrderView {
        ByteBuffer buf; int base;
        OrderView wrap(ByteBuffer b, int off) { buf = b; base = off; return this; }
        int instrument() { return buf.getInt(base); }
        int qty()        { return buf.getInt(base + 4); }   // negative = sell
        long price()     { return buf.getLong(base + 8); }
    }

    final OrderView view = new OrderView();
    final Int2LongOpenHashMap position = new Int2LongOpenHashMap(256);
    final StringBuilder audit = new StringBuilder(64);
    long rejected;

    void onBatch(ByteBuffer buf, int count) {
        for (int i = 0; i < count; i++) {
            OrderView o = view.wrap(buf, i * SIZE);
            long next = position.get(o.instrument()) + o.qty();
            if (Math.abs(next) > 1_000) {               // risk limit
                rejected++;
                audit.setLength(0);
                audit.append("reject inst=").append(o.instrument()).append(" qty=").append(o.qty());
                continue;
            }
            position.put(o.instrument(), next);
        }
    }

    public static void main(String[] args) {
        int count = 1024;
        ByteBuffer buf = ByteBuffer.allocateDirect(count * SIZE);
        for (int i = 0; i < count; i++) {
            int qty = (i % 3 == 0) ? -40 : 30;
            buf.putInt(i * SIZE, i % 16).putInt(i * SIZE + 4, qty).putLong(i * SIZE + 8, 10_000 + i);
        }

        OrderHandler h = new OrderHandler();
        for (int i = 0; i < 16; i++) h.position.put(i, 0);   // pre-insert every key
        for (int w = 0; w < 5_000; w++) h.onBatch(buf, count);

        h.rejected = 0;
        long b = allocated();
        for (int r = 0; r < 100; r++) h.onBatch(buf, count);
        long bytes = allocated() - b;

        System.out.println("orders: " + 100 * count);
        System.out.println("bytes/order: " + Math.round((double) bytes / (100 * count)));
        System.out.println("rejected > 0: " + (h.rejected > 0));
        System.out.println("positions within limit: "
                + h.position.values().longStream().allMatch(p -> Math.abs(p) <= 1_000));
    }
}

Output

orders: 102400
bytes/order: 0
rejected > 0: true
positions within limit: true

Keys are inserted before warmup so that put never triggers a rehash on the hot path. The final check uses a stream, which allocates, but it runs after the measured section. In production the same measurement runs as a test: a regression that adds one boxed value per order shows up as 24 bytes per order.

Interview points

Allocation per operation is measured with com.sun.management.ThreadMXBean.getThreadAllocatedBytes around a warmed-up loop; the goal on a hot path is 0 bytes per operation in steady state.
Fewer allocated bytes means fewer young collections, which lowers tail latency more than average latency.
Escape analysis removes non-escaping objects but cannot be relied on; measure.
Boxing allocates outside the small-value caches (-128..127); primitive collections such as fastutil store values in arrays and update them in place.
Pools suit long-lived reusable holders; their risks are use-after-release and leaks.
A flyweight reads fields from a buffer at fixed offsets; one instance is re-wrapped per message.
Logging on a hot path appends to a reused buffer; formatting into String allocates each time.
Structure-of-arrays layouts give sequential memory access with no headers or pointers.
Busy spinning with Thread.onSpinWait trades a full core for no wake-up latency; affinity keeps that core dedicated.
With a single writer per variable, a release store (lazySet) replaces CAS.

Summary

getThreadAllocatedBytes(threadId) reports heap bytes allocated by one thread.
A Long outside the cache costs 24 bytes; HashMap.merge with boxed arguments allocated 60 bytes per call here.
Int2LongOpenHashMap.addTo updates a primitive slot without allocation.
Pools, mutable holders, and flyweights replace per-message objects.
A reused StringBuilder with enough capacity appends numbers without allocation.
ArrayList grows by 50% per step; pre-sizing avoids the copies.
Thread.onSpinWait (Java 9) is a spin-loop hint, PAUSE on x86.
The JDK has no thread-affinity API; OpenHFT Affinity or taskset provide it.