std::vector<> considered harmful

[AlvaroBegue]

In C# is use List<> for the move list. Should be equivalent to a generic array. To add a move to the list I use List<MoveBase>:Add(move)

I know close to nothing about C#, but a quick web search seems to indicate that using List in C# is the equivalent of using std::vector in C++. If you indicate the desired capacity for your List at construction time, then you are doing essentially the same thing as the original code with std::vector that is being discussed in this thread.

Alternatively, you could use an Array, which has a fixed size, but I am afraid that also requires dynamic memory allocation. I expect the performance will be very similar.

Unfortunately, I don't think C# allows you to use an array on the stack, so the speed improvement we are talking about here is not available to you.

[jdart]

Still, even calling malloc() once per construction will cost you.

--Jon

[flok]

Still, even calling malloc() once per construction will cost you.

--Jon

Yeah what I do: I have a stack of states (for the do/undo move). Instead of free/malloc, I have an index that I lower and higher. Then there's a try/catch around the code that automatically increases the stack-size if there's an out-of-bound access. This greatly improved the speed.

[Rein Halbersma]

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.

[syzygy]

I wonder if any of you has suggestions for improving it any further.

Do not allocate any objects at all within your search. It is extremely predictable what memory the search will need, so just make sure it fits in the static arrays you allocate at program initialisation.

The exception is static arrays or objects you might want to allocate on the stack. That is basically free. Maybe you do that with your MoveList objects, but I suspect you don't.

Your erase() method is a bad idea. Whatever you need it for, there is a better solution not involving a memmove().

[flok]

I wonder if any of you has suggestions for improving it any further.

Do not allocate any objects at all within your search. It is extremely predictable what memory the search will need, so just make sure it fits in the static arrays you allocate at program initialisation.

Yeah those arrays are only allocated at the start of an iteration in iterative deepening.

Your erase() method is a bad idea. Whatever you need it for, there is a better solution not involving a memmove().

What I do is: first I create a list of all possible moves in a positition. Then I go through them and remove the ones that are not valid (e.g. stay in check or move to check).
Thanks putting this under attention because only now I realise I could also just move the last in the list to the position I want to remove! (as it gets sorted later on anyway)

[flok]

Your erase() method is a bad idea. Whatever you need it for, there is a better solution not involving a memmove().

What I do is: first I create a list of all possible moves in a positition. Then I go through them and remove the ones that are not valid (e.g. stay in check or move to check).
Thanks putting this under attention because only now I realise I could also just move the last in the list to the position I want to remove! (as it gets sorted later on anyway)

5% improvement!

[syzygy]

Your erase() method is a bad idea. Whatever you need it for, there is a better solution not involving a memmove().

What I do is: first I create a list of all possible moves in a positition. Then I go through them and remove the ones that are not valid (e.g. stay in check or move to check).
Thanks putting this under attention because only now I realise I could also just move the last in the list to the position I want to remove! (as it gets sorted later on anyway)

5% improvement!

Told you

[Volker Annuss]

Your class MoveList has a method push_back, so I assume, you also used std::vector::push_back.
Although you pre-allocated your memory, every time you insert a move into the vector, the code has to check if the size is sufficient.

[Aleks Peshkov]

No need to use legacy C-code, use std::array<>.