Add ltable to follow Lua 5.1 C reference table implementation
Improve table implementation, use the original table data structure in Lua reference implementation (it cannot be built exactly with go slice and map), and fix the following problem:
- exact GetN() and MaxN() semantics
- fix excessively large memory occupation for sparse integer keys, e.g.
table.insert(tab, SOME_LARGE_NUMBER)(current impl might cause the potential of OOM)
local t = {1,2,3,4,5}
table.insert(t, 10000000, true) -- current implementation uses ~800MB, right implementation uses less than 1KB
- auto shrink/rehash array/hash part on delete in some cases
- remove some magic numbers, e.g. MaxArrayIndex
Performance, for some basic use cases, this impl is about 10% faster than the original implementation (and use smaller memory for small table)
Coverage increased (+0.1%) to 88.251% when pulling b7e665aa6105ddf9b5e20249764d1a49b81d7c7a on chyh1990:add_ltable into 6ff375d91eabb95a1fb05873aef638c2583f3704 on yuin:master.
@yuin what do you think about this new implementation? it is impossible to support integer-key (sparse) map in current implementation, and the new one solves other table related issues.
I like this code / implementation. The auxsort function is a bit convoluted but everything is obvious if you read the comments. Would be great to see this getting merged.
I also ran the benchmark for master and this branch:
Master:
goos: linux
goarch: amd64
pkg: github.com/yuin/gopher-lua
BenchmarkCallFrameStackPushPopAutoGrow-4 229708 4955 ns/op
BenchmarkCallFrameStackPushPopFixed-4 358860 2936 ns/op
BenchmarkCallFrameStackPushPopShallowAutoGrow-4 10660772 109 ns/op
BenchmarkCallFrameStackPushPopShallowFixed-4 12964251 92.1 ns/op
BenchmarkCallFrameStackPushPopFixedNoInterface-4 462762 2341 ns/op
BenchmarkCallFrameStackUnwindAutoGrow-4 289152 3664 ns/op
BenchmarkCallFrameStackUnwindFixed-4 479227 2218 ns/op
BenchmarkCallFrameStackUnwindFixedNoInterface-4 ^[[D 577413 1819 ns/op
BenchmarkRegistryPushPopAutoGrow-4 5174 220594 ns/op
BenchmarkRegistryPushPopFixed-4 5300 217636 ns/op
BenchmarkRegistrySetTop-4 95607 12146 ns/op
PASS
ok github.com/yuin/gopher-lua 22.752s
Branch add_ltable:
goos: linux
goarch: amd64
pkg: github.com/yuin/gopher-lua
BenchmarkLTableNew-4 711598 1618 ns/op
BenchmarkLTableMap-4 1247182 1014 ns/op
BenchmarkLTableHashLua-4 50818975 22.2 ns/op
BenchmarkCallFrameStackPushPopAutoGrow-4 214328 4987 ns/op
BenchmarkCallFrameStackPushPopFixed-4 376160 2861 ns/op
BenchmarkCallFrameStackPushPopShallowAutoGrow-4 9264632 121 ns/op
BenchmarkCallFrameStackPushPopShallowFixed-4 12877148 88.4 ns/op
BenchmarkCallFrameStackPushPopFixedNoInterface-4 452493 2449 ns/op
BenchmarkCallFrameStackUnwindAutoGrow-4 275089 3919 ns/op
BenchmarkCallFrameStackUnwindFixed-4 472480 2222 ns/op
BenchmarkCallFrameStackUnwindFixedNoInterface-4 595113 1867 ns/op
BenchmarkRegistryPushPopAutoGrow-4 5593 199547 ns/op
BenchmarkRegistryPushPopFixed-4 5970 204827 ns/op
BenchmarkRegistrySetTop-4 122106 9510 ns/op
PASS
ok github.com/yuin/gopher-lua 27.244s