Re: 5.4 with arrays patch (work in progress)

[Petri Häkkinen <petrih3@...>]

> On 18 Mar 2018, at 18.14, Petri Häkkinen <petrih3@gmail.com> wrote:
> 
> 
>> On 18 Mar 2018, at 17.46, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
>> 
>>> Well, I took a stab at it myself for some Sunday fun. It’s still very much work in progress, but the initial results seem promising.
>>> 
>>> Here are some benchmarking results for a large number of table reads/writes vs. array reads/writes.
>>> 
>>> [...]
>> 
>> Among other problems, your implementation slows down table access,
>> because every access first has to check whether the value is an array. A
>> fairer comparison would be of your implementation with tables against
>> tables in an unmodified Lua source. (Another caveat is that you are
>> testing accesses to constant indices, which is not the usual way arrays
>> are used.)
>> 
>> -- Roberto
>> 
> 
> Ok, thanks for the feedback! I’ll try to come up with a more realistic benchmark and improve the implementation. To be fair, array vs. table speed difference should be negligible unless the data set is larger and the hash part is larger than in this crude & simple benchmark.
> 
> Petri
> 

Ok, here’s another try. I started from scratch and only added “truearray” and “sizeused” fields to the Table struct. Operator # uses sizeused field in the case of a true array (a table created with table.newarray()), so that it becomes O(1).

Below are the results of some benchmarks. The differences in execution times between unmodified Lua 5.4 and patched Lua 5.4 seem to fall below measurement precision, although I believe the patched version is tiny bit slower because of the added sizeused++ in luaV_finishset(). With arrays, table insertion time (new key) is consistently 3-4% faster (with this data set and benchmark) and when using t[#t+1] the array version (see the results of “Push” below) is of course much faster, because of the O(1) version of ‘#'.

I’m sure there are some cases which will cause the implementation to break down (I’ve probably missed a few places where “sizeused” should be updated) and there’s no way to shrink arrays at this point...

Also, I’m not sure if luaC_barrierback() should be called when updating the array in luaH_newkey()?

It’s unlikely I have much time to work on this during the week, but I could maybe have another pass at this next weekend.

Code here: https://github.com/petrihakkinen/lua-array/tree/subtype

Good night!

Petri

—

Lua 5.4 unmodified:

~/lua5.4$ ./lua ../lua-array/tests/benchmark1.lua 
Insert: 	0.9718
Write:  	0.407359
Read:   	0.397737
Push:   	2.734785
~/lua5.4$ ./lua ../lua-array/tests/benchmark1.lua 
Insert: 	0.972278
Write:  	0.416123
Read:   	0.381854
Push:   	2.738113
~/lua5.4$ ./lua ../lua-array/tests/benchmark1.lua 
Insert: 	0.973581
Write:  	0.414254
Read:   	0.394199
Push:   	2.763055


Lua 5.4 + array patch, using tables:

~/lua-array$ ./lua tests/benchmark1.lua 
Insert: 	0.977163
Write:  	0.415051
Read:   	0.407623
Push:   	2.775749
~/lua-array$ ./lua tests/benchmark1.lua 
Insert: 	0.975
Write:  	0.411272
Read:   	0.392261
Push:   	2.748044
~/lua-array$ ./lua tests/benchmark1.lua 
Insert: 	0.985894
Write:  	0.404667
Read:   	0.381863
Push:   	2.765178


Lua 5.4 + array patch, using arrays:

~/lua-array$ ./lua tests/benchmark1.lua 
Insert: 	0.94087
Write:  	0.421692
Read:   	0.384909
Push:   	1.11765
~/lua-array$ ./lua tests/benchmark1.lua 
Insert: 	0.934092
Write:  	0.413033
Read:   	0.380161
Push:   	1.112937
~/lua-array$ ./lua tests/benchmark1.lua 
Insert: 	0.935013
Write:  	0.4224
Read:   	0.403127
Push:   	1.157352