FSet
the second collection
An immutable, unboxed set on the FArray playbook (a generated Java core, per-kind specialization,
inline dispatch), plus one contrarian bet. Every immutable set on the JVM pays
the persistent-trie tax to make single-element updates cheap. FSet refuses to pay it, and builds an
immutable set the way you actually use one: frozen flat leaves, queried hard, combined
lazily. Everything on this page is a consequence of that one bet. And as everywhere on this site:
every bar is a JMH measurement you can hover, every snippet is extracted from source that compiles.
FSet is a step behind FArray in maturity. FArray is itself a milestone-stage experiment; FSet is younger still — the design is here and the benchmarks are real, but it has had less testing, fewer users, and more edges left to find. Read the numbers as a direction, and expect rougher corners than FArray's.
The trie tax
Persistent sets (Scala's immutable.Set, Clojure's, CHAMP, all of them) are built around one trade:
store the elements in a 32-way trie so that adding one element shares almost the whole structure. It's
a good trade if your workload is single-element churn with old versions retained. But it taxes
everything else: every contains hops pointer-to-pointer down the trie, every primitive is boxed into
a node, every bulk union walks and rebuilds tree structure, and the whole thing runs 4–15× the memory
of the flat data. And the workload most immutable sets actually live is the opposite one: build
once, then query and combine a lot.
So FSet inverts the trade. A materialized set is a frozen flat leaf (a packed sorted primitive
array, a frozen open-addressing hash table, a dense bitmap, or a 16-byte range) with no tree to hop
and nothing boxed. And the persistent operations don't rebuild anything at all: ∪ ∩ ∖ ⊕, + and -
are O(1) lazy nodes that share both operands. No other set on the JVM has a lazy set algebra.
Immutability becomes an asset: a table that will never grow again can be laid
out for pure probe speed, and the algebra comes free.
Same construction as FArray's core: generated, final, fields-and-methods
Java, one class per shape per element kind, all behind opaque type FSet[A] <: AnyRef = SBase (an
opaque type is a compile-time-only alias, erased to bare SBase at runtime): zero
wrapper allocation, primitives never boxed.
A set is more than a HashSet
Mainstream languages ship one thing called "Set": a finite, enumerable hash collection. But that's the
special case, not the concept. Mathematically a set of As is an element of the Boolean algebra
2A: something you can ask membership of, union, intersect, subtract, complement. "All
the Ints above 5" is a perfectly good set; you just can't enumerate it. FSet models the whole algebra,
and recovers the classical enumerable set as the materialized special case.
The type system tracks which kind you're holding, as a small lattice of capabilities built on a
Scala 3 trick. The folklore says opaque types can't subtype each other; it's
false. An opaque type's upper bound doesn't have to be spent on AnyRef: bound it against the
parent opaque type and you get real, externally visible, zero-wrapper subtyping. Every level below
is the same bare SBase at runtime; upcasts are free; an op defined once at the top is inherited by
everything beneath it:
Membership and the algebra live at the top. Traversals and transforms (foreach, filter, map,
flatMap) live on FSetFinite: anything provably finite may enumerate (they materialize internally,
memoized on the node), and since a transform builds a fresh materialized set anyway, demanding an
explicit .materialize first would add a keyword but no information. The cheap observations and value
equality (size, iterator, sameElements) need the frozen leaf itself and sit on
FSetMaterialized. The compiler enforces the split: (a ++ b).size doesn't compile until you
.materialize, and FSet.above(5).size doesn't compile at all. FSetInfinite is the outlier:
an infinite set is a predicate, so it's contravariant like one, kept out of the invariant chain
and bridged in by a Conversion (a compiler-applied implicit conversion). Ranges round it out: FSet.range(0, 1_000_000_000) is a finite,
materializable set that costs 16 bytes.
Finiteness is never computed, only propagated. Whether an arbitrary set is finite is undecidable (Rice's theorem), so FSet never asks. Finiteness is a syntactic property of which combinator built the set, and each operation has a transfer rule:
| operation | result is finite iff | why |
|---|---|---|
| a ∪ b | both finite | infinite if either side is |
| a ∩ b | either finite | infinite ∩ finite is always finite |
| a ∖ b | left finite | removing anything from a finite set stays finite |
| a ⊕ b | both finite | infinite ⊕ infinite is unknown, unlike ∪ |
| ¬a | never (from finite) | complement of a finite set is infinite; of an infinite one, unknown |
| a + x · a − x | same as a | single-element updates preserve the class |
The useful rule is intersection: anything ∩ finite is finite, so filtering an infinite set by a
finite one gives an enumerable result, and the types know it statically. The cases the rules
can't decide (infinite ∩ infinite, a set handed to you as bare FSet) fall to the top type,
narrowable at runtime by .finite: Option[FSetFinite[A]], a conservative structural inspection that
never returns a false Some.
Two more consequences of taking the algebra seriously. Emptiness is the single decision primitive:
a == b is (a ⊕ b).isEmpty, a subsetOf b is (a ∖ b).isEmpty, disjointness is
(a ∩ b).isEmpty, so the comparisons ride the same lazy algebra as everything else. And map is not
a homomorphism (the image of a set doesn't distribute over ∩ or ¬), which is why map
lives on the finite tier while filter, which is just ∩ with a predicate, could in principle stay
symbolic. The capability lattice follows the algebra's own structure, spelled as types.
The crown op: contains
Everything above was designed backwards from one question: how fast can xs.contains(x) possibly be?
The answer is one compiled-once loop per element kind: no recursion on the spine, no allocation.
Negations get a shortcut: SXor and SComplement are not evaluated; they flip a parity bit
that's applied to whatever the leaf answers. On the common leaf-only path flip is provably false and
folds away.
Each arm is a leaf giving its best answer: the bitmap is a single bit-test, the range is two compares,
the frozen hash is a one-hop probe, the small sorted leaf is an early-exit scan that stays in
registers. And the algebra arms are why the lazy nodes are queryable at all: contains distributes
over ∪ ∩ ∖ ⊕ ¬ as a Boolean homomorphism (evaluate membership at a point and the whole algebra
collapses to Boolean logic), so membership in a combined set never materializes anything.
For references there's no primitive trick to lean on, so the frozen leaf borrows the best idea in
modern hash tables: Facebook's F14 / abseil's control bytes. Next to the key array sits a dense
byte[] of 7-bit hash fingerprints; a probe reads one cache-resident byte and rejects almost every
miss before touching a key object, and only a fingerprint match pays .equals:
That's why misses, half of real membership traffic, are where the frozen layout shines: FSet's
miss path is fastest-or-tied in the whole field at every size, mutable tables included. The gap
is elsewhere: probe with a scrambled mix of hits and misses, defeating branch prediction, and the
chained layout of scala.mutable and friends pulls 1.4–2× ahead on String. That loss is structural
and accepted: SWAR group probing, cheaper multiplicative
hashes, higher load factors and ctrl-less small tables were each tried and killed by JMH. It's the
one tax paid for a layout that wins nearly everything else on this page.
Dense Int data wants to be a bitmap
Int sets in the wild are rarely random 32-bit noise; they're dense: IDs, indices, year ranges, enum
ordinals. The leaf builder measures density at construction and, when the value
span is at most 64× the element count, skips hashing entirely: the set becomes SIntBitmap, a bare
long[] where contains is one shift and one mask.
The payoff compounds on bulk operations, because the algebra closes over the representation: bitmap ∪
bitmap is a word-parallel OR, intersection an AND, difference an AND-NOT (64 elements per
instruction, cardinality by popcount), and the merge kernels work region-split, so an intersection
only touches the window where the two bitmaps overlap. That is why a general-purpose
immutable set can stand next to immutable.BitSet (Scala's built-in word-array bitmap set) and RoaringBitmap in their own niche while also
being a set of Strings tomorrow.
One cell goes the other way: at size 16, Scala's BitSet1/BitSet2 keep their entire
population in one or two fields, no array, no indirection, and no array-backed bitmap can match a
single-word update. That loss is measured and accepted.
The algebra is lazy, and materialize is a merge
Because a ++ b is just a node, the natural way to use FSet is to build an algebra and query it.
When you do need the elements, .materialize folds the tree into one leaf, iteratively, spine-first,
never JVM recursion (a loop-built chain of ten thousand + nodes must not be a StackOverflow), and
memoizes the result on the node, so a shared subtree is merged once ever. Even this was measured:
the first cut collected a spine list for every materialize and regressed
small merges; shallow trees like a plain a & b now take a fast path that allocates nothing but the
answer:
To materialize or not: two opposite answers
So when should you actually call .materialize? The benchmarks give a clean answer, and it is
different per element kind, which is itself an argument for a lazy algebra: the
right eagerness depends on the data, not the call site, so the library decides.
For Int, merging is nearly free (a word-parallel OR), so the smart ++ constructor eagerly
merges cheap pairs (two bitmaps, two tiny leaves) on the spot, and a chain of unions collapses
into a single bitmap. There is no lazy-versus-eager distinction left to care about:
For references, merging is the expensive part (every String rehashed into a new table), so FSet
keeps reference unions lazy and lets contains distribute over the tree. Every competitor must pay
the full O(n) rebuild before answering a single query; FSet just answers:
At n queries over the union, the lazy tree also beats FSet's own materialized path: by ~2.7× at 16, ~2× at 1000, ~1.2× at 100k. Deferring the merge wins even when you query as many times as there are elements; materializing a reference union pays off only when you query it far more than that. And when you do, you still come out ahead:
References merge on cached hashes
What makes that materialized-String row fast is that the bulk algebra for reference elements has its
own unboxed column: every materialized Ref leaf carries its elements alongside a parallel int[] of
cached hashes, kept hash-sorted. Union, intersection, difference and xor then become two-pointer
merges over plain int comparisons, cache-sequential and allocation-tight, with .equals paid only
inside a hash-collision run:
Even the build is arranged around the freeze. Constructing a String set dedups through the F14 table and records the hashes as it goes, deferring the hash-sort to a memoized view that only exists if the algebra ever asks for it. The result: building the frozen, immutable set is faster than building any mutable one:
The same two sorted hash columns make value equality fast: two pointers over int compares,
no probing one set with the other's elements. sameElements on String sets is the clearest
structural win in the whole suite:
Even map stays in bitmap-land
Transforms are where set semantics usually force a detour: collect values, sort, dedup, rebuild.
FSet's map on an Int set instead word-scans the source bitmap and ORs each f(e) straight into a
growable bitmap accumulator that re-bases on both ends. Dense in, dense out: no intermediate array, no
sort, dedup for free. If the output turns out sparse, the builder degrades once to the ordinary
path and loses nothing.
flatMap gets the same treatment, split by write kind. Each element's result set is already a
materialized leaf, so for Int the leaves fold together with pairwise word-OR union rounds; for
references each part's raw element column is appended (a bulk System.arraycopy, no iterator, no
boxing) and the deduplicating one-pass build runs once at the end. That choice was
measured: the first cut merged Ref leaves pairwise too, re-allocating at every round, and lost to
immutable.Set; append-once turned it into a win.
Where it lands
The same leaderboard treatment as FArray's: every operation at every size, each structure scored by the geometric mean of its distance from the fastest-in-cell. The bet is visible in the table: the scattered-probe and size-16 cells documented above go to the specialists, and everything structural (build, merge, equality, transforms, the algebra itself) goes to FSet, usually by multiples.
The full record is on the FSet benchmarks page: every chart, every
competitor, with the exact @Benchmark source behind each card.