A live-handle roster: what sentex-ids / justification-ids / premise-ids hand
back, for a store big enough that the shape matters.
The three enumerations answer a java.util.Set of handles, and every store the engine
ships answers a PersistentHashSet<Long> — the memory store because that is what its own
state already is, the disk store by materializing one from the LiveRoster below at the
call. At the scale a server-backed store exists for, that shape is the cost: measured
over contiguous handles, a PersistentHashSet<Long> retains 48–75 bytes per handle
(the hash trie's fill varies with cardinality), so 4.5–7.0 GB at 100M — and
rebuild-tms holds the sentex roster while it walks the premises and the
justifications.
Handles are minted in assertion order (next-id) from one counter across the three
kinds, so a roster is a strided run of longs — holes where records were deleted, and
holes where the other kinds' handles fall. That is the one shape a compressed bitmap is
built for. Over the same handles with a tenth of them punched out, a Roaring64Bitmap
retains 0.13–0.26 bytes per handle, and less than that on an unbroken run, where
the whole roster is a few run containers. It answers contains? in less time than
the hash set, not more (vaelii.impl.protocols, the enumeration contract).
Not an IPersistentSet. conj, disj and clojure.set need one, so a caller wanting
those converts with (set roster) — which is the 4.5 GB, paid at the call site that
asked for it rather than by every store on every enumeration. What the seam promises is
membership, iteration, cardinality and ordering, which is what every caller in the
engine uses.
Immutable once built, so concurrent readers need no coordination — the one property the bitmap has to have here, since a store's readers enumerate while its writer writes.
A store that answers a roster also holds one, and that one is mutated on every put
and every delete. LiveRoster is the same bitmap kept in place for that: the disk
store's per-kind live-handle set, where the PersistentHashSet<Long> it replaces
costs 48–75 bytes a handle — 9.47 GB at 100M records and the second-largest resident
row in the engine (docs/density.md).
It synchronizes nothing, deliberately. A Roaring64Bitmap is mutable and not
thread-safe, so every call here needs a monitor around it — and the monitor is the
caller's, because the caller already has one. The disk store mutates its live set under
the owning kind's lock, in the same acquisition as the file write the set is a claim
about (vaelii.impl.disk.record-store, "two monitors"); an internal lock would be a
second, weaker one that still could not make the pair atomic. So: hold the lock that
covers the field, for reads as well as writes. A tally and a first handle are reads
that a boxed set needs no monitor for and this one does.
A reader that outlives the call gets live-snapshot, an immutable HandleRoster over a
copy: it costs the bitmap's size, not the corpus's, which is why handing one out is
affordable where copying the boxed set was the thing to avoid.
A **live-handle roster**: what `sentex-ids` / `justification-ids` / `premise-ids` hand back, for a store big enough that the shape matters. The three enumerations answer a `java.util.Set` of handles, and every store the engine ships answers a `PersistentHashSet<Long>` — the memory store because that is what its own state already is, the disk store by materializing one from the `LiveRoster` below at the call. At the scale a server-backed store exists for, that shape *is* the cost: measured over contiguous handles, a `PersistentHashSet<Long>` retains **48–75 bytes per handle** (the hash trie's fill varies with cardinality), so **4.5–7.0 GB at 100M** — and `rebuild-tms` holds the sentex roster while it walks the premises and the justifications. Handles are minted in assertion order (`next-id`) from one counter across the three kinds, so a roster is a strided run of longs — holes where records were deleted, and holes where the other kinds' handles fall. That is the one shape a compressed bitmap is built for. Over the same handles with a tenth of them punched out, a `Roaring64Bitmap` retains **0.13–0.26 bytes per handle**, and less than that on an unbroken run, where the whole roster is a few run containers. It answers `contains?` in *less* time than the hash set, not more (`vaelii.impl.protocols`, the enumeration contract). ## What this is not Not an `IPersistentSet`. `conj`, `disj` and `clojure.set` need one, so a caller wanting those converts with `(set roster)` — which is the 4.5 GB, paid at the call site that asked for it rather than by every store on every enumeration. What the seam promises is membership, iteration, cardinality and ordering, which is what every caller in the engine uses. Immutable once built, so concurrent readers need no coordination — the one property the bitmap has to have here, since a store's readers enumerate while its writer writes. ## The live roster beside it A store that *answers* a roster also *holds* one, and that one is mutated on every put and every delete. `LiveRoster` is the same bitmap kept in place for that: the disk store's per-kind live-handle set, where the `PersistentHashSet<Long>` it replaces costs 48–75 bytes a handle — **9.47 GB at 100M records** and the second-largest resident row in the engine (`docs/density.md`). **It synchronizes nothing, deliberately.** A `Roaring64Bitmap` is mutable and not thread-safe, so every call here needs a monitor around it — and the monitor is the caller's, because the caller already has one. The disk store mutates its live set under the owning kind's lock, in the same acquisition as the file write the set is a claim about (`vaelii.impl.disk.record-store`, "two monitors"); an internal lock would be a second, weaker one that still could not make the pair atomic. So: **hold the lock that covers the field, for reads as well as writes.** A tally and a first handle are reads that a boxed set needs no monitor for and this one does. A reader that outlives the call gets `live-snapshot`, an immutable `HandleRoster` over a copy: it costs the *bitmap's* size, not the corpus's, which is why handing one out is affordable where copying the boxed set was the thing to avoid.
(collector)A mutable [add! finish] pair, for a caller with a row loop rather than a reducible —
a SQL store's cursor walk. add! takes one handle; finish returns the immutable
roster and is called once.
A mutable `[add! finish]` pair, for a caller with a row loop rather than a reducible — a SQL store's cursor walk. `add!` takes one handle; `finish` returns the immutable roster and is called once.
(live-add! r id)Add handle id, which must be an integer a long can hold — every caller is putting a
handle the store itself minted, where live-has? and live-remove! take whatever a
caller passed. Returns nil.
Add handle `id`, which must be an integer a `long` can hold — every caller is putting a handle the store itself minted, where `live-has?` and `live-remove!` take whatever a caller passed. Returns nil.
(live-add-all! r ids)Add every handle in ids (anything reducible). Returns nil.
Add every handle in `ids` (anything reducible). Returns nil.
(live-clear! r)Empty the roster in place. Returns nil.
Empty the roster in place. Returns nil.
(live-has? r id)Is id live? Answers false — never throws — for anything that is not a handle this
roster could hold, which is what contains? on the set this replaces answers.
Is `id` live? Answers false — never throws — for anything that is not a handle this roster could hold, which is what `contains?` on the set this replaces answers.
(live-least r)The smallest live handle, or nil when there is none. A boxed set answers first with
whichever handle its hash order puts in front; this answers the lowest. Both satisfy
the question the callers ask — is there one at all (vaelii.impl.protocols,
Tallying) — and a determinate answer is the better one to give them.
The smallest live handle, or nil when there is none. A boxed set answers `first` with whichever handle its hash order puts in front; this answers the lowest. Both satisfy the question the callers ask — *is there one at all* (`vaelii.impl.protocols`, `Tallying`) — and a determinate answer is the better one to give them.
(live-optimize! r)Fold contiguous runs into run containers. Worth calling once after a bulk build in ascending order — an open's idx scan — and not worth calling per write, since the next insert into a container undoes it. Returns nil.
Fold contiguous runs into run containers. Worth calling once after a bulk build in ascending order — an open's idx scan — and not worth calling per write, since the next insert into a container undoes it. Returns nil.
(live-remove! r id)Drop handle id, or do nothing when it is not a handle this roster could hold. A
no-op on a member it does not have, like the disj it replaces. Returns nil.
Drop handle `id`, or do nothing when it is not a handle this roster could hold. A no-op on a member it does not have, like the `disj` it replaces. Returns nil.
(live-remove-all! r ids)Drop every handle in ids. Returns nil.
Drop every handle in `ids`. Returns nil.
(live-snapshot r)An immutable HandleRoster over a copy of r — what a reader that outlives the
caller's monitor gets, and what an iteration that mutates the roster as it walks needs.
Costs the bitmap's size rather than the corpus's.
An immutable `HandleRoster` over a copy of `r` — what a reader that outlives the caller's monitor gets, and what an iteration that mutates the roster as it walks needs. Costs the bitmap's size rather than the corpus's.
(live-tally r)How many handles are live.
How many handles are live.
(roster ids)The handles in ids as a HandleRoster. ids is anything reducible — a seq, a
vector, an array — and need not arrive sorted.
The handles in `ids` as a `HandleRoster`. `ids` is anything reducible — a seq, a vector, an array — and need not arrive sorted.
(roster? x)Is x one of these? For a caller deciding whether (set x) would cost anything.
Is `x` one of these? For a caller deciding whether `(set x)` would cost anything.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |