[Project] NS2 Lua Algorithm Optimisation
Ironsoul
Join Date: 2011-03-12 Member: 86048Members
Join Date: 2011-03-12 Member: 86048Members
in Squad Five
<div class="IPBDescription">Server Side and Client Side</div>Hi guys, this is a simple thread to put it out there that I think we might be able to help significantly with optimizing ns2.
The premise is simple, study, analyse, research and document the natural selection 2 lua code and identify potential places we can optimse the code instructions.
Then, we take the core of each lua algorithm script, maintain it's functionality, including inputs and outputs, and rewrite the instructions to provide the same output, but with less overhead.
I'll be working on a much better document detailing the core of the project with more clarity, but I'm hoping to get invited to base37 so I can do it there instead.
The premise is simple, study, analyse, research and document the natural selection 2 lua code and identify potential places we can optimse the code instructions.
Then, we take the core of each lua algorithm script, maintain it's functionality, including inputs and outputs, and rewrite the instructions to provide the same output, but with less overhead.
I'll be working on a much better document detailing the core of the project with more clarity, but I'm hoping to get invited to base37 so I can do it there instead.
Comments
We can't promise to use the changes, but often we agree with the changes and we merge them in and it's shipped with the next patch!
Keep in mind that we'll need you to sign <a href="http://www.unknownworlds.com/ns2/forums/index.php?showtopic=115732" target="_blank">our contributor agreement</a> if we are to use any of your code.
I'd really like to have a more usable profiler for this though. The current one is so incredibly annoying, since the tree view resets after every frame and you have to dig and find the function again. It's not feasible to find the execution time of irregularly called functions like this. Something like a search term for the profiler would already help a lot, e.g. 'profile "GUIMinimap:Update"' in console would only display GUIMinimap:Update for every frame.
@Flayra: Wth is up with your icons? Need ego boost? :)
<img src="https://pickhost.eu/images/0005/1960/WTFIcons.png" border="0" class="linked-image" />
So, you're a retired developer <b>and</b> a developer <b>and</b> a playtester (kinda redundant with developer) <b>and</b> also donated to yourself? :D
We can't promise to use the changes, but often we agree with the changes and we merge them in and it's shipped with the next patch!
Keep in mind that we'll need you to sign <a href="http://www.unknownworlds.com/ns2/forums/index.php?showtopic=115732" target="_blank">our contributor agreement</a> if we are to use any of your code.<!--QuoteEnd--></div><!--QuoteEEnd-->
Do you have a list of bugs and known optimization targets that UWE is not currently looking in to (to help direct the community efforts)?
I'd really like to have a more usable profiler for this though. The current one is so incredibly annoying, since the tree view resets after every frame and you have to dig and find the function again. It's not feasible to find the execution time of irregularly called functions like this. Something like a search term for the profiler would already help a lot, e.g. 'profile "GUIMinimap:Update"' in console would only display GUIMinimap:Update for every frame.
@Flayra: Wth is up with your icons? Need ego boost? :)
<img src="https://pickhost.eu/images/0005/1960/WTFIcons.png" border="0" class="linked-image" />
So, you're a retired developer <b>and</b> a developer <b>and</b> a playtester (kinda redundant with developer) <b>and</b> also donated to yourself? :D<!--QuoteEnd--></div><!--QuoteEEnd-->
Like on of those dictators covered with every kind of military medal :P
I am almost positive you could write your own profiler in lua code. All you need is a function to query the current time with somewhat like millisecond precision, a table to store collected data, and some code to print the results. You will get solid results as soon as you start averaging over multiple execution time measurements.
I'm interested in this as well and any tweaks/improvements I discover from working on MvM I'll throw in the "pot".
It will be organised via base36 and I don't currently have any specific areas to target in the ns2 code. That will all be worked out after the project is up on base 52.
If you are looking for a specific function, the non hierarchical view might be more helpful (hit M to open, T to toggle sorting by time).
<img src="https://pickhost.eu/images/0005/1960/WTFIcons.png" border="0" class="linked-image" />
So, you're a retired developer <b>and</b> a developer <b>and</b> a playtester (kinda redundant with developer) <b>and</b> also donated to yourself? :D<!--QuoteEnd--></div><!--QuoteEEnd-->
Funny, quite a few people seem to be getting that problem.
But I'm struggling to work out the easiest way for me to contribute.
While I'm not versed in LUA, I could at least identify the low hanging fruit for performance tuning.
There is not much algorithmic about the movement code though, it's mainly a bunch of linear vectorial math.
Something I wonder. There is a lot of function like self:GetSomething() that just return self.something or so. Is this slower than defining a local variable instead? Javascript has some of those kind :
<a href="http://james.padolsey.com/javascript/zakas-javascript-performance-tips/" target="_blank">http://james.padolsey.com/javascript/zakas...rformance-tips/</a>
Unless you're a complete ass hat, I'll only be removing people to keep track of who is (currently)actively supporting the project.
Note: unless you have explicitly said something like "I want to help with this", you will not be getting a pm.
yes it is slower, but these getter functions are done for encapsulation and programming style. i think you want to be selective in any optimizations just to maintain clarity.
a common technique, which you can find on the web, is to take a global function call that is in a loop and assign it to a local variable outside the loop. what this does is put the function in a 'register' so each call of the function doesnt require a table lookup by name. the typical example is calls to the math library functions. the performance benefit would only matter if the loop is doing a ton of calls though.
So i don't think it is something that should be applied everywhere.
Another common optimization is memoizing. Take a look at LookupTechData in TechData.lua. That function is called *everywhere*.
It is essentially memoized through cachedTechData. I still don't think that is efficient as it could be, since it is still doing some named lookups and scans of records. note: this isnt implemented like a typical memoize, but a similar concept might be useful on other heavily called functions. Its a memory/performance tradeoff.
Think of all the constants in this game, there are lookups every time (find the module by name, find the variable by name). But again, programming clarity trumps hardcoding constants..
I hope forthcoming engine optimizations will take care of much of this - dealing with loop invariants, efficient lookups, etc.
one more edit: this effort should focus first on algorithms instead of lua specific language tricks - only looking at doing the latter in very obvious cases.
Think of all the constants in this game, there are lookups every time (find the module by name, find the variable by name). But again, programming clarity trumps hardcoding constants..<!--QuoteEnd--></div><!--QuoteEEnd-->
String lookups are actually not that expensive in Lua. They are converted to hashes and then it is just an int compare.
<!--quoteo--><div class='quotetop'>QUOTE </div><div class='quotemain'><!--quotec-->one more edit: this effort should focus first on algorithms instead of lua specific language tricks - only looking at doing the latter in very obvious cases.<!--QuoteEnd--></div><!--QuoteEEnd-->
I agree, except that it is very important to know the Lua specific tricks so that you don't end up making things worse. Every language has its quirks. The fact that string compares actually aren't that bad completely goes against my instincts as a C++ programmer, but "fixing" it in Lua would not actually give any/many gains. It would just make the code worse.
Here's some more info about Lua specific optimization (including more detailed info about how lua handles strings): <a href="http://www.lua.org/gems/sample.pdf" target="_blank">http://www.lua.org/gems/sample.pdf</a>
Some more info: <a href="http://lua-users.org/wiki/OptimisationCodingTips" target="_blank">http://lua-users.org/wiki/OptimisationCodingTips</a>
Here's some more info about Lua specific optimization (including more detailed info about how lua handles strings): <a href="http://www.lua.org/gems/sample.pdf" target="_blank">http://www.lua.org/gems/sample.pdf</a>
Some more info: <a href="http://lua-users.org/wiki/OptimisationCodingTips" target="_blank">http://lua-users.org/wiki/OptimisationCodingTips</a><!--QuoteEnd--></div><!--QuoteEEnd-->
i was referring to table lookups not string compare, which is why local is used to optimize in some cases. even then lookups arent *that* expensive - i mean it is a core element of how lua works.
good refs - maybe they should be linked from the basecamp project
- Type 'profile' in console to bring it up
- Press 'spacebar' to pause it
- Press '[' or ']' to move the view between different frames recorded by the profiler
- Use the mouse and scroll wheel to traverse the hierarchical view
- Press 'M' to toggle between a flat and hierarchical view
- Press 'T' to toggle between sorting by time or by ABC.
- Click on a function to have it display that particular functions performance over all the recorded frames (shows yellow bars indicating as such)
- Add PROFILE( "Functionname" ) at the top of a lua function's body to add it to the profiler
Weirdness/Bugs
1. In the top area, the bars for the different components (renderer, engine, game, etc) can go past 100% making it harder to see at a glance what is consuming the most CPU time
2. For some reason I keep seeing negative numbers in the profiler, which then really throws off the sums. Max, is there a setting I'm missing that would fix this?
Request
1. Filter by component - it would be great to be able to hide any non-game measurements so that if we're looking at Lua all we see is Lua. Is there a way to do this already that I haven't found?
But I'm struggling to work out the easiest way for me to contribute.
While I'm not versed in LUA, I could at least identify the low hanging fruit for performance tuning.<!--QuoteEnd--></div><!--QuoteEEnd-->
Please do. That would be incredibly helpful.
I see you're not on basecamp yet. PM myself or IronSoul with your email addy for an invite.