Re: "String builder"-style optimization

[Martin <eden_martin_fuhrspam@...>]

On 07/03/2017 12:16 PM, J Doe wrote:
> Hi,
> 
> In chapter 2 of "Lua Gems", Roberto mentions the fact that building a string in a loop by concatenating more string data to it on each iteration is wasteful as a new string must be allocated, the existing elements copied, the old string GC'ed (at some point) and the addition of the new portion of the string.
> 
> The recommendation for optimization is to emulate "string builder" functionality by storing each piece as an element in a table and then calling table.concat(t).
> 
> I am wondering if this is also a good pattern for building a regular string that has multiple concatenations . . . but say on the order of 5 to 10 concatenation operations:
> 
> t = {"Banned UA:", bad_ua, "reason: ", reason_ua, "stats", clck_elapsed}
> s = table.concat(t, " ")

For your case you'd better to use string:format().


For my measurements, lame chunks concatenation in loop is faster than
insertion them in table up to ~60 elements.

But "faster" not always mean "better". As mentioned, it wastes memory
by storing substrings.

So

  msg = 'id: ' .. id .. ', name: ' .. name

is faster (and does not store substrings) than

  msg = ('id: %s, name: %s'):format(id, name)

But anyway I mostly prefer second variant.

--
Below is the code I've created for measurements.

<els> is chunks we add.
<test_chunks> is alternative functions to concat <els>.
<test_period_secs> is time to run for each <test_chunks>[i] function.

--
local els =
  {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C',
'D', 'E', 'F',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C',
'D', 'E', 'F',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C',
'D', 'E', 'F',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C',
'D', 'E', 'F',
  }

local test_chunks =
  {
    [1] =
      function()
        local s = ''
        for i = 1, #els do
          s = s .. els[i]
        end
      end,
    [2] =
      function()
        local t = {}
        for i = 1, #els do
          t[#t + 1] = els[i]
        end
        local s = table.concat(t)
      end,
    [3] =
      function()
        local fmt_str = ('%s'):rep(#els)
        local s = fmt_str:format(table.unpack(els))
      end,
  }

local test_period_secs = 1.0

local start_time

local tic =
  function()
    start_time = os.clock()
  end

local tac =
  function()
    return os.clock() - start_time
  end

local counters = {}
for i = 1, #test_chunks do
  tic()
  local cnt = 0
  local f = test_chunks[i]
  while (tac() < test_period_secs) do
    f()
    cnt = cnt + 1
  end
  counters[i] = cnt
end

for i = 1, #counters do
  print(('%d: %.2f ops/sec'):format(i, counters[i] / test_period_secs))
end

-- Martin