Algorithmic Complexity & Code-Level Optimization Questions

Direct answer. A single global mutex (a lock that only one thread can hold at a time, the mechanism protecting the shared data structure here) serializes every critical-section access regardless of which piece of data is actually being touched, so adding cores just adds more threads queueing for the same lock instead of doing more concurrent work. The fix is always some form of "stop pretending it's one resource": split it into independently-lockable pieces, avoid locking when contention is the exception rather than the rule, or remove locks entirely with a structure designed for concurrent access.

Structured elaboration: a prioritized list of refactors.

1. Sharding (striping). Split the single structure into $K$ independent shards, each with its own lock, and route each key to a shard (e.g. by hash). This is usually the first thing to try: it is a mechanical change, keeps the same programming model (still a mutex, just many of them), and scales contention down roughly by the shard count as long as keys are reasonably spread across shards. A concrete example: replacing one synchronized block wrapping a single hash map (a very common shape for exactly this bug, e.g. a Java service using synchronized(this) around a HashMap) with 16 independently-locked shards cuts the probability that two arbitrary threads collide on the same lock roughly to $1/16$ of what it was, assuming close to uniform key distribution; a language runtime's own concurrent map (e.g. ConcurrentHashMap) already implements this internally.
2. Optimistic concurrency (compare-and-swap, versioning). Instead of locking before every read/modify/write, read the current value and a version/generation counter, compute the new value, and commit only if the version has not changed since the read (retry if it has). This wins when contention is low to moderate (retries are rare and cheap) and reads dominate writes.
3. Lock-free structures. Data structures built directly on hardware atomic operations (compare-and-swap, atomic increment) with no blocking lock at all, so no thread ever waits behind another. These give the best scalability under high contention but are hard to design correctly: two specific traps are the ABA problem (a thread reads a value A, gets paused, and when it resumes the value is still A, so it assumes nothing changed; but in between, another thread actually changed A to B and back to A, and any state that depended on "nothing changed" is now wrong) and memory reclamation while other threads may still be reading (a node gets freed by one thread while another thread is mid-read on it, corrupting memory). These are usually reached for only after sharding and optimistic approaches have been tried.

Worked example. With 8 cores contending on one mutex, throughput flattens near the single-thread rate because 7 of 8 threads are typically waiting rather than working. Moving to 16 shards, assuming reasonably uniform key distribution, each shard sees roughly $1/16$ of the traffic, so the effective contention per lock drops sharply and throughput can scale much closer to linearly with added cores, up to the point where shard-level contention itself becomes the new bottleneck.

Trade-offs & pitfalls. Sharding adds memory overhead roughly proportional to shard count (each shard needs its own lock and, if resizable, its own capacity bookkeeping) and complicates any operation that must span multiple shards (e.g. "iterate all entries" now needs to lock, or snapshot, several shards). Optimistic concurrency adds CPU overhead from retries under contention and requires the underlying operation to be safely retryable (side effects during a doomed attempt must not leak out). Lock-free structures carry the highest implementation and review cost, and the memory-overhead cost of safe reclamation schemes (e.g. hazard pointers: each thread publishes, in a small shared array, which node it's currently accessing, so any other thread that wants to free a node first checks that no one has "raised a hazard" on it and delays the free until it's safe), so they are the right choice only when the first two options have been tried and contention is still the dominant bottleneck.

Approach

Wrap the cached function's results in an OrderedDict, which supports moving an existing key to the end and popping the oldest key in O(1), exactly what least-recently-used (LRU) eviction needs. Guard both the read path (checking for a cache hit) and the write path (inserting a new result and possibly evicting) with a single threading.Lock, so a hit, a miss, and an eviction can never interleave and corrupt the cache's bookkeeping.

import threading
from collections import OrderedDict
from functools import wraps
from typing import Any, Callable, Dict, TypeVar

F = TypeVar("F", bound=Callable[..., Any])


def lru_memoize(max_size: int = 128) -> Callable[[F], F]:
    def decorator(func: F) -> F:
        cache: "OrderedDict[Any, Any]" = OrderedDict()
        lock = threading.Lock()
        stats = {"hits": 0, "misses": 0}

        @wraps(func)
        def wrapper(*args: Any, **kwargs: Any) -> Any:
            key = (args, tuple(sorted(kwargs.items())))
            with lock:
                if key in cache:
                    cache.move_to_end(key)
                    stats["hits"] += 1
                    return cache[key]
                stats["misses"] += 1

            result = func(*args, **kwargs)  # computed OUTSIDE the lock

            with lock:
                cache[key] = result
                cache.move_to_end(key)
                if len(cache) > max_size:
                    cache.popitem(last=False)  # evict least-recently-used
            return result

        def cache_info() -> Dict[str, int]:
            with lock:              # introspection reads the same shared state
                return dict(stats, size=len(cache))

        wrapper.cache_info = cache_info  # type: ignore[attr-defined]
        return wrapper  # type: ignore[return-value]

    return decorator


@lru_memoize(max_size=3)
def slow_square(n: int) -> int:
    return n * n


print(slow_square(2), slow_square(3), slow_square(4))
print("info after 3 unique calls:", slow_square.cache_info())
print(slow_square(2))       # hit, refreshes recency of key 2
print(slow_square(5))       # miss, cache full -> evicts LRU key (3)
print("cache size stays bounded:", slow_square.cache_info()["size"])

Output:

4 9 16
info after 3 unique calls: {'hits': 0, 'misses': 3, 'size': 3}
4
25
cache size stays bounded: 3

A concurrency check (8 threads each calling the function 200 times against a shared 5-key rotation) confirmed zero errors and the cache size staying exactly bounded at max_size afterward, since the lock serializes every read and write of the shared OrderedDict.

Key points

The function call itself happens OUTSIDE the lock, deliberately: holding the lock for the whole computation would let one slow call block lookups for every OTHER key, serializing unrelated work for no reason. The trade-off this makes: two threads racing to compute the exact SAME missing key at the same moment may both compute it once each (a redundant computation, not a correctness bug), which is only safe because the decorator assumes the wrapped function is pure or at least idempotent.

cache_info takes the lock too, and this is the easiest part of the design to get wrong. It is tempting to write it as a one-line lambda: dict(stats, size=len(cache)) on the grounds that it only reads, but stats and len(cache) are two separate reads of state that another thread is actively mutating between them, so an unguarded version can return a hit/miss pair and a size that never coexisted: hits plus misses from before an insert, size from after it. That is not a crash, it is a silently wrong number in exactly the counter an operator would use to decide whether the cache is sized correctly. Taking the lock makes the snapshot internally consistent, and it cannot deadlock because wrapper never calls cache_info while holding the lock itself.

Complexity

Hit and miss-plus-insert are both O(1) expected time (hashing the key plus OrderedDict operations). Eviction is O(1) via popitem(last=False). Space is O(k) for a cache holding k entries, bounded by max_size. cache_info is O(1) as well, since len() on a dict is a stored count, not a walk.

Edge cases

Unhashable arguments (a list or dict passed positionally) raise a TypeError when the key tuple is built, a real and expected limitation worth calling out rather than hiding. Keyword arguments are order-independent because they're sorted before becoming part of the key, so f(a=1, b=2) and f(b=2, a=1) correctly hit the same cache entry. Note also that sorting keyword items requires the keyword NAMES to be comparable, which they always are since they are strings, so the sort itself is safe even when the VALUES are of mixed types.

Approach

Buffer writes in an array and flush when either the buffer reaches N items or T milliseconds have elapsed since the FIRST item in the current buffer was added. Arm a timer only when a fresh batch starts (buffer goes from empty to one item), and clear that timer whenever a size-triggered flush fires first, so the two triggers never both fire for the same batch.

type WriteItem = { id: number; payload: string };
type FlushFn = (batch: WriteItem[]) => Promise<void>;

class WriteBatcher {
  private buffer: WriteItem[] = [];
  private timer: NodeJS.Timeout | null = null;
  private readonly maxSize: number;
  private readonly maxWaitMs: number;
  private readonly flush: FlushFn;

  constructor(maxSize: number, maxWaitMs: number, flush: FlushFn) {
    this.maxSize = maxSize;
    this.maxWaitMs = maxWaitMs;
    this.flush = flush;
  }

