Lua Source Code Reading (Part 3)

Lua source code series:

• Lua Source Code Reading Plan
• Lua Source Code Reading (Part 1)
• Lua Source Code Reading (Part 2)
• Lua Source Code Reading (Part 3)
• Lua Source Code Reading (Part 4)
• Lua Source Code Reading (Part 5)
• Lua Source Code Reading (Part 6)

Content from Chapter 4 to 4.2.1 of “Lua Source Code Appreciation” mainly covers source code related to Lua tables.

Contents

Lua Table

A Lua table structure consists of at most three contiguous memory blocks: a Table structure, an array storing consecutive integer indices, and a hash table with size as a power of 2. The size of each part is reallocated by the computesize function when calling the rehash function, ensuring utilization is above 50%. The hash table uses closed hashing for collision resolution. When a collision occurs, the two colliding keys are linked together with a singly linked list.

Hash Algorithm Details

Hash

During table queries, lazy hash computation for long strings is also encountered. Yun Feng explains the reason for this optimization in his book:

In most applications, long strings are objects for text processing rather than comparison operations, and internal uniquification would bring additional overhead

However, string optimization was only added after Lua 5.2.0. Whether this is also present in the LuaJIT that comes with OpenResty is still a question mark.

https://github.com/xiaocang/lua-5.2.2_with_comments/releases/tag/lua_table_04