33 Secrets to a 10x Performance Boost- You Must Use the ’table’ Properly #

Hello, I’m Wen Ming.

In OpenResty, besides strings, tables are also a potential performance bottleneck. In previous chapters, we introduced various table-related functions, but we did not specifically mention their impact on performance. Today, I will discuss the performance implications of working with tables.

Unlike strings, developers are less familiar with optimizing table performance, mainly due to two reasons:

• First, OpenResty uses its own branch of LuaJIT, which is different from the standard LuaJIT or Lua. Most developers are not aware of the differences and tend to use the standard Lua table library to write OpenResty code.
• Second, the documentation related to table operations in both standard LuaJIT and OpenResty’s own LuaJIT branch is deeply hidden, making it difficult for developers to find. Moreover, the documentation lacks example code, requiring developers to search for examples in open-source projects themselves.

This creates a relatively high barrier to understanding, resulting in a polarizing effect. Seasoned OpenResty developers can write highly performant code, while beginners may doubt whether OpenResty’s high performance is just a hype. Of course, once you finish studying the content of this lesson, you will easily break through this barrier and realize that achieving a tenfold performance improvement is not a dream.

Before delving into the details of table optimization, I want to emphasize one point: there is a simple principle for optimizing table-related operations:

Reusing tables whenever possible and avoiding unnecessary table creation.

Remember this point. Now, let’s discuss the optimization techniques for table creation, element insertion, clearing, and looping.

Pre-generating arrays #

The first step is naturally to create an array. In Lua, creating an array is very simple:

local t = {}

The above line of code creates an empty array. Of course, you can also initialize the array when creating it:

local color = {first = "red", "blue", third = "green", "yellow"}

However, the second form causes significant performance loss because every time an array element is added or removed, it involves array space allocation, resizing, and rehashing.

So how can we optimize this? One common optimization strategy is trading space for time. Since the performance bottleneck here is dynamic array space allocation, the optimization direction can be to pre-generate an array of a specified size. Although this may waste some memory space, multiple space allocations, resizings, rehashings, and other actions can be combined into a single operation, improving efficiency significantly.

In fact, the table.new(narray, nhash) function in LuaJIT was added for this purpose.

This function pre-allocates the specified array and hash space instead of dynamically growing when elements are inserted. This is also the meaning of its two parameters, narray and nhash.

Let’s look at a specific usage through a simple example. Since this function is an extension of LuaJIT, we need to require it first before using it:

local new_tab = require "table.new"
local t = new_tab(100, 0)
for i = 1, 100 do
  t[i] = i
end

In addition, because older versions of OpenResty do not fully bind LuaJIT and support standard Lua, some old code makes compatibility adjustments. If the table.new function is not found, it will simulate an empty function to ensure consistency for the caller:

local ok, new_tab = pcall(require, "table.new")
if not ok then
  new_tab = function (narr, nrec) return {} end
end

Calculating table indices yourself #

Once you have a table object, the next step is to add elements to it. The most direct method is to use the table.insert function to insert elements:

local new_tab = require "table.new"
local t = new_tab(100, 0)
for i = 1, 100 do
    table.insert(t, i)
end

Alternatively, you can first get the length of the current array and add elements using indices:

local new_tab = require "table.new"
local t = new_tab(100, 0)
for i = 1, 100 do
    t[#t + 1] = i
end

However, both of these methods require calculating the length of the array before adding elements. Obviously, this operation has a time complexity of O(n). Taking the example of the code above, the for loop calculates the length of the array 100 times, which naturally affects performance, especially as the array size increases.

So how can we solve this problem? Let’s take a look at how the official library lua-resty-redis handles it:

local function _gen_req(args)
    local nargs = #args

    local req = new_tab(nargs * 5 + 1, 0)
    req[1] = "*" .. nargs .. "\r\n"
    local nbits = 2

    for i = 1, nargs do
        local arg = args[i]
        req[nbits] = "$"
        req[nbits + 1] = #arg
        req[nbits + 2] = "\r\n"
        req[nbits + 3] = arg
        req[nbits + 4] = "\r\n"
        nbits = nbits + 5
    end
    return req
end

This function pre-generates the req array, its size determined by the function’s input parameters, which helps minimize wasted space.

Then, it uses the nbits variable to maintain the indices of req, abandoning the built-in table.insert function and the # operator for calculating the length. As you can see, in the for loop, calculations such as nbits + 1 are used to directly insert elements using indices; and at the end, nbits = nbits + 5 is used to keep the index value correct.

The advantage of this approach is quite obvious: it eliminates the O(n) operation of obtaining the array size and uses index access directly, reducing the time complexity to O(1). Of course, the downside is also quite apparent: it decreases code readability and significantly increases the likelihood of errors. You could say it’s a double-edged sword.

Reusing a Table #

Since tables are not easy to come by, we naturally need to cherish them and try to reuse them as much as possible. However, reusing a table also comes with certain conditions. First, we need to clean up the existing data in the table to avoid contamination for the next user.

This is where the table.clear function comes in handy. From its name, you can see its purpose. It clears all the data in the array, but the size of the array remains the same. This means that if you create an array of length 100 using table.new(narray, nhash), after clearing it, the length will still be 100.

To help you better understand its implementation, I have provided a code example below that is compatible with standard Lua:

local ok, clear_tab = pcall(require, "table.clear")
if not ok then
  clear_tab = function (tab)
    for k, _ in pairs(tab) do
      tab[k] = nil
    end
  end
end

As you can see, the clear function simply sets each element to nil.

Generally, we place tables that are intended for reuse at the top level of a module. This way, when you use the functions in the module, you can decide based on your actual situation whether to use the table directly or clear it before using it.

For example, let’s take a look at an example of its actual usage. The following pseudocode is taken from the open-source microservices API gateway APISIX when loading plugins:

local local_plugins = {}

function load()
    core.table.clear(local_plugins)

    local local_conf = core.config.local_conf()
    local plugin_names = local_conf.plugins

    local processed = {}
    for _, name in ipairs(plugin_names) do
        if processed[name] == nil then
            processed[name] = true
            insert_tab(local_plugins, name)
        end
    end

    return local_plugins
end

As you can see, local_plugins is an array that is a top-level variable in the plugin module. At the beginning of the load function that loads the plugins, the table is cleared and then a new plugin list is generated based on the current situation.

Table Pool #

So far, you have mastered the optimization methods for looping through a single table. But you can take it a step further by using a table pool to store multiple tables for easy retrieval. The official lua-tablepool package is designed for this purpose.

The following code demonstrates the basic usage of a table pool. We can retrieve a table from the specified pool, use it, and then release it back into the pool:

local tablepool = require "tablepool"
local tablepool_fetch = tablepool.fetch
local tablepool_release = tablepool.release

local pool_name = "some_tag"
local function do_sth()
    local t = tablepool_fetch(pool_name, 10, 0)
    -- use t for some purposes
    tablepool_release(pool_name, t) 
end

As you can see, the tablepool module utilizes some of the methods we introduced earlier. The code for this module is less than a hundred lines, so if you have the capacity, I highly recommend searching for it and studying it yourself. Here, I will mainly introduce two of its APIs.

The first one is the fetch method, which takes parameters similar to table.new, but adds a pool_name parameter. If there are no idle arrays in the pool, the fetch method will use table.new to create a new array.

tablepool.fetch(pool_name, narr, nrec)

The second one is the release function, which puts a table back into the pool. The no_clear parameter at the end is used to configure whether to call table.clear to empty the array.

tablepool.release(pool_name, tb, [no_clear])

You see, all the methods we introduced earlier are now connected here.

However, be careful not to abuse the table pool. The use of table pool in actual projects is not common. For example, it is not used in Kong, and only a few calls exist in APISIX. In most cases, not using this level of encapsulation in the table pool is sufficient for our needs.

Conclusion #

Performance optimization is a tough challenge in OpenResty and is also a hot topic of concern for all of us. Today, I have introduced some performance optimization techniques related to tables, hoping that they will be helpful for your actual projects.

Finally, I leave you with a homework question: Can you perform a performance test yourself to compare the performance difference before and after using table-related optimization techniques? Feel free to leave a comment and discuss with me. Your approaches and opinions are the voices I hope to hear. I also welcome you to share this article and get more people involved.