Lua Optimizing

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
Zilarrezko
Party member
Posts: 345
Joined: Mon Dec 10, 2012 5:50 am
Location: Oregon

Lua Optimizing

Post by Zilarrezko » Thu Aug 28, 2014 8:27 pm

Alright, I'd like to make this post as good for me as for everyone else to learn optimizing techniques.

So I'd like to get some user advice after reading a couple manuals.

Out of everything that's terribly unoptimized in my code, I'm going to choose the shunting yard algorithm and reverse polish notation calculator I put together. It's quite inefficient, my string library calculator is faster than it. But any tips you'd like to throw out on this babeh, go ahead! As well if you just want to make a post about optimizing that doesn't relate to the shuntingyard/reversepolishcalculator then go ahead (you may have to give examples for me to understand).

*I decided to make this algorithm when Roland_Yonaba suggested it*
Roland_Yonaba wrote:I'd like to suggest taking a look at a famous algorithm that might be of interest, to you. It is named Shunting-Yard algorithm. There a dozens of implementations available over the internet, so porting it to Lua would not be a problem, hopefully.
Attachments
Shunting.lua
(3.58 KiB) Downloaded 167 times

User avatar
ivan
Party member
Posts: 1564
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Lua Optimizing

Post by ivan » Fri Aug 29, 2014 4:26 am

Hey Zilarrezko. Going briefly over the code (and I might be wrong), looks like you're coming from another language, probably C++.
Regarding speed optimizations, there several things to point out.
Lua is an interpreted language so you want to avoid duplicate operations/function calls, ex:

Code: Select all

			if type(tonumber(string:sub(i, i))) == "number" then
				recall = recall .. string:sub(i, i)
In C/C++ the "string.sub" call would be optimized by the compiler by storing and reusing the result in a temporary variable - since "string.sub" is a 'const' function. However with interpreted languages like Lua it would be executed twice.
This is rarely a bottleneck, but you you want to keep in mind that the Lua interpreter doesn't know what's 'const' and what isn't.
Performance issues are more likely to come from creating intermediate strings/tables like:

Code: Select all

recall = recall .. string:sub(i, i)
This could be alleviated by using pattern matching which is usually faster (than iterating char by char) and can 'capture' entire tokens.
Lua doesn't have 'switch' so large elseif statements could be optimized by using lookup tables, ex:

Code: Select all

			if temp == "+" then
				local x = table.remove(stack, #stack - 1)
				local y = table.remove(stack, #stack)
				table.insert(stack, #stack + 1, x + y)
			elseif temp == "-" then
				local x = table.remove(stack, #stack - 1)
				local y = table.remove(stack, #stack)
				table.insert(stack, #stack + 1, x - y)
			elseif temp == "*" then
				local x = table.remove(stack, #stack - 1)
				local y = table.remove(stack, #stack)
				table.insert(stack, #stack + 1, x * y)
			elseif temp == "/" then
				local x = table.remove(stack, #stack - 1)
				local y = table.remove(stack, #stack)
				table.insert(stack, #stack + 1, x / y)
			end
could become:

Code: Select all

lookup = {}
lookup["*"] = function(a, b) return a*b end
lookup["/"] = function(a, b) return a/b end
lookup["+"] = function(a, b) return a+b end
lookup["-"] = function(a, b) return a-b end
local p2 = table.remove(stack)
local p1 = table.remove(stacK)
local res = lookup[Op_Token](p1, p2)
table.insert(stack, res)
Also, isn't

Code: Select all

table.insert(queue, #queue + 1, x)
the same as:

Code: Select all

table.insert(queue, x)
That's all I can come up with for now, hope it helps. :)

PS. Oh ya, and forgot to mention that local functions are faster, if you declare them at the beginning of the script ex:

Code: Select all

local remove = table.remove

User avatar
nuno
Party member
Posts: 137
Joined: Wed Dec 11, 2013 12:00 pm
Location: Portugal
Contact:

Re: Lua Optimizing

Post by nuno » Fri Aug 29, 2014 10:49 am

Take a look at this: http://springrts.com/wiki/Lua_Performance
great tips for lua optimization. I implemented a few and noticed big differences in performance.

User avatar
Zilarrezko
Party member
Posts: 345
Joined: Mon Dec 10, 2012 5:50 am
Location: Oregon

Re: Lua Optimizing

Post by Zilarrezko » Fri Aug 29, 2014 9:57 pm

Wowy ivan! Made that function too efficient. Now it's faster than my string library calculator. Thanks a bunch! And I hardly know a thing about C++, only that Lua was written in it, the variable types, and something called classes haha. But you still helped nevertheless!

And I'll be looking through my code and that url you posted nuno. I haven't read that site's optimization techniques. I'll let you know how it goes, thanks!

User avatar
Hexenhammer
Party member
Posts: 175
Joined: Sun Feb 17, 2013 8:19 am

Re: Lua Optimizing

Post by Hexenhammer » Sun Aug 31, 2014 5:57 pm

nuno wrote:Take a look at this: http://springrts.com/wiki/Lua_Performance
great tips for lua optimization. I implemented a few and noticed big differences in performance.
Lua not LuaJIT though and LÖVE uses LuaJIT by default now. E.g.
Don't use math.[max|min]() in time critical code!
Maybe right for Lua, but wrong for LuaJIT. LuaJIT recognizes calls to math.max and produces optimized code. The "faster" if-clause version given in the linked article is actually slower when you use LuaJIT to run the code. In general do not assume that code optimized for the PUC Lua interpreter will be optimized for LuaJIT too. In fact it is very likely that the optimized code will run slower.

User avatar
Robin
The Omniscient
Posts: 6506
Joined: Fri Feb 20, 2009 4:29 pm
Location: The Netherlands
Contact:

Re: Lua Optimizing

Post by Robin » Sun Aug 31, 2014 6:18 pm

Exactly. Premature optimization is bad.

Generally what happens if you try to optimize too soon is:
  1. Speedups are usually unnoticable or even negative.
  2. They decrease maintainability, which means finishing the rest of your game costs more time and energy.
  3. They often increase the buggy-ness of your code.
  4. They take up time and effort you could put towards finishing your game in the first place
When do you optimize? When you're finished, and you notice slowness. What you do then is:
  1. Find the bottle-neck.
  2. Improve the code, preferably using algorithmic choices. Only bother with micro-optimizations if there is no big-Oh improvement possible. (Sometimes an algorithm that has a worse time-complexity is actually faster in your case, especially if the N is small and the overhead or the multiplicative constant is large. That's why the next point is important.)
  3. Measure the results.
  4. Double-check for bugs with tests, debugging or just your eyes.
  5. Is it good enough? Great, you're done. If not, go back to step 1.
Help us help you: attach a .love.

User avatar
Zilarrezko
Party member
Posts: 345
Joined: Mon Dec 10, 2012 5:50 am
Location: Oregon

Re: Lua Optimizing

Post by Zilarrezko » Sun Aug 31, 2014 8:06 pm

Hexenhammer wrote: Lua not LuaJIT though and LÖVE uses LuaJIT by default now. E.g.
Ah poo, Is there anything else other than the math calls that I should change? Or are the other tests and suggestions good or no?



And Robin, you're just like the first Lua optimization document I read. It said...
Rule1: Don't do it.
Rule2: Don't do it yet (for advanced users only).

You know what? I should probably get a profiler going... anyone know of a profiler?

Post Reply

Who is online

Users browsing this forum: No registered users and 47 guests