High-performance .NET collections that beat the BCL on documented workloads.

int-keyed dictionary, default Wang hash.

long-keyed dictionary, default Wang hash.

Generic dictionary with a struct hasher constraint.

Robin Hood open addressing: bounded probe variance for clustered keys.

Swiss-table SIMD group probing: one Vector128 compare tests 16 slots per lookup.

Struct-of-arrays layout with a cached-fingerprint side array: probes scan metadata only and short-circuit expensive key equality.

ArrayPool-backed, disposable dictionary that recycles its buffers to cut GC pressure.

Build-once string-keyed dictionary with perfect hashing for single-probe lookups.

One-to-many map: each key groups multiple values. Implements ILookup.

Counting multiset (bag): each element maps to its multiplicity. Single-probe Add for frequency counting.

Flat-array, linear-scan dictionary tuned for the very-small (n ≤ ~16) case.

Dense array-backed dictionary for enum keys (the .NET EnumMap): a lookup is a direct array index — no hashing, no probing, no collisions. Ascending-value enumeration. The dictionary counterpart of EnumSet.

int-keyed set, default Wang hash.

long-keyed set, default Wang hash.

Generic set with a struct hasher constraint.

Swiss-table SIMD group probing for sets: one Vector128 compare tests 16 slots per membership check, so negative lookups stay cheap. The set counterpart of SwissDictionary.

Robin Hood open addressing for sets: bounded probe variance and early-exit negative lookups on clustered elements. The set counterpart of RobinHoodDictionary.

Struct-of-arrays layout with a cached-fingerprint side array for sets: probes scan metadata only and short-circuit expensive element equality. The set counterpart of HashCachingDictionary.

ArrayPool-backed, disposable set that rents its backing array and returns it on Dispose, recycling buffers to cut GC pressure on short-lived, frequently-rebuilt sets. The set counterpart of PooledCelerityDictionary.

Build-once string set with perfect hashing for single-probe membership tests. Implements IReadOnlySet.

Flat-array, linear-scan set tuned for the very-small (n ≤ ~16) case. No hasher; the default element is stored inline. The set counterpart of SmallDictionary.

Bit-vector set for enum keys (the .NET EnumSet): membership is a single bit test and set algebra is word-wise bitwise ops — no hashing, no boxing. Ascending-value enumeration.

Bounded-universe integer set (Briggs–Torczon sparse set): O(1) Clear that leaves the backing arrays untouched and dense, cache-friendly iteration — for clear-and-rebuild "visited" sets in graph / ECS / sweep-line code.

Exact compressed set of 32-bit integers: each 65,536-value chunk is stored as a sorted array or a bitmap by density, with an opt-in run-length form for clustered data that Optimize() and AddRange() produce. Set algebra runs word-parallel inside a chunk and skips a whole chunk with one comparison, and enumeration is in ascending order. For huge-and-sparse integer sets — posting lists, row-id sets, cohort intersection — where HashSet<int> costs ~10x the memory and one hash probe per element. No portable Roaring format: this is an in-process structure, not an interop codec.

Probabilistic membership filter: bit-array storage, no false negatives, tunable false-positive rate. A fraction of a HashSet's memory.

Probabilistic membership filter that supports deletion: fingerprint buckets, no false negatives, tunable false-positive rate, ≤2 cache lines per lookup. The Bloom filter you can Remove from.

Probabilistic membership filter that is build-once & immutable: ~9.84 bits/element (smaller than a Bloom filter at the same rate), three probes + two XORs per lookup. The smallest, fastest-to-query filter for a fixed element set.

Dense exact bit vector: O(n/64) population count and SIMD-accelerated bulk And/Or/Xor/Not over 64-bit words. A faster, count-aware BitArray.

Immutable succinct index over a dense bit vector: Rank (set bits below a position) in O(1) and Select (position of the k-th set bit) in O(log n), for 25% space over the bits. The BCL has no rank or select anywhere — the alternative is a hand-rolled O(i/64) popcount loop. Build-once: any mutation means rebuilding the index.

Probabilistic cardinality estimator: counts distinct elements in a fixed few KB with ~0.8% error, no matter how many you add. Mergeable; a fraction of a HashSet's memory.

Probabilistic frequency estimator: estimates how often each element occurs from a fixed few KB, never underestimating. Mergeable; a fraction of a frequency-table Dictionary's memory.

Top-k / heavy-hitters sketch (Space-Saving): reports a stream's most frequent elements from a fixed k monitors, never underestimating. O(k) memory instead of one entry per distinct key.

