A dense in-memory KvBackend (vaelii.impl.kv) — the :dense index axis, under either
record store (:memory-dense, :disk-dense).
The index's handle-set families (trie leaves, the context / functor / argument roots, the
rule and exception indexes) are the bulk of its RAM, and a bake-off across candidate
encodings found a packed sorted int[] ~5.6× denser than the
PersistentHashSet<Long> the memory backend stores, with RoaringBitmap winning only the
few large/hot postings. So a handle set here is an IntPostings: an exact sorted int[]
while small, promoted to a RoaringBitmap once it crosses a threshold (dense for large,
O(log) add, fast intersect). The trie's child-label set ([:trie :children …]) holds tokens —
including numbers — not handles, so it stays an ordinary set; counters stay Longs. The
backend dispatches on the key tag.
kv-intersect narrows in that representation rather than in the sets it would make:
RoaringBitmap/and where both sides are hot, a sorted merge where both are cold, and a
probe of the cold side into the bitmap where the tiers differ, and a binary search of the
short run into the long one where neither is a bitmap. Smallest posting first, and one
Clojure set built at the end at the size of the answer. What that buys is not mainly
speed on the big case (hot ∩ hot at 32k: 29.2 → 0.56 ms) but the shape of the common
one: a query pins a rare argument on a hot predicate, and 4 handles against a root of n
went from 4.73 ms at n=32,000 to 0.0015 ms at any n — flat in the extent the argument
roots exist to avoid scanning. lein perf --only intersect-selectivity is the gate on
that, and what cost is left tracks the answer rather than the columns, which is the
boundary contract and not the narrowing.
Off by default (:index :dense); proven set-equal to MemoryKvBackend by
dense_kv_oracle_test. Single-writer: the int structures are mutated in place, and
kv-members / kv-intersect materialize a fresh Clojure set at the boundary so a caller
never holds the mutable structure. Handles fit int through 2³¹ (≫ 100M).
A dense in-memory `KvBackend` (`vaelii.impl.kv`) — the `:dense` index axis, under either record store (`:memory-dense`, `:disk-dense`). The index's handle-set families (trie leaves, the context / functor / argument roots, the rule and exception indexes) are the bulk of its RAM, and a bake-off across candidate encodings found a **packed sorted `int[]`** ~5.6× denser than the `PersistentHashSet<Long>` the memory backend stores, with `RoaringBitmap` winning only the few large/hot postings. So a handle set here is an `IntPostings`: an exact sorted `int[]` while small, promoted to a `RoaringBitmap` once it crosses a threshold (dense for large, O(log) add, fast intersect). The trie's child-*label* set (`[:trie :children …]`) holds tokens — including numbers — not handles, so it stays an ordinary set; counters stay `Long`s. The backend dispatches on the key tag. `kv-intersect` narrows **in that representation** rather than in the sets it would make: `RoaringBitmap/and` where both sides are hot, a sorted merge where both are cold, and a probe of the cold side into the bitmap where the tiers differ, and a binary search of the short run into the long one where neither is a bitmap. Smallest posting first, and one Clojure set built at the end at the size of the answer. What that buys is not mainly speed on the big case (hot ∩ hot at 32k: 29.2 → 0.56 ms) but the *shape* of the common one: a query pins a rare argument on a hot predicate, and 4 handles against a root of n went from 4.73 ms at n=32,000 to 0.0015 ms at any n — flat in the extent the argument roots exist to avoid scanning. `lein perf --only intersect-selectivity` is the gate on that, and what cost is left tracks the answer rather than the columns, which is the boundary contract and not the narrowing. Off by default (`:index :dense`); proven set-equal to `MemoryKvBackend` by `dense_kv_oracle_test`. Single-writer: the int structures are mutated in place, and `kv-members` / `kv-intersect` materialize a fresh Clojure set at the boundary so a caller never holds the mutable structure. Handles fit `int` through 2³¹ (≫ 100M).
(dense-index-store opts)A dense in-memory IndexStore — KvIndexStore over a TieredKvBackend.
A dense in-memory `IndexStore` — `KvIndexStore` over a `TieredKvBackend`.
(dense-kv-backend {:keys [space] :or {space 1}})A dense in-memory KvBackend. Only :space matters (selects the shared state atom).
A dense in-memory `KvBackend`. Only `:space` matters (selects the shared state atom).
(int-postings)(intersect-postings postings)The intersection of postings — each an IntPostings or an ascending int[] — as a
Clojure set of Longs.
Smallest first, which is not the tie-break it looks like: the accumulator can only shrink, so seeding it with the narrowest column is what keeps every later step a probe of a few entries rather than a scan of a hot one. An accumulator that empties stops the fold, since nothing after it can put a handle back.
Public because vaelii.impl.dense-roots holds the same postings under its own keys and
must narrow them the same way.
The intersection of `postings` — each an `IntPostings` or an ascending `int[]` — as a Clojure set of Longs. **Smallest first**, which is not the tie-break it looks like: the accumulator can only shrink, so seeding it with the narrowest column is what keeps every later step a probe of a few entries rather than a scan of a hot one. An accumulator that empties stops the fold, since nothing after it can put a handle back. Public because `vaelii.impl.dense-roots` holds the same postings under its own keys and must narrow them the same way.
(padd! p h)Add handle h (in place); return p.
Add handle h (in place); return p.
(pand p acc)acc — a sorted int[] or a RoaringBitmap — narrowed to the handles this posting
also holds, as a fresh accumulator. Dispatches on both representations: two hot
postings meet in RoaringBitmap/and, two cold ones in a sorted merge, and a mixed
pair probes the cold side's entries into the bitmap. So neither side is materialized,
and neither side is mutated — RoaringBitmap.and the instance method would mutate
its receiver, and a query that quietly shrank a posting is a corrupt index the oracle
finds late rather than never.
`acc` — a sorted `int[]` or a `RoaringBitmap` — narrowed to the handles this posting also holds, as a **fresh** accumulator. Dispatches on both representations: two hot postings meet in `RoaringBitmap/and`, two cold ones in a sorted merge, and a mixed pair probes the cold side's entries into the bitmap. So neither side is materialized, and neither side is mutated — `RoaringBitmap.and` the *instance* method would mutate its receiver, and a query that quietly shrank a posting is a corrupt index the oracle finds late rather than never.
(pcard p)Cardinality.
Cardinality.
(pcontains? p h)Is handle h present? A binary search on the int[], or the bitmap's own test —
the O(log n) / O(1) probe that answers membership without building the set
pmembers builds, which is what an index gate calling it per firing needs.
Is handle h present? A binary search on the `int[]`, or the bitmap's own test — the O(log n) / O(1) probe that answers membership without building the set `pmembers` builds, which is what an index gate calling it per firing needs.
(pints p)A fresh sorted int[] of the handles — the boxing-free read, for a caller that
iterates rather than set-tests. Fresh (never the live array) because callers walk
it while mutating the posting, which is exactly what vaelii.impl.dense-jtms does
when it pushes a node's justifications onto a worklist.
A fresh sorted `int[]` of the handles — the boxing-free read, for a caller that iterates rather than set-tests. Fresh (never the live array) because callers walk it while mutating the posting, which is exactly what `vaelii.impl.dense-jtms` does when it pushes a node's justifications onto a worklist.
(pmembers p)A fresh Clojure set of the handles (as Longs).
A fresh Clojure set of the handles (as Longs).
(prem! p h)Remove handle h (in place); return p.
Remove handle h (in place); return p.
(pseed p)This posting as an intersection accumulator — its own int[] or its own
RoaringBitmap, handed back rather than copied. Safe because pand allocates its
result on every arm, so nothing downstream can write through it.
This posting as an intersection accumulator — its own `int[]` or its own `RoaringBitmap`, handed back rather than copied. Safe because `pand` allocates its result on every arm, so nothing downstream can write through it.
(postings-set p)A posting — an IntPostings or an ascending int[] — as a fresh Clojure set of Longs,
for the mixed fold a caller falls back to when one of the keys is not a handle family.
A posting — an `IntPostings` or an ascending `int[]` — as a fresh Clojure set of Longs, for the mixed fold a caller falls back to when one of the keys is not a handle family.
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 |