  add(item: WriteItem): void {
    this.buffer.push(item);
    if (this.buffer.length === 1) {
      this.timer = setTimeout(() => this.doFlush("timeout"), this.maxWaitMs);
    }
    if (this.buffer.length >= this.maxSize) {
      this.doFlush("size");
    }
  }

  private doFlush(reason: "size" | "timeout"): void {
    if (this.timer) {
      clearTimeout(this.timer);
      this.timer = null;
    }
    if (this.buffer.length === 0) return;
    const batch = this.buffer;
    this.buffer = [];
    console.log(`flush(${reason}): ${batch.length} item(s) -> ids [${batch.map(b => b.id).join(",")}]`);
    this.flush(batch).catch(err => {
      console.error(`batch of ${batch.length} failed: ${(err as Error).message}`);
    });
  }
}

async function fakeDbWrite(batch: WriteItem[]): Promise<void> {
  for (const item of batch) {
    if (item.payload === "bad") {
      throw new Error(`row ${item.id} violated a constraint`);
    }
  }
}

const batcher = new WriteBatcher(3, 50, fakeDbWrite);
for (let i = 0; i < 5; i++) {
  batcher.add({ id: i, payload: i === 4 ? "bad" : "ok" });
}

Output:

flush(size): 3 item(s) -> ids [0,1,2]
flush(timeout): 2 item(s) -> ids [3,4]
batch of 2 failed: row 4 violated a constraint

Amortized complexity per write

Each add call is O(1): an array push, and at most one setTimeout/clearTimeout. A flush of k items costs O(k) to build and send the batch. Since that O(k) cost is paid once and covers k individual writes, the amortized cost per write is O(1), the same style of argument used for a dynamic array's doubling resize: an occasional larger operation spread evenly over the operations that led up to it.

Throughput, latency, and memory

Batching raises throughput because fixed per-request overhead (network round trip, query parsing, transaction commit) is now paid once per N rows instead of once per row. It changes average latency for the worse in one specific way: an item that arrives when the buffer is empty can wait up to T milliseconds even with nothing else going on, so N and T are a direct throughput-versus-latency dial, larger values favor throughput, smaller values favor low per-write latency. Memory stays bounded: the buffer never holds more than N pending items, so the batcher's footprint doesn't grow with total write volume, only with N.

Error handling under partial failures

The shown code treats a batch failure as all-or-nothing at the log level, which is a real gap: a production version needs the underlying write call to report which SPECIFIC rows failed within the batch (not just "the batch failed"), so only the actually-bad rows get retried or surfaced to the caller, the rows that succeeded must not be silently retried too, since re-applying an already-successful write is either wasted work or, worse, a duplicate, unless every write is idempotent (for example, keyed by a client-generated id so a retried insert becomes a no-op upsert instead of a second row).

Edge cases

A flush that never resolves (a hung connection) currently leaves no way to apply backpressure (deliberately slowing, queuing, or rejecting new work when a downstream consumer cannot keep up, instead of letting it pile up unbounded) to add, letting new batches pile up during the outage; a production version would want add to signal or reject once too many in-flight flushes are outstanding. A process crash between accepting an item and its flush completing loses that item, since the buffer only lives in memory, acceptable for some workloads and not others depending on the durability guarantee the caller expects.

Direct answer. Big-O complexity describes how operation count scales, but wall-clock time also depends on the cost per operation, which memory access patterns change dramatically: an algorithm that touches memory unpredictably (scattered, pointer-chasing access) pays a cache-miss penalty on nearly every access, while one with sequential, predictable access mostly hits cache. With a large enough gap in per-operation cost, an asymptotically "worse" $O(N\log N)$ algorithm can beat an asymptotically "better" $O(N)$ one in practice.

Structured elaboration: building the estimate. Model each algorithm's time as (number of memory accesses per element) times (base op cost plus miss-rate-weighted miss cost):

where $a, b$ are memory accesses per element for each algorithm and $m_a, m_b$ are their respective cache-miss rates.

First, the miss rates the question suggests. Plug in $N = 10^6$, $t_{op} = 5\text{ns}$, $t_{miss} = 100\text{ns}$, $a = 3$, $b = 1$, and the two rates named in the question, 10% for the scattered linear algorithm and 1% for the sequential log-factor one:

At those rates there is no crossover at all: the linear algorithm still wins by about 2.7x. That is the first thing worth saying out loud, because it sets the bar for what "realistic conditions" has to mean. A $\log_2 10^6 \approx 19.93$ factor is a 20x handicap, and a 10% miss rate only triples the linear algorithm's per-access cost (from 5ns to 15ns). Tripling does not cover 20x.

The break-even miss rate. Solve for the $m_a$ at which the two are equal, holding $m_b = 0.01$, $a = 3$, $b = 1$:

So the linear algorithm has to miss cache on roughly 35% or more of its accesses before the log-factor algorithm catches it, given three accesses per element against one. That single number is the actual answer to "under what conditions", and it is far outside the 1%-to-10% band the question offers, which is why the crossover needs a genuinely pathological access pattern rather than a merely mediocre one.

Worked example at a rate that does cross over. Suppose the $O(N)$ algorithm is implemented with pointer-chasing (e.g. a linked structure like a chained hash table with poor locality), needing $a = 3$ memory accesses per element at a high $m_a = 0.95$ miss rate (scattered heap allocations rarely share a cache line, so almost every access is a fresh line):

Meanwhile the $O(N\log N)$ algorithm is a comparison-based sort over a contiguous array (e.g. mergesort), doing $\log_2(10^6) \approx 19.93$ comparisons per element with $b = 1$ access per comparison and a low $m_b = 0.01$ miss rate (sequential scans prefetch well):

Under these assumptions the $O(N\log N)$ algorithm (about 120 ms) beats the $O(N)$ algorithm (about 300 ms) by roughly 2.5x, purely because its per-access cost is so much lower. Note that $m_a = 0.95$ is well past the 0.35 break-even derived above, which is the point: the crossover exists, but it lives in the pathological corner of the parameter space, not in the ordinary one.

Trade-offs & pitfalls: the realistic conditions for this crossover. This happens specifically when the $O(N)$ algorithm's constant factor combines a higher access count per element AND a much higher miss rate than the $O(N\log N)$ alternative, typically because the linear algorithm relies on scattered, pointer-heavy structures (hash tables with chaining, trees with heap-allocated nodes) while the log-factor algorithm operates on contiguous, cache-friendly memory. The crossover shrinks or disappears if the $O(N)$ algorithm is instead implemented cache-consciously (e.g. open-addressing with a compact array, low load factor, few probes), which is exactly why "asymptotically better" implementations still lose to careful engineering of the "asymptotically worse" one only under specific memory-layout conditions, not as a general rule.

Two limits of the model are worth stating when you present it. First, it charges the full $t_{miss}$ for every miss, which overstates the cost of the sequential algorithm: a prefetcher and multiple outstanding misses overlap latency, so a stream of predictable misses costs far less than their sum. That bias makes the model conservative in favour of the linear algorithm, so a crossover the model predicts is more likely to be real than one it rules out. Second, the break-even $m_a \approx 0.35$ moves with $a$ and $b$: at $a = 1$ instead of 3, the required rate exceeds 100% and no crossover is possible at these constants at all, so the access count per element matters as much as the miss rate does.

