This page needs a newer browser to run its tools. You can still read everything here.

Assembly (x86-64, AArch64, RISC-V) Module 13

Atomics and memory ordering interview questions

Interview questions on atomics and memory ordering: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

11 questions: 3 warm-ups and 8 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

Two threads each run counter++ on a shared variable 1,000,000 times. Why can the total be less than 2,000,000, and what does an atomic instruction change?

Answered in the lesson Atomic instructions: lock, LL/SC and AMOs
Mid to senior

What does x86-64's total store order allow that sequential consistency does not?

Answered in the lesson Memory ordering: TSO, weak models and fences
Fresher to mid

Why does summing a large C matrix row by row run faster than column by column?

Answered in the lesson Caches, cache lines and false sharing

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

Senior to staff

A lock-free stack pops by reading its top node, reading that node's next pointer, and swinging top to it with a compare-and-swap. Under load it sometimes hands out a node that is still in use. Why can the compare-and-swap succeed although the stack changed in between, and how do x86-64, AArch64 and RISC-V let you prevent it?
What it tests

The ABA problem: a compare-and-swap checks a value, not a history. Whether the candidate can repair it with a version counter and a double-width compare-and-swap, and knows what LL/SC and memory reclamation change.

First step

Write the interleaving out: thread 1 reads top = A and next = B, thread 2 pops A and B and pushes A back, and thread 1's compare-and-swap finds A on top and installs B, a node another thread now owns. Then ask what the compare-and-swap would have to compare to notice that the stack changed.
Follow-ups
- How does a version counter next to the pointer fix it, and which instructions compare 16 bytes at once?
- Does an LL/SC loop on AArch64 or RISC-V have the same problem?
- Why does freeing popped nodes make the problem worse, and what do hazard pointers or epochs change?
From the lesson Atomic instructions: lock, LL/SC and AMOs
Model answer, Pro. Model answers open with any pass; prices are in the notice on this page.
Opening the model answers with your pass…
Model answers open with any MySmartCoPilot pass.
Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so the model answers can’t be opened at the moment. If you have a pass, enter your licence key.
Choose a pass I have a licence key
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Mid to senior

Under contention, a test-and-set spinlock lets the same two cores win again and again while a third waits for a long time. Design a lock that serves waiting threads in the order they arrived, and write its lock and unlock paths in AArch64 or x86-64 instructions.
What it tests

Whether the candidate knows the ticket lock: one fetch-and-add hands out tickets, waiters spin on a now-serving counter, and the release is a plain increment of that counter with release ordering.

First step

Give the lock two counters, next and serving. To lock, take a ticket with one atomic fetch-and-add on next, then wait until serving equals the ticket. To unlock, add 1 to serving with a releasing store. Then write the fetch-and-add and the wait loop for one ISA.
Follow-ups
- Why does the unlock path need no atomic read-modify-write?
- What happens to the threads behind it when a waiting thread is preempted just as its turn comes?
- What does every waiter spinning on one serving word cost, and how does a queue lock avoid it?
From the lesson Atomic instructions: lock, LL/SC and AMOs
Model answer, Pro.
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A producer thread fills in a new object and then stores its address in a shared pointer; a consumer loads the pointer and reads the object's fields. On AArch64 the consumer sometimes sees fields that were never written. Explain why, and give the cheapest correct fix for AArch64, x86-64 and RISC-V.
What it tests

Message passing through a pointer: which side needs which order, release on the publishing store, what the consumer's address dependency already provides, and what each ISA's compiler emits for the fix.

First step

Write it as message passing: the field stores are the data and the pointer store is the flag. Ask which of the four orders the code relies on, which ones AArch64 may break, and which instruction on each side restores them.
Follow-ups
- Why does the consumer, which reads the fields through the pointer it loaded, need no barrier on AArch64 hardware?
- What do compilers do with memory_order_consume, and why?
- What does the fix cost on x86-64?
From the lesson Memory ordering: TSO, weak models and fences
Model answer, Pro.
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

A profile of a hot loop on x86-64 points at one line, a store of a flag with atomic_store, whose default order is seq_cst. The same line costs little on AArch64. Explain the difference in the machine code, and say when the order may be weakened and how you would check that change.
What it tests

Whether the candidate can read in compiler output where each ISA pays for sequential consistency, and can decide from the flag's protocol whether a release store is enough.

First step

Read the compiler output for both targets: a locked xchg on x86-64 against an stlr on AArch64. Then list every thread that reads or writes the flag, and write down which of its other accesses must stay before or after this store as other cores see them.
Follow-ups
- Why is the AArch64 seq_cst store only an stlr?
- Which pattern breaks if the store becomes a release store?
- How would you test the weakened order before shipping it?
From the lesson Memory ordering: TSO, weak models and fences
Model answer, Pro.
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

A lock-free queue passes thousands of test runs on x86-64 machines and under emulation of Arm, but loses entries on Arm servers. How do you find the missing ordering, and how should the testing change?
What it tests

