Lua source code series:
Content from Chapter 4.2.2 to the end of Chapter 4 of “Lua Source Code Appreciation” still mainly covers source code related to Lua tables.
Contents
Hashing of Numeric Types
Regarding hashing of numeric types, several version iteration improvements were mentioned.
Lua 5.1 directly reads and adds data from corresponding memory blocks for hashing. This algorithm could produce a bug on 64-bit systems where the same number produces different hash results:
On 64-bit systems, long double is considered 16 bytes instead of 12 bytes on 32-bit systems to maintain alignment. But the value itself is still 12 bytes, with the other 4 bytes filled with random garbage data
Lua 5.2 improved this algorithm with two user-configurable algorithms. One uses a union to calculate number hashes (conditions: number type is double, target machine uses IEEE574 standard floating point). The other has lower performance but uses a more general and standard hash algorithm.
Table Iteration (next)
Table iteration is frequently used in Lua. After carefully reading the source code, I understood the principle behind checking whether a table structure is empty that I had seen online.
First, let me explain Lua’s definition of table length: if t[n] is non-empty and t[n + 1] is empty, then n is the table’s length. Additionally, when the array part of the table is full or empty, the hash table part’s length is also calculated.
Another point I hadn’t noticed before: in other languages, any operations on a table are prohibited during iteration. But in Lua, during table iteration, you can modify or even delete existing values (assign to nil) without affecting the iteration result.
When deleting elements from a table being iterated, if GC happens to occur, key-value pairs set to nil will be marked as dead, and the findindex function handles this situation.
If you create new elements in a table being iterated, the new key might not be traversed, or if the creation triggers a rehash action, it may cause duplicate traversal issues.
Lua’s next(table [,index]) function accepts two parameters. I always use it like this to check if a table is empty:
local tal_empty = next(t)
Metamethod Optimization
Lua’s implementation of complex data structures heavily relies on attaching a metatable to a table
Therefore, operations on metatables are hotspots in Lua, and the necessity of optimizing hotspots goes without saying.
From the moment Lua creates a table, these metamethods are directly attached to the Lua table, and using the flags bits in the Table structure to mark metamethods can greatly improve metamethod query speed. In actual queries, you can directly query the corresponding metamethod using the corresponding bits.
When Lua creates metatables, I noticed that Lua uses luaS_fix to mark data structures in the state machine. When marked as FIXEDBIT, the structure won’t be garbage collected.
https://github.com/xiaocang/lua-5.2.2_with_comments/releases/tag/lua_table_metatable_04
