Author Topic: Memory problem in new path finder  (Read 1778 times)

daniel.santos

  • Guest
Memory problem in new path finder
« on: 12 September 2009, 21:23:05 »
I ran into this when working on 0.2.12 and I noticed a compiler warning.  It's basically using the address of a temporary object beyond the lifetime of the temporary object.  Here's the patch:

Code: [Select]
Index: source/glest_game/path_finder/annotated_map.cpp
===================================================================
--- source/glest_game/path_finder/annotated_map.cpp     (revision 187)
+++ source/glest_game/path_finder/annotated_map.cpp     (working copy)
@@ -92,7 +92,8 @@

        // the cell to the nothwest...
        Vec2i *corner = NULL;
-       if ( pos.x-1 >= 0 && pos.y-1 >= 0 ) corner = &Vec2i(pos.x-1,pos.y-1);
+       Vec2i defaultCorner(pos.x-1,pos.y-1);
+       if ( pos.x-1 >= 0 && pos.y-1 >= 0 ) corner = &defaultCorner;

        for ( int i = 0; i < size; ++i ) {
                // Check if positions are on map, (the '+i' components are

silnarm

  • Local Moderator
  • Behemoth
  • ********
  • Posts: 1,373
    • View Profile
Re: Memory problem in new path finder
« Reply #1 on: 13 September 2009, 00:33:48 »
I ran into this when working on 0.2.12 and I noticed a compiler warning.  It's basically using the address of a temporary object beyond the lifetime of the temporary object.  Here's the patch:

If I had formatted that code properly, I reckon I might have noticed that! ;)
Glest Advanced Engine - Code Monkey

Timeline | Downloads

daniel.santos

  • Guest
Re: Memory problem in new path finder
« Reply #2 on: 14 September 2009, 00:23:06 »
hehe, no problem, we'll get there. :)  I know I'm a stickler about stuff like that, but it's only due to what I've learned from experience.  I don't know that "defaultCorner" is the best description for that, you would know what to call it more. 

Also, I'm going to add some type of "language.h" to the shared_lib if there isn't already something similar, to encapsulate non-standard language extensions and various extensions from different language versions (like the DELETE_FUNC macro) and I'm going to add "likely()" and "unlikely()" macros to encapsulate GCC's branch optimization annotations.  It basically tells the compiler if a branch is likely or not.  Using it will optimize the likely condition, but make the unlikely condition less modified.  The only draw-back is that if you use it incorrectly, it will slow down your code.  I believe it works by putting grouping the unlikely code in an object file somewhere to keep it from getting loaded and cached by the CPU, (unless it's invoked, of course) thereby leaving more of the CPU's cache filled with code you are actually executing.  The Linux kernel does this as well.  But for something as CPU intensive as the pathfinder, this should be able to speed it up where there are conditions that rarely occur.  And if you ever have any doubts about the effect of the CPU cache, just go into your BIOS some day and turn it off and see how long it takes to start your OS (any OS)!  I did this once when troubleshooting hardware problems, yikes!

I still haven't read what you've posted about all of this pathfinder stuff and the annotated map, but it looks very interesting.  And one more thing, in regards to what you said in IRC about stability, yea it sucks arse! =)  If we don't include multi-player, I think we were stable in 0.2.11b or something like that, but multi-player is a pretty big deal -- and I've never had that working correctly, LOL!

I worked some on the save game issue, and I'm a bit confused as to what is happening where.  I re-wrote the entire GameSettings class in the (now) "network" branch, so I'm having to think back an iteration.  It has both a map and mapPath data member -- I presume "map" is supposed to be the base map name while mapPath is supposed to be the relative path to the file.  The same is true for tileset and techTree.  Then we come along and add "scenario" and "scnarioDir", there by totally screwing the previous schema.  So it turns out that mapPath had the base map name and everything was screwed around.  I still have to figure out how all of that happened and we need to have one schema or the other, but not both, present, as it is reasonable to have a mod, with it's own directory that has it's own maps, scenarios, tilesets and techtree(s?) and even mods that have dependencies upon other mods, and will refer to their maps, scenarios, tilesets and techtrees.  Then, if we implement Lua-based AIs, they can have maps, scenarios, tilesets, techtrees and AIs.  (I like typing things out a lot of times, can you tell?)  Then if we add customizable geological data (for substances) then we have maps, secnarios....... =)


