Light Style© by Fisana

Jump to content


Photo

[DISCUSS] Performance Optimisations


  • Please log in to reply
41 replies to this topic

#1 k776

k776

    Centurio

  • WFG Retired
  • 724 posts

Posted 16 January 2013 - 11:13 PM

This thread is public but only reply to it if you have the skills needed to contribute something useful. Any posts that don't add anything to the thread will be deleted!

The game is getting to a point where the speed is really killing us. We need to find ways of speeding up the game, and doing so within the next release or two. Lag causes players to give up and leave. We need to start attracting fans to play regularly.

So the point of this thread is to discuss, collect, and action on ways we can actually speed up the game. Found a really slow part of the game? Post where it is and some ideas for improving it. Working on something to speed it up? Post about it an get feedback early.

This is now top priority for all developers. Other work can continue, but you should be working together to get the game faster. Communicate, collaborate, contribute....

Here are some ideas/tickets to get things started.
  • Finish developing the new path finder - http://trac.wildfire...com/ticket/1756
    The new pathfinder is designed to be faster and give closer results between long range and short range path finding.
  • CCmpRangeManager optimisation - http://trac.wildfire...com/ticket/1707
  • Implement an Octree - http://en.wikipedia.org/wiki/Octree
  • Rewrite the AI base system in C++ - AI are very slow. From what I understand, several systems are implemented in JS when they would be much faster in C++, e.g. building placement needs to copy data from C++ to JS and then loop over the data. Move as much of the AI system to C++ for speed.
  • If we keep the javascript AI system then a fairly simple improvement is to make the entity collection updates use the heirarchy of entity collections to save significant work.
  • boost::unordered_map is potentially faster than std::map in some situations. This is now serializable so should be very easy to change (it won't even break multiplayer sync because it serializes as a std::map). I don't know if there are any situations currently where this would help though. (Except for CCmpRangeManager, but the proposal in the ticket is better for that).
Here are things which could be done but hopefully won't need to be. This is just a list we can come back to near when we release if we still need to improve:
  • Disable the ability to have arrows hit units other than the one they targetted, this would save looking up entities near to the arrows hit location.

  • 3

Kieran P [ aka k776 ]


#2 quantumstate

quantumstate

    Primus Pilus

  • WFG Retired
  • 1,150 posts

Posted 16 January 2013 - 11:25 PM

I had a look around for open source octree implementations and I thought that this looked promising. http://www.hxa.name/...a7241_2005.html . Though I am not sure if we already use something for graphical clipping, does anyone know?

The places where the octree should help is in the graphical code. Currently the position interpolation, rendering transforms and some other stuff is done globally for all units. This should be restricted to visible entities and some stuff can be cached to save time for stationary entities (like trees).

Also the code which highlights things under the cursor loops through all entities at the moment. This should also use the octree so that large maps with lots of trees don't cause lag here.

The good thing is that there are potentially huge gains to be made at the moment, though with some areas like the pathfinder this is quite tricky.
  • 0

Jonathan Waller [ aka quantumstate ]

Wildfire Games Programmer
Contact me: jonathanmarkwaller at gmail dot com


Support Wildfire Games!


#3 Yves

Yves

    Primus Pilus

  • WFG Programming Team
  • 1,015 posts

Posted 16 January 2013 - 11:52 PM

  • Rewrite the AI base system in C++ - AI are very slow. From what I understand, several systems are implemented in JS when they would be much faster in C++, e.g. building placement needs to copy data from C++ to JS and then loop over the data. Move as much of the AI system to C++ for speed.
  • If we keep the javascript AI system then a fairly simple improvement is to make the entity collection updates use the heirarchy of entity collections to save significant work.

I think we can get a lot of performance out of JS. I've seen that we have already enabled JIT (Just In Time compiling) for release builds.
Why do we even need to do it "Just in Time" when we (opposed to Firefox) know all scripts before we run them?
In addition to that, there were a lot of improvements in Firefox's Javascript engine (Spidermonkey) which we are using.
The latest versions of Firefox has come with many significant performance improvements and introduced a new JIT compiler called Ion Monkey. This compiler should further improve the optimization for compiled JS code.

Here's an interesting blog-post about that topic (also other topics are interesting on that blog):
https://blog.mozilla...-in-firefox-18/

One difficulty about using a newer version of Spidermonkey is that Mozilla doesn't seem to be interested in doing the work required to release a new standalone (not part of Firefox) version. This means also that documentation is lacking.
https://bugzilla.moz...g.cgi?id=735599
Another difficulty is that the API of 1.8.5 isn't compatible with the newer versions. I don't know yet how much work it would be to integrate a new version of Spidermonkey into the game.

Last but not least I assume that garbage collection and memory allocation could be a major bottleneck for certain parts of JS code that update a lot of data very often. I don't have any proof for that yet. Maybe we can optimize something or if that fails we could still fall back to C++ code.

I'm very interested in doing more research about that matter, but I'd like to complete my current work first.
  • 0

#4 fabio

fabio

    Centurio

  • WFG Programming Team
  • 651 posts

Posted 17 January 2013 - 10:18 AM

Here are a couple of interesting tickets:
  • 0

Graphics problems with 0 A.D. under Ubuntu and free drivers? Check out the Updated and Optimized Graphics Drivers Archive: includes updated drivers with fixes and improvements for games, including 0 A.D..


#5 Thanduel

Thanduel

    Discens

  • Community Members
  • Pip
  • 40 posts

Posted 20 January 2013 - 10:29 AM

I would like to contribute to improving the performance of 0ad, I've been following the game for about two years now but I've never had time. However, I may have some time opening up soon. I'm interested in working on the pathfinder however I expect there is quite a lot to become familiar with before anything meaningful can be contributed. What has been done and what still needs to be done. I see there is a patch on trac, is all the work in the patch documented in Ykrosh's forum posts?

Edited by Thanduel, 20 January 2013 - 10:29 AM.

  • 0

#6 wraitii

wraitii

    Primus Pilus

  • WFG Programming Team
  • 1,664 posts

Posted 20 January 2013 - 12:32 PM

Further information for AI-side optimizations:
My API v3 (still not in the game, afaik) will use a shared component and a player-specific component. The architecture would thus be this:

C++ Side:
AI Manager -> AiWorker (for threading). The AI Worker deals with getting the simulation state (from Ai Manager), running the shared component and sending it to each AI Player script, and runs the AIPlayer (C++ side) which calls the javascript AI.
Javascript side:
shared component / Ai script.

Basically this architecture means that the shared component could probably, for the most part, be ported to C++. I do not believe it should necessarily be too easily moddable since it's only there to do basic, but necessary stuffs: entity filtering (possibly entity collections too, but that might be kept JS side using a clever hierarchical (ie à la octree)). It does map filtering and things like that, which could be ported to C++ efficiently (I believe).

AI scripts should however probably remain mostly JS only, for easier moddability. There are areas of improvements there too: detecting what is ran too often and running it less often, optimizing probably in a lot of places, porting some logic to the shared component if it happens to be worthwhile. Furthermore, the JS itself could be faster.

About the GC: AIs tend to waste a lot of memories in allocations and deallocation. With a small runtime size (the default 16Mb or the current 24Mb), this means running the GC fairly often. It should be tested wether it's more efficient to run the GC once in a while with a larger runtime (I think we could afford 32Mb), or fairly often with a smaller runtime.
  • 0
Lancelot de Ferrière le Vayer [ aka Wraitii ]
Wildfire Games Programmer, AI developer, auxiliary map designer, dealing with anything water.
Contact me: wraitii@wildfiregames.com

Also the world's only three-dimensional poodle.

#7 quantumstate

quantumstate

    Primus Pilus

  • WFG Retired
  • 1,150 posts

Posted 20 January 2013 - 05:30 PM

I would like to contribute to improving the performance of 0ad, I've been following the game for about two years now but I've never had time. However, I may have some time opening up soon. I'm interested in working on the pathfinder however I expect there is quite a lot to become familiar with before anything meaningful can be contributed. What has been done and what still needs to be done. I see there is a patch on trac, is all the work in the patch documented in Ykrosh's forum posts?


There is a pdf here http://trac.wildfire.../pathfinder.pdf otherwise I think the forums are the best source. I was also thinking about looking at the pathfinder if I have time. I think it is reasonable to have both of us looking at it at once, but obviously we would need to communicate progress.
  • 0

Jonathan Waller [ aka quantumstate ]

Wildfire Games Programmer
Contact me: jonathanmarkwaller at gmail dot com


Support Wildfire Games!


#8 Thanduel

Thanduel

    Discens

  • Community Members
  • Pip
  • 40 posts

Posted 20 January 2013 - 07:42 PM

Thanks, the PDF looks pretty good, with a few holes like a full explanation of the JPS* algorithm. But great that gives me a much better picture of what needs to be done. Indeed I will keep you posted, I can't promise I'll have time but it does look like time will be opening up.
  • 0

#9 quantumstate

quantumstate

    Primus Pilus

  • WFG Retired
  • 1,150 posts

Posted 20 January 2013 - 07:45 PM

Thanks, the PDF looks pretty good, with a few holes like a full explanation of the JPS* algorithm. But great that gives me a much better picture of what needs to be done. Indeed I will keep you posted, I can't promise I'll have time but it does look like time will be opening up.


If you want to learn more about JPS then this is a good source http://harablog.word...p-point-search/ . There is a link to a paper on that site as well.
  • 0

Jonathan Waller [ aka quantumstate ]

Wildfire Games Programmer
Contact me: jonathanmarkwaller at gmail dot com


Support Wildfire Games!


#10 fabio

fabio

    Centurio

  • WFG Programming Team
  • 651 posts

Posted 20 January 2013 - 08:30 PM

There are some interesting old posts about pathfinding work in this thread (the link should be the last one). The same posts are copied here (see starting from Feb 24, 2012 and older).
  • 0

Graphics problems with 0 A.D. under Ubuntu and free drivers? Check out the Updated and Optimized Graphics Drivers Archive: includes updated drivers with fixes and improvements for games, including 0 A.D..


#11 Thanduel

Thanduel

    Discens

  • Community Members
  • Pip
  • 40 posts

Posted 21 January 2013 - 08:01 AM

If you want to learn more about JPS then this is a good source http://harablog.word...p-point-search/ . There is a link to a paper on that site as well.


Thanks that is a great link.
  • 0

#12 sbte

sbte

    Tiro

  • Community Newbie
  • 1 posts

Posted 23 February 2013 - 06:36 PM

As a reply to the blog post, I am willing to help with any optimizations, but of course I do not want to do any work that has already been done. Since the last post in this thread is more than a month old, I was wondering what tasks are still available for a starting developer. As an alternative, maybe it'd be a good idea for me to find performance critical functions using profiling/callgrind and find something that is relatively easy to fix just to get started.
  • 2

#13 quantumstate

quantumstate

    Primus Pilus

  • WFG Retired
  • 1,150 posts

Posted 23 February 2013 - 07:09 PM

There has been no reported progress on the above things. I think you could fairly safely work on anything.
  • 0

Jonathan Waller [ aka quantumstate ]

Wildfire Games Programmer
Contact me: jonathanmarkwaller at gmail dot com


Support Wildfire Games!


#14 quantumstate

quantumstate

    Primus Pilus

  • WFG Retired
  • 1,150 posts

Posted 23 February 2013 - 07:16 PM

Another relatively easy but significant item is to make the sim interpolation only do work when an entity changes position. This saves doing calculations every frame for a load of trees and buildings. This will have a more significant impact now until the oct tree filtering for the sim interpolation gets implemented (since then the calculation can be avoided for everything which is not in sight), I still think it is worth having anyway though.
  • 1

Jonathan Waller [ aka quantumstate ]

Wildfire Games Programmer
Contact me: jonathanmarkwaller at gmail dot com


Support Wildfire Games!


#15 scroogie

scroogie

    Discens

  • Community Members
  • Pip
  • 73 posts

Posted 24 February 2013 - 09:42 AM

quantumstate: Wouldn't it be enough to implement a quadtree for the map/entities? Or would you need the 3rd dimension somewhere?
And could you elaborate the idea in your last post a bit? Isn't the sim interpolation also for calculating positions etc. (which would still be needed for units out of sight)? Sorry, but maybe others are also interested.

Edited by scroogie, 24 February 2013 - 09:54 AM.

  • 0

#16 quantumstate

quantumstate

    Primus Pilus

  • WFG Retired
  • 1,150 posts

Posted 24 February 2013 - 02:04 PM

Our terrain is 3d so unit positions do vary in z. The camera angle is changeable so that is properly 3D as well. Also using an octtree makes things more flexible if someone adds flying units. It would be possible to use a quadtree but I think it is simpler and more robust to use an octtree and performance should be good enough.

The game has the simulation which is network synchronised, this does all of the game play. The simulation is currently run 2/5 times per second (multi/single player). So this handles moving units from a gameplay perspective. Obviously 2 turns a second would look terrible so there is an interpolation layer so that the graphics system gets nice smooth movement. So since it is purely graphical it only needs to be done for stuff on the screen.
  • 0

Jonathan Waller [ aka quantumstate ]

Wildfire Games Programmer
Contact me: jonathanmarkwaller at gmail dot com


Support Wildfire Games!


#17 wraitii

wraitii

    Primus Pilus

  • WFG Programming Team
  • 1,664 posts

Posted 25 February 2013 - 06:19 AM

I'm not quite sure about the quad tree/octree thing. There might be a slight speed up which would be interesting to have.
As Philip said yesterday on IRC, we must be wary of the cost of updating entities in the octree. This could get high. Perhaps we could rather use an octree/quadtree with some added pointers to their direct neighbors, instead of having to go the long way in some cases. Would be longer at initializing but probably faster later on.
Basically we need to take into account that we're having an RTS with fairly small maps, not an FPS (for which octrees seem more fitting)
  • 1
Lancelot de Ferrière le Vayer [ aka Wraitii ]
Wildfire Games Programmer, AI developer, auxiliary map designer, dealing with anything water.
Contact me: wraitii@wildfiregames.com

Also the world's only three-dimensional poodle.

#18 plumo

plumo

    Primus Pilus

  • 0 A.D. Art Team
  • 1,004 posts

Posted 25 March 2013 - 12:02 PM

We need to bring this topic back into the spotlight.

(open) tickets related to performance optimisations:

http://trac.wildfire...com/ticket/1707
http://trac.wildfire...com/ticket/1878

For promotion: it would be interesting to know whether recent patches (from sbte) have improved the performance and if so, to what extent.
  • 0
B. Guns [aka Plumo]
0 A.D. Community Liaison
Contact email: plumo@wildfiregames.com

#19 fabio

fabio

    Centurio

  • WFG Programming Team
  • 651 posts

Posted 25 March 2013 - 03:21 PM

I did some test and yes, the sim interpolation improved quite a bit performance, at least when FPS is already good, with many units the bottleneck is somewhere (pathfinder) and the sim interpolation improvement become insignificant.

If you read this whole thread you'll find other open tickets, there is also this one not here: http://trac.wildfire...com/ticket/1860 .

There should be a performance page on wiki to have a page with updated information (I may do it if it's OK).
  • 0

Graphics problems with 0 A.D. under Ubuntu and free drivers? Check out the Updated and Optimized Graphics Drivers Archive: includes updated drivers with fixes and improvements for games, including 0 A.D..


#20 plumo

plumo

    Primus Pilus

  • 0 A.D. Art Team
  • 1,004 posts

Posted 25 March 2013 - 06:50 PM

I'll ask K776 to update the first thread. This information ought to get a wiki page, true. Ask someone on IRC?
  • 0
B. Guns [aka Plumo]
0 A.D. Community Liaison
Contact email: plumo@wildfiregames.com