String Concatenation Performance in Lua

The Problem

Inefficient string concatenation in Lua can lead to significant performance issues, especially when building large strings or working with loops.

-- Bug Example: Inefficient string building
local result = ""
for i = 1, 1000000 do
    result = result .. "x"  -- Creates a new string each iteration
end

Why It Happens

In Lua, strings are immutable. Each concatenation operation creates a new string, leading to O(n²) complexity when building strings in a loop.

How to Fix It

1. Using table.concat for efficient string building:

-- Solution 1: Using table.concat
local parts = {}
for i = 1, 1000000 do
    parts[i] = "x"
end
local result = table.concat(parts)  -- Much faster

2. Buffer-like approach for dynamic content:

-- Solution 2: Buffer implementation
local StringBuffer = {}
StringBuffer.__index = StringBuffer

function StringBuffer.new()
    return setmetatable({
        parts = {},
        length = 0
    }, StringBuffer)
end

function StringBuffer:append(str)
    self.length = self.length + 1
    self.parts[self.length] = str
end

function StringBuffer:toString()
    return table.concat(self.parts)
end

-- Usage
local buffer = StringBuffer.new()
for i = 1, 1000000 do
    buffer:append("x")
end
local result = buffer:toString()

3. Format strings for complex concatenation:

-- Solution 3: Using string.format
local function formatUser(user)
    return string.format(
        "%s %s (%d)",
        user.firstName,
        user.lastName,
        user.age
    )
end

Performance Comparison

-- Performance test
local function testConcat(n)
    local start = os.clock()
    local result = ""
    for i = 1, n do
        result = result .. "x"
    end
    return os.clock() - start
end

local function testBuffer(n)
    local start = os.clock()
    local parts = {}
    for i = 1, n do
        parts[i] = "x"
    end
    local result = table.concat(parts)
    return os.clock() - start
end

print("Concat:", testConcat(100000))    -- Slow
print("Buffer:", testBuffer(100000))    -- Fast

Best Practices

1. Use table.concat for known number of strings
2. Implement a buffer for dynamic string building
3. Pre-allocate tables when size is known
4. Use string.format for complex formatting
5. Avoid concatenation in tight loops

Common Pitfalls

-- Pitfall 1: Hidden concatenation
local function buildPath(...)
    local path = ""
    for i = 1, select("#", ...) do
        path = path .. "/" .. select(i, ...)  -- Inefficient
    end
    return path
end

-- Better:
local function buildPath(...)
    local parts = {"/"}
    local args = {...}
    for i = 1, #args do
        parts[i + 1] = args[i]
    end
    return table.concat(parts, "/")
end

Memory Considerations

-- Memory efficient string handling
local function processLargeString(str)
    local chunks = {}
    for i = 1, #str, 1024 do
        chunks[#chunks + 1] = str:sub(i, i + 1023)
    end
    return chunks
end

Pattern Matching Alternative

-- Using patterns instead of concatenation
local function extractNames(text)
    local names = {}
    for name in text:gmatch("%w+") do
        names[#names + 1] = name
    end
    return table.concat(names, ", ")
end

Related Concepts

• Memory management
• Garbage collection
• Pattern matching
• Buffer implementations
• String interning

Learn More

• Lua Reference Manual: String Manipulation
• Programming in Lua: String Manipulation