flok wrote:Hi,
I always thought that std::vector<> would have some overhead but probably not beyond the noise-factor. While profiling my chess program using valgrind I saw that my "addMove" method used quite a bit of cpu-time. So I did some googling and found reports on stackoverflow that in some cases std::vector<> indeed is a bit slow.
I did make some measurements a few years ago on the performance of std::vector vs builtin arrays:
http://talkchess.com/forum/viewtopic.php?t=39934
Currently I am using Howard Hinnant's stack allocator:
http://howardhinnant.github.io/stack_alloc.html (note this is C++11 code, and probably won't work out-of-the-box on non-Linux compilers. I could help you out if you get stuck on Visual C++ with this code).
The idea behind it is to allocate a stack-based array of compile-time size, pass that array (called an "arena") to a special allocator. This allocator is in turn passed to the constructor of the std::vector containing the move lists.
As you know, std::vector has a hidden template parameter that defaults to std::allocator that does dynamic memory allocation. Passing the stack allocator with the arena object to the vector will override the library default. What then happens is that all moves will be placed inside the stack-based arena until that is exhausted. When that happens, the allocator will use dynamic allocation to add further moves. You should still use the reserve() function to avoid reallocations within the arena.
What I do in my draughts engine is to make the arena large enough to hold the number of moves in 99% of all nodes. This will give a performance that is very close (~5%) to a purely array based solution. For regular chess, an array with 218 moves is probably better, but I have a draughts engine that plays on arbitrary large boards, and there the added safety of doing dynamic initialization
for very large move lists only, is a nice benefit.