Skip to content

Sprout v0.0.30 — maps get a hash index (O(n^2) -> O(n))

Choose a tag to compare

@fizzexual fizzexual released this 12 Jun 21:10
· 13 commits to main since this release

Maps are now O(1) — the first benchmark-driven optimization.

The new benchmark suite (added this cycle) flagged maps as O(n²): every m[key] walked the keys, so building a large map got quadratically slow. Fixed.

SMap now keeps a hash index beside its ordered keys[]/vals[] arrays, so lookups are O(1) average — with identical semantics:

  • insertion-order iteration preserved (for each, keys(), values(), JSON, copy)
  • remove-then-re-add still puts the key at the back
  • only lookups got faster
map_insert 20k:   ~780 ms  ->  ~57 ms    (14×)
map_insert 100k:  ~18 s    ->  ~110 ms   (now linear)

This is polish, not expansion — no new syntax, no behavior change, just a faster core data structure where the data said it mattered.

Part of a maturation push toward v0.1

  • A small benchmark suite (benchmarks/) with a documented baseline — so optimizations are driven by data and regressions get caught.
  • A garbage-collector design (docs/gc-design.md) — the plan to solve the memory model safely (conservative mark-sweep; correctness over speed).
  • An AddressSanitizer CI job — proves the interpreter is memory-clean today, and is the safety net the GC will be built against.

Reviewed by an adversarial pass (which caught one latent invariant gap, now fixed); the Linux ASan job covers memory safety. CI green on Linux, macOS, Windows. Windows installer attached.