Fixed-capacity least-recently-used cache with O(1) get/put and automatic eviction. Recency runs through an intrusive list over fixed arrays, so the hot get/put/evict path allocates nothing — unlike the idiomatic Dictionary+LinkedList LRU that allocates a node per insert.

Fixed-capacity least-frequently-used cache with expected-O(1) get/put and ties between equally-frequent entries broken by least-recently-used; the eviction bookkeeping itself is worst-case O(1) rather than logarithmic, while the open-addressed key-index probe leaves the whole operation expected O(1), as everywhere else here. It exists for the one failure mode recency cannot see: an LRU is scan-vulnerable, so a single sequential pass over a capacity’s worth of cold keys evicts the whole hot set no matter how often those keys were used. Here a scan key arrives at frequency 1, so a scan of any length costs at most one entry that has been read more than once — one if the cache was full with nothing at frequency 1 when the scan began, none if it had spare room — against an LRU losing its whole working set. The guarantee is conditional and the condition is the policy: an entry inserted and never read again sits at the scan’s own frequency and is older than the incoming keys, so a scan takes it. LFU protects demonstrated reuse, and one use demonstrates none. Entries sit in frequency buckets held in an ascending-frequency list, both threaded through fixed arrays allocated once, so the hot path allocates nothing — against an idiomatic Dictionary+SortedSet LFU that is O(log n) per operation and allocates a tree node per insert. The tradeoff is stated rather than hidden: frequencies never age, so a key that was hot long ago can hold its slot; use it for a stable, skewed popularity distribution and keep LruCache for recency-dominated ones.

Growable double-ended queue backed by a circular buffer: O(1) push/pop/peek at both ends and O(1) random access. The array-backed deque the BCL lacks — a bounded churn allocates nothing (vs a node per op for LinkedList) and enumerates contiguous memory.

Immutable indexed sequence over a 32-way bit-partitioned trie with a tail buffer: every operation returns a new vector sharing all but O(log32 n) of the old one's storage. Indexes and appends an order of magnitude faster than ImmutableList's per-element AVL nodes, where ImmutableArray copies the whole array on every append.

Immutable hash map over a CHAMP trie (the refinement of Clojure's HAMT that Scala's HashMap adopted in 2.13): a single-key edit returns a new map sharing all but one root-to-leaf path of the old one's storage, and a write that changes nothing hands back the receiver. Branching factor 32 with entries inline in flat arrays, against ImmutableDictionary's AVL tree of branching factor two with a heap node per entry — so a lookup is a few popcount-indexed array reads rather than a pointer chase per level. The map for state read far more often than it is written and still handed to readers as a snapshot: a config or feature-flag set swapped atomically, a symbol table threaded through a compiler pass, an interpreter environment.

Immutable hash set: PersistentHashMap's CHAMP trie with the value array taken out. A single-element edit returns a new set sharing all but one root-to-leaf path of the old one's storage, and an edit that changes nothing hands back the receiver. Branching factor 32 with elements inline in flat arrays, against ImmutableHashSet's AVL tree of branching factor two with a heap node per distinct hash — so a membership test is a few popcount-indexed array reads rather than a pointer chase per level. The set for membership state tested far more often than it is written and still handed to readers as a snapshot: an allow- or deny-list swapped atomically, a visited set threaded through a backtracking search.

Union-find over arbitrary elements: partitions them into disjoint sets with near-O(1) amortized Union/Find/Connected via union-by-size and path halving. The union-find the BCL lacks — incremental connectivity, connected components, and Kruskal MST in near-linear time, where a Dictionary+HashSet set-merge is quadratic.

Addressable binary min-heap: unlike the BCL PriorityQueue it can change a queued element's priority (Update / decrease-key) and remove an arbitrary element in O(log n), and answer Contains/TryGetPriority in O(1). The heap the priority-relaxation loop of Dijkstra / Prim / A* needs — no lazy-deletion heap growth.

