Skip to content

v0.0.13: O(1) table hash insertion

Choose a tag to compare

@ianm199 ianm199 released this 29 May 14:49
· 170 commits to main since this release

Fixes the O(n²) table hash-part insertion reported in #38 (the part that's slow even with GC stopped).

get_free_pos used to scan the whole node vector for a chain predecessor on every probe, so each hash insert was O(n) and building a table was O(n²). A free node is now found in O(1), matching upstream Lua's getfreepos. Inserting 100k distinct string keys goes from ~14s to ~0.1s.

Validated against the full official Lua 5.4 suite (33/33) and differential stresses against reference C Lua 5.4.7.

Still open from #38/#37: GC throughput under churn, and the ~1M-entry table cap. No breaking changes.