[Project] NS2 Lua Algorithm Optimisation

IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Members
<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.
«1

Comments

  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Members, Super Administrators, Forum Admins, NS2 Developer, NS2 Playtester
    I would also be interested in this.
  • UzguzUzguz Join Date: 2003-06-05 Member: 17016Members, Constellation
    Haven't dug into the NS2 source for a long time myself, but hey - no time like the present, right?
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Members
    hehe yeah, it's gonna be fun. And ongoing.
  • FlayraFlayra Game Director, Unknown Worlds Entertainment San Francisco Join Date: 2002-01-22 Member: 3Super Administrators, NS2 Developer, Subnautica Developer
    Please do this - and send us the fixes. Matso and others have been doing this for a long time and helping us quite a bit. Just be sure to make your code look as much as possible like the existing code: style, structure, etc. Make the code as simple as possible.

    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.
  • DghelneshiDghelneshi Aims to surpass Fana in post edits. Join Date: 2011-11-01 Member: 130634Members, Squad Five Blue, Reinforced - Shadow
    edited April 2012
    Great project. :)

    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
  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Members, Super Administrators, Forum Admins, NS2 Developer, NS2 Playtester
    <!--quoteo(post=1931862:date=Apr 30 2012, 07:04 AM:name=Flayra)--><div class='quotetop'>QUOTE (Flayra @ Apr 30 2012, 07:04 AM) <a href="index.php?act=findpost&pid=1931862"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Please do this - and send us the fixes. Matso and others have been doing this for a long time and helping us quite a bit. Just be sure to make your code look as much as possible like the existing code: style, structure, etc. Make the code as simple as possible.

    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)?
  • peregrinusperegrinus Join Date: 2010-07-16 Member: 72445Members
    <!--quoteo(post=1931926:date=Apr 30 2012, 09:16 PM:name=Dghelneshi)--><div class='quotetop'>QUOTE (Dghelneshi @ Apr 30 2012, 09:16 PM) <a href="index.php?act=findpost&pid=1931926"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Great project. :)

    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
  • jeffcojeffco Join Date: 2011-02-14 Member: 81785Members
    <!--quoteo(post=1931926:date=Apr 30 2012, 10:16 PM:name=Dghelneshi)--><div class='quotetop'>QUOTE (Dghelneshi @ Apr 30 2012, 10:16 PM) <a href="index.php?act=findpost&pid=1931926"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->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.<!--QuoteEnd--></div><!--QuoteEEnd-->
    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.
  • McGlaspieMcGlaspie www.team156.com Join Date: 2010-07-26 Member: 73044Members, Super Administrators, Forum Admins, NS2 Developer, NS2 Playtester, Squad Five Blue, Squad Five Silver, Squad Five Gold, Reinforced - Onos, WC 2013 - Gold, Subnautica Playtester
    <!--quoteo(post=1932070:date=Apr 30 2012, 08:16 PM:name=peregrinus)--><div class='quotetop'>QUOTE (peregrinus @ Apr 30 2012, 08:16 PM) <a href="index.php?act=findpost&pid=1932070"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Like on of those dictators covered with every kind of military medal :P<!--QuoteEnd--></div><!--QuoteEEnd-->Lmfao! Wp sir, wp. ;)

    I'm interested in this as well and any tweaks/improvements I discover from working on MvM I'll throw in the "pot".
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Members
    I'm still waiting on the invite to base37, but I got a few (probably good) things brewing in my head about how we'll do things.

    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.
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
    Looking at the profiler it seems ControllerMixin:PerformMovement use quite a bit of time, it's used more heavily by the skulk to avoid to get blocked on map geometry.
  • MaxMax Technical Director, Unknown Worlds Entertainment Join Date: 2002-03-15 Member: 318Super Administrators, Retired Developer, NS1 Playtester, Forum Moderators, NS2 Developer, Constellation, Subnautica Developer, Pistachionauts, Future Perfect Developer
    <!--quoteo(post=1931926:date=Apr 30 2012, 01:16 PM:name=Dghelneshi)--><div class='quotetop'>QUOTE (Dghelneshi @ Apr 30 2012, 01:16 PM) <a href="index.php?act=findpost&pid=1931926"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->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.<!--QuoteEnd--></div><!--QuoteEEnd-->
    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).
  • JanosJanos Join Date: 2002-08-02 Member: 1050Members, Constellation, NS2 Playtester
    <!--quoteo(post=1931926:date=Apr 30 2012, 08:16 PM:name=Dghelneshi)--><div class='quotetop'>QUOTE (Dghelneshi @ Apr 30 2012, 08:16 PM) <a href="index.php?act=findpost&pid=1931926"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->@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-->

    Funny, quite a few people seem to be getting that problem.
  • extolloextollo Ping Blip Join Date: 2010-07-16 Member: 72457Members
    i'd like to assist with this as well, once you get your plan in place.
  • ScardyBobScardyBob ScardyBob Join Date: 2009-11-25 Member: 69528Forum Admins, Forum Moderators, NS2 Playtester, Squad Five Blue, Reinforced - Shadow, WC 2013 - Shadow
    One place you might start is in the NPC code. I've certainly noticed that multiple NPCs moving at the same time (think MAC, drifter, or ARC spam) causes servers to seriously tank. It makes me think that could possibly be a good candidate for optimization.
  • PlasmaPlasma Join Date: 2003-04-26 Member: 15855Members, Constellation, Squad Five Blue
    Something is up with the ARCs (if you have many, they seem to both misfire and have very small tickrates).
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Members
    bump, hello? attention? Still waiting on this invite, over 1 week later.
  • CaptScumCaptScum UK Join Date: 2005-01-09 Member: 34017Members, Constellation, Reinforced - Shadow
    edited May 2012
    I would like (or at least try) to help out with this aswell if I can
  • MrGreenMrGreen Join Date: 2010-12-10 Member: 75602Members
    The annoying thing is that I actually work in performance testing of software as my day job, with past experience as a developer.

    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.
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
    Early game it seems movement related code is a big factor, anyone can confirm ?

    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>
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Members
    yeah some time last year I noticed that moving would drop fps instantly by about 30.
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Members
    edited May 2012
    Alright, I'm on basecamp, I'll send out a few pms to people who want to help out. You will be put on a sorta "trial" for one week to see if you are going to help out. Don't worry if it turns out you can't help out significantly, later on, just ask to join again when you feel like trying out again.

    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.
  • UzguzUzguz Join Date: 2003-06-05 Member: 17016Members, Constellation
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Members
  • extolloextollo Ping Blip Join Date: 2010-07-16 Member: 72457Members
    edited May 2012
    <!--quoteo(post=1934374:date=May 8 2012, 05:24 AM:name=Yuuki)--><div class='quotetop'>QUOTE (Yuuki @ May 8 2012, 05:24 AM) <a href="index.php?act=findpost&pid=1934374"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->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 :<!--QuoteEnd--></div><!--QuoteEEnd-->

    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.
  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Members, Super Administrators, Forum Admins, NS2 Developer, NS2 Playtester
    edited May 2012
    <!--quoteo--><div class='quotetop'>QUOTE </div><div class='quotemain'><!--quotec-->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..<!--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>
  • extolloextollo Ping Blip Join Date: 2010-07-16 Member: 72457Members
    <!--quoteo(post=1935442:date=May 11 2012, 11:02 AM:name=Psyke)--><div class='quotetop'>QUOTE (Psyke @ May 11 2012, 11:02 AM) <a href="index.php?act=findpost&pid=1935442"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->String lookups are actually not that expensive in Lua. They are converted to hashes and then it is just an int compare.

    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
  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Members, Super Administrators, Forum Admins, NS2 Developer, NS2 Playtester
    Info about using the profiler:
    - 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?
  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Members, Super Administrators, Forum Admins, NS2 Developer, NS2 Playtester
    <!--quoteo(post=1934367:date=May 7 2012, 11:29 PM:name=MrGreen)--><div class='quotetop'>QUOTE (MrGreen @ May 7 2012, 11:29 PM) <a href="index.php?act=findpost&pid=1934367"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->The annoying thing is that I actually work in performance testing of software as my day job, with past experience as a developer.

    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.
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Members
    anyone who i have not invited yet but still wants to join the project... can you please say so after this post. I'm just making sure I don't miss anyone.
Sign In or Register to comment.