Hierarchical timing wheel — a container of pending deadlines, with no thread, no clock and no callback: the caller owns time and drives it with Advance. Cancel is O(1) and Schedule amortized O(1) — the one call in a growth cycle resizes the backing arrays — and an advance is bounded by the wheel’s own geometry — O(levels × slots + fired + cascaded) — rather than by the ticks it crosses. The workload is defined by cancellation — almost every timeout is cancelled because the reply arrived — and that is where the BCL fails: PriorityQueue has no removal at all on net8 and the one .NET 9 added is O(n), so the standard workaround is lazy deletion, a heap that grows with the timers that will never fire and a hash probe per pop. Timers land in the lowest of four stacked 256-slot wheels that can express their delay, threaded through one flat entry array as intrusive doubly-linked lists, so there is no object per timer; a cascade only ever moves a timer down a level. Advance is not the textbook tick-at-a-time loop — it computes the slots a move crosses per level, so a clock that jumps a million ticks pays for the wheel, not for the jump. On the round it is sold for — 100,000 timeouts scheduled, nine in ten cancelled, the clock run out — CI measures 6.81x the lazy-deletion heap and 7.09x IndexedPriorityQueue. Three things are traded for that: the horizon is finite (256⁴ ticks, about 49 days at a millisecond) and a longer delay is rejected rather than misplaced; a batch of fired timers comes back in no particular order, since a wheel buckets rather than sorts; and Schedule is an outright loss to the BCL heap, about 2x at 100,000, because appending to a contiguous array beats writing a scattered slot head and a back-link — it still beats the addressable heap by 2.71x, and the round, which charges the cancels the heap defers, is the number this type lives on. A large-population type: at a thousand timers Cancel is 2.2x slower and a tick-by-tick drive 1.8x slower.

A rope — a balanced tree of bounded character runs, so the cost of an edit stops scaling with the document. Where a contiguous buffer shifts O(n) characters on every edit whatever its size, this moves at most one leaf: Insert is O(log n + k + ChunkSize) and Remove O(log n + ChunkSize), both amortized over an occasional defragmenting rebuild. The library’s only mutable text type: Trie, SuffixArray and AhoCorasick all search text that does not change. StringBuilder is a chunk list whose head is the end, which makes appending excellent and Insert, Remove and everything else linear in the document — ten times the text is ten times the cost of one edit. It also has two operations the BCL has at no cost at all: Split cuts a document in two in O(log n + ChunkSize) and AppendAndClear joins two back in O(log n), where Concat, Substring and slice-and-copy are full copies. Leaves are AVL-balanced and filled to three quarters of ChunkSize on purpose, so the ordinary short edit lands in a leaf that has room and is a memmove that allocates nothing; filling them to capacity instead measured a 2.9x loss. Fragmentation is undone by an amortized rebuild gated on leaf count, O(ChunkSize) per edit. On a round of 200 scattered insert/remove pairs it measures 98x StringBuilder at a million characters and 1.49x at ten thousand, with Remove at about 94x and a hundred split-and-rejoin cycles at 713x (186 KB against 400 MB). Three operations are outright losses and this is not a general StringBuilder replacement: appending is 36.8x slower — a bounds check and a store, against a tree descent, so text that is only appended to belongs in a StringBuilder — random access is 7.1x slower, since a builder built from a string is a single chunk and indexes directly, and ToString() is 1.68x. Memory is about 2.7 bytes per character against two, and indices are UTF-16 code units, so a cut can split a surrogate pair.

Ordered prefix tree mapping string keys to values: GetByPrefix lists every entry under a prefix in O(prefix + matches) and TryGetLongestPrefix finds the longest stored prefix of a query in O(query). The trie the BCL lacks — autocomplete, routing, and ordered iteration, where a Dictionary must scan every key and run StartsWith.

The build-once prefix tree, whose tree shape costs two bits per node (about 3 bytes a node once labels, the terminal bit and the two rank/select indexes are counted): the same GetByPrefix, TryGetLongestPrefix and ordered enumeration as Trie, over a level-order unary degree sequence (LOUDS) held in a RankSelectBitVector plus one label array — the composition that primitive’s own documentation named and the library never shipped. What it buys is footprint. A pointer-based trie spends an object header, a char[], a Node[], a child count, a value slot and a flag on every node; at 100,000 keys that is 40.16 MB retained against this type’s 1.05 MB — 38.1x smaller — and the key strings are never stored at all, which a Dictionary<string, TValue> must keep alive alongside its own 3.04 MB. A node that is only a waypoint costs no value slot: which nodes end a key is a second rank/select vector whose Rank indexes a compact value array. Every query arm is slower and that is the trade being sold: exact Lookup is 28x a Dictionary and 6.4x Trie, building is 12.5x, and a span lookup is 12x — though it allocates nothing where the dictionary allocates a string per probe. The prefix win is a matter of selectivity: on a nearly-complete token with a handful of completions it is 1,042x a Dictionary, which must read every key it holds; on bulk-enumerating a sixteenth of the table it is 3.6x slower than one — an arm Trie does not win either (1.16x), because the dictionary’s scan hits a match every sixteen entries and both tries are charged for materializing 100,000 result strings. Read the two prefix cards together. Immutable, so a changed key set means a rebuild — fill a Trie and snapshot it. Ordinal over UTF-16 code units; the empty string is a valid key; safe to share across threads.

