Description
Consider the following benchmark which encodes the deeply nested structure [1000, [999, [998, [...]]]]:
local json = require"json"
for _ = 1, 1e3 do
local t = {}
for i = 1, 1e3 do
t = {i, t}
end
json.encode(t)
endthis should run in a fraction of a second. Instead, it takes ~2 seconds on my device. This is because string concatenations / recursive table.concat are internally used to encode the JSON:
return "[" .. table.concat(res, ",") .. "]"This means that the outer loop will have to add the [ and ] brackets in time linear in table.concat(res, ","), which in our example will be just marginally shorter, which in turn will only differ in length by a constant. Thus you do a linear time operation linearly often, resulting in worst-case quadratic encoding runtime in the depth of the nested structure.
The proper fix is to use a shared rope and have all recursive calls write to the same rope. You then only concatenate strings once at the end. Building the string then runs in linear time. You can find an example of this approach in my JSON implementation.