DEV Community: Gaurav Tyagi

I Benchmarked CAS vs. a Lock — and Caught Myself Drawing the Wrong Conclusion Halfway Through

Gaurav Tyagi — Wed, 23 Sep 2026 10:18:25 +0000

"Lock-free beats locks" is close to something of a folk wisdom in Java concurrency circles. Wanting a concrete answer, I implemented both a hand-rolled compare-and-swap (CAS) retry loop and a plain synchronized counter in a Java project — benchmarked the two against each other under JMH with a 1/2/4/6/8 thread sweep on 4-core hardware. The first result I'd gotten almost led me to a precisely the sort of over generalization that made me want to run the test in the first place.

The setup: two counters, same shape

Both of the benchmarked implementations increment and return in a single atomic call, implemented deliberately via hand-rolled code rather than directly via AtomicInteger.incrementAndGet(), to expose the retry mechanism:

// CASCounter — a hand-rolled CAS retry loop
public int incrementAndGet() {
int expected = counter.get();
while (!counter.compareAndSet(expected, expected + 1)) {
expected = counter.get();
}
return expected + 1;
}

// LockCounter — mutual exclusion via a monitor
public synchronized int incrementAndGet() {
counter++;
return counter;
}

The annotated (@State(Scope.Benchmark)) instances of these classes are shared between every thread in a given benchmark method, not per-thread — Scope.Thread would give each thread a distinct instance and make for effectively zero contention, as far as this benchmark is concerned.

A JMH trap that was hiding in the annotations

Each benchmark method loops 1,000,000 incrementAndGet() calls, and both classes thus have @OperationsPerInvocation(1_000_000). Here's what that annotation actually buys you, worked out in numbers rather than just asserted.

Without it, JMH's Mode.Throughput reports how many times the annotated @Benchmark method itself completes per second — not how many incrementAndGet() calls happen per second. Take the real, correctly-measured CAS number at 1 thread: ~120.1M increments/sec. Each call to call1() performs 1,000,000 of those increments before returning, so the method itself only completes about 120,100,000 ÷ 1,000,000 = 120.1 times per second. Strip the annotation, and that's the number JMH would report as "ops/s" — 120.1, not 120,100,000.

Now suppose that omission happened on only one side of the comparison — CASCounter's annotation missing, LockCounter's intact. JMH would report CAS at "120.1 ops/s" (loop completions) against Lock's correctly-annotated "57,200,000 ops/s" (actual per-increment rate). Read at face value, that makes Lock look roughly 57,200,000 ÷ 120.1 ≈ 476,000x faster than CAS — the exact opposite of reality, where CAS is actually ~2.1x faster at 1 thread. One missing annotation on one of two classes doesn't just blur the numbers, it can flip the conclusion entirely.

Even a symmetric mistake — both classes missing the annotation — wouldn't break the CAS-vs-Lock comparison (both numbers get divided by the same 1,000,000, so the ratio between them survives), but the absolute figures would become meaningless on their own: "120.1 ops/s" reads like a counter incrementing about 120 times a second, six orders of magnitude slower than what's actually happening. That's the specific failure mode the JMH methodology primer warns about — not vague noise, but a benchmark that reports a wrong number with total confidence.

First look — and the conclusion I almost drew

The first thing I ran benchmarked was CASCounter on its own, for the aggregate throughput of the threadCount-thread harness:

Threads	Throughput (relative)
1	129.6 (baseline)
2	14.5 (not ~2x, ~9x worse)
4	5.6
6	4.8
8	4.1

Increasing from 1 to 2 threads didn't roughly double the aggregated throughput of the program — it collapsed by ~9x. That would be an intuitively plausible opportunity for someone to conclude "well, obviously a lock would've done better here", having not actually run the other benchmark. Reading a conclusion about LockCounter out of results for CASCounter would be no different from concluding that "this program would be faster if it had a different set of inputs". The fact that CASCounter simply collapses under contention tells us nothing about it by itself, before running the other harness.

The real head-to-head