Direct answer
Design a controlled comparison that pins a benchmark thread and its memory to specific NUMA (Non-Uniform Memory Access, where each CPU socket has its own local memory and accessing another socket's memory is slower) nodes with numactl, measure the local versus remote bandwidth and latency gap on the actual hardware rather than assume a textbook number, then apply thread/memory affinity or data sharding and re-run the exact same measurement as the acceptance test for the fix.

Structured elaboration

1. Map the topology first. numactl --hardware reports node count, which CPUs belong to which node, and the distance matrix (typically 10 for local, roughly 20-32 for one hop, higher for a longer hop) on this specific machine, since the actual penalty varies by platform and should not be assumed.
2. Size the benchmark before you run it, or the experiment cannot detect anything. Two sizing rules decide whether the next step measures NUMA at all:
   • The working set must be several times the last-level cache, and the LLC on a modern socket is tens of megabytes. A buffer that fits in LLC is served without ever reaching a memory controller, so local and remote look identical and you will conclude, wrongly, that NUMA does not matter here. Read the LLC size from lscpu and pick a buffer at least four times larger per thread.
   • The access pattern must defeat the prefetcher for the latency arm. A sequential scan of a large buffer measures bandwidth even if you time it per access, because the prefetcher hides the latency you were trying to observe.
3. Use two different microbenchmarks, because latency and bandwidth cannot come from the same run. This is the step most often collapsed into one, and collapsing it produces numbers that look fine and mean nothing:
   • Latency requires a dependent access chain: build a randomized pointer-chase through the buffer so each load's address depends on the previous load's result. That serializes the accesses, defeats memory-level parallelism, and yields a real per-access latency. Report nanoseconds per dependent access.
   • Bandwidth requires the opposite: many independent streams saturating the controller (a STREAM-style triad over several threads on the node). Report GB/s sustained.
     Running one benchmark and reading both columns off it gives you a latency that is really bandwidth divided by access count, which understates the remote penalty badly, because the remote link's extra latency is largely hidden when dozens of accesses are in flight.
4. Isolate the variable with three runs of each microbenchmark:
   • numactl --cpunodebind=0 --membind=0 ./bench (local: thread and memory both on node 0)
   • numactl --cpunodebind=0 --membind=1 ./bench (remote: thread on node 0, memory on node 1)
   • no numactl at all (default OS placement, usually first-touch, which can still land on the wrong node under memory pressure or after a thread migrates)
     Comparing the first two isolates the pure NUMA-distance effect; comparing both against the third shows how much the default policy is already costing you. Verify the placement actually happened rather than trusting the flag: numastat -p <pid> or /proc/<pid>/numa_maps should show the pages sitting on the node you asked for. Note also that --membind=1 will fail the allocation (and can get the process killed) if node 1 does not have the capacity, which is itself a result worth recording rather than a reason to loosen the binding.
5. Diagnose the real application, not just the microbenchmark: numastat -p <pid> or perf stat -e node-loads,node-load-misses on the running service shows what fraction of its actual memory accesses cross a node boundary, which tells you whether NUMA is even the bottleneck before you invest in a fix.
6. Code-level fixes, in order of how much they cost to build:
   • Thread affinity: pin worker threads to cores on one node (pthread_setaffinity_np / sched_setaffinity / taskset) so a thread that mostly touches one shard's data runs on the same node as that shard.
   • Memory affinity: allocate a shard's data with an explicit numa_alloc_onnode() or mbind() call instead of relying on first-touch, since first-touch breaks the moment a different thread happens to touch the page first, for example during single-threaded warm-up before workers spin up.
   • Sharding: partition the working set into as many shards as nodes and route each shard's traffic to threads pinned to that node, so most accesses stay local by construction instead of by lucky placement.
7. Validate by re-running the exact same benchmarks and the same perf/numastat counters after the fix, and require both the bandwidth and latency gap and the node-load-miss ratio to have moved in the expected direction, not just an end-to-end throughput number, which can improve for unrelated reasons.

Worked example
The results table your experiment should produce has this shape (illustrative structure, not measured values, since actual bandwidth and latency depend on the specific hardware under test). The latency column comes from the pointer-chase run and the bandwidth column from the streaming run; they are separate executions reported side by side, not two readings of one run.

The point of running it this way is that the gap between the local and remote rows on your hardware is the number you design against, not a number from a blog post about a different chip. Expect the two columns to disagree about how bad remote is, and that disagreement is information: a large latency gap with a small bandwidth gap means the workload will suffer only where it has dependent accesses (pointer chasing, hash lookups) and will be nearly unaffected where it streams.

Trade-offs & pitfalls
Sharding by NUMA node can create load imbalance if request traffic is not uniform across shards, so one node's data can get hotter than the others even though the sharding fixed the raw locality problem. Pinning threads too aggressively removes the OS scheduler's ability to load-balance if a node's cores become contended by an unrelated process on the same host. It is also worth testing an interleaved memory policy (numactl --interleave=all) as an alternative to picking one "best" node: for memory-bound workloads with unpredictable access patterns, spreading demand across all memory controllers can beat concentrating it on one node's controller, so the experiment design should include that arm too, not just local versus remote. Two more things that will quietly invalidate a run: transparent huge pages change both the TLB behaviour and the granularity at which pages get placed, so record whether they were on, and a single-threaded benchmark cannot saturate one node's memory controller on a modern socket, so a bandwidth arm that uses one thread measures a per-core limit rather than the node's.