Skip to content

CHANGELOG.md

Latest commit

 

History

History
192 lines (123 loc) · 12.4 KB

CHANGELOG.md

File metadata and controls

192 lines (123 loc) · 12.4 KB

Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

[Unreleased]

[4.1.0] - 2026-05-01

Added

  • Auto-create constructors for unbounded MP/SP variants. newUnboundedMupmuc[S, T, MaxThreads](strategy), newUnboundedSipmuc[S, T, MaxThreads](strategy), and newUnboundedMupsic[S, T, MaxThreads](strategy) (the last auto-registers the caller as the consumer). Each heap-allocates a private DebraManager owned by the queue; teardown happens inside the queue's =destroy after segment cleanup. The existing explicit-manager API (addr manager) is preserved for multi-queue setups that share a manager.
  • Auto-register getProducer() / getConsumer() overloads. No-arg variants that call registerThread internally. Each call consumes one thread slot; threads using multiple queues with a shared manager should prefer the explicit-handle overloads.
  • Bidirectional client refcount on DebraManager (via nim-debra >= 0.5.0). Queue constructors call bindClient; =destroy calls unbindClient. The manager's destructor asserts clientCount == 0, catching the case where a shared manager is destroyed before its queues.

Changed

  • Bump minimum debra to 0.5.0.
  • Bump minimum typestates to 0.6.0.
  • src/lockfreequeues/atomic_dsl.nim no longer defines a local compareExchange shim — it's now provided by debra/atomics.

Documentation

  • README.md "Thread safety" section rewritten with the correct explanation of why ref items are rejected (=copy/=sink hooks race on slot refcounts in the shared array[S, T]), replacing the prior incorrect spinlock claim.
  • "Choosing a queue" table split into separate Bounded and Unbounded tables for better rendering.
  • The same {.error.} strings inside unbounded_*.nim were updated to match.

Fixed

  • docs/api/epoch.md removed (referenced a module extracted into nim-debra); was breaking the mkdocs build step in the docs deploy workflow.
  • .github/workflows/docs.yml triggers extended to include devel branch and workflow_dispatch.

[4.0.0] - 2026-04-30

BREAKING

  • Bounded MPMC/SPMC/MPSC slot protocol switched to per-slot sequence counters (Vyukov bounded-MPMC). Fixes a confirmed race that allowed two consumers to claim the same physical slot across generations, producing silent duplicate-item delivery and producer-vs-producer storage races. The race was TSAN-confirmed at 100% reproduction and ran at roughly a 5% release-mode duplicate rate under contention.
  • Mupmuc, Mupsic, Sipmuc types: the committed*, reservedHead*, reservedTail*, and storage* fields have been removed. They are replaced with cells*: MPMCCellArrayN[N, T]. Consumers introspecting these fields directly must migrate to the new accessors.
  • head and tail cursors on the bounded queue types are now Atomic[uint64] instead of Atomic[int]. Code reading these via .load(...) will need an explicit cast or a local rename.
  • Bulk push(items) / pop(count) semantics have changed. The previous implementation performed an atomic block-claim across the requested range; the new implementation performs a best-effort fill via a loop of singleton operations. Partial completion is reported through the existing Option[Slice[int]] / Option[seq[T]] return types, so the API surface is unchanged but the intra-call atomicity guarantee is gone.
  • CommittedFlagsN type removed. Replaced with SlotSeqN, MPMCCellPayload, and MPMCCellArrayN. The tests/t_committed_flags_n.nim file has been deleted; equivalent and stronger coverage lives in tests/t_slot_seq_n.nim.

