string building

Showcase your libraries, tools and other projects that help your fellow love users.
Post Reply
Rigachupe
Citizen
Posts: 83
Joined: Fri Jun 18, 2021 11:21 am

string building

Post by Rigachupe »

I present here some solution. First i gonna write about the slow string appending method i needed to replace with something faster.

The slowdown is when you use :
local str="hello".." ".."world".."!"

To replace this with a faster solution you need just a table where you put all the strings. And at the end you use table.concat to join them. This was 10x faster on my laptop when i measured it.

Code: Select all

-- a fast way of manipulating strings into a big string instead of using the slow way like this str=str.."some text "..value.."\n"
-- the speed improvement is almost 10x faster than the normaly used string appending version (also less memory used)

local String={}

function String.buffer()
	return {}
end

function String.append(o,str)
	table.insert(o,str)
end

function String.newline(o)
	table.insert(o,"\n")
end

function String.indent(o,spaces)
	local str=string.rep(" ",spaces)
	table.insert(o,str)
end

function String.format(o,fmt,...)
	local str=string.format(fmt,...)
	table.insert(o,str)
end

function String.tostring(o)
	return table.concat(o)
end

return String
Some tips at the end:
- if you need to append strings for some reason do not do this in love.draw call, but in love.update call
- if you draw lot of text then use bitmap font instead of true type font
User avatar
dusoft
Party member
Posts: 482
Joined: Fri Nov 08, 2013 12:07 am
Location: Europe usually
Contact:

Re: string building

Post by dusoft »

That's really just a microoptimization. Do this only, if you have resolved all other slowdowns, but there is no point probably with fast modern computers.

And regarding update/draw, that's what manual says as well. Use update to do any updates, use draw to do any painting.

Why you don't recommend using TTF fonts? If you initialize it once in love.load() as recommended, there are no issues.
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: string building

Post by pgimeno »

Rigachupe wrote: Wed Jun 07, 2023 8:59 am The slowdown is when you use :
local str="hello".." ".."world".."!" [citation needed]
Have you run the numbers?

Tables need allocation, reallocation and garbage collection.

Rigachupe wrote: Wed Jun 07, 2023 8:59 am Some tips at the end:
- if you need to append strings for some reason do not do this in love.draw call, but in love.update call
Why? It could actually improve performance if you give the GPU time to process some things while the CPU is busy with others.

Rigachupe wrote: Wed Jun 07, 2023 8:59 am - if you draw lot of text then use bitmap font instead of true type font
Citation needed too. A truetype font is converted to a bitmap font internally. If you draw a lot of CONSTANT text, then use Text objects; that is good advice.


And I recommend to ignore the microoptimization crap. Sometimes you do need to finetune some stuff. I don't advocate for this particular optimization, because it makes things actually worse, but in general it's easy to apply certain habits that may prevent you regretting not having made optimizations from the beginning. Some programs (this one in particular, for example) would not even have been possible if the author didn't microoptimize from the very beginning.
Rigachupe
Citizen
Posts: 83
Joined: Fri Jun 18, 2021 11:21 am

Re: string building

Post by Rigachupe »

pgimeno wrote: Wed Jun 07, 2023 10:03 amHave you run the numbers?
Yes, but the result will varry depending on the cpu used. I was pleased by the change i made. Because the whole save process was suddenly quicker without noticing a small lag.
Citation needed too. A truetype font is converted to a bitmap font internally. If you draw a lot of CONSTANT text, then use Text objects; that is good advice.
I have no idea how the inner api is working. At this point i assumed that it works with polygons. That means, each letter is a triangulated polygon to be drawn on the screen.
And I recommend to ignore the microoptimization crap...
No, i need this optimalizations. Again.. cpu low end. Not the worst this decade of upgrading to the highest standart. But yet still viable to watch a 10 year old cpu still kicking some ass and eating crackers that explode in the salivation of mouth while drolling on the results achieved. :)
User avatar
zorg
Party member
Posts: 3435
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: string building

Post by zorg »

Rigachupe wrote: Wed Jun 07, 2023 11:53 am
pgimeno wrote: Wed Jun 07, 2023 10:03 amHave you run the numbers?
Yes, but the result will varry depending on the cpu used. I was pleased by the change i made. Because the whole save process was suddenly quicker without noticing a small lag.
Yes, using table.concat with a table of strings might be faster than using .. to concatenate them individually due to each of those operations also generating a new string... although i'm not sure if this is that relevant with luaJIT; if you want it to be even faster, newest version of that (coming with löve 12.0, also 11.5) has actual string buffers, that might be even faster, but less user friendly to use.

Still, if anything, the dent should be on speed, not space taken up, and it shouldn't be *that* noticeable.
Rigachupe wrote: Wed Jun 07, 2023 11:53 am
Citation needed too. A truetype font is converted to a bitmap font internally. If you draw a lot of CONSTANT text, then use Text objects; that is good advice.
I have no idea how the inner api is working. At this point i assumed that it works with polygons. That means, each letter is a triangulated polygon to be drawn on the screen.
No, each Font object has a texture atlas on the gpu that the glyphs you want to print get rasterized to; it'll take some time to initially do that, but it's still fast; the letters are rectangles anyway, in terms of mesh shape, as far as i know, so it's not like more complex characters like Kanji (assuming your font supports those, löve's default doesn't due to space considerations) would take up more triangles due to the complexity of their shape.
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.
BurrickSlayer
Prole
Posts: 15
Joined: Sat Dec 21, 2013 4:28 pm

Re: string building

Post by BurrickSlayer »

Regarding the table-based string buffer: This is actually recommended in the official "Programming in Lua" book, at least in the third edition (Lua 5.2).

In the book, a code snippet is presented that reads a file line by line:

Code: Select all

for line in io.lines() do
    buff = buff .. line .. "\n"
end
The author states:
Despite its innocent look, this code in Lua can cause a huge performance penalty for large files. (...) Why is that? To understand what happens, let us assume that we are in the middle of the read loop; each line has 20 bytes and we have already read some 2500 lines, so buff is a string with 50 kB. When Lua concatenates buff..line.."\n", it allocates a new string with 50020 bytes and copies the 50000 bytes from buff into this new string. That is, for each new line, Lua moves around 50 kB of memory, and growing. More specifically, the algorithm is quadratic. After reading 100 new lines (only 2 kB), Lua has already moved more that 5 MB of memory. When Lua finishes reading 350 kB, it has moved around more than 50 GB.
But the author also points out that this is only a problem for large strings, so it's not a problem in most common cases.
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: string building

Post by pgimeno »

BurrickSlayer wrote: Mon Jun 12, 2023 1:54 pm Regarding the table-based string buffer: This is actually recommended in the official "Programming in Lua" book, at least in the third edition (Lua 5.2).

In the book, a code snippet is presented that reads a file line by line:

Code: Select all

for line in io.lines() do
    buff = buff .. line .. "\n"
end
[...]
Right, but there's a difference between that, and this:

Rigachupe wrote: Wed Jun 07, 2023 8:59 am The slowdown is when you use :
local str="hello".." ".."world".."!"
Progressive string building is indeed a problem. If I had to do it, I'd probably go with an FFI-based solution with dynamic allocation; tables are still a problem in this case because of the many garbage objects that are created.

In fact, garbage generation is precisely the reason why I didn't port string.gsub when I ported the pattern functions to pure Lua.
Post Reply

Who is online

Users browsing this forum: No registered users and 14 guests