lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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