Whether the candidate can explain why the x86-64 and emulated runs passed, find each publication point and the order it needs, and design a native stress test that can catch the bug.

First step

List every place one thread publishes something for another, such as a slot's contents before an index, and the order each needs. Compare the Arm compiler output at those points with that list, then reproduce the loss on Arm hardware.
Follow-ups
- Why could the emulated runs never show the bug?
- What makes a stress test likely to catch an ordering bug?
- Why is a passing stress test still no proof that the queue is correct?
From the lesson Memory ordering: TSO, weak models and fences
Model answer, Pro.
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A server keeps one request counter per worker thread in an array, long counts[16], indexed by thread number, so that no two threads ever write the same counter. Adding threads makes it slower, not faster. Explain why, show how you would confirm it, and fix it.
What it tests

False sharing: separate variables in one cache line, the coherence traffic it causes, an experiment that confirms it, and a layout fix that holds on every target.

First step

Work out the layout first: how many bytes the 16 counters take, and how many cache lines that is on a machine with 64-byte lines and on one that reports 128. Then ask what each increment does to a line that other cores also write.
Follow-ups
- Why do the counts stay correct although the threads slow each other down?
- Which padding works on both 64-byte and 128-byte lines?
- What would you do instead of padding if there were thousands of counters?
From the lesson Caches, cache lines and false sharing
Model answer, Pro.
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A linked list and an array hold the same two million records, and a loop sums one field of each. Both loops are O(n), yet the list's loop is many times slower. Explain the gap in terms of cache lines and loads, and say when a list can be made fast.
What it tests

Pointer chasing against walks in memory order: lines per element, what dependent loads do to the overlap of misses, the hardware prefetcher, and layouts that restore locality.

First step

Count the cache lines each loop touches, then ask when each loop learns the address of its next load, and what the core can do while it waits.
Follow-ups
- Why does a list allocated in visiting order walk so much faster than a scattered one?
- What does a hardware prefetcher need to see to help?
- Which layout changes keep a linked structure but cut its misses?
From the lesson Caches, cache lines and false sharing
Model answer, Pro.
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

A library pads per-thread data to avoid false sharing and must run on x86-64 Linux servers and on Apple silicon Macs. How do you choose the padding at compile time, how would you query the line size at run time on each system, and what does each answer cost?
What it tests

Where each system reports its line size (sysctl, sysfs, CPUID, CTR_EL0 and its limits), the difference between a compile-time constant and a run-time query, and how to pick a constant that is safe on every target.

First step

List the targets and the line size each one documents or reports: Intel's manual for the x86-64 servers, hw.cachelinesize for the Macs. Then separate what must be fixed when the code compiles from what a program can ask when it starts.
Follow-ups
- Why is CTR_EL0 not a portable way to ask on macOS?
- What does the padding you chose cost on a machine with 64-byte lines?
- Why is DminLine not the right number for padding?
From the lesson Caches, cache lines and false sharing
Model answer, Pro.
In the answer:
- Model answer
- Common mistakes
- Rubric
- Variants
- about 3 minutes

All Assembly (x86-64, AArch64, RISC-V) interview questions · The Assembly (x86-64, AArch64, RISC-V) track

Warm-up questions

Two threads each run counter++ on a shared variable 1,000,000 times. Why can the total be less than 2,000,000, and what does an atomic instruction change?

What does x86-64's total store order allow that sequential consistency does not?

Why does summing a large C matrix row by row run faster than column by column?

Questions with model answers

Under contention, a test-and-set spinlock lets the same two cores win again and again while a third waits for a long time. Design a lock that serves waiting threads in the order they arrived, and write its lock and unlock paths in AArch64 or x86-64 instructions.

A producer thread fills in a new object and then stores its address in a shared pointer; a consumer loads the pointer and reads the object's fields. On AArch64 the consumer sometimes sees fields that were never written. Explain why, and give the cheapest correct fix for AArch64, x86-64 and RISC-V.

A profile of a hot loop on x86-64 points at one line, a store of a flag with atomic_store, whose default order is seq_cst. The same line costs little on AArch64. Explain the difference in the machine code, and say when the order may be weakened and how you would check that change.

A lock-free queue passes thousands of test runs on x86-64 machines and under emulation of Arm, but loses entries on Arm servers. How do you find the missing ordering, and how should the testing change?

A server keeps one request counter per worker thread in an array, long counts[16], indexed by thread number, so that no two threads ever write the same counter. Adding threads makes it slower, not faster. Explain why, show how you would confirm it, and fix it.

A linked list and an array hold the same two million records, and a loop sums one field of each. Both loops are O(n), yet the list's loop is many times slower. Explain the gap in terms of cache lines and loads, and say when a list can be made fast.

A library pads per-thread data to avoid false sharing and must run on x86-64 Linux servers and on Apple silicon Macs. How do you choose the padding at compile time, how would you query the line size at run time on each system, and what does each answer cost?