Performance issues

This is a discussion on Performance issues within the C++ Programming forums, part of the General Programming Boards category; Hello there! Long story short -- I'm currently working on project where I have to implement simple board game and ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    42

    Performance issues

    Hello there!
    Long story short -- I'm currently working on project where I have to implement simple board game and few algorithms working with it. One of first things I had to write was movements generator (which is supposed to find all possible moves from given game state, possible to do by selected player).
    Problems started when I began using it to generate quite large amounts of moves... say 100'000. It was running incredibly slow... To start off, I removed widely used vectors, like this:

    Code:
    vector <OldGameStateClass*>* stateHolder;
    ...and replaced it with linked list class like this:

    Code:
    class GameState {
    private:
    	int value;
    	signed char** currBoard;
    	GameState* childrenList;
    	GameState* nextElem;
    };
    This class holds pointer to next element (another move reachable from parent level) and also pointer to new list (children), moves available from this given game state.

    It slightly improved whole generator, but it was still too slow.

    Later, I changed ints to signed chars, as I was copying arrays very often -- it also helped a bit. Doing some tests later, I've found out copyBoard method was being major reason of time consumption.
    And this is how it looks:

    Code:
    signed char** copyBoard(signed char **currBoard)
    {
    	signed char **board = new signed char*[13];
    	for (int i = 0; i < 13; i++) {
    		board[i] = new signed char[8];	
    		for (int j = 0; j < 8; j++)
    			board[i][j] = currBoard[i][j];
    	}
    	return board;
    }
    Generating 100'000 moves also means memory has to be allocated 100'000 times and values copied (but this doesn't seem to be much of a problem, it's rather memory allocation that is slow).

    Are there faster ways of doing such? Or perhaps I should use different way of storing data (static arrays in class maybe?)?
    Also, is there a way to make vector less slow? The whole push_back operation seems to take a lot of time, but using vector is quite comfortable. I also tried to use deque, but it seemed slow too.

    If anybody had similar problems or knows best way of storing & copying many small game boards - I'll be thankfull for any help :-)
    Last edited by jimzy; 09-11-2007 at 03:50 PM.

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by jimzy View Post
    If anybody had similar problems or knows best way of storing & copying many small game boards - I'll be thankfull for any help :-)
    Why copy the board at all? In all the minimax games I've ever written, I did move generation by temporarily modifying the board, then changing it back. If you remember what move you just made, it's pretty easy to undo it.

    I never had zillions of copies of boards flying around...

    EDIT: Also, vector.push_back should not be slow. Why do you believe that it is?

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    42
    Quote Originally Posted by brewbuck View Post
    Why copy the board at all? In all the minimax games I've ever written, I did move generation by temporarily modifying the board, then changing it back. If you remember what move you just made, it's pretty easy to undo it.
    I've been thinking about that too... but been too busy with debugging generator xP. Well, it seems to be best solution I got so far.

    Quote Originally Posted by brewbuck View Post
    EDIT: Also, vector.push_back should not be slow. Why do you believe that it is?
    In the very early debugging part (when I didn't yet know it's about memory allocation), I've been googling for push_back performance, and somebody posted that vector reallocates whole memory from time to time (once the default memory it has gets used up, it frees whole memory it used and reallocates new, bigger memory chunk -- that's what more or less person was saying).
    Anyways, I replaced to linked list, which seemed to be little gain on time, not too big though :x

    One more thing, will the whole saving moves, updating, undoing and so on be faster in the end than allocations (guess I can test it on my own anyways)?

    Thanks brewbuck :-)

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    Read this from Stroustrup. In particular, look at the last paragraph of that section.

    http://www.research.att.com/~bs/bs_f...low-containers

    Of course, if std::list proves to be faster for your application by all means use it.

  5. #5
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by jimzy View Post
    In the very early debugging part (when I didn't yet know it's about memory allocation), I've been googling for push_back performance, and somebody posted that vector reallocates whole memory from time to time (once the default memory it has gets used up, it frees whole memory it used and reallocates new, bigger memory chunk -- that's what more or less person was saying).
    That's pretty much correct, but it doesn't have as big of an impact as you might think. When the vector grows, it DOUBLES in size (or by some other constant factor), it does not expand linearly. This amortizes the inefficiency over time, making the operation just a tad bit worse than O(1).

    Another important thing to remember with vectors is to pre-allocate if possible. If you know, for instance, that the vector will hold anywhere from 1 to 1000 elements, then when you create the vector in the first place, allocate enough space for 1000 elements. This guarantees it will never have to expand:

    Code:
    std::vector<whatever> big_vector(1000);
    Anyways, I replaced to linked list, which seemed to be little gain on time, not too big though :x
    A linked list supports O(1) insertions at the end, so it is theoretically more efficient than a vector in that regard. But there are always tradeoffs. A vector holds its data contiguously in memory, but the elements of a linked list could be scattered all over the place. This can lead to poor performance in itself, by reducing the efficiency of the CPU's memory cache.

    One more thing, will the whole saving moves, updating, undoing and so on be faster in the end than allocations (guess I can test it on my own anyways)?
    Unless the moves are terribly complex, it is almost guaranteed that "doing/undoing" is faster. Store the move data in a class called Move, or something, and make sure you store enough information to undo the move. For instance, if you're talking chess, you'd just store the move as it is normally annotated -- where the piece came from, and where it went to.

    Thanks brewbuck :-)
    I love coding zero-sum games. What game is this? A 13x8 board?

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Don't allocate the board as an array of pointers to arrays of values. Allocate one block of memory and do the offset transformation yourself, or use a Boost.Multi_Array to do it for you.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    42
    @Daved: thanks for the link :-)

    I assume I should use reserve() then -- I can estimate the size of vector that will be needed (if I decide to switch back to vectors that is).


    Quote Originally Posted by brewbuck
    Unless the moves are terribly complex, it is almost guaranteed that "doing/undoing" is faster. Store the move data in a class called Move, or something, and make sure you store enough information to undo the move. For instance, if you're talking chess, you'd just store the move as it is normally annotated -- where the piece came from, and where it went to.
    They aren't. Mostly moving to adjacent cells / sliding, most complex are beatings (especially multiple). Oh, and the board is 11x6 in fact, I'm using 13x8 to create border... some way of preventing checking index out of range every time.
    And the game is Bivouac. Some resources incase you'd be interested:
    http://www.zillionsofgames.com/cgi-b...do=show;id=113
    http://www.di.fc.ul.pt/~jpn/gv/bivouac.htm

    @CornedBee: what's the gain if I do so? You mean if I keep copying the board, or I should use such array anyways?

    Thanks for replies guys!

  8. #8
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    You should definately do/undo moves on one board instead of allocating new boards if that's what you're doing.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    And if you MUST copy the board for some reason, make sure your board is one contiguous 2D array in memory, that way, you can copy it using memcpy, which is probably 3-5 times faster than your method.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Nov 2006
    Posts
    42
    @matsp: thanks for the tip.

    As suggested, I gave up using whole boards, and created Move class which looks like this:

    Code:
    class Move {
    private:
    	int oldX;
    	int oldY;
    	int newX;
    	int newY;
    	Move* parentMove;
    	Move* beatenPawns;
    	vector <Move*>* chlidrenMoves;
    };
    And did some first performance tests. Like previously, I've been generating 100'000 new game states.
    Using std::list -- 7000 ms.
    Using std::vector (with reserve() call) -- 5000 ms.
    And using my custom linked list class described in first post it took 1500 ms.
    Both vector and list push_back are slower it seems, so guess I'll stick to list.

    Maybe I should also remove vector (considering push_back will be used there aswell) from Move class and replace it with list..?

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If there is such wild difference between std containers and your custom linked list, are you sure that a) you are timing them with an optimized build (std containers can benefit very much from compiler optimizations), b) your own linked list implementation is working properly (e.g no memory leaks etc), c) you were not seriously misusing std containers (e.g telling vector to resize each time you added something)? In addition it seems that std containers held different classes in your earlier code, and it's not clear why they would hold pointers instead of the object itself (it goes into heap memory one way or another).

    The greatest optimization, of course, would be not to generate 100 000 game states...
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Registered User
    Join Date
    Nov 2006
    Posts
    42
    Quote Originally Posted by anon View Post
    The greatest optimization, of course, would be not to generate 100 000 game states...
    Well, I did that to see which container is best... generating smaller numbers might not be easy to measure.

    Anyways, while designing new classes for moves and so on, I run into quite silly problem.. and for some reasons i can't go past it. Say we got 2 classes:

    Code:
    class A {
      B* cB;
    }
    
    class B {
      A* cA;
    }
    How to fix headers to make it work?

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by jimzy View Post
    Anyways, while designing new classes for moves and so on, I run into quite silly problem.. and for some reasons i can't go past it. Say we got 2 classes:

    Code:
    class A {
      B* cB;
    }
    
    class B {
      A* cA;
    }
    How to fix headers to make it work?
    use:
    Code:
    class B;  // Tell the compiler "We will have a class B - tell you later what it contains".
    
    class A {
       B* cB;
    };
    
    class B {
      A* cA;
    };
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Registered User
    Join Date
    Nov 2006
    Posts
    42
    Ahh... thanks a lot matsp, knew it was going to be silly

  15. #15
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    by the way: would that forward-method also work if the remote classes are used as template arguments, for example in case he would use

    Code:
    class A {
      auto_ptr<B> cB;
    }
    
    class B {
      auto_ptr<A> cA;
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Performance and footprint of virtual function
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-31-2008, 06:34 PM
  2. File map performance
    By George2 in forum C++ Programming
    Replies: 8
    Last Post: 01-04-2008, 03:18 AM
  3. Observer Pattern and Performance questions
    By Scarvenger in forum C++ Programming
    Replies: 2
    Last Post: 09-21-2007, 11:12 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. inheritance and performance
    By kuhnmi in forum C++ Programming
    Replies: 5
    Last Post: 08-04-2004, 12:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21