Offset and descending sparse integer keys skip the compact numeric slots (#31 follow-up)
Maintainers usually reply within 1 day
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 35/100
Research direction
The admission check is in the sparse branch of lr_rawset in src/runtime.eigs, with the k <= 2*(live+1) test as the gate for compact numeric slots. Read that branch alongside tools/measure/table-memory.lua to see how the existing sparse row is produced, then add offset and descending modes to that script. Done means offset and descending sparse integer keys at density of at least 1/2 land within 1.5x of the ascending sparse row's memory per entry.
Written by the indexing model from the issue text.
Description
After the #31 compact-table work (fix-31 round 2, 79f76d8), integer keys only use the compact numeric slots when k <= 2*(live integer hash keys + 1) (src/runtime.eigs, sparse branch of lr_rawset). That favours keys that are dense starting from low indices, like the benchmark's root[2*i]. Other sparse integer shapes still take the identity map: an encoded string key per entry, plus key/value slots.
- Offset sparse keys (
t[1003], t[1005], ...): the key stays about 1000 above 2×live, so admission never succeeds. - Descending sparse keys (
for k = 2000000, 2, -2 do t[k] = 1 end, 1M live): 1,096,380 KB on EigenLua vs 39,080 KB on PUC Lua 5.4 (main: 1,388,768 KB).
Found by the blind critic on fix-31 round 2.
Done when
Sparse integer keys at density >= 1/2 use roughly the same memory per entry whatever their starting offset or insertion order. tools/measure/table-memory.lua gains offset and descending sparse modes, and they come within 1.5x of the ascending sparse row.
- Dominant language
- Lua
- Stars
- 0
- Forks
- 0
- Avg merge
- 54m
- Merged PRs (30d)
- 19
Getting set up
Starts the project's dev container in your browser, under your own GitHub account.
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from InauguralSystems/EigenLua
-
documentation good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
InauguralSystems/EigenLua#60 ·
Maintainers usually reply within 1 day
-
Difficulty 3/5 1-2 days Newbie friendliness 35/100
InauguralSystems/EigenLua#63 ·
Maintainers usually reply within 1 day
-
front-end good first issue
Difficulty 3/5 Half a day Newbie friendliness 70/100
InauguralSystems/EigenLua#62 ·
Maintainers usually reply within 1 day
-
front-end good first issue
Difficulty 3/5 Half a day Newbie friendliness 66/100
InauguralSystems/EigenLua#61 ·
Maintainers usually reply within 1 day
-
1/0 and 0/0 abort the program with 'EigenScript value error: division by zero' (ref: inf / nan)Openbug eigenscript-gap
Difficulty 3/5 1-2 days Newbie friendliness 42/100
InauguralSystems/EigenLua#50 ·
Maintainers usually reply within 1 day
All issues in InauguralSystems/EigenLua
Similar issues
-
documentation enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
EmirErtorer/ink-away.koplugin#38 · 1 comment ·
-
Feature Request
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
Questie/QuestieTrace#92 ·
Maintainers usually reply within 1 day
-
bug
Difficulty 1/5 Under an hour Newbie friendliness 85/100
Maintainers usually reply within 1 day
-
WitchOpen
Difficulty 1/5 Under an hour Newbie friendliness 88/100
LuaLS/lua-language-server#3471 ·
-
RadlNavi Routing V2.3.5 Rechts/Links Kombinationen halb unterdrücktPossibly taken @thomas-munichways claimed this 1 day ago. Open
Difficulty 2/5 1-3 hours Newbie friendliness 62/100