Canonicalizing token table probed with a ReadOnlySpan<char>: GetOrAdd returns the one shared string for those characters and allocates only on a miss, so a 10M-cell parse over 100 distinct tokens creates 100 strings, not 10,000,000. The collection you cannot build on the pre-.NET-9 BCL — HashSet<string> makes you allocate the string before you can discover you already had it. The same span-keyed lookups also ship on FrozenCelerityDictionary, FrozenCeleritySet, CelerityDictionary, CeleritySet, and Trie.

Binary Indexed Tree over a fixed-length numeric sequence: point update and prefix / range sum both in O(log n), in one array with no per-node overhead. The prefix-sum structure the BCL lacks — running aggregates, rank counters and cumulative-frequency tables, where a plain array is O(n) per query or O(n) per update.

Range aggregates over an arbitrary associative fold, with point updates and range queries both in O(log n), in one flat array of 2n cells. The half of the range-query space a Fenwick tree cannot reach: its query is the difference of two prefix folds, so it needs an inverse — a segment tree stores each node's fold outright, so range min, max, gcd, bitwise and/or — and any monoid you write — are all in reach. The BCL has no range-aggregate structure at all, so the baseline is a plain array scanned per query. Non-commutative folds are safe: the query preserves index order.

The build-once half of the range-aggregate space: the same range fold as a segment tree, answered in O(1) — two array reads and one combine, no loop and no descent. It precomputes the fold of every window whose length is a power of two, then covers an arbitrary range with the two such windows anchored at its ends. Those windows always overlap — by 2·2^k − length elements, which is never zero, and at an exact power-of-two length they are the same window, so the whole range is folded twice — and everything in the overlap is combined twice. That is harmless exactly when the operation is idempotent. That law is in the type system, not a doc paragraph: the fold is constrained to IIdempotentMonoid<T>, which MinMonoid, MaxMonoid, BitwiseAndMonoid, BitwiseOrMonoid and a gcd you write yourself satisfy — and SumMonoid does not, so SparseTable<int, SumMonoid<int>> is a compile error rather than a quietly inflated answer. The BCL has no range-aggregate structure at all, so the outside baseline is the same plain array scanned per query: a batch of range-minimum queries measures about 100x that scan at a thousand elements and 8,200x at a hundred thousand. The comparison that actually decides between the two Celerity types is against SegmentTree, measured in the same benchmark class: the query is roughly 9–11x at a thousand and 16–19x at a hundred thousand. Both comparisons are asymptotic — O(1) against O(n) and against O(log n) — but they widen at very different rates: the margin over the array scan grows linearly in n, while the margin over a segment tree grows only as log n, which is why it moves so little across two orders of magnitude and reads like a large constant. These are ranges rather than single figures because two short runs of identical code disagree by up to 25% on them; the memory numbers below are exact, being allocation counts. Read the Build card with it. That O(1) is bought with an O(n log n) build into levels × n cells against a segment tree’s O(n) into 2n: the build measures about 4–5x the segment tree’s at both sizes and the table holds 5x its memory at a thousand elements and 8.5x at a hundred thousand (13.6 MB there). So the crossover is published rather than assumed — roughly 800–1,000 queries at a thousand elements and 65,000 at a hundred thousand before the extra build is repaid. Query fewer times than that and the segment tree is the better type; query a short range and the array scan beats both. Immutable: there is no point update, no Clear, and no version — so once built an instance is safe to share for reading, with the caveat that every query calls the fold, so a monoid that is not itself thread-safe makes concurrent queries unsafe however immutable the table is (the five shipped folds are stateless). Non-commutative idempotent folds are safe: the left window is combined first, so index order is preserved.

Build-once spatial index over points in the plane, answering which point is nearest, which lie within this radius and which lie inside this box without measuring every point. .NET ships no spatial index of any kind — no k-d tree, no quadtree, no R-tree — so the alternative is an array and a loop over all of it; ordering that array by x lets a scan work outward from the query and stop on the horizontal gap alone, which is a real optimization and the baseline worth judging the type by, but it can still only bound one of the two dimensions. Nearest store or driver, viewport culling, collision broadphase, the neighbour queries inside k-means and DBSCAN. The ratio tracks selectivity, not size: pruning discards subtrees that cannot hold a result, so a query answering with much of the tree converges on the scan. The nearest, predicate, count and copy-into-your-buffer tiers allocate nothing — the k-nearest query heaps inside the caller's own buffer — and the whole structure is two flat arrays — interleaved coordinates and the payloads — with no per-point node.

