Skip to content

v0.16.0

Choose a tag to compare

View all tags
@github-actions github-actions released this 26 Oct 02:08
· 29 commits to main since this release
v0.16.0
This tag was signed with the committer’s verified signature.
orieg Nicolas Brousse
GPG key ID: 1E928D96DF0CE650
Verified
Learn about vigilant mode.
26ef7ac
This commit was created on GitHub.com and signed with GitHub’s verified signature.
GPG key ID: B5690EEEBB952194
Verified
Learn about vigilant mode.

Breaking

The packed-suffix cargo feature is retired (#1599). Naming it now fails the build with a compile_error!, so remove it from your feature list. In every build, string-map suffix leaves are now allocated from the map's own node allocator. The diagnostic ablation-unpacked-suffix feature restores the old global allocation.

Python 3.8 and 3.9 are no longer supported (#1584).

  • Wheels are cp310-abi3 (they were cp38-abi3), and requires-python = ">=3.10", so pip on 3.8 or 3.9 keeps resolving expanse-trie 0.15.x.
  • Reason: GHSA-6w46-j5rx-g56g (pytest < 9.0.3) is fixed only in pytest 9.0.3, which needs Python 3.10.

Changed (string maps)

A memory reading that no longer stops writers (#1599). On 64-bit builds, SyncExpanseStrMap::mem_used, the ordered-bytes map's delegate and expanse_sync_strmap_mem_used in C read the allocator's counters without excluding writers.

  • Accuracy: the value is exact once writes finish, and can differ by the bytes of the operations in flight while writers run. It is not an upper bound.
  • mem_held still excludes writers.
  • Stall removed: with 4 writers at 2·10⁷ keys and a reader polling once per second, the largest insert went from 0.5–2 s to about 0.15 ms (docs/benchmarks/concurrency/METHODOLOGY.md §47.10).

What mem_used counts changed on every ExpanseStrMap, plain or shared.

  • Node shells and suffix leaves are now allocator blocks, counted at their allocated sizes.
  • mem_held on prefix-heavy keys rises, because allocator overhead is now counted.
  • Uuid-shaped keys use 17–20% less memory, allocator headers included (§47.2).
  • Budgets set from earlier readings should be re-derived.

Cost (METHODOLOGY §47.10–§47.13):

  • Shared string inserts lose about 5% throughput at 1 writer and 3–4% at 8.
  • Instruction counts rise by up to +4.66% on shared short-key inserts.
  • Plain strmap_churn is +1.15% on CI, a cost accepted after one remedy failed its bound (#1604).

Fixed

  • stats() on a string map filled by concurrent writers (#1605). It now sums to mem_used. Before, it stopped at the first branch whose count those writers had left stale, and reported a fraction of the map.
  • A single insert stalling for most of 30 s (#1606). This happened on a SyncExpanseStrMap held at constant population under short-key churn. Every removal that took the serialised path recounted the whole sub-map it removed from, with writers held. It now counts only as far as its decision needs, ROOT_LEAF_CAP + 1 keys. On the reference host the cell's largest insert reads BCa 95% [96,050, 422,553] ns (METHODOLOGY §48.4).

Known limitations

  • Serialised removals at large N. Under short-key churn at 2·10⁷ keys, a large share of removals still take the serialised path, which limits multi-writer throughput there. The cause is not yet measured (#1610).
  • Outdated string-map figures. The string-map memory and throughput figures in README.md and the hot_comparison and masstree_comparison READMEs predate this release and are marked pending re-measurement (#1611).

Compatibility

  • Public Rust API: unchanged (.github/public-api/ diff v0.15.0..main is empty).
  • include/Judy.h: unchanged.
  • include/expanse.h: comments only. They state the mem_used and mem_held semantics above for the shared string, bytes and ordered-bytes maps.
  • Binary image format: unchanged (version 2).

Dependencies

  • webpki-root-certs 1.0.10 (RUSTSEC-2026-0383, #1590).
  • ctutils 0.4.5 (RUSTSEC-2026-0385, #1600).

What's Changed

Other Changes

  • ci(python): drop Python 3.8 support, floor moves to 3.10 by @orieg in #1584
  • bench(strmap): Callgrind arm for SyncExpanseStrMap::mem_used, the locked walk (Refs #1586) by @orieg in #1587
  • chore(deps): webpki-root-certs 1.0.10 for RUSTSEC-2026-0383 by @orieg in #1590
  • bench(strmap): stall of a periodic SyncExpanseStrMap::mem_used reading, METHODOLOGY §44 (Refs #1586) by @orieg in #1589
  • fix(bench): distinct per-thread key streams in reclaim_stall, withhold the multi-writer figures by @orieg in #1591
  • fix(bench): host guard excludes samples inside driver-recorded pauses (strmap_poll_stall, Refs #1586) by @orieg in #1592
  • docs(bench): record the second discarded §44 run and its causes (Refs #1586) by @orieg in #1593
  • eval(strmap): §44 outcome, S1 PASS and M1 MATERIAL (Refs #1586) by @orieg in #1594
  • docs(strmap): state the writer stall of mem_used and mem_held, and how to budget without it (Refs #1586) by @orieg in #1595
  • refactor(strmap): plain/shared dispatch moves to the call sites (Refs #1586) by @orieg in #1597
  • eval(strmap): pre-register design B, METHODOLOGY §47 (Refs #1586) by @orieg in #1598
  • chore(deps): ctutils 0.4.5 for RUSTSEC-2026-0385 by @orieg in #1600
  • fix(bench): writer_scaling provenance labels a base-ref build outside the repository (Refs #1586) by @orieg in #1601
  • feat(strmap): design B, shells and suffixes through NodeAlloc and a lock-free mem_used (Refs #1586) by @orieg in #1599
  • fix(strmap): stats() walks sub-maps whose branch counts optimistic writers left stale (Refs #1603) by @orieg in #1605
  • fix(strmap): count a dirty sub-map only to the root-leaf cap before an exclusive removal (Refs #1602) by @orieg in #1606
  • eval(strmap): §48.4, G48-stall passes on the reference host (Refs #1602) by @orieg in #1607
  • ci(miri): run the C ABI Miri step on Tier-1 shard 2 for headroom on shard 3 by @orieg in #1609
  • docs: cite the re-measurement tracking issue beside each design-B pending marker (Refs #1611) by @orieg in #1614
  • chore(release): 0.16.0 by @orieg in #1615

Full Changelog: v0.15.0...v0.16.0

Contributors

orieg
Assets 38
Loading