silnarm

  • Local Moderator
  • Behemoth
  • ********
  • Posts: 1,373
    • View Profile
Re: Memory problem in new path finder
« Reply #3 on: 15 September 2009, 22:47:50 »
hehe, no problem, we'll get there. :)  I know I'm a stickler about stuff like that, but it's only due to what I've learned from experience.  I don't know that "defaultCorner" is the best description for that, you would know what to call it more.  

It's nice to have 'a stickler' looking over it :) The more critical eyes the better, I say.  I ended up going with 'cornerHolder', it could have just been 'corner' the whole time of course, and then set to -1,-1 when not of interest anymore.  But I obviously felt compelled to use a pointer... old habits die hard :)

Regarding the Cache, I'm very aware of it's importance, the path finder's storage was designed to be a compact as possible... however, you got me thinking about it, and I have the data interleaved, the clearances for all fields are stored for a cell together, I should have a very compact array for each field instead, as a single search is only interested in one field.

The branch prediction stuff will be interesting, though I'm not sure the path finder will benefit greatly. Also, we have a bunch of virtual functions getting in the way... the model renderer for example is abstract, virtual functions make predictive execution stop in it's tracks.  Something to be aware of.  In our case we have only one 'concrete' ModelRender Class anyway, ModelRenderGl, so it may be worth our while removing the virtual calls, obviously rendering models is something we do a bit of :)

Quote
I still haven't read what you've posted about all of this pathfinder stuff and the annotated map, but it looks very interesting.
The old topic probably doesn't actually explain that much about the new system, I started writing out an explanation of how it all works a few days ago, I'll finish that up soon and post it to the wiki.

Quote
...  I still have to figure out how all of that happened and we need to have one schema or the other, but not both, present, as it is reasonable to have a mod, with it's own directory that has it's own maps, scenarios, tilesets and techtree(s?) and even mods that have dependencies upon other mods, and will refer to their maps, scenarios, tilesets and techtrees...

Sounds good, a more functional GameSettings object would also make me feel better about it actually being a class... I remember reading about the 'new game settings model' a while back, I'll have to have a good look at the network branch some time...

Edit:
Looks like I can return the favour ;)

Compiling the network branch I got an interesting warning, "warning C4804: '>=' : unsafe use of type 'bool' in operation"

server_interface.cpp(59) :
if(!getPeers().size() >= GameConstants::maxPlayers) {


'not' has a higher precedence than the other logical operators, you need another set of parenthesis :)
« Last Edit: 15 September 2009, 23:57:00 by silnarm »
Glest Advanced Engine - Code Monkey

Timeline | Downloads

daniel.santos

  • Guest
Re: Memory problem in new path finder
« Reply #4 on: 17 September 2009, 22:01:42 »
Edit:
Looks like I can return the favour ;)

Compiling the network branch I got an interesting warning, "warning C4804: '>=' : unsafe use of type 'bool' in operation"

server_interface.cpp(59) :
if(!getPeers().size() >= GameConstants::maxPlayers) {


'not' has a higher precedence than the other logical operators, you need another set of parenthesis :)
good catch! =)

... I ended up going with 'cornerHolder', it could have just been 'corner' the whole time of course, and then set to -1,-1 when not of interest anymore.  But I obviously felt compelled to use a pointer... old habits die hard :)

Regarding pointers, I have no problem with this where performance is at issue.  I prefer references to pointers, but this is only feasible where you will continue to reference the same object throughout a function call or code block.  Otherwise, use a pointer.  Copying a pointer is always 1 or 2 instructions.  Copying an object (even small) is rarely that few.  However, if the function is called a lot, you can make cornerHolder "static const" so it's only allocated once (and const so you don't accidentally change it :).

But then I will quote two oft stated statements (that repetition was redundant huh? :) "First make it right, then make it fast" and "85% of your CPU is spent in 5% of your code" (or some such).  So only worry about tweaking the high-use stuff and if the rest is a bit flabby, that's probably OK.  It's often a trade-off between beauty of design and performance.  Optimizations can be ugly and if we take a few more bytes & CPU cycles for code that doesn't execute a lot, then the flabbiness is OK -- especially if the trade-off is a cleaner design, which results in higher maintainability (i.e., it's easier to understand and modify and harder to make an error when it is modified).

One prime example (that I still tend to get fussy about) is exception handlers:  they very seldom execute and can therefore be fat and slow.  I know I tend to scoff at operator+(std::string, std::string) because it's flabby, but it really doesn't matter in exception handlers and I'll try to chill out on that.  The only thing about using string's operator+ is that we end up having to call our own custom conversion functions and I would rather use iostreams for that since it handles it so well.  The draw back of that is that it takes 3 lines of code where operator+ can be hacked together in one.

EDIT: Another area of note is that my network code makes use of a lot of virtual function calls.  I don't care here because network data is only handled a few times a second, and it's not time critical (as long as it doesn't bloat in size unnecessarily).  The ObjectPrinter stuff is something that I may encapsulate in some pre-processor #if/#endif however, and leave them empty in-line implementations (i.e., "compile them out") if some value is set when compiled because that does add measurable bloat.  On the other hand, it will greatly aid in troubleshooting network problems in the initial stages of this new network code, so I don't plan on releasing the 1st time with that compiled out. :)

Sounds good, a more functional GameSettings object would also make me feel better about it actually being a class... I remember reading about the 'new game settings model' a while back, I'll have to have a good look at the network branch some time...

Well, I just hope I don't revisit my new GameSettings and decide that it's crap! lol!  I remember it not feeling very flexible when I was done, but I haven't looked at it closely in the last several months.  One of the paradigms that I remember it following correctly was de/serialization to/from XML -- that makes it work both accross the network and for saved games.  At currently, there is still far too much data being sent as zlib-compressed XML, but the idea here is that it's easy to troubleshoot and debug and that the fat part (unit updates & the like) can later be implemented using a binary protocol that's much tighter -- after the major flaws are resolved.

I need to regenerate the Doxygen docs (with the cute UML diagrams), but in essence, the new GameSettings consists of (in summary):

Code: [Select]
class GameSettings : public XmlWritable, Uncopyable {
public:
    typedef map<int, shared_ptr<Player> > PlayerMap;
    class Team : public IdNamePair, Uncopyable { ... }
    typedef vector<shared_ptr<Team> > Teams;
    class Faction : public IdNamePair, Uncopyable { ... }
    typedef vector<shared_ptr<GameSettings::Faction> > Factions;

private:
    PlayerMap players;
    Teams teams;
    Factions factions;
}

players is a map of all players, indexed by their player ID (I think the server is always zero or some such) including computer players.  Game::Player is an abstract base class with Game::HumanPlayer and Game::AiPlayer subclassing it and the human player "has a" Game::Net::NetworkInfo object (unless you're playing a local game).  Then the GameSettings has a list of teams (Game::GameSettings::Team) and factions (Game::GameSettings::Faction).  So a game must have at least one team, although less than two teams isn't very useful out side of scripting some cut scene in a campaign or some such.  Then each faction belongs to exactly one team.  However, a player can control zero or more factions (zero if they are an observer/spectator) and each faction must be controlled by at least one player.  This allows a game setup where people can share control of their faction with others, have two human players controlling the same faction or even share control with an AI.

While I think this design encompasses a lot of possibilities, I don't think the implementation is especially flexible, and that may be OK.  What I think is needed to take it to the next level, however, is for GameSettings (along with it's teams, factions, players (both Human and AI)) to contain arbitrary name/value pairs, vectors and maps based upon a given mod -- but I'm not worrying about that for now.

In short, I think it's a good step forward, but will also have to be revisited a number of times.

EDIT: OK, sorry for the long post.  I also wanted to mention that shared_ptr is a new thing in my repertoire and I've learned that it's quite the valuable pattern.  It essentially allows you a lot of flexibility on when an object is allocated and who will de-allocate it and solved a lot of the problems I had as a result of not wanting to implement a copy constructor for GameSettings (since I thought it was wasteful -- maybe I was being too picky :).
« Last Edit: 17 September 2009, 22:14:19 by daniel.santos »

silnarm

  • Local Moderator
  • Behemoth
  • ********
  • Posts: 1,373
    • View Profile
Re: Memory problem in new path finder
« Reply #5 on: 18 September 2009, 12:25:35 »
But then I will quote two oft stated statements (that repetition was redundant huh? :) "First make it right, then make it fast" and "85% of your CPU is spent in 5% of your code" (or some such).  So only worry about tweaking the high-use stuff and if the rest is a bit flabby, that's probably OK.  It's often a trade-off between beauty of design and performance.  Optimizations can be ugly and if we take a few more bytes & CPU cycles for code that doesn't execute a lot, then the flabbiness is OK -- especially if the trade-off is a cleaner design, which results in higher maintainability (i.e., it's easier to understand and modify and harder to make an error when it is modified).
Too true. I've been testing and profiling a lot recently, the path finder isn't actually consuming that much time "all-up", but a flood of requests can kill it, we could have just managed the path calculations, so some units would have to wait a few frames until they got their path... but then I remembered something... (I do that too! I probably forget more, but I remember a few things along the way ;) )

It's a classic case of thinking outside of the box. David Silver's paper on 'Cooperative A*' contains the gem, I can't believe I didn't realise it's true value earlier... Reverse Resumable A*. Details in a new topic very soon, I've already started rewriting... but as you'll soon see, this should be last time... the search algorithm is templated on Goal, Cost, & Heuristic functions.  With the reverse resumable A* 'adapter' on this, we can calculate 'group' paths (or at least paths for many units to the same destination) cheap as chips!

Quote
EDIT: Another area of note is that my network code makes use of a lot of virtual function calls.  I don't care here because network data is only handled a few times a second, and it's not time critical
Yeah, network is no problem there, I'm all for polymorphic objects generally, indeed I've added virtual function calls for command updates in the refactor branch, but for time sensitive stuff like the renderer it would be best to remove it.  The renderer of course has other issues, of which my recent testing and profiling has revealed some interesting things... more on that soon too.

The GameSettings would be nice to sort out, there are a few messy areas actually  :-[ Hopefully we can sort that out this weekend, and get a 0.2.12a out... 0.2.13 could probably follow shortly there after, with all the new Lua goodies.
Glest Advanced Engine - Code Monkey

Timeline | Downloads

daniel.santos

  • Guest
Re: Memory problem in new path finder
« Reply #6 on: 18 September 2009, 18:54:20 »
I've got the bulk of the ugliness in GameSettings (in 0.2.12) sorted out and I'm just tending to the aftermath now.  I replaced scenario and scenarioDir with scenarioPath and I removed map, tileset and tech, leaving mapPath, tilesetPath and techPath, so that GameSettings will only store the full relative path (from the game base) to each of these objects.  I refactored up the shared_libs util.h/cpp renaming lastDir to basename, cutLastFile to dirname and eliminating cutLastDir (which just called cutLastFile), thus following at least the POSIX standard names for these functions.  So now, whenever you need to derive the directory or the base name from the full path, you can just call one of these functions (there's another function to remove the extension).

 

anything