Tuning tables

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Tuning tables

Jasper Klein
Hello everyone,

In C++ it is possible for some container types, like std::vector or  
std::unordered_set, to reserve a number of elements.
For containers that use hashes you can also set the 'load factor' or force  
a rehash.
Lua doesn't have these functions for a table.

The array part of a table is already pretty efficient from what I've seen  
in the sources.
However there is no way to control or tune the hash part of the table.
If the number of hash elements is known then it would be nice to let the  
table reserve the right number buckets and avoid rehashing
Also forcing a rehash can optimize a table when integer keys can be moved  
to the array part because some integer index holes were filled.

Like tuning the garbage collector I think tuning a table should be made  
possible.
The work versions of Lua 5.4 shows a focus on performance improvements and  
this may fit well.

Something like these functions I had in mind:
table.reserve( t, narray, nhash ) -- Reserves space for at least 'narray'  
elements in the array part and 'nhash' elements for the hash part of the  
table. May rehash if bucket count was increased.
table.rehash( t, [nhash] ) -- Rehashes the table and optional reserve  
'nhash' elements for the hash part of the table.

But in the end the Lua authors should make the right decision how the  
table tuning API is exposed (if they will ever add it).

I have hacked the table.reserve variant in Lua 5.3. The patch is attached.
Benchmarks showed no improvement for the array part. For the hash part  
there was about 45% speedup when inserting 26500 unique items.

Who else likes this idea and have applications that could benefit?

-- Jasper

table_reserve.patch (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Tuning tables

Pierre Chapuis
On Sat, Dec 15, 2018, at 14:05, Jasper Klein wrote:

> Something like these functions I had in mind:
> table.reserve( t, narray, nhash ) -- Reserves space for at least 'narray'  
> elements in the array part and 'nhash' elements for the hash part of the  
> table. May rehash if bucket count was increased.
> table.rehash( t, [nhash] ) -- Rehashes the table and optional reserve  
> 'nhash' elements for the hash part of the table.

This does not do everything you want, but some libraries just expose
`lua_createtable`.  Are there practical use cases where this is not
enough, i.e. where you need to reserve space in an existing table
as opposed to during table creation?

--
Pierre Chapuis

Reply | Threaded
Open this post in threaded view
|

Re: Tuning tables

Jasper Klein
Op Sat, 15 Dec 2018 19:04:14 +0100 schreef Pierre Chapuis:

...

>
> This does not do everything you want, but some libraries just expose
> `lua_createtable`.  Are there practical use cases where this is not
> enough, i.e. where you need to reserve space in an existing table
> as opposed to during table creation?
>

You are right that reserving space is mostly done at creation of a table  
and therefore exposing lua_createtable can do the job.
However I think that another table constructor function is not desirable.

My first choice would be the table.rehash variant because in my  
experiments only reserving the hash part seemed to be relevant.
This also gives us the option to optimize a table after it has been  
populated.

Maybe there are better options for tuning a table than what I proposed.

-- Jasper