Running both counters through the same harness, normalized again to per-increment throughput (99.9% confidence intervals don't overlap on any thread count — this crossover is real):

Threads	CAS (ops/s)	Lock (ops/s)	Winner
1	~120.1 M	~57.2 M	CAS, ~2.1×
2	~14.6 M	~31.2 M	Lock, ~2.1×
4	~6.9 M	~16.6 M	Lock, ~2.4×
6	~5.6 M	~11.8 M	Lock, ~2.1×
8	~5.7 M	~10.2 M	Lock, ~1.8×

CAS wins uncontended by roughly an order of magnitude, but lock contention negates that advantage almost entirely and hands the victory to the lock by a similar margin. The uncontested CAS has a bare-metal CAS that has succeeded on the first try and thus is cheaper than even an uncontended synchronized block. Once there's any contention at all, the CAS's lack of backoff mechanism makes it much slower than the lock — the compareAndSet will always keep spinning in a tight loop without any pauses, whereas a thread blocked on a synchronized it doesn't hold waits entirely outside the coherence protocol.

Why the crossover happens: spin vs. park

Concrete trace of what happens when both Thread A and Thread B read the same value and CAS() fails, due to the cache line being invalidated by A's CAS() having succeeded:

sequenceDiagram
participant A as Thread A
participant Mem as counter (cache line)
participant B as Thread B

Mem-->>A: read counter = 5
Mem-->>B: read counter = 5
A->>Mem: CAS(5, 6) — succeeds
Note over Mem: cache line invalidated on every other core
B->>Mem: CAS(5, 6) — fails (live value is 6)
B->>Mem: re-read counter = 6
B->>Mem: CAS(6, 7) — succeeds

CASCounter.incrementAndGet() contains no backoff mechanism, and the moment a compareAndSet fails, will immediately proceed to re-read counter value and retry as many times as necessary in a spinloop until it manages to CAS() successfully. A thread that iblocked on a synchronized monitor it cannot acquire will instead enter park() and completely exit the cache-coherence picture until it manages to acquire the lock again.

The generalization — and it isn't "use locks"

The accurate generalization is a narrower, more specific one — a CAS retry loop in the absence of backoff mechanism loses to locks under contention. The resolution is an exponentially-increasing backoff with jitter, to prevent threads that collided from restarting at the same point in the spinloop and colliding again — but at this operation's nanosecond timescale, Thread.sleep() is the wrong level of granularity (nanoseconds vs. milliseconds) to have such a coarse-grained mechanism as sleep(). For smaller backoffs, Thread.onSpinWait() is appropriate (a CPU instruction on x86 telling the processor that this spinloop is waiting for an external event to happen and thus should occasionally yield to other threads), and eventually LockSupport.parkNanos() is more appropriate than sleep().

This is precisely the reason LongAdder exists and is able to outperform a single AtomicLong under contention: it does not pick a different mutual-exclusion primitive to handle the hot spot, but stripes the counter in such a way that threads collide less often in the first place. The same technique also powers the Disruptor's multi-producer case (though not the high-performance single-producer one): each producer operates on a cell of the array in turn, and each thread only collides with any other thread if they pick the same cell.

In fact, neither LongAdder nor Disruptor eliminates a shared touchpoint altogether, only reducing the frequency with which threads collide on it. The mechanisms described apply whenever threads do collide in spite of such measures and need to compete for access.

Takeaway

A benchmark's first result may not be a comparison. CASCounter's preliminary result, where increasing the number of threads from 1 to 2 caused a ~9x drop in throughput, did not say anything about LockCounter's behavior until both were actually benchmarked against each other. Once they had, the actual result turned out to be closer to a crossover than an outright rout, and the reason for this difference pointed directly to the means of resolution — backoff, and not a switch in primitives, was the appropriate action in this case.

The hashCode()-to-Array-Index Bug Almost Everyone Writes Once

Gaurav Tyagi — Sun, 06 Sep 2026 20:57:37 +0000

"hash % capacity" looks trivial until you trace it by hand. Two separate bugs hide in that one line — and the fix for one of them has its own hole.

Building a HashMap from scratch, the "turn a key into a bucket index" line looks like it should be the easy part:

int bucket = key.hashCode() % capacity;

I traced this by hand before writing a single line of MyHashMap, and it broke immediately — for a reason that has nothing to do with hashing.

Bug one: `%` isn't modulo

hashCode() returns a signed 32-bit int — anything from Integer.MIN_VALUE to Integer.MAX_VALUE, including negative numbers. Trace -7 % 16 in Java by hand before reading the next sentence.

Java's % is a remainder operator, not mathematical modulo — the result takes the sign of the dividend, not the divisor. -7 % 16 is -7, not 9. Feed that straight into array[bucket] and you get an ArrayIndexOutOfBoundsException, not a wrong-but-harmless bucket.

The naive fix has its own hole

First instinct: wrap it in Math.abs().

int bucket = Math.abs(key.hashCode() % capacity); // looks fixed. isn't, always.

This works for almost every input — and then silently breaks on exactly one value. Integer.MIN_VALUE (-2147483648) has no positive counterpart in 32-bit two's complement — the range is -2147483648 to 2147483647, one more negative number than positive. Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE itself, still negative. It's documented behavior, not a JVM bug — and it means Math.abs() doesn't actually guarantee a non-negative result for every int, which defeats the entire point of reaching for it here.

The actual fix

Math.floorMod(hash, capacity), added in Java 8, does true floored modulo — always non-negative for a positive divisor, no edge case:

private int getBucket(K key, int length) {
    int hashCode = key.hashCode();
    int hash = fnvHash(hashCode);
    int bucket = Math.floorMod(hash, length);
    return bucket;
}

Bug two (a design choice, really): bitmask vs. modulo

java.util.HashMap doesn't use modulo at all — it uses hash & (capacity - 1), a bitmask. That only works correctly when capacity is a power of two: 16 - 1 = 15 = 0b01111, a clean run of 1-bits that extracts exactly the low 4 bits regardless of the input's sign. Try it with a non-power-of-two capacity and the mask stops behaving like a clean modulo at all. In exchange for that constraint, bitmask AND is measurably faster than a division-based modulo — division/remainder is one of the more expensive basic ALU operations, and benchmarks commonly show bitmask coming out several times faster at scale.

MyHashMap deliberately went the other way: Math.floorMod instead of a bitmask, trading that speedup for not forcing capacity to always be a power of two. Worth being honest about which one you're picking and why, rather than defaulting to whichever the JDK does without registering there's a choice at all.

Bug three: fixing the sign doesn't fix distribution

Even with a correct, always-non-negative index, there's a separate problem hiding underneath. Bitmask (and, to a lesser extent, modulo) only meaningfully uses the low bits of the hash. If a class's hashCode() implementation happens to vary mostly in its high bits — this is common, not hypothetical (float-derived hashes and sequential object-identity hashes are classic examples) — a small table can collide those distinct hashCodes into the same few buckets, even though the hashCodes themselves are all different.

This is why java.util.HashMap doesn't use a key's raw hashCode() — it runs it through h ^ (h >>> 16) first: shift the top 16 bits down, XOR them into the bottom 16. Cheap — one shift, one XOR — and it's enough to fold high-bit entropy into the bits that actually get used for indexing.

MyHashMap goes further: a full FNV-1a mix over all four bytes of the hashCode, not just a single XOR-fold:

private static int fnvHash(int hashCode) {
    int hash = STARTING_SEED; // 0x811C9DC5, the FNV offset basis
    for (int shift = 24; shift >= 0; shift -= 8) {
        byte b = (byte) ((hashCode >> shift) & 0xFF);
        hash ^= (b & 0xFF);
        hash *= 0x01000193; // FNV prime, 32-bit
    }
    return hash;
}

This is a genuine cost/benefit tradeoff, not a strict improvement: four iterations of shift/XOR/multiply per hash call is meaningfully more work than the JDK's single shift-and-XOR. Whether that's worth it depends on how confident you are in your keys' hashCode() distribution and how hot the code path is — the JDK's choice is "cheapest fix that's good enough for general-purpose use," not "best possible mixing."

Takeaway

One line, three separate bugs, none of them about hashing itself: sign handling (and a naive fix for it that has its own edge case), a speed/flexibility tradeoff in how you reduce to a valid range, and a distribution problem that survives fixing the first two. Trace -7 % 16 by hand before you trust any "obviously correct" indexing line again.

I Built My Own Fail-Fast HashMap — Here's Why a Boolean Flag Wasn't Enough

Gaurav Tyagi — Sun, 30 Aug 2026 20:45:30 +0000

If you've done LeetCode's Design HashMap, you've implemented put, get, and remove. What that exercise usually skips is the part that actually breaks in production: what happens when someone mutates the map while another piece of code is iterating over it.

I ran into this directly while building MyHashMap, a from-scratch single-threaded HashMap (separate chaining, resize on load factor). Getting put/get/remove right was the easy 80%. Getting entrySet().iterator() to correctly detect concurrent mutation — including the case where a second, completely separate iterator is the one that should notice — took three wrong turns before landing on the pattern the JDK actually uses.

The problem, concretely

Iterator<Entry<K,V>> it = map.entrySet().iterator();
it.next();
map.put(someNewKey, someValue); // structural change, mid-iteration
it.next(); // ??? — undefined behavior if we don't guard against this

Without a guard, next() might return a stale entry, skip entries entirely, or throw an unrelated exception depending on internal bucket-array state. Java's real collections handle this with ConcurrentModificationException (CME) — but the interesting part isn't the exception, it's the mechanism that detects when to throw it.

First idea: a boolean "dirty" flag

Obvious first attempt: a boolean modified field on the map, flipped to true on any put/remove, checked by the iterator. This works for exactly one iterator. It falls apart the moment two iterators are alive at once:

Iterator A calls next(), sees modified == false, proceeds.
Something else mutates the map. modified flips to true.
Iterator B — created after that mutation — checks the same shared modified flag, sees true, and incorrectly throws, even though nothing has changed since B was created.

A single shared boolean can't represent "changed since this specific iterator was created" for more than one iterator at a time. Resetting it on read doesn't help either — now the other iterator stops seeing the change it legitimately needed to see.

Second idea: a timestamp

Next instinct: give the map a lastModified timestamp instead, and have each iterator capture the current time on creation. Compare timestamps instead of a shared flag — now each iterator has its own baseline.

This closes the multi-iterator gap, but introduces a different bug: resolution. Two mutations in a tight loop, or a mutation immediately followed by iterator creation, can land in the same millisecond (System.currentTimeMillis()) — or even the same tick of System.nanoTime() on some platforms. If a real modification and an iterator's baseline capture ever produce the same timestamp value, the comparison can't tell who happened first. Worse, currentTimeMillis() isn't even guaranteed monotonic — it can jump backward on a clock adjustment.

The deeper issue: this isn't a timing problem. It's a "did anything change since I looked" problem, and wall-clock time is the wrong tool for a question that has nothing to do with elapsed time.

What actually works: a monotonic counter (modCount)

Every mutation increments a plain long counter. Every iterator, at creation, snapshots the counter's current value. Every next() call compares its snapshot against the live value:

final class MyEntryIterator implements Iterator<Entry<K, V>> {
    private long expectedVersion;
    // ...
    public MyEntryIterator() {
        this.expectedVersion = version;   // snapshot at creation
    }

    @Override
    public Entry<K, V> next() {
        if (expectedVersion != version) {
            throw new ConcurrentModificationException();
        }
        // ... advance and return
    }
}

No shared mutable flag, no clock. Each iterator carries its own independent baseline (expectedVersion), so the multi-iterator case that broke the boolean flag now works automatically — iterator B's snapshot is whatever the counter was when B was created, completely independent of A's. And since it's a plain increment, not a physical measurement, there's zero resolution/collision risk: every mutation gets a value strictly different from every other, no matter how fast they happen. This is exactly the pattern java.util.HashMap, ArrayList, and friends use internally — go read AbstractList's modCount field and the ConcurrentModificationException javadoc directly; it's short.

The subtlety that actually caught me: no "free" first call

Here's the case that exposed a real bug in my own test suite, not just the implementation. Two iterators, A and B, created back to back — before either has called next() even once:

sequenceDiagram
    participant Map
    participant IteratorA
    participant IteratorB

    Note over Map: version = 3 (after 3 puts)
    IteratorA->>Map: create (snapshot version=3)
    IteratorB->>Map: create (snapshot version=3)

    IteratorA->>Map: next()
    IteratorA->>Map: remove() → version = 4

    IteratorB->>Map: next()
    Map-->>IteratorB: ConcurrentModificationException
    Note over IteratorB: B never called next() before A's<br/>change — still invalidated on its<br/>very first call

I originally wrote a test that let iterator B succeed on its first next() call before asserting a second call would throw. That's wrong: B's snapshot predates A's remove(), so B is already stale the instant A mutates — there's no "one free call" grace period. The check only cares whether a modification happened since the snapshot was taken, not whether the iterator has navigated yet. Fixing that test (not the implementation) was the actual bug.

The self-invalidation trap

One more sharp edge: an iterator's own remove() legitimately bumps the shared counter — so if the iterator doesn't resync its own expectedVersion immediately afterward, it trips its own check on the very next call:

@Override
public void remove() {
    if (!nextCalled) {
        throw new IllegalStateException();
    }
    MyEntry entryToDelete = currentEntry;
    this.next();
    MyHashMap.this.remove(entryToDelete.getKey());
    this.expectedVersion = version;   // resync — or self-CME on the next call
    this.nextCalled = false;
}

One more nuance most write-ups skip: not every write is "structural"

The counter shouldn't bump on every put() — only on ones that actually change the map's shape. Overwriting the value of an already-present key isn't structural (same key, same position, same size) and doesn't need to invalidate a live iterator; inserting a genuinely new key is, and does:

if (entry == null) {
    entries[bucket] = new MyEntry(key, value);
    ++count;
    ++version;              // new key: structural
} else {
    // walk the chain...
    if (matchFound) {
        entry.setValue(value); // existing key, value-only: NOT structural, no bump
    }
}

This matches java.util.HashMap's real behavior, and it's the kind of detail that only shows up once you've actually built the thing rather than read about it.

Takeaway

Fail-fast iteration looks like a one-line trick (modCount) until you actually have to defend it against a second iterator, a same-millisecond race, or your own iterator's legal mutation. Building it from scratch — and writing tests that actually exercise the multi-iterator case — surfaced three separate designs before landing on the one that's actually in the JDK, plus a bug in the test for the final design, not the code.

DEV Community: Gaurav Tyagi

I Benchmarked CAS vs. a Lock — and Caught Myself Drawing the Wrong Conclusion Halfway Through

The setup: two counters, same shape

A JMH trap that was hiding in the annotations

First look — and the conclusion I almost drew

The real head-to-head

Why the crossover happens: spin vs. park

The generalization — and it isn't "use locks"

Takeaway

Further reading

The hashCode()-to-Array-Index Bug Almost Everyone Writes Once

Bug one: `%` isn't modulo

The naive fix has its own hole

The actual fix

Bug two (a design choice, really): bitmask vs. modulo

Bug three: fixing the sign doesn't fix distribution

Takeaway

Further reading

I Built My Own Fail-Fast HashMap — Here's Why a Boolean Flag Wasn't Enough

The problem, concretely

First idea: a boolean "dirty" flag

Second idea: a timestamp

What actually works: a monotonic counter (modCount)

The subtlety that actually caught me: no "free" first call

The self-invalidation trap

One more nuance most write-ups skip: not every write is "structural"

Takeaway

Further reading

DEV Community: Gaurav Tyagi

I Benchmarked CAS vs. a Lock — and Caught Myself Drawing the Wrong Conclusion Halfway Through

The setup: two counters, same shape

A JMH trap that was hiding in the annotations

First look — and the conclusion I almost drew

The real head-to-head

Why the crossover happens: spin vs. park

The generalization — and it isn't "use locks"

Takeaway

Further reading

The hashCode()-to-Array-Index Bug Almost Everyone Writes Once

Bug one: % isn't modulo

The naive fix has its own hole

The actual fix

Bug two (a design choice, really): bitmask vs. modulo

Bug three: fixing the sign doesn't fix distribution

Takeaway

Further reading

I Built My Own Fail-Fast HashMap — Here's Why a Boolean Flag Wasn't Enough

The problem, concretely

First idea: a boolean "dirty" flag

Second idea: a timestamp

What actually works: a monotonic counter (modCount)

The subtlety that actually caught me: no "free" first call

The self-invalidation trap

One more nuance most write-ups skip: not every write is "structural"

Takeaway

Further reading

Bug one: `%` isn't modulo