unknown
The implementation is in ~/spsc_queue.py — a lock-free SPSC bounded queue based on Dmitry Vyukov's sequence-number protocol. No locks or semaphores are used; coordination relies entirely on atomic reads/writes of integer sequence numbers (safe under CPython's GIL).
Core algorithm (ring buffer with sequence slots):
Capacity = power of 2, mask = capacity - 1
Initial state: seq[i] = i for all slots i
Enqueue(item):
spin until seq[tail & mask] == tail # producer owns slot
buf[tail & mask] = item
seq[tail & mask] = tail + 1 # publish — linearization point
tail += 1
Dequeue():
spin until seq[head & mask] == head + 1 # consumer owns slot
item = buf[head & mask]
buf[head & mask] = None
seq[head & mask] = head + capacity # release slot back to producer
head += 1
Key design properties:
- Lock-free: Threads only spin-wait (no OS locks, no semaphores). At least one thread always makes progress.
- Batching: enqueue_batch() and dequeue_batch() handle multiple items, with opportunistic early-exit on dequeue when the next slot isn't ready.
- Backpressure: Producer spins when the queue is full (all sequence slots are owned by the consumer); consumer spins when empty. This naturally rate-limits the faster party.
- Memory safety: The producer and consumer never access the same slot simultaneously — the sequence-number condition seq[idx] == tail (producer) and seq[idx] == head + 1 (consumer) are mutually exclusive.
Linearizability proof (excerpt):
- Enqueue: linearization point is seq[idx] = tail + 1 — before this store the item is invisible; afterward the consumer may read it.
- Dequeue: linearization point is the successful load seq[idx] == head + 1 — this is the instant the consumer acquires ownership of the item.
- Batch: each slot is linearized independently; a consumer may observe a prefix of a batch, which is a valid linearizable outcome reflecting the queue state at that instant.
All tests pass (16/16). The test suite covers: | Test | What it verifies | |---|---| | `test_enqueue_dequeue` | Basic FIFO ordering | | `test_nonblocking_empty/full` | `try_enqueue`/`try_dequeue` on boundary conditions | | `test_capacity_rounding` | Power-of-2 rounding | | `test_wrap_around` | 100 full-drain cycles exercising wrap-around | | `test_enqueue_batch` / `test_dequeue_batch` | Batch operations in single-threaded mode | | `test_clear` / `test_len_bool` | Convenience methods | | `test_producer_consumer` | 1000 items, producer and consumer running concurrently | | `test_batch_concurrent` | Batch enqueue + dequeue under concurrency | | `test_stress_wrap` | 5000 items with capacity=16 (many wrap cycles) | | `test_backpressure_producer` | Producer blocks when full, consumer drains | | `test_producer_faster_than_consumer` | Producer ahead, backpressure engaged | | `test_consumer_faster_than_producer` | Consumer spins on empty queue | | `test_nonblocking_concurrent` | try_enqueue/try_dequeue do not corrupt state | **Edge cases tested:** - Empty queue dequeue (spins until data arrives) - Full queue enqueue (spins until slot freed) - Wrap-around at every index offset - Batch dequeue returning a partial prefix when queue drains - Both threads racing with non-blocking primitives - Consumer starting before producer (spins on empty) - Producer running far ahead (spins on full) ---
{"model": "deepseek-v4-flash", "result": "completed"}The implementation is in ~/spsc_queue.py — a lock-free SPSC bounded queue based on Dmitry Vyukov's sequence-number protocol. No locks or semaphores are used; coordination relies entirely on atomic reads/writes of integer sequence numbers (safe under CPython's GIL).
Core algorithm (ring buffer with sequence slots):
Capacity = power of 2, mask = capacity - 1
Initial state: seq[i] = i for all slots i
Enqueue(item):
spin until seq[tail & mask] == tail # producer owns slot
buf[tail & mask] = item
seq[tail & mask] = tail + 1 # publish — linearization point
tail += 1
Dequeue():
spin until seq[head & mask] == head + 1 # consumer owns slot
item = buf[head & mask]
buf[head & mask] = None
seq[head & mask] = head + capacity # release slot back to producer
head += 1
Key design properties:
- Lock-free: Threads only spin-wait (no OS locks, no semaphores). At least one thread always makes progress.
- Batching: enqueue_batch() and dequeue_batch() handle multiple items, with opportunistic early-exit on dequeue when the next slot isn't ready.
- Backpressure: Producer spins when the queue is full (all sequence slots are owned by the consumer); consumer spins when empty. This naturally rate-limits the faster party.
- Memory safety: The producer and consumer never access the same slot simultaneously — the sequence-number condition seq[idx] == tail (producer) and seq[idx] == head + 1 (consumer) are mutually exclusive.
Linearizability proof (excerpt):
- Enqueue: linearization point is seq[idx] = tail + 1 — before this store the item is invisible; afterward the consumer may read it.
- Dequeue: linearization point is the successful load seq[idx] == head + 1 — this is the instant the consumer acquires ownership of the item.
- Batch: each slot is linearized independently; a consumer may observe a prefix of a batch, which is a valid linearizable outcome reflecting the queue state at that instant.
All tests pass (16/16). The test suite covers: | Test | What it verifies | |---|---| | `test_enqueue_dequeue` | Basic FIFO ordering | | `test_nonblocking_empty/full` | `try_enqueue`/`try_dequeue` on boundary conditions | | `test_capacity_rounding` | Power-of-2 rounding | | `test_wrap_around` | 100 full-drain cycles exercising wrap-around | | `test_enqueue_batch` / `test_dequeue_batch` | Batch operations in single-threaded mode | | `test_clear` / `test_len_bool` | Convenience methods | | `test_producer_consumer` | 1000 items, producer and consumer running concurrently | | `test_batch_concurrent` | Batch enqueue + dequeue under concurrency | | `test_stress_wrap` | 5000 items with capacity=16 (many wrap cycles) | | `test_backpressure_producer` | Producer blocks when full, consumer drains | | `test_producer_faster_than_consumer` | Producer ahead, backpressure engaged | | `test_consumer_faster_than_producer` | Consumer spins on empty queue | | `test_nonblocking_concurrent` | try_enqueue/try_dequeue do not corrupt state | **Edge cases tested:** - Empty queue dequeue (spins until data arrives) - Full queue enqueue (spins until slot freed) - Wrap-around at every index offset - Batch dequeue returning a partial prefix when queue drains - Both threads racing with non-blocking primitives - Consumer starting before producer (spins on empty) - Producer running far ahead (spins on full) ---
{"model": "deepseek-v4-flash", "result": "completed"}