gopher-lua icon indicating copy to clipboard operation
gopher-lua copied to clipboard

Add ltable to follow Lua 5.1 C reference table implementation

Open chyh1990 opened this issue 5 years ago • 3 comments

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:

  1. exact GetN() and MaxN() semantics
  2. 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
  1. auto shrink/rehash array/hash part on delete in some cases
  2. 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)

chyh1990 avatar May 25 '20 06:05 chyh1990

Coverage Status

Coverage increased (+0.1%) to 88.251% when pulling b7e665aa6105ddf9b5e20249764d1a49b81d7c7a on chyh1990:add_ltable into 6ff375d91eabb95a1fb05873aef638c2583f3704 on yuin:master.

coveralls avatar May 25 '20 06:05 coveralls

@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.

chyh1990 avatar Jun 04 '20 05:06 chyh1990

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

epikur-io avatar Aug 23 '20 21:08 epikur-io