The mutable spatial index: constant-time Move and Remove — and amortized-constant Add — addressed by a handle, plus radius, rectangle and nearest queries that touch only the cells they cover. KdTree is build-once and says so in its own docs — rebuilding it per frame costs more than the queries save — which leaves the commonest spatial workload of all unanswered: game entities and projectiles, drivers and couriers on a map, cursors and drag targets, particles and agents. All of them move every tick and all of them ask "what is near me" every tick. The baseline is not a strawman: a Dictionary<(int, int), List<T>> bucketed grid is what a competent developer writes, and what it costs is a tuple hash and a bucket probe per cell touched, a list object per occupied cell, and a pointer chase into it. A populated grid here is three flat arrays — the cells' list heads, the fixed-size entry records threaded through them, and the payloads kept apart so the cell walk never touches them — with no per-cell or per-entry object, and every tier but the two Get helpers allocates nothing. 5.0x that hand-roll on a frame of 100,000 entities, and 13.3x rebuilding a KdTree instead. Read the caveat with the number: everything gained is per cell, not per point, so the margin thins as cells fill — 1.12x at ten points per cell — and on clustered data the grid loses, because a long cell list is a serial chain of dependent loads where the baseline's contiguous list is not. Uniform cells want points spread evenly. If yours cluster hard, the measurement is unflattering and stated anyway: the hand-roll beats this type there, and rebuilding a KdTree every frame is level with it rather than a way out.

Build-once spatial index over extents rather than points — axis-aligned rectangles — answering which boxes overlap this box and which contain this point without testing every box. KdTree cannot stand in: a box can overlap the query while its centre sits far outside it, which is the two-dimensional form of the argument that made IntervalTree necessary on one axis. Collision broadphase for bodies with a size, map label placement, hit-testing a canvas, viewport culling, spatial joins. The boxes are permuted by STR (Sort-Tile-Recursive) packing and a fixed-fanout tree laid over them implicitly, so there are no per-node objects and no child pointers — one flat array of extents, one of payloads, one of node bounding boxes. The predicate, count and copy-into-your-buffer tiers allocate nothing. The received wisdom that it only earns its keep when extents vary by orders of magnitude, and that uniform ones belong to a bucketed grid, is measured rather than repeated — and does not survive: against a grid arm of its own the tree is 1.30x ahead on varying extents and 3.01x ahead on uniform ones, because a grid’s query cost is dominated by the cells a query covers while an R-tree’s node boxes get tighter as extents get more alike. The real reason to reach for a grid is that it is mutable and this is build-once.

Build-once index over half-open [start, end) ranges answering which ranges cover this point and which overlap this window in time that tracks the matches found, not the intervals stored — O(log n + k) when they cluster, O(min(n, (k + 1) log n)) when scattered, O(n) worst case once zero-length intervals are stored. .NET ships no interval structure at all, so the alternative is a List<T> scanned per query; sorting it by start lets the scan stop at the upper bound but not skip the front, since a range beginning far to the left can still cover the point, so it stays linear. Booking-conflict checks, IP-range lookup, effective-dated pricing, "which trace spans were live at t". The predicate, count and copy-into-your-buffer tiers allocate nothing (the two Get helpers return an array, by definition); the whole structure is four flat arrays with no per-interval node. Zero-length intervals are stored but never match, and cannot be pruned in bulk — filter them before building if your data has many.

Mutable map from disjoint half-open ranges of keys to values — the coalescing interval map IntervalTree is not. Assigning a value to [start, end) overwrites whatever was there, splitting any range that straddles either edge, and ranges left adjacent with equal values merge, so the map always holds the maximal runs. .NET ships nothing for this; the alternative is a List<T> kept sorted by start, which binary-searches a lookup well but memmoves its tail on every assignment. Keyspace and IP-range ownership edited as shards move, an allocator’s used-versus-free map, effective-dated configuration edited in place, style runs, availability calendars. Stored as a B-tree keyed by each range’s end, so a lookup is one descent and an assignment O((k + 1) log n) for the k ranges it overwrites; a write that changes nothing leaves the map, and its enumerators, untouched. At 100,000 ranges an assignment measures 7.5x a sorted List<T> patched in place; every read loses to that list’s binary search (lookup 1.5x, window walk 3x slower), and at 1,000 ranges so does the write — it is for maps you keep editing.

Build-once graph, stored compressed sparse row: an offset per vertex and one contiguous target array, so Neighbors(v) hands back a ReadOnlySpan<int> slice of the graph’s own storage — no copy, no enumerator, no List<int> object per vertex. .NET ships no graph type at all — no adjacency list, no adjacency matrix, no traversal — so the alternative is a Dictionary<int, List<int>>, or a List<int>[] once you notice the ids are dense; both are benchmarked rather than only the weaker one. Dependency and build ordering, package and module resolution, link / follower / call graphs, reachability and impact analysis. Breadth-first traversal and a topological order both use the caller’s destination buffer as the queue, so a repeated walk allocates nothing once the ArrayPool it borrows its visited set from is warm, and Reverse() is the transpose as an O(V + E) counting scatter where the adjacency map has to rebuild itself list by list. Every ratio names its baseline, because the three disagree by a lot — and against the best hand-roll this is not a speed win. The identical walk over the identical edges is about 2.5x a Dictionary<int, List<int>>, 1.8x a List<int>[], and 1.2x an int[][] sized exactly and filled in vertex order, where at 1,000 vertices that hand-roll beats this type, as it does on build. List<int> grows its backing array in the order the edges arrive, so the data scatters however tidily the list objects were made; size the rows exactly and a caller has taken most of what flattening them would give. What survives against that baseline is the transpose (2.5–3.0x) — structurally, since the jagged form must allocate a row per vertex where CSR scatters into arrays it already holds — a 1.8x smaller footprint, and not writing, testing or maintaining the traversal, Kahn’s algorithm, the transpose, the deduplication and the sorted-target invariant on a structure .NET does not ship at all. A pre-registered kill criterion (≥3x on the traversal) was missed, at 2.5–2.6x across two CI runs, and two successive explanations published for that miss were wrong before tight baselines were measured for every claim. The ratios are ranges because two CI runs of identical code disagree by up to 20% on the allocation-heavy arms. All of it is recorded rather than rounded away. Immutable, dense ids only, no edge weights and no shortest paths.

Build-once text index: every suffix of a block of text in sorted order, plus the longest-common-prefix array beside it, so where does this substring occur is answered in time that tracks the pattern rather than the text — two binary searches over the suffix order, at O(m log n) against the scan’s O(n). .NET ships no text index at all: string.IndexOf, MemoryExtensions.IndexOf and Regex are vectorized scans that re-read the text on every query, and .NET 9’s SearchValues<string> indexes the needles, not the haystack. Log search, document and source-code search, plagiarism and near-duplicate detection, bioinformatics — anywhere the text is fixed and the queries keep coming. Contains, CountOccurrences, IndexOf and a zero-copy TryGetOccurrences that hands back a slice of the index itself; TryGetLongestRepeatedSubstring reads the longest repeat off the LCP array in one pass, which is a question no scan-shaped API can even express and whose naive answer is quadratic. At 100,000 characters, counting a pattern measures 68x the scan and ruling an absent one out 64x; at 1,000 characters both fall to about 1.3x. This is a build-once index and one query against a text read once is a loss — the build is repaid at roughly 1,000 counting queries at 100,000 characters and about 3,900 at 1,000, so the crossover is published rather than assumed. And the second baseline is not the scan but the Dictionary<string, int[]> k-gram index a caller writes instead, which wins by 10.3x on query cost at the one pattern length it can answer, and pays for it on build (1.39x) and footprint. Ordinal over UTF-16 code units, about 10 bytes per character, immutable: changing the text means rebuilding.

Build-once multi-pattern matcher: a fixed set of patterns compiled into one automaton that finds every occurrence of every pattern in one left-to-right pass, at a cost that does not grow with how many patterns there are. This is the other half of the text axis and neither neighbour reaches it: Trie matches a prefix of the query and cannot resume inside a text, while SuffixArray indexes one fixed text and answers one pattern at a time — the wrong way round when the text is what streams past. .NET has nothing for it either: string.IndexOf is a single-needle scan, so k patterns cost k passes, and .NET 9’s SearchValues<string> answers only where is the first of these, not every occurrence of each and which one it was. Log and alert scanning, keyword and profanity filters, WAF and IOC rule sets, tokenizer dictionaries, DLP scanning. Overlapping matches are reported, not resolved — "he", "she" and "hers" over "ushers" is three matches — because which one wins is the caller’s policy, not the matcher’s. Two baselines, and one of them beats it. Against a compiled Regex alternation of the same 256 patterns over 100,000 characters — driven through the allocation-free Regex.EnumerateMatches, so the baseline is not charged for a Match object per hit — it measures 10.0x on ContainsAny and 4.8x on enumerating every match; building the automaton is 4.7x constructing that same alternation uncompiled, which is the only fair build comparison, since RegexOptions.Compiled emits IL. Against the obvious k-IndexOf loop it wins one shape and loses the other: 4.1x on counting every occurrence of patterns that are present, but 0.98x — a loss — on ruling 256 absent ones out, because a scan that never finds a candidate worth verifying stays inside its vectorized sweep and covers many characters per step where this pass covers one; at eight patterns the loop wins by 5.0x. Those crossovers are the numbers to check first: the loop is O(k · n) and this is O(n), so break-even lands near fifty patterns for counting and several hundred for absent membership, and every arm is on the dashboard. Stored flat in breadth-first order — a compressed child table binary-searched per character, a direct-mapped root table for the ASCII step a scan spends most of its time on, plus a failure and an output link per state — with no per-node objects. Ordinal over UTF-16 code units; duplicates collapse and the empty pattern is rejected; immutable, so changing the pattern set means rebuilding.

