[Project] NS2 Lua Algorithm Optimisation

IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Posts: 806Members
Server Side and Client Side
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: 23112Posts: 2,428Members, NS2 Playtester, Community Dev Team
    I would also be interested in this.
    [ Rek | Reklys | remedy | remi.D | blu.knight | Psyke | Sky ]
    I have way too many names.
  • UzguzUzguz Join Date: 2003-06-05 Member: 17016Posts: 342Members, 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: 86048Posts: 806Members
    hehe yeah, it's gonna be fun. And ongoing.
  • FlayraFlayra Game Director, Unknown Worlds Entertainment San Francisco Join Date: 2002-01-22 Member: 3Posts: 6,828Super Administrators, NS2 Developer, Subnautica Developer admin
    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 our contributor agreement if we are to use any of your code.
    Charlie Cleveland
    Game Director, Unknown Worlds Entertainment
  • DghelneshiDghelneshi Aims to surpass Fana in post edits. Join Date: 2011-11-01 Member: 130634Posts: 941Members, 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? :)
    image
    So, you're a retired developer and a developer and a playtester (kinda redundant with developer) and also donated to yourself? :D
    Post edited by Unknown User on
  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Posts: 2,428Members, NS2 Playtester, Community Dev Team
    QUOTE (Flayra @ Apr 30 2012, 07:04 AM) »
    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 our contributor agreement if we are to use any of your code.

    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)?
    [ Rek | Reklys | remedy | remi.D | blu.knight | Psyke | Sky ]
    I have way too many names.
  • peregrinusperegrinus Join Date: 2010-07-16 Member: 72445Posts: 2,426Members
    QUOTE (Dghelneshi @ Apr 30 2012, 09:16 PM) »
    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? :)
    image
    So, you're a retired developer and a developer and a playtester (kinda redundant with developer) and also donated to yourself? :D


    Like on of those dictators covered with every kind of military medal :P
  • jeffcojeffco Join Date: 2011-02-14 Member: 81785Posts: 61Members
    QUOTE (Dghelneshi @ Apr 30 2012, 10:16 PM) »
    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.

    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 Lord MuckyMuck of the Programmers Join Date: 2010-07-26 Member: 73044Posts: 824Members, NS2 Playtester, Squad Five Blue, Reinforced - Onos, WC 2013 - Gold, Subnautica Playtester, Community Dev Team
    QUOTE (peregrinus @ Apr 30 2012, 08:16 PM) »
    Like on of those dictators covered with every kind of military medal :P
    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".

    Colored Skins Mod ( Forum Thread - Steam Workshop )
    Marine vs Marine Mod ( Forum Thread - Steam Workshop - Mod Tracker )
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Posts: 806Members
    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: 75079Posts: 1,731Members
    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: 318Posts: 1,650Super Administrators, Retired Developer, NS1 Playtester, Forum Moderators, NS2 Developer, Constellation, Subnautica Developer, Pistachionauts
    QUOTE (Dghelneshi @ Apr 30 2012, 01:16 PM) »
    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.

    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).
    Max McGuire
    Technical Director, Unknown Worlds Entertainment
  • JanosJanos Join Date: 2002-08-02 Member: 1050Posts: 390Members, Constellation, NS2 Playtester
    QUOTE (Dghelneshi @ Apr 30 2012, 08:16 PM) »
    @Flayra: Wth is up with your icons? Need ego boost? :)
    image
    So, you're a retired developer and a developer and a playtester (kinda redundant with developer) and also donated to yourself? :D


    Funny, quite a few people seem to be getting that problem.
  • extolloextollo Ping Blip Join Date: 2010-07-16 Member: 72457Posts: 366Members
    i'd like to assist with this as well, once you get your plan in place.
  • ScardyBobScardyBob ScardyBob Join Date: 2009-11-25 Member: 69528Posts: 4,983Forum Admins, Forum Moderators, NS2 Playtester, Squad Five Blue, Reinforced - Shadow, WC 2013 - Shadow mod
    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: 15855Posts: 605Members, 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: 86048Posts: 806Members
    bump, hello? attention? Still waiting on this invite, over 1 week later.
  • CaptScumCaptScum UK Join Date: 2005-01-09 Member: 34017Posts: 26Members, Constellation, Reinforced - Shadow
    edited May 2012
    I would like (or at least try) to help out with this aswell if I can
    Post edited by Unknown User on
    Hi
  • MrGreenMrGreen Join Date: 2010-12-10 Member: 75602Posts: 31Members
    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: 75079Posts: 1,731Members
    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 :

    http://james.padolsey.com/javascript/zakas...rformance-tips/
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Posts: 806Members
    yeah some time last year I noticed that moving would drop fps instantly by about 30.
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Posts: 806Members
    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.
    Post edited by Unknown User on
  • UzguzUzguz Join Date: 2003-06-05 Member: 17016Posts: 342Members, Constellation
    Sign me up.
  • YuukiYuuki Join Date: 2010-11-20 Member: 75079Posts: 1,731Members
  • extolloextollo Ping Blip Join Date: 2010-07-16 Member: 72457Posts: 366Members
    edited May 2012
    QUOTE (Yuuki @ May 8 2012, 05:24 AM) »
    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 :


    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.
    Post edited by Unknown User on
  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Posts: 2,428Members, NS2 Playtester, Community Dev Team
    edited May 2012
    QUOTE
    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..

    String lookups are actually not that expensive in Lua. They are converted to hashes and then it is just an int compare.

    QUOTE
    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.

    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): http://www.lua.org/gems/sample.pdf
    Some more info: http://lua-users.org/wiki/OptimisationCodingTips
    Post edited by Unknown User on
    [ Rek | Reklys | remedy | remi.D | blu.knight | Psyke | Sky ]
    I have way too many names.
  • extolloextollo Ping Blip Join Date: 2010-07-16 Member: 72457Posts: 366Members
    QUOTE (Psyke @ May 11 2012, 11:02 AM) »
    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): http://www.lua.org/gems/sample.pdf
    Some more info: http://lua-users.org/wiki/OptimisationCodingTips


    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: 23112Posts: 2,428Members, NS2 Playtester, Community Dev Team
    Info about using the profiler:
    - Type 'profile' in console to bring it up
    - Press 'spacebar' to pause it
    - Press '' 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?
    [ Rek | Reklys | remedy | remi.D | blu.knight | Psyke | Sky ]
    I have way too many names.
  • remiremi remedy [blu.knight] Join Date: 2003-11-18 Member: 23112Posts: 2,428Members, NS2 Playtester, Community Dev Team
    QUOTE (MrGreen @ May 7 2012, 11:29 PM) »
    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.

    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.
    [ Rek | Reklys | remedy | remi.D | blu.knight | Psyke | Sky ]
    I have way too many names.
  • IronsoulIronsoul Join Date: 2011-03-12 Member: 86048Posts: 806Members
    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.
«1
Sign In or Register to comment.