1

I am making a chess engine, and have hit a brick wall with optimization. After using a profiler, I have found that the move generation is the biggest factor. When I looked closer, it turned out that a large portion of time generating moves was spent calling std::vector.push_back(move) when I had found a move.

Is there a way to have a dynamically sized c++ container that is fast? It can't be a fixed size array, as I have no way of knowing ahead of time how many moves will be generated (although there are usually less than 50).

Does anyone have experience with this sort of issue? I would write my own container if necessary, but I feel like there should be an standard way of doing this.

Lukas Schmit
  • 1,118
  • 2
  • 9
  • 14
  • The answers should lead you into the right direction. The issue with profilers is sometimes that you only see which methods get called most but not why, maybe you can reduce the number of push_backs overall before trying to optimize the container. You can also have a look here to get some infos about the insert and its complexity: http://www.cplusplus.com/reference/vector/vector/push_back/ – Excelcius Jan 13 '14 at 06:10
  • How big is `move`? Is the cost in copying it into the vector? – Ben Jackson Jan 13 '14 at 06:13
  • A move really should fit in 32 bits, although you should have a `class Move` which wraps that in a much nicer interface. Even with that interface, `Move::Move(Move const&`)` would still be just a copy of a `long`. – MSalters Jan 13 '14 at 10:40
  • If moving 50 elements in a vector takes long (*"hit a brick wall"*) then I would look into the move / copy constructor of the elements and fix that. It sounds like a design issue with the elements and not with `std::vector`. – Ali Jan 13 '14 at 11:39

5 Answers5

4

Call std::vector::reserve() with adequate size before the following push_back() calls to avoid memory re-allocation again and again.

timrau
  • 22,578
  • 4
  • 51
  • 64
  • Wouldn't reserving more than I need in the vector result in eating up a lot of memory though? – Lukas Schmit Jan 13 '14 at 05:44
  • Yes, so you should trade off between runtime to reallocate memory and extra memory consumption. Make sure you don't reserve _much_ more then you need. Also, you could compact the extra memory by [Shrink-to-fit idiom](http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Shrink-to-fit) after all the push_backs. – timrau Jan 13 '14 at 05:47
  • 1
    Oh, so with c++11 I could use shrink_to_fit() once I finished my push_back()'s? – Lukas Schmit Jan 13 '14 at 05:55
  • @LukasSchmit You can try `shrink_to_fit`, but don't be surprised if it doesn't have much (or any) effect. Note that if you always reserve() to the average size, the total memory requested may only increase by a maximum factor of 2. That's usually acceptable, it's a worst case. – Potatoswatter Jan 13 '14 at 06:21
  • @LukasSchmit: That's an expensive call - it would copy all elements if a smaller memory block is allocated. It's useful if you're going to keep that block of memory for a long time, but your moves will become outdated in one turn anyway. – MSalters Jan 13 '14 at 10:37
  • After trying it, it seems that reserve() helps a lot. Getting rid of this overhead has showed me other bottlenecks, and allowed me to move ahead with optimization. Thanks a ton! – Lukas Schmit Jan 14 '14 at 01:19
1

  1. Vector::reserve() helps. You can try to profile and see the distribution of number of moves, and try to reserve an optimal number in advance. Don't worry about memory waste because when you have 32 - 50 moves, the memory reserved might be 64, and there's a waste of 14 - 32. So reserve a memory of 8 or even 16 may not take much more memory.

  2. Do you need to access moves by index? why not use std::list?

  3. Or you can try to push_back a shared_ptr of a move, and then reserve some number in advance, there will be less memory waste.

user534498
  • 3,926
  • 5
  • 27
  • 52
1

Did you try profiling with std::deque? If you've no requirement that the objects be allocated in a contiguous fashion, then it might be an optimal solution. It provides constant time insert and erase to the front; usually std::deque is preferred if you need to insert or erase at both ends of the sequence.

You can read the details in GotW 54.

legends2k
  • 31,634
  • 25
  • 118
  • 222
0

You can use std::vector and call its reserve method at appropriate places.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
0

I use this method of profiling.

It doesn't surprise me that push_back is a big time-taker, and reserve should fix that.

However, if you profile again, you might find something else is the big time-taker, such as calls to new and delete for your move objects.

Fix that (by pooling), and do it again. Now, something else will be big.

Each time you do this, you get a speedup factor, and those factors multiply together, until you will be really pleased with the result.

Community
  • 1
  • 1
Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135