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 0}})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).
(drop-index-space! space)Forget the derived index state held under space — the dense twin of
vaelii.impl.memory/drop-index-space!, core/close!'s release of the RAM index a
disk-backed KB derived. A no-op for a space nothing holds; returns true when an entry
was dropped.
Forget the derived index state held under `space` — the dense twin of `vaelii.impl.memory/drop-index-space!`, `core/close!`'s release of the RAM index a disk-backed KB derived. A no-op for a `space` nothing holds; returns true when an entry was dropped.
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 |