Tuning tables

["Jasper Klein" <jasper@...>]

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

Attachment: table_reserve.patch
Description: Binary data