Added

  • New lockfreequeues/backoff module with backoffOnRetry (exponential) and backoffOnPeerWait (cpuPause-only) helpers. Used internally on CAS-retry paths to handle CPU oversubscription without burning unbounded CPU.
  • Bench harness now supports the Mupmuc 8P/8C topology. The previous topology table was implicitly capped at 4P/4C.
  • New LFQ_STRESS_DURATION_SEC environment variable on threaded stress tests, for sustained-load runs beyond the default iteration budget.
  • New tests/t_slot_seq_generation_rollover.nim: a deterministic single-threaded reproduction of the original protocol-bug scenario, asserting that the new sequence-counter protocol rejects the stale second-consumer claim.
  • Throughput bench harness for UnboundedMupsic (1P/1C, 2P/1C, 4P/1C) at benchmarks/nim/bench_throughput.nim plus a thin adapter at benchmarks/nim/adapters/lockfreequeues_unbounded_mupsic.nim that owns the queue and DebraManager. Producer threads register their own ThreadHandle in-thread (handles are per-thread by construction). The new variants run for 33 timed iterations + 3 warmup; existing Sipsic/Mupmuc/Channels run counts are unchanged.
  • bench_throughput accepts variant-group args (sipsic, mupmuc, unbounded_mupsic, channels) to limit which benchmarks run. With no args, all variants run (backward compatible). Multiple args take the union of groups. Unknown args print the supported list and exit non-zero. Lets gate runs target a single queue family without paying for the slow bounded MPMC variants.
  • Compile-time overrides for bench_throughput run shape via {.intdefine.} constants: -d:MessageCount=N, -d:DefaultRuns=N, -d:WarmupRuns=N, -d:UnboundedMupsicRuns=N, -d:UnboundedMupsicSegmentSize=N, -d:UnboundedMupsicMaxThreads=N. Defaults are unchanged (1M messages, 33 runs, 3 warmup). Lets gate runs trade statistical confidence for wall-clock budget without source edits. bench_throughput also unbuffers stdout in isMainModule so progress is visible under file redirect.

Fixed

  • Mupmuc 4P/4C livelock under CPU oversubscription. The combination of new backoff helpers and monotonic per-thread retry counters resolves the scheduler-pressure livelock; the bounded queue can now run 8 contending threads on 4 vCPUs without hangs.
  • Bench harness messageCount div P truncation bug. Consumers waited forever for items the integer-division truncation had silently discarded. Spread-the-remainder fix applied in three places.
  • Several pre-existing breakages in the unbounded threaded stress tests. The 3.2.0 DEBRA migration left them on a deleted EpochManager API; the tests have been updated to the current handle-based API. A small number remain disabled pending separate cleanup.

Changed

  • Bounded queue documentation updated to reflect the new sequence-counter publication protocol. Unbounded queue documentation now explicitly disambiguates the segment-local committed-flag protocol from the bounded sequence-counter protocol. See docs/safety-model.md and docs/slot-ownership-typestates.md.

[3.2.0] - 2026-04-27

Added

  • New queue types:
    • Sipmuc: bounded single-producer, multi-consumer queue.
    • UnboundedSipsic: segmented unbounded single-producer, single-consumer queue (no reclamation needed).
    • UnboundedSipmuc: segmented unbounded single-producer, multi-consumer queue with DEBRA reclamation.
    • UnboundedMupsic: segmented unbounded multi-producer, single-consumer queue with DEBRA reclamation.
    • UnboundedMupmuc: segmented unbounded multi-producer, multi-consumer queue with DEBRA reclamation.
    • Segment storage uses libc c_calloc / c_free (via system/ansi_c); a nil return from c_calloc raises OutOfMemDefect. Avoids the cross-thread free hazard from Nim's allocShared, which routes through per-thread heap metadata.
    • The consumer-visible head pointer is Atomic[ptr Segment] and is CAS-advanced past exhausted segments; the CAS winner retires the old segment via DEBRA.
  • Typestate-driven push and pop modules under src/lockfreequeues/typestates/ for both bounded and unbounded queues. The high-level queue APIs now build on these typestate transitions.
  • DeallocationStrategy (Manual / Eager) on the unbounded queues, configured at queue construction. Eager retires and immediately attempts reclamation per pop; Manual accumulates retired segments for an external tryReclaim call. Default is Eager, except Manual under --gc:none.
  • Compile-time -d:LockFreeQueuesAdvanceEvery=N (default 64) to tune the per-pop epoch-advance cadence in the unbounded queue retirement paths.
  • Compile-time lock-free check for queue item types: arc/orc compilation errors when a queue holds ref items (which fall back to spinlock refcounting on those memory managers). Opt out with -d:allowNonLockFreeQueueItems.
  • Threaded reclamation tests for all four unbounded queue variants (t_unbounded_*_threaded), exercised under arc, orc, and refc, plus the TSAN and ASAN sanitizer matrix.
  • Latency and throughput benchmark suite under benchmarks/nim/ (bench_latency.nim, bench_throughput.nim, bench_main.nim) with adapters for each queue type.
  • New examples: audio_buffer.nim, event_collector.nim, job_scheduler.nim, task_fanout.nim, and sipmuc.nim.
  • Thread safety section and slot-ownership typestate documentation in README.
  • CI matrix across arc, orc, and refc memory managers, including a -d:nimEnforceLockFreeAtomics lane.
  • Dependency on debra >= 0.3.0 for safe memory reclamation in the unbounded multi-consumer queues.
  • Dependency on typestates >= 0.3.1 (already used; bumped to pull in the latest API).

