-
Notifications
You must be signed in to change notification settings - Fork 25
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
String concatenation slowing things down #36
Comments
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:
|
The place I noticed it impacting performance (testing with ProFi) was in the example code:
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. |
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. |
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 likefoo[x..','..y] = bar
. Replacing this withfoo[(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: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.
The text was updated successfully, but these errors were encountered: