Skip to content

ROADMAP.md

Latest commit

 

History

History
241 lines (158 loc) · 53.2 KB

ROADMAP.md

File metadata and controls

241 lines (158 loc) · 53.2 KB
Raw

Celerity Roadmap

This document tracks the planned direction for the Celerity project. It is a living document maintained by the project maintainers and updated as priorities shift.

Status legend: planned, in-progress, done, deferred.

Guiding Principles

  1. Correctness first. A "fast" collection that returns wrong answers is worthless. Every optimization must be covered by tests.
  2. Zero-cost abstractions. Hashers are structs, generic constraints are struct, IHashProvider<T>, so the JIT can devirtualize and inline. This is a hard rule.
  3. Parity with BCL where it makes sense. TryGetValue, Clear, enumeration, IReadOnlyDictionary<TKey, TValue> — users should be able to drop Celerity in wherever they use Dictionary<,>.
  4. Benchmark every perf claim. The README's numbers are the contract. If a change regresses them, it ships only with a written justification.
  5. Document the tradeoffs. Celerity is not "always faster." Each collection should document the workloads where it wins and where it loses.

Vision

Celerity ships three NuGet packages as of v2.0.0 (the package split — see milestone 2.0.0 below; the roadmap previously described a single Celerity.Collections package, which predates that release). Long-term, the project will continue to expand into a family of focused packages — each targeting a specific area where specialized, high-performance implementations can outperform the BCL in niche scenarios. The package structure mirrors the .NET ecosystem's own organization:

  • Celerity.Collections — dictionaries, sets, and specialized collection types
  • Celerity.Hashing — hash providers, hash evaluation utilities (positioned on distribution quality, determinism, and zero-cost devirtualization — not on beating GetHashCode() for speed; see milestone 1.6.0)
  • Celerity.Primitives — low-level utilities that fill genuine BCL gaps: FastMod/FastDiv, struct PRNGs, span varint, integer digit-count, fast/compliant GUID, alignment/bit-packing (see milestone 2.1.0; we deliberately do not reimplement what BitOperations/TensorPrimitives already inline)

Each package will remain narrowly scoped: if a type doesn't offer a measurable performance advantage over its BCL counterpart in at least one documented workload, it doesn't ship.

The "Built with Celerity" showcase tier

Alongside the core packages, a separate showcase tier ships standalone libraries built on Celerity, each filling a niche where a pure-managed .NET implementation beats dropping to native code. These are downstream consumers, not core packages: they demonstrate the core in a real problem domain and are held to their own domain bar rather than to the core's "must beat the BCL counterpart" rule (in most cases the BCL has no counterpart at all).

  • Celerity.Ring — deterministic consistent-hash and rendezvous (HRW) rings for sharding and request routing, producing byte-identical node assignment across OS / architecture / runtime.
  • Celerity.Sentinel — streaming abuse / heavy-hitter detection (top offenders, per-key rate, fan-out cardinality) in a fixed footprint regardless of key cardinality.
  • Celerity.Cardinality — mergeable approximate COUNT(DISTINCT) and windowed dedup over unbounded managed streams, with deterministic cross-shard merge.

Cross-process sketch wire-serialization is deliberately deferred — it needs core Celerity to expose sketch bytes first, and the core is explicitly not a serialization library.

Completed milestones

1.0.0 / 1.0.1 — Stability & correctness

  • Fixed IntDictionary<TValue> constructor argument forwarding bug. Status: done.
  • Fixed IntDictionary key-0 corruption. Status: done.
  • Fixed CelerityDictionary default(TKey) corruption. Status: done.
  • Added constructor validation (capacity, loadFactor). Status: done.
  • Added TryGetValue, Clear, Add, TryAdd on both dictionaries. Status: done.
  • Stood up CI workflow (.github/workflows/ci.yml). Status: done.
  • Comprehensive test suites: collision tests, load-factor boundary tests, constructor validation. Status: done.
  • Added CONTRIBUTING.md, CHANGELOG.md, ROADMAP.md. Status: done.

Milestone 1.1.0 — API parity, hashers, and benchmarks

The next release rounds out the Celerity.Collections package with missing collection types, expands the hasher library, and stands up CI benchmark tracking.