Sorted map backed by a B-tree with up to 31 keys per node in flat arrays, so a lookup visits ~log₃₂(n) nodes instead of chasing ~log₂(n) pointers. The B-tree the BCL lacks — Min/Max, lower/upper bound and O(log n + k) range scans, where SortedDictionary is a red-black tree with an object per entry and SortedList memmoves on every insert.

The set counterpart: ordered elements packed 31 to a node, with the same ordered surface and an in-order walk over contiguous arrays instead of successor pointers. Beats SortedSet on the interleaved insert + membership + range-scan workload, and stores no values, so the memory saving is larger still.

The ordered set that also answers what rank would this element occupy and what is the k-th smallest, both in O(log n), on a set still being inserted into and removed from. .NET has no counterpart: SortedSet has no rank and no positional accessor, so the answers are ElementAt(k) and a walk to the probe — both linear; SortedList and a hand-rolled sorted List<T> do index and rank, and memmove half the array on every insert. Live leaderboards, exact percentiles over a moving window, a sweep line that needs the median of its active set. Elements sit in sorted buckets whose capacity tracks √n (never below 512), with a Fenwick tree over the bucket lengths carrying the positional half, so a rank is a prefix sum and a select is one binary-lifting descent plus an array index — no per-element node. That is sqrt decomposition, and it is the whole trade: the queries are O(log n), the mutations are O(√n) — one bounded, contiguous memmove, which still measures faster than SortedSet’s pointer chase at 100k. Buckets are not narrowed as elements leave, so after a sharp contraction that is the high-water √n until TrimExcess() rebuilds at the current size — stated rather than left to be discovered. RemoveAt(rank) has no BCL equivalent at all. At 100,000 elements a rank measures 9,240x the SortedSet answer and a select 33,900x — both linear there — with the churn-plus-query workload 137x it and 1.62x the hand-rolled sorted List<T>. It does not win at pure selection against that hand-roll, where indexing one array is O(1) and unbeatable, and at a thousand elements the hand-roll wins the mixed workload too — this is a large-set type, and every ratio names its baseline.

Immutable succinct index over a sequence of ints that answers what a range fold cannot: the k-th smallest value inside a positional window, and how many values in that window fall in a band — both in O(log σ) over the distinct values, independent of how wide the window is. A segment tree folds a window down to one value and so cannot reach the k-th; a ranked set has no window and no duplicates. Build-once, and it loses to a plain scan on a short window.

Set algebra over already-sorted spans (in Celerity.Primitives): Intersect / Union / Except straight into a caller-owned Span<T>, plus IntersectCount / Overlaps that need no buffer and allocate nothing. The BCL has no set operation over spans, so the alternatives — HashSet<T>.IntersectWith and LINQ Intersect — allocate a table and hash every element instead of exploiting the order the data already has. 4.2× faster at 1M × 1M with zero allocation against 17.9 MB, and 257× on the asymmetric 1k × 10M shape, where it gallops. Sorted by construction, or this is worthless: unsorted input silently returns a wrong answer.

Space-filling curves (in Celerity.Primitives): map a 2-D or 3-D integer coordinate to one ulong whose ordering keeps nearby points nearby, and back. This is what lets a one-dimensional structure answer a spatially local question — sort a point set by its curve index and a plain array becomes a cache-coherent spatial container. BitOperations has no bit-interleave and the BCL has no Hilbert anything, so today it starts with hand-written magic numbers. Morton is the cheap default; Hilbert costs a loop over the bit levels and buys the one property Morton cannot give — consecutive indices are always neighbouring cells, at every scale.

LSD radix sort over primitive keys ((u)int, (u)long, float, double): four or eight counting passes with sequential reads and no comparisons and no data-dependent branches, where Array.Sort is a scalar comparison introsort whose partition steps mispredict on random data. Keys alone, keys with a parallel payload, or an index permutation (argsort) that ranks without moving a wide payload. Stable. Array.Sort is contractually in-place and radix needs O(n) scratch, so the BCL structurally cannot close this; the scratch overloads let a hot loop supply its own buffers and allocate nothing. Below a few hundred elements Array.Sort wins — the crossover is measured, not asserted.