Changed

  • Eager-strategy unbounded queues now gate reclaimNow on advanceEvery returning true, eliminating per-pop epoch-safety atomic loads when the global epoch hasn't advanced. Reclamation latency is bounded by LockFreeQueuesAdvanceEvery (default 64), the same cadence the user already controls.
  • Bounded queues (Sipsic, Mupsic, Mupmuc) reimplemented on the typestate layer. SPSC uses N+1 storage slots to distinguish empty from full; MPSC, SPMC, and MPMC use N storage slots paired with per-slot committed flags so producers can publish before consumers observe the slot. Surface API (push/pop, head/tail, capacity semantics) is unchanged for SPSC; the multi-producer / multi-consumer variants gain a published-before-visible ordering guarantee they did not previously provide.
  • atomic_dsl.nim now re-exports debra/atomics instead of wrapping std/atomics. Call-site DSL (relaxed, acquire, release, sequential) is unchanged.
  • Stress test runner exercises all three memory managers.

Removed

  • std/atomics dependency. Atomic[T] and the memory-order primitives are now sourced from debra/atomics.
  • src/lockfreequeues/constants.nim. CacheLineBytes is now sourced from debra/atomics.
  • Removed the internal lockfreequeues/ops submodule. It was documented as internal, had no callers inside the library, and its index helper had silently shifted from value mod capacity (3.1.0) to value mod (capacity + 1) during the queue refactor. External code that imported lockfreequeues/ops directly should migrate to the public typestate API or inline the small helpers it contained.

[3.1.0] - 2024-09-28

Changed

  • Fixed wraparound issue in full()
  • Drop support for Nim v1 due to compilation issue with atomics.

[3.0.0] - 2021-12-14

Added

  • README link to Gitter chat room.

Changed

  • Regenerate documentation on PR merge.
  • Test against Nim 1.6.0.
  • Convert NoConsumersAvailableDefect and NoProducersAvailableDefect to CatchableErrors; there might be some value in catching them.

Removed

[2.1.0] - 2021-07-19

Added

Changed

  • Use correct memory orderings, as reported in #6
  • Move changelog from README.md to CHANGELOG.md

Removed

[2.0.6] - 2021-01-25

Added

Changed

  • Fix issue with htmldocs submodule during nimble install lockfreequeues.

Removed

[2.0.5] - 2021-01-06

Added

Changed

  • Moved from Travis CI to GitHub Actions.

Removed

[2.0.4] - 2020-08-10

Added

  • Multi-producer, single-consumer queue (Mupsic)
  • Multi-producer, multi-consumer queue (Mupmuc)
  • Nicer examples

Changed

  • Refactor
  • Fix wrap-around bug, improve test coverage

Removed

  • Shared memory queues

[1.0.0] - 2020-07-06

Added

Changed

  • Addresses feedback from #1
  • head and tail are now in the range 0 ..<2*capacity
  • capacity doesn’t have to be a power of two
  • Use align pragma instead of padding array

Removed

[0.1.0] - 2020-07-02

Added

  • Initial release, containing SipsicSharedQueue and SipsicStaticQueue

Changed

Removed