Collections

  • Implement CeleritySet<T, THasher> — set counterpart to CelerityDictionary. Status: done.
  • Implement LongDictionary<TValue> — IntDictionary equivalent for long keys. Status: done.
  • Implement LongSet<T> — IntSet equivalent for long values; completes the dictionary-to-set parity (IntDictionary → IntSet, CelerityDictionary → CeleritySet, LongDictionary → LongSet). Status: done — shipped in v1.3.0.
  • Implement IReadOnlyDictionary<TKey, TValue> on CelerityDictionary and IntDictionary. Status: done.
  • Add Keys / Values enumerable views and GetEnumerator() on the dictionaries. Status: done.
  • Constructor accepting IEnumerable<KeyValuePair<TKey, TValue>>. Status: done.
  • Add GetEnumerator() and IEnumerable<T> conformance on the sets (IntSet, CeleritySet, LongSet). Status: done.
  • Full ISet<T> set-algebra conformance on the mutable set family (CeleritySet, SwissSet, IntSet, LongSet) — UnionWith / IntersectWith / ExceptWith / SymmetricExceptWith, the IsSubsetOf / IsSupersetOf / Overlaps / SetEquals query family, and CopyTo, all with BCL HashSet<T> semantics, so a Celerity set drops in wherever an ISet<T> / ICollection<T> is expected. Status: done — shared once via the internal SetOperations helper and reconciled against a HashSet<T> oracle by a randomized differential test; completes the HashSet<T> drop-in-parity gap (Guiding Principle #3) discovered while reading the source after the roadmap was otherwise exhausted. Tracked in #240.

Hashers

  • Add Int32Murmur3Hasher, Int64WangHasher, GuidHasher, UInt32Hasher, UInt64Hasher — all done.
  • Add DefaultHasher<T> fallback to EqualityComparer<T>.Default.GetHashCode(). Status: done.

Infrastructure

  • Set up github-action-benchmark for continuous performance tracking. Status: done — benchmarks job in ci.yml runs the full suite on every PR and pushes results to gh-pages on main, with PR comments and a 200% regression fail-threshold.
  • Create hash function evaluator for comparing distribution quality. Status: done — HashQualityEvaluator.Evaluate<T, THasher>(keys, bucketCount) returns a HashQualityReport (collision count / rate, bucket occupancy, max bucket load, chi-squared, and a normalized distribution score) so callers can compare candidate hashers for a given key shape offline. See docs/api/hashing.md. Tracked in #2.
  • Comprehensive benchmark suite: uniform, clustered, and adversarial key distributions. Status: done — DistributionBenchmark sweeps uniform/sequential/clustered shapes and AdversarialHasherBenchmark shows the naive hasher degrading to O(n) while Murmur3 recovers. Tracked in #60.
  • Benchmark suite expansion: realistic workloads, memory-allocation, concurrent-access, cache-locality, large-dataset (millions), and FrozenDictionary<,> comparison benchmarks. Status: done — added as an extended, on-demand suite kept out of the per-PR CI regression run; see docs/performance.md. Tracked in #26.
  • Cross-platform testing (Windows, Linux, macOS). Status: done.
  • Improve code coverage. Status: done — coverage reporting is gated in CI (coverage.yml, 100% line coverage on the library, rendered by an in-repo generator and published to the coverage dashboard), edge-case tests close the non-generic enumerator / throw / backward-shift corners, property-based parity tests (CsCheck) and a seedable differential fuzzer (Celerity.Fuzz, nightly soak) check every collection against its BCL oracle, and the approach is written up in docs/testing.md. Tracked in #29.
  • Improve documentation. Status: done — added a performance tuning guide, a BCL migration guide, a troubleshooting guide, and a FAQ, alongside the existing README usage examples, "choosing a collection" table, and API reference. Tracked in #15.
  • Bump XML doc coverage; treat missing docs as warning-as-error. Status: done — Celerity.csproj promotes CS1591 to error.

Milestone 1.2.0 — Performance & advanced collections

Focus on raw performance and specialized collection types that serve more advanced use cases.

Collections

  • FrozenCelerityDictionary — build-once, read-many variant with perfect hashing for string keys, comparable in spirit to System.Collections.Frozen but tunable via IHashProvider<T>. Status: done — FrozenCelerityDictionary<TValue> / <TValue, THasher> search for a collision-free single-probe layout at construction and fall back to linear probing when the chosen hasher collides two keys' raw codes, so lookups are always correct. Tracked in #62.
  • Frozen collections family — the set counterpart FrozenCeleritySet / FrozenCeleritySet<THasher> completes the build-once read-many family (FrozenCelerityDictionary → FrozenCeleritySet), sharing the same perfect-hash-with-linear-probing-fallback build and implementing IReadOnlySet<string>. Status: done. Tracked in #22.
  • CelerityMultiMap<TKey, TValue, THasher> — multi-value dictionary. Status: done — a one-to-many map that reuses CelerityDictionary's open-addressed key table and stores a List<TValue?> value group per key; Add appends rather than overwrites, Remove(key, value) / RemoveAll(key) are the two removal shapes, the indexer returns an empty group for an absent key, and the type implements ILookup<TKey, TValue?>. Tracked in #18.
  • CelerityMultiSet<T, THasher> — counting multiset (bag/counter), the element→count sibling that completes the CelerityMultiMap one-to-many family. Status: done — reuses CelerityDictionary's open-addressed table with a parallel int[] multiplicity per element; Add / Add(count) are single-probe increments (vs the two-probe Dictionary<T,int> GetValueOrDefault idiom — the documented BCL-beating frequency-counting workload), Remove / RemoveAll / SetCount manage multiplicities, Count is distinct elements and TotalCount the sum of occurrences, and it enumerates (element, count) pairs. Filed and shipped after the roadmap was otherwise exhausted (a tier-(c) enhancement). Tracked in #235.
  • SmallDictionary<TKey, TValue> — flat-array implementation optimized for n <= ~16. Status: done — SmallDictionary<TKey, TValue> linear-scans insertion-dense parallel arrays with EqualityComparer<TKey>.Default (no hasher, so the default key is stored inline rather than out-of-band), trading O(1) for O(n) to win at small n; it implements IReadOnlyDictionary<TKey, TValue?> with the full dictionary surface. Tracked in #61.

Performance

  • Robin Hood hashing experiment as alternative to linear probing. Status: done — shipped as a new collection type, RobinHoodDictionary<TKey, TValue, THasher>, a drop-in peer of CelerityDictionary that uses Robin Hood open addressing (per-slot probe sequence length, displace-the-richer-resident inserts, backward-shift-with-PSL-decrement deletes) to bound probe-length variance and keep worst-case lookups close to the average on clustered / adversarial keys; negative lookups terminate early via the PSL invariant. The default is unchanged — this is an additional opt-in type for the clustered case, not a replacement (the per-slot PSL int and extra insert work make it a wash or a slight loss on uniform keys). Tracked in #63.
  • Performance optimizations across existing collections.
  • Native AOT support and trimming compatibility. Status: done — the library is marked <IsAotCompatible>true</IsAotCompatible> (trim + AOT analyzers run on every build), and a Native AOT publish smoke test runs the full collection / hasher surface as a native binary in CI. See docs/aot.md. An AOT-vs-JIT benchmark comparison remains a follow-up. Tracked in #32.

Milestone 1.6.0 — Hasher performance audit & honest positioning

A correctness-of-claims pass on the hashing layer, prompted by the observation that the hashers are not necessarily faster than GetHashCode() — and, for int keys, cannot be (int.GetHashCode() is identity, i.e. zero work). The real value of the struct hashers is distribution quality (avalanche), determinism, adversarial resistance, and the zero-cost devirtualized generic — not raw hashing speed. This milestone makes the benchmarks and the docs tell that honest story. It ships in the current single package, before the 2.0.0 restructure.

  • Benchmark hashers end-to-end through the dictionaries (insert/lookup across uniform / sequential / clustered / adversarial key distributions), reporting collision rate and avg/max probe length — not just an isolated Hash() loop. The clustered/adversarial cases are where a strong hasher wins end-to-end even though it "loses" the isolated microbench. Status: done — HasherEndToEndBenchmark (extended suite) times every integer hasher through IntDictionary for insert + lookup across all four key shapes vs the BCL Dictionary, and the new public ProbeStatisticsEvaluator / ProbeStatistics (docs/api/hashing.md) replays the real open-addressed linear-probing placement to report average / worst-case probe length and the open-addressing collision rate (surfaced as a deterministic --probe-analysis markdown report and a measured table in docs/performance.md). The numbers show the cheap hashers winning on uniform/sequential keys and the naive fold collapsing on clustered/adversarial keys while the Wang/Murmur3 finalizers hold near a 1.75 average probe. Tracked in #182.
  • Make the isolated microbenchmarks honest: consume results (the identity int hash is otherwise dead-code-eliminated), add an EqualityComparer<T>.Default baseline (the realistic thing a dev replaces), and label identity/GetHashCode() as the zero-work floor no mixing hasher can beat. Status: done — every hasher microbenchmark already XOR-folds its codes into a returned value (BDN consumes it, so no DCE), and both IntegerHasherBenchmark ({Type}_EqualityComparer per int/long/uint/ulong/Guid) and StringHasherBenchmark (EqualityComparer_Default) now carry an EqualityComparer<T>.Default.GetHashCode() baseline arm alongside the direct GetHashCode() one — the per-probe call a BCL Dictionary<,> actually makes. The class remarks label the microbenchmarks a raw-mixing-cost diagnostic and the int/long identity/_Bcl rows the zero-work floor; the new arms auto-render on the gh-pages Hash function throughput dashboard. Tracked in #183.
  • Reposition the hasher docs/README away from "faster hashing" toward distribution/avalanche/determinism, with an honest "choosing a hasher" guide (the speed-vs-quality curve, the F14/ahash/FxHash framing, the Marvin32 string-determinism tradeoff, and the caveat that fixed-seed hashers are not a HashDoS defence). Status: done — README.md reframes the "up to 2.4× faster" headline as a collection-layout win independent of the hasher, and both README.md and docs/api/hashing.md lead with distribution/determinism and carry an explicit HashDoS caveat (fixed-seed hashers are not a flooding defence; what stops flooding is a keyed PRF with a secret, per-process-random key, so BCL Marvin32 is the safe default for untrusted string keys). hashing.md's "Choosing a hasher" section gains a speed-vs-quality-curve framing block, and the benchmark docs across hashing.md / docs/performance.md reframe the isolated Hash() sweeps as a raw-mixing-cost diagnostic. Tracked in #184.
  • Add explicit identity/passthrough integer hashers (Int32IdentityHasher / Int64IdentityHasher) as the zero-work floor, and document the rule: uniform/trusted keys → skip mixing; clustered/adversarial keys → mix. Status: done — Int32IdentityHasher (Hash(key) => key) and Int64IdentityHasher (Hash(key) => (int)key) ship as the labelled floor of the integer hasher ladder (no mixing hasher beats identity on speed; the value of the struct hashers is distribution/determinism, not hashing speed), are exercised as *_Identity rows in IntegerHasherBenchmark, and carry the skip-vs-mix decision rule plus the open-addressed-table-sensitivity and not-a-HashDoS-defence caveats in docs/api/hashing.md and the README. Library defaults are unchanged (identity is opt-in). Tracked in #185.

Milestone 2.0.0 — Multi-package restructure

Split the monolithic Celerity.Collections into focused packages mirroring the .NET package structure. This is a breaking change in packaging (not necessarily in API). The new collections and infrastructure work below has shipped, the package restructure itself — the defining work of this milestone — has landed (the library builds and packs as three packages, each multi-targeting net8.0;net9.0;net10.0, #189), and the release pipeline is now complete (symbol packages, SourceLink, deterministic builds, and a publish-time package-validation gate, #190). v2.0.0 shipped on 2026-06-21, closing the human-gated release review (#213); the milestone is complete and closed.

Package split

Shipped: three projects under src/ form an acyclic layer — Celerity.Primitives (FastUtils, struct PRNGs, VarInt, FastGuid) ← Celerity.Hashing (IHashProvider<T>, the hashers, the evaluators) ← Celerity.Collections (the Celerity assembly: dictionaries, sets, frozen/sketch types). Namespaces are unchanged except FastUtils, which moved from Celerity to Celerity.Primitives (#187). dotnet pack produces three .nupkgs with the correct transitive dependency graph and shared MinVer versioning.

  • Celerity.Collections — dictionaries, sets, and specialized collections.
  • Celerity.Hashing — IHashProvider<T>, built-in hashers, HashQualityEvaluator. Status: done — extracted into src/Celerity.Hashing (depends on Celerity.Primitives for FastUtils.NextPowerOfTwo), packs independently, AOT analyzers + CS1591-as-error preserved. Tracked in #186.
  • Celerity.Primitives — low-level utilities, seeded with FastUtils; content expansion is milestone 2.1.0. Status: done — extracted into src/Celerity.Primitives with no package dependencies; FastUtils moved to the Celerity.Primitives namespace. Tracked in #187.
  • Preserve back-compat for existing Celerity.Collections consumers (meta-package and/or [TypeForwardedTo]). Status: done — Celerity.Collections carries non-private NuGet dependencies on the two lower packages (source/meta-package back-compat) and a full [TypeForwardedTo] set in TypeForwarders.cs for every moved type (binary back-compat); migration written up in docs/migration.md. Tracked in #188.
  • CI: build, pack, and publish three packages with shared MinVer versioning. Status: done — per-package metadata (id, description, tags, icon, README) and shared MinVer lockstep were already in place; this work completes the pipeline. Shared publishing settings now live once in src/Directory.Build.props: every shipped package emits a .snupkg symbol package (IncludeSymbols + SymbolPackageFormat=snupkg, portable PDBs), embeds SourceLink (the .NET 8+ SDK's built-in GitHub SourceLink — no explicit package ref — plus PublishRepositoryUrl / EmbedUntrackedSources, so the .nupkg carries the repo URL + commit SHA and the PDB maps every source file to raw.githubusercontent.com/<commit>/…), and is built deterministically (ContinuousIntegrationBuild=true in CI, normalizing embedded source paths). release.yml / nightly-preview.yml pack with -p:ContinuousIntegrationBuild=true, upload and attach the .snupkgs (the dotnet nuget push *.nupkg loop auto-pushes the adjacent symbol package to the NuGet.org symbol server), and run a publish-gate validator (.github/scripts/validate-packages.ps1) that fails the release unless exactly the three expected packages were produced, each with a matching .snupkg and the required license / README / icon / repository-URL-with-commit metadata. Tracked in #190.

New collections

  • Specialized collections for domain-specific workloads (e.g. graph traversal, spatial indexing). Status: done — four specialized types shipped and #30 was closed as substantially complete (the two remaining checklist entries, StringDictionary and StructDictionary, were descoped as redundant with CelerityDictionary's existing string-hasher surface and zero-boxing struct-key support — per the guiding rule, a type that doesn't beat the BCL on a documented workload doesn't ship). BloomFilter<T, THasher> is a probabilistic membership filter with bit-array storage, no false negatives, and a tunable false-positive rate, sizing m / k from the expected element count and deriving its k bit probes from a single IHashProvider<T> call by double hashing. BitSet is its exact, deterministic counterpart: a dense fixed-length bit vector packed into 64-bit words with O(n/64) hardware-popcount cardinality (Count) and SIMD-accelerated bulk And / Or / Xor / Not, a faster, count-aware alternative to System.Collections.BitArray. HyperLogLog<T, THasher> is the probabilistic cardinality estimator: it counts the number of distinct elements in a stream of any size from a fixed array of 2^precision one-byte registers (16 KB by default) with a ~0.8% relative standard error and no growth with the data, derives its 64-bit hash from a single IHashProvider<T> call by SplitMix64 avalanche, applies linear counting for small cardinalities, and merges equal-precision estimators with UnionWith for distributed counting. CountMinSketch<T, THasher> completes the streaming-sketch trio (membership → cardinality → frequency): it estimates how many times each element occurs from a fixed depth × width grid of counters sized from an epsilon / delta error budget, never underestimates (overestimates bounded by epsilon · TotalCount with confidence 1 − delta), derives its depth counter columns from a single IHashProvider<T> call by double hashing, and merges equally-sized sketches with UnionWith for distributed heavy-hitter / frequency counting. Tracked in #30 (closed). CuckooFilter<T, THasher> later extended the family with deletable membership (#223): the same no-false-negatives / tunable-false-positive contract as BloomFilter but backed by partial-key cuckoo hashing (power-of-two fingerprint buckets, i2 = i1 XOR h(fingerprint), eviction with a single-entry victim cache), so it supports Remove with ≤2-bucket lookups — the membership filter for a set that shrinks as well as grows. Status: done. TopKSketch<T, THasher> later completed the streaming-sketch family's fourth axis — top-k / heavy hitters (#238): the Space-Saving algorithm (Metwally et al. 2005) reports a high-cardinality stream's most frequent elements from a fixed k monitors (an indexed min-heap keyed on count, with the element→monitor index dogfooding CelerityDictionary), in O(k) memory rather than the O(distinct) a Dictionary<T,int> frequency table needs to rank the top few; it never underestimates a monitored count and never misses an element above TotalCount / k. Add-and-query only, with no UnionWith (bounded top-k summaries have no exact merge). Filed and shipped after the roadmap was otherwise exhausted (a tier-(c) enhancement). Status: done.
  • Memory-pooled collections for zero-allocation hot paths. Status: done — PooledCelerityDictionary<TKey, TValue, THasher> is a drop-in, IDisposable peer of CelerityDictionary whose backing key/value arrays are rented from ArrayPool<T>.Shared and returned on Dispose (and on every internal resize), recycling buffers across build/use/dispose cycles to cut Gen 0 / LOH pressure on hot paths that rebuild dictionaries frequently. It tracks its logical power-of-two capacity independently of the (possibly over-provisioned) rented array length, clears reference-type buffers on return to prevent leaks, and throws ObjectDisposedException after disposal. Tracked in #21.
  • SIMD-accelerated probing (SSE2/AVX2) similar to Swiss Tables / F14. Status: done — shipped as a new opt-in collection type, SwissDictionary<TKey, TValue, THasher>, a drop-in peer of CelerityDictionary that keeps a parallel one-byte control-tag array so a single portable Vector128 compare tests a whole 16-slot group per probe, filtering candidates by a 7-bit hash fragment before any key comparison; deletion uses tombstones reclaimed by an occasional rehash. The default is unchanged — this is an additional type for lookup-heavy workloads (large tables, many negative lookups, clustered keys), at the cost of one control byte per slot. Tracked in #64.
  • Struct-of-arrays layout experiment for cache-friendly memory access. Status: done — shipped as a new opt-in collection type, HashCachingDictionary<TKey, TValue, THasher>, a drop-in peer of CelerityDictionary that keeps a dense side array of 32-bit hash fingerprints alongside the parallel key/value arrays. A probe scans only that compact metadata buffer and dereferences a key (running the full equality check) only on a fingerprint match, so cache-cold lookups and lookups with expensive key equality short-circuit on a single integer compare; because the forced occupied bit sits above the table mask, the cached fingerprint also yields the slot index directly, so a resize re-homes every entry without recomputing a single hash. The default is unchanged — this is an additional type for lookup-dominated / costly-equality workloads, complementary to the SIMD-probing SwissDictionary (#64), at the cost of four bytes of metadata per slot. Tracked in #65.

Infrastructure

  • Multi-target net8.0;net9.0 (evaluate net10.0) across all three packages, so newer-runtime consumers get TFM-gated optimizations (AVX-512 SIMD paths, JIT improvements). Status: done — all three packages now multi-target net8.0;net9.0;net10.0 (the "evaluate net10.0" decision: included now, since net10.0 is GA/LTS and the SDK the family already builds with; net9.0 kept as required though it is STS; net8.0 LTS stays the floor). dotnet pack emits lib/net8.0 + lib/net9.0 + lib/net10.0 in each .nupkg with the per-TFM transitive dependency graph intact, the shared TFM list lives once in src/Directory.Build.props, and CI provisions all three SDKs so dotnet test runs the suite per-TFM and the aot-publish job matrixes the Native AOT smoke test over every framework. No #if-gated code paths today (the source compiles identically on every TFM); multi-targeting is the enabling step for later runtime-gated optimizations, and CONTRIBUTING.md records the #if NET9_0_OR_GREATER / NET10_0_OR_GREATER + net8.0-fallback convention. Tracked in #189.
  • Publish a results dashboard so users can track performance over time. Status: done — the core per-commit dashboard and the weekly extended dashboard are published to gh-pages and linked from the site nav.

Milestone 2.1.0 — Celerity.Primitives: fast math & low-level utilities

The "fast-utils" expansion that fills Celerity.Primitives with specialized BCL alternatives. Comprehensive research against the current .NET (8/9/10) surface shows the BCL has closed most classic gaps — System.Numerics.BitOperations, System.Numerics.Tensors.TensorPrimitives, Convert.ToHexString, System.Buffers.Text.Base64, and generic-math Math already inline to optimal/SIMD code. So this milestone ships only the defensible white space, each with a documented BCL-beating workload (the hard rule), and deliberately does not reinvent what the BCL already does well.

Ship — real gaps with a documented workload

  • FastMod / FastDiv — Lemire reciprocal modulo & division by a runtime-constant divisor (the BCL's HashHelpers.FastMod is internal-only); 2–4× over %// for repeated mod by the same divisor (hash buckets, ring buffers, sharding). Status: done — shipped on FastUtils with 32-bit (uint → ulong multiplier) and 64-bit (ulong → UInt128 multiplier) overloads: GetFastModMultiplier precomputes the ceil(2^W / d) reciprocal once, then FastMod / FastDiv reduce each operation to a widening multiply + shift. FastMod is exact for every value and divisor >= 1; FastDiv for divisor >= 2 (the divisor == 1 multiplier overflows to 0 — a documented call-site guard). Correctness is fuzzed against % / / across both widths (representative + extreme divisors, boundary + random + exhaustive-low-range dividends), benchmarked vs the hardware operators in the extended-suite FastModBenchmark, documented in docs/api/utilities.md and the README, and exercised by the Native AOT smoke test. Tracked in #191.
  • Struct PRNG suite — value-type, allocation-free, inlinable, seed-deterministic xoshiro256** / xoroshiro128+ / SplitMix64 (+wyrand/PCG). System.Random is a heap class behind virtual dispatch and its seeded path falls back to the legacy Knuth algorithm. Curated, no marginal variants. Status: done — Celerity.Primitives.SplitMix64 / Xoshiro256StarStar / Xoroshiro128Plus / WyRand / Pcg32 ship as mutable structs implementing a one-method IRandomSource (ulong NextUInt64()); the shared NextUInt32 / NextDouble / NextSingle / NextBool / bounded-and-unbiased (Lemire) NextInt / NextInt64 / NextBytes surface is built once over the interface as ref this extension methods constrained to where TRng : struct, IRandomSource, so it devirtualizes, inlines, and runs zero-cost over any generator (e.g. a generic Fisher–Yates shuffle). Every constructor is explicitly seeded and deterministic; the multi-word generators expand the seed through SplitMix64 so every seed (including 0) is valid. Cross-checked against independent reimplementations and the published SplitMix64 seed-0 vector, covered family-wide by RandomSourceContractTests, benchmarked vs seeded/shared System.Random in the extended-suite PrngBenchmark, documented in docs/api/utilities.md and the README, and exercised by the Native AOT smoke test. Tracked in #192.
  • Span-based varint codec — LEB128 + zig-zag Try(Write|Read) over spans (the BCL's 7-bit-encoded int is only on BinaryReader/BinaryWriter, stream-bound and allocating). Status: done — Celerity.Primitives.VarInt ships TryWriteVarInt / TryReadVarInt over Span<byte> / ReadOnlySpan<byte> for uint / ulong (LEB128) and int / long (zig-zag + LEB128), plus a VarIntLength size helper, the MaxVarIntLength32 / MaxVarIntLength64 buffer-sizing ceilings, and standalone ZigZagEncode / ZigZagDecode transforms. Every Try* is bounds-safe (returns false with 0 bytes on a short / truncated / over-length / overflowing buffer, never throws). Round-trip-fuzzed (per-width boundaries + extremes + dense exhaustive low-range sweeps), benchmarked vs BinaryWriter.Write7BitEncodedInt64 in the extended-suite VarIntBenchmark, documented in docs/api/utilities.md and the README, and exercised by the Native AOT smoke test. Tracked in #193.
  • Integer digit-count / Log10 — public CountDigits (the BCL's LZCNT-based one is internal); for buffer sizing and column alignment. Status: done — FastUtils.CountDigits ships uint / ulong (exact, branch-lean: the 32-bit path is Lemire's single-Log2/LZCNT-plus-magic-table count, the 64-bit path a one-division comparison ladder) plus signed int / long overloads that count the magnitude (sign excluded, MinValue handled without overflow), and the companion integer Log10(uint) / Log10(ulong) (CountDigits - 1, exact at every power of ten where the floating-point Math.Log10 mis-rounds; Log10(0) returns 0). Correctness is reconciled against value.ToString().Length (two dense exhaustive [0, 2,000,000) sweeps + every power-of-ten boundary + ~200k random per width), benchmarked vs a naive divide-by-ten loop and (int)Math.Log10 + 1 in the extended-suite CountDigitsBenchmark, documented in docs/api/utilities.md and the README, and exercised by the Native AOT smoke test. Tracked in #194.
  • Fast non-crypto GUID v4 (from the struct PRNG) + RFC-9562 big-endian v7 (sortable, DB-friendly; the BCL's CreateVersion7 uses a non-big-endian layout that bloats DB indexes). Status: done — FastGuid.CreateVersion4<TRng>(ref TRng) is a non-cryptographic random v4 filled from any IRandomSource struct PRNG, and FastGuid.CreateVersion7<TRng>(ref TRng, long unixTimeMilliseconds) is an RFC 9562 v7 whose 48-bit timestamp sits in the big-endian most-significant bytes so the canonical string sorts in creation order (unlike .NET 9's mixed-endian Guid.CreateVersion7, which scrambles the DB sort order); the Guid is built via the field constructor with big-endian reads so this needs no .NET 9-only API (the library targets net8.0). GuidV7Generator<TRng> adds a strictly monotonic v7 sequence (RFC 9562 monotonic-counter method: a 12-bit rand_a counter that advances within a millisecond and borrows from the next on overflow), so a same-millisecond burst is still strictly increasing. Both set the correct version/variant bits, are deterministic from a seeded generator, and are documented prominently as NOT cryptographically secure (use Guid.NewGuid() for unguessable IDs). Benchmarked vs Guid.NewGuid() (and Guid.CreateVersion7 under #if NET9_0_OR_GREATER) in the extended-suite GuidBenchmark, documented in docs/api/utilities.md and the README, and exercised by the Native AOT smoke test. Tracked in #195.
  • Alignment helpers + span bit-packing over caller-owned memory (AlignUp/AlignDown/IsAligned, span bit get/set/scan/popcount), distinct from the owning BitSet collection. Status: done — FastUtils.AlignUp / AlignDown / IsAligned ship power-of-two alignment for int / long sizes and pointer-sized nuint addresses (the internal BCL Align trick, exposed and BitOperations.IsPow2-validated), and Celerity.Primitives.SpanBits is the non-owning counterpart to BitSet: Get / Set / Clear / Flip / hardware-POPCNT PopCount / TZCNT NextSetBit scan over a caller-owned Span<ulong> (a stackalloc buffer, a slice, a pooled array), plus a WordCount sizing helper — where BitSet owns its storage, SpanBits operates on memory you already manage. Reconciled against a modulo oracle (alignment) and a bool[] model (bits), benchmarked vs System.Collections.BitArray in the extended-suite SpanBitsBenchmark, documented in docs/api/utilities.md and the README, and exercised by the Native AOT smoke test. Tracked in #196.
  • Sequential bit-field cursors over caller-owned spans — BitWriter / BitReader. Status: done — a bounds-safe pair of ref struct cursors for packing and unpacking arbitrary-width bit fields over a Span<byte> / ReadOnlySpan<byte>, with no stream and no allocation, filling the gap between byte-granular VarInt and random-access SpanBits: a record of odd-width fields occupies exactly ceil(total_bits / 8) bytes instead of one byte per field (wire protocols, compression bitstreams, packed columnar / bitmap-index encodings). Bit order is LSB-first (the DEFLATE convention); the BCL has no span-based multi-bit bit writer. Released in v2.3.0 and rostered here retroactively by the 2026-Q3 roadmap review — it landed after this milestone was otherwise complete, but belongs to the SpanBits / VarInt line above rather than to the collection work it shipped alongside.

Research — verify the win before shipping

  • Fused/specialized SIMD reductions not covered by TensorPrimitives (simultaneous min+max, integer histogram, overflow-checked sum) — spike, ship only the winners. Status: done — shipped as Celerity.Primitives.SimdReductions with the two candidates that beat the BCL composition on a documented workload: MinMax (int/long/uint/ulong) folds two running Vector<T> accumulators in a single pass vs the two-pass TensorPrimitives.Min + TensorPrimitives.Max, measuring ~1.8× faster on a large out-of-cache span (a memory-bandwidth win; a wash in-cache, documented), and CheckedSum (int) widens each lane to long so the SIMD accumulation cannot overflow and throws OverflowException rather than wrapping like TensorPrimitives.Sum, measuring ~4.6× faster than the only safe alternative (a scalar checked loop). The third candidate, an integer histogram / bincount, was evaluated and not shipped — its only BCL alternative is LINQ GroupBy().Count(), the win is purely allocation avoidance achievable with a one-line counts[v]++ loop, and the scatter pattern does not vectorize portably. See docs/api/utilities.md. Tracked in #197.
  • Guaranteed-branchless conditional Select — verify the JIT actually branches (it already emits cmov for Math.Min/Max/Abs/Clamp) before shipping. Status: done — the spike confirmed the JIT does not reliably if-convert a general data-dependent condition ? a : b: a per-element blend over a 1,000,000-element span with a 50/50 unpredictable condition runs ~6× faster branch-free (~0.5 ms vs ~3.0 ms), the textbook misprediction signature. Shipped as Celerity.Primitives.Branchless.Select — scalar overloads for int/long/uint/ulong/float/double (floats bit-exact via integer-bit reinterpret) plus bulk per-element span blends (int/long/float/double) that auto-vectorize, all via the mask trick whenFalse ^ ((whenTrue ^ whenFalse) & mask). The recognised cmov idioms (Math.Min/Max/Abs/Clamp) are deliberately not re-shipped, and the docs/benchmark flag that the win is specific to the unpredictable-condition case (a well-predicted branch is free). See docs/api/utilities.md. Tracked in #198.

Explicitly out of scope — the BCL already does these well

Per the guiding rule, these are not worth shipping because they already inline to optimal/SIMD code: next-power-of-two / IsPow2 / Log2 / PopCount / LeadingZeroCount / TrailingZeroCount / RotateLeft/Right (System.Numerics.BitOperations); SIMD Sum/Min/Max/Dot/IndexOf/Contains (TensorPrimitives, generic over INumber<T>, + MemoryExtensions/SearchValues); hex and Base64 encode/decode (Convert.ToHexString, System.Buffers.Text.Base64, AVX-512); byte-swap/endianness (BinaryPrimitives); branchless Min/Max/Abs/Clamp (JIT cmov); and generic xxHash/CRC span hashing (System.IO.Hashing — depend on it rather than reimplement).

Milestone 2.3.0 — specialized-collection expansion (shipped 2026-07-19)

Rostered retroactively by the 2026-Q3 roadmap review. The planned roadmap was complete through 2.1.0, but development did not stop — it continued under the convention this project had already been following informally: when the plan is exhausted, the next item comes from reading the source, either a BCL-parity gap or a family whose members are not symmetric. That produced a full release worth of collections that were never on the roadmap. This section records them so the roadmap stays a faithful account of what shipped, not only of what was planned.

Dictionary → set parity (the specialized-set family)

The dictionary family had four specialized performance peers while the set family had none. Closing that asymmetry produced four types, each a drop-in peer of CeleritySet differing only in probing/storage strategy. All done.

  • RobinHoodSet<T, THasher> — Robin Hood open addressing; bounds probe-length variance on clustered / adversarial elements, negative lookups exit early.
  • HashCachingSet<T, THasher> — parallel cached hash fingerprints; a probe compares one integer before dereferencing an element, winning on lookup-dominated sets and costly-equality elements.
  • PooledCeleritySet<T, THasher> — ArrayPool-backed and IDisposable; recycles buffers for short-lived, frequently-rebuilt sets instead of generating Gen 0 / LOH garbage.
  • SmallSet<T> — flat-array linear scan for n <= ~16, the set counterpart of SmallDictionary and the last dictionary→set parity gap.

Their differential fuzz targets landed with them (#252), closing a harness gap where the newest sets were not driven against a BCL oracle.

Enum-keyed collections

  • EnumSet<TEnum> — bit-vector set for enum element types (the .NET analogue of Java's EnumSet); membership is a single bit test and set algebra is word-wise. Status: done. Tracked in #259.
  • EnumMap<TEnum, TValue> — dense array-backed dictionary for enum keys, the dictionary counterpart of EnumSet; a lookup is a direct array index, not a hash probe. Status: done. Tracked in #263.

Both support enums whose members are small non-negative integers; a negative or sparse ([Flags]) enum throws at construction. Note: these are enum-generic, so they cannot join the int-parameterized shared test suites — they carry dedicated coverage instead.

BCL gaps — structures .NET does not ship at all

Each of these fills a genuine hole in the framework rather than beating an existing BCL type.

  • Deque<T> — growable double-ended queue over a circular buffer. .NET has no array-backed deque (Queue<T> / Stack<T> are single-ended; LinkedList<T> allocates per element). All four end operations plus a front-relative indexer are O(1) amortized. Status: done. Tracked in #268.
  • DisjointSet<T> — union-find with union-by-size and path halving. .NET ships no union-find; the idiomatic Dictionary<T, HashSet<T>> merge is quadratic where this is near-linear. Status: done. Tracked in #272.
  • LruCache<TKey, TValue, THasher> — fixed-capacity LRU. .NET ships no bounded LRU cache; the steady-state get/put/evict path allocates nothing, unlike the idiomatic Dictionary + LinkedList hand-roll. Status: done. Tracked in #266.
  • IndexedPriorityQueue<TElement, TPriority, THasher> — an addressable binary heap: unlike PriorityQueue<,> it supports decrease-key / update-priority and remove-by-element in O(log n), the operation Dijkstra / A* / event simulation need and the BCL type cannot do without a lazy-deletion workaround. Status: done.

Membership filters

  • XorFilter<T, THasher> — build-once, immutable membership filter; smaller (~9.84 bits/element) and faster to query (three probes, no probe loop) than BloomFilter or CuckooFilter at the same false-positive rate, completing the membership-filter family with its static member. Status: done.

Primitives

  • BitWriter / BitReader also shipped in this release; they are rostered under milestone 2.1.0 above, alongside the SpanBits / VarInt work they extend.

Milestone 2.4.0 — rolling post-roadmap work

The planned roadmap is complete through 2.1.0, and the two releases since have been driven entirely by source-reading rather than by the plan. Rather than let that work keep landing unrostered — the drift the 2026-Q3 review was opened to catch — 2.4.0 is a standing milestone that new post-roadmap work is filed against as it is identified. It is not a fixed scope with a completion date; it is the home for the tier-(c) lane.

Work admitted here is held to exactly the same bar as everything above: the hard rule (a documented workload where it beats its BCL counterpart, or a genuine BCL gap) and the non-goals.

In flight

Shipped to main, awaiting the next release tag:

  • Trie<TValue> — ordered prefix tree mapping string keys to values; the operation no hash table can do is prefix enumeration in sorted order without scanning every key. Status: done. Tracked in #285.
  • SparseSet — bounded-universe [0, Universe) integer set with O(1) clear and dense iteration; the classic ECS / graph-visited-set structure, where HashSet<int>.Clear() and hash iteration both lose. Status: done. Tracked in #287.
  • FenwickTree<T> — Binary Indexed Tree over a fixed-length sequence: O(log n) point update and prefix-sum query, where a running-sum array gives O(1) query but O(n) update and a plain array gives the reverse. Status: done. Tracked in #289.

Planned

The 2026-Q3 review surveyed the shipped surface against the current .NET 8/9/10 BCL and adversarially verified each candidate against the hard rule and the non-goals. Thirty-six candidates were proposed; twelve were rostered, in four themes. The open issues on the 2.4.0 milestone carry the detail.

Drop-in parity and correctness in the shipped surface. Work on code already on NuGet, and the highest-confidence group.

  • Fix HyperLogLog's hash-entropy floor. Hash64 widens a 32-bit IHashProvider<T> result, so the reachable hash space is 2^32 — while the type's own docs assert a 64-bit space and skip the classical large-range correction on that basis. The bias exceeds the advertised 0.81% standard error from ~1e8 distinct elements, in exactly the regime the type is sold for. Needs an IHashProvider64<T> sibling interface and 64-bit-native hashers; the same floor is inherited by every other sketch. Status: planned.
  • Implement IReadOnlySet<T> on the mutable sets and IDictionary<TKey, TValue> on the dictionaries. The sets implement ISet<T> and the dictionaries IReadOnlyDictionary<,>, but ISet<T> does not derive from IReadOnlySet<T> — so an ordinary BCL-shaped API taking either interface is a compile error against a Celerity type today. This is the same Guiding Principle #3 gap the 2.2.0 set-algebra work closed, one level up. Status: planned.
  • Delete the per-probe virtual call. The probe loops test for an empty slot with EqualityComparer<TKey>.Default.Equals(slot, default(TKey)), which the JIT devirtualizes for value-type keys but not under __Canon-shared reference-type instantiations — one callvirt per probe iteration to perform what is a null check. Guiding Principle #2 exists to remove exactly this. Status: planned.
  • Span-keyed lookups on the string-keyed collections. .NET 9's GetAlternateLookup<ReadOnlySpan<char>> lets the BCL Dictionary probe with a span key and no allocation; Celerity's string-keyed types require a materialized string, so the BCL is now ahead on the axis this library has invested most in. Status: planned.

The ordered / compressed integer-data lane. Opened by the sorted-container hole — 38 collections and not one sorted map or set, with Trie the only ordered type, and that one string-keyed. The B-trees below close that half; the compressed-integer half is still open.

  • BTreeDictionary<TKey, TValue, TComparer> / BTreeSet<T, TComparer> — cache-friendly sorted containers against SortedDictionary<,> / SortedSet<T>, which are red-black trees with a pointer chase and an allocation per node. Status: done. Tracked in #305.
  • CompressedIntSet — a Roaring-style compressed set of 32-bit integers, covering the huge-and-sparse shape that neither BitSet (dense, bounded) nor SparseSet (small universe, O(Universe) memory) nor IntSet (hash) serves. Status: planned.
  • RankSelectBitVector — succinct Rank / Select over a dense bit vector, the primitive the above compose on. Status: planned.
  • Sorted-span set algebra in Celerity.Primitives — merge-based Intersect / Union / Except / IntersectCount over already-sorted spans, where the BCL answer is LINQ or a HashSet round-trip. Status: planned.

A fourth core package: Celerity.Sorting. Array.Sort / MemoryExtensions.Sort are scalar comparison introsort with no radix, counting, or selection path for primitive keys — and the BCL structurally cannot close it, because Array.Sort is contractually in-place while radix needs O(n) scratch. That is precisely the flexibility-for-speed trade this project's Vision licenses, against a named BCL counterpart. Would layer on Celerity.Primitives, mirroring how Hashing and Collections layer today. Status: planned — see the package-scoping caveat below.

Build- and release-pipeline integrity. Three guards the repo advertises but does not have.

  • The coverage gate measures one of the six shipping assemblies. src/coverage.runsettings filters to [Celerity]* with the comment "Measure only the shipping library assembly" — written when there was one. Celerity.Hashing, Celerity.Primitives and the three showcase packages are unmeasured, while CONTRIBUTING.md and CLAUDE.md describe the 95%/90% gate as library-wide. Status: planned.
  • Nothing can fail after the NuGet push. release.yml pushes six packages irreversibly, then extracts the release notes and creates the GitHub Release — so an over-long release body (a failure this repo has actually hit) leaves a half-published release. The notes check should be hoisted ahead of the push. Status: planned.
  • No API-compatibility gate. Six packages publish on a tag with no ApiCompat / PackageValidation / public-API-baseline check anywhere in the repo — in a project that already needed a hand-written TypeForwarders.cs to survive one assembly split. Status: planned.

Two areas were judged real but deliberately deferred rather than rostered: a Celerity.Statistics package (DDSketch / reservoir sampling / running moments — a coherent fourth axis, but two new packages in one cycle is too much at once), and a batch of fuzz-target and AOT-smoke-coverage gaps (real, but low expected defect yield; better folded into whichever collection PR lands next than pursued on their own).

Non-goals

  • We are not trying to replace Dictionary<,> in every scenario. Celerity trades flexibility for speed on specific shapes; that tradeoff must be documented, not hidden.
  • We are not a thread-safe collections library. Callers that need concurrency should compose with locks or use ConcurrentDictionary<,>.
  • We are not a serialization library. Celerity collections should be straightforward to serialize via System.Text.Json / MessagePack, but we won't ship formatters ourselves.
  • We are not a general-purpose data structures library. If a collection doesn't beat the BCL on a documented benchmark, it doesn't belong here.