String concatenation slowing things down

[airstruck]

One place this happens is in asserts. See the excellent article by @pgimeno here. Benchmarks in the article show that this severely impacts performance. This should really be avoided in any performance-critical section of the code.

Another place it happens is in the examples. The callback functions passed to Map:create use something like foo[x..','..y] = bar. Replacing this with foo[(y-1)*width+x] = bar speeds up map generation of an Arena by about 10x on my machine.

Incidentally, if the callback were guaranteed to be called on cells in left-to-right, top-to-bottom order instead of the current top-to-bottom, left-to-right, you could simply do foo[#foo + 1] = bar, ignoring the x and y params, and then later:

for i = 1, #foo, width do
    print((table.concat(foo, '', i, i + width - 1)))
end

So I propose removing any string concatenation that's unnecessary (including any that happens as part of a passing assert), and possibly re-jiggering and formalizing iteration order of Map:create.

[paulofmandown]

I don't think this faux pas is in any performance critical section. It seems to be limited to keeping track of door and wall locations. I did a quick search of the map directory and this is what it turned up:

Searching 14 files for "\.\.['"],['"]\.\." (regex)

rotLove\src\rot\map\brogueRoom.lua:
  255      for x=left,right do
  256          for y=top,bottom do
  257:             if self._doors[x..','..y] then
  258                  value=2
  259              elseif self:_coordIsFloor(x, y) then
  ...
  316  
  317  function BrogueRoom:addDoor(x, y)
  318:     self._doors[x..','..y]=1
  319  end
  320  

rotLove\src\rot\map\corridor.lua:
   37  function Corridor:debug()
   38   local command    = write and write or io.write
   39:  local debugString= 'corridor: '..self._startX..','..self._startY..','..self._endX..','..self._endY
   40   command(debugString)
   41  end

rotLove\src\rot\map\digger.lua:
  113       self._dug=self._dug+1
  114   else
  115:      self._walls[x..','..y]=1
  116   end
  117  end
  ...
  128  
  129  function Digger:_priorityWallCallback(x, y)
  130:  self._walls[x..','..y]=2
  131  end
  132  
  ...
  179       local x    =cx+delta[1]
  180       local y    =cy+delta[2]
  181:      self._walls[x..','..y]=nil
  182       x=2*delta[1]
  183       y=2*delta[2]
  184:      self._walls[x..','..y]=nil
  185   end
  186  end

rotLove\src\rot\map\room.lua:
   19   self._doors= {}
   20   if doorX then
   21:      self._doors[doorX..','..doorY] = 1
   22   end
   23  end
   ..
  117  -- @tparam int y the y-position of the door
  118  function Room:addDoor(x, y)
  119:  self._doors[x..','..y]=1
  120  end
  121  
  ...
  165   for k,_ in pairs(self._doors) do door=door..'; '..k end
  166   local debugString= 'room    : '..(self._x1 and self._x1 or 'not available')
  167:                            ..','..(self._y1 and self._y1 or 'not available')
  168:                            ..','..(self._x2 and self._x2 or 'not available')
  169:                            ..','..(self._y2 and self._y2 or 'not available')
  170:                            ..','..door
  171   command(debugString)
  172  end
  ...
  204   for x=left,right do
  205       for y=top,bottom do
  206:          if self._doors[x..','..y] then
  207               value=2
  208           elseif x==left or x==right or y==top or y==bottom then

16 matches across 4 files

[airstruck]

The place I noticed it impacting performance (testing with ProFi) was in the example code:

function calbak(x, y, val)
    map[x..','..y]=val
end

Pretty much every dungeon example uses some code like this. This is tricky since it's not really part of the library, but is sort of a recommendation about how to use it. In any case, after getting rid of that string concatenation the examples generate maps about 10x faster on my machine (meaning the biggest map that can be generated in "a reasonable amount of time" becomes 10x bigger).

I think (large) map gen is likely to be the only major place where performance is an issue, since other things like FOV and pathfinding are generally going to process much less data at once, at least in the context of a traditional roguelike where FOV radius is maybe 10 or 11 units and mobs only track you when you're fairly close by.

I'll run some more tests with ProFi later and see how the cases you found above affect performance. I had the impression it was only used for debug stuff, which isn't a big deal. The example code is more of a concern to me. Someone will put that in their code, try to generate a big map, and then decide rotLua is too slow, where really their "own" code is to blame.

Of course the examples shouldn't be overly complicated either. I have sort of a half-formed idea about adding a small utility function or two to address this; will follow up with that later.

[airstruck]

Here's a quick performance test:

local ROT = require 'src.rot'

local size = 1000 -- try changing this to different values
local width, height = size, size
local map = ROT.Map.Arena(width, height)
local glyphs = { [0] = '.', '#', '+', '-' }

local n, p = os.clock() -- start timer

local t = {}
map:create(function (x, y, val)
    t[(y - 1) * width + x] = glyphs[val] or '?'
end)

n, p = os.clock(), n
print(('-- %.2f seconds -- numbers'):format(n - p))

local t = {}
map:create(function (x, y, val)
    t[#t + 1] = glyphs[val] or '?'
end)

n, p = os.clock(), n
print(('-- %.2f seconds -- lazy numbers'):format(n - p))

local t = {}
map:create(function (x, y, val)
    if not t[x] then t[x] = {} end
    t[x][y] = glyphs[val] or '?'
end)

n, p = os.clock(), n
print(('-- %.2f seconds -- nested'):format(n - p))

local t = {}
map:create(function (x, y, val)
    t[x .. ',' .. y] = glyphs[val] or '?'
end)

n, p = os.clock(), n
print(('-- %.2f seconds -- strings'):format(n - p))

Try running that in LuaJIT.

For small maps, it's not that noticeable, but as the size of the maps increases, the time spent on the string concatenation increases dramatically. For a 1000x1000 map, string concatenation is about 50x or 60x slower than the "numbers" solution on my machine. For a 2000x2000 map, it's more like 100x slower. At 3000x3000, the string concatenation approach crashes with "luajit: not enough memory," while the other solutions finish quickly.