Counting sort over a bounded key range (byte, ushort, or int over a declared [min, max]): one histogram pass and one run-fill, O(n + range), for the shape that enum ordinals, bucket ids and quantized scores take. The keys-only forms never move an element twice and allocate nothing at all for byte keys; the key+payload forms are stable. Loses once range approaches n — that is the documented rule of thumb, not a footnote.

Selection instead of sorting: O(n) introselect for the k smallest (Select / Sort) and an O(n log k) bounded heap for the k largest of a read-only span (TopK). A three-way partition keeps duplicate-heavy input linear and a depth budget bounds the adversarial case. Honest caveat: LINQ’s OrderBy().Take(k) already partial-sorts, so the win there is allocation and boxing, not asymptotics.

Quantiles over an unbounded stream with a relative-error guarantee: the reported value is within α of the true one at every quantile, in memory proportional to the log of the value range rather than to the sample count (in Celerity.Statistics). The BCL ships no quantile type at all — no percentile, no median, nothing past Average — so the alternative is to retain every sample in a List<double>, sort it and index, which is unbounded memory and an O(n log n) sort per query. A relative bound is the one latency work wants: 1% of 10 ms and 1% of 10 s, not a fixed number of milliseconds that is meaningless at one end of the range. Negatives and zero are handled rather than rejected, and two sketches of the same accuracy merge so per-shard sketches combine without re-reading anything — bucket-exactly, unless a shard has already exhausted its bin budget, which no merge can undo and HasCollapsed reports. Read the caveats with the number: adding a value costs a log() and loses to a list append, and if your data is static and you can sort it once, an array index beats the sketch by a wide margin — both are charted rather than left out. What the sketch buys is the query on a stream that keeps moving, and a footprint that does not grow. When the bin budget runs out it collapses the lowest buckets and says so through HasCollapsed, because a guarantee that has quietly stopped holding is worse than no guarantee.

A fixed-size uniform sample of a stream whose length is not known in advance (in Celerity.Statistics), via Li’s Algorithm L: O(k) memory and O(k · log(n / k)) random draws over the whole stream rather than one per item. The BCL has no sampler; OrderBy(random).Take(k) sorts the entire sequence to keep k of it and cannot run on a stream at all. The baseline measured here is the better hand-roll — materialize into a List<T> and partial Fisher-Yates — which is a good algorithm whose only problem is that it has to hold the stream. Seeded, so the same seed and stream give the same sample on a given runtime and platform — deliberately not promised byte-identical across them the way Celerity.Ring is, because the skip arithmetic goes through Math.Log / Math.Exp, whose last bit .NET does not contractually fix. Deliberately no Merge: a uniform merge needs a hypergeometric draw over the two stream lengths, and replaying one side into the other over-weights the shorter one.

Count, mean, variance, standard deviation, skewness, kurtosis, min and max in a single pass (in Celerity.Statistics), using Welford’s recurrence extended to the fourth moment. System.Linq has Average and nothing else, so the two things a caller writes are a two-pass shape that needs the sequence twice — which a stream will not give you — or the one-pass sum / sumOfSquares shortcut, which is faster than this type and catastrophically wrong when the mean is large relative to the spread: at 1e10 ± 6 the two terms agree to fifteen digits and the answer is assembled out of rounding error, negative variances included. This is a mutable struct on purpose — default is a valid empty accumulator and an array of per-bucket statistics costs no allocations — and it merges by Chan’s parallel formulas, so a sharded pass gives the same moments as a sequential one. The win is correctness at roughly the cost of the thing that is wrong, not speed.

Wang, Murmur3, FNV-1a, Guid, default fallback.

Consistent-hash & rendezvous (HRW) rings for sharding and request routing. Byte-identical node assignment across OS, architecture, and runtime (x64, arm64, Blazor WASM), so every node in a cluster agrees on the mapping. Fills a gap the BCL has no type for. Separate NuGet package.

Streaming abuse / heavy-hitter detection: top offenders, per-key rate, and fan-out cardinality of a request stream in a fixed footprint regardless of key cardinality, so it survives the attacker key-rotation that OOMs a Dictionary<,> counter. Separate NuGet package.

Mergeable approximate COUNT(DISTINCT) and windowed dedup over unbounded streams: exact for small inputs, promoting to a fixed ~16 KB estimator, with deterministic cross-shard merge identical on every runtime. Separate NuGet package.