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.
In my program I used that vector for storing lists of moves. At allocation time I made sure that the vector was pre-allocating memory.
I replaced this yesterday with a custom MoveList class (with a static allocation of 218 moves) and lo and behold the most conservative speed-up of my chess program was 16%! That is amazing!
The code is as follows. I wonder if any of you has suggestions for improving it any further.
Oh the 218 moves: I googled that 218 is the maximum number of moves that can happen in a position.
Code: Select all
class MoveList
{
private:
Move moves[218];
int nIn;
public:
inline MoveList()
{
nIn = 0;
}
inline void clear()
{
nIn = 0;
}
inline void push_back(const Move & m)
{
moves[nIn++] = m;
}
inline const Move & at(const long unsigned int idx) const
{
return moves[idx];
}
inline void set(const long unsigned int idx, const Move & m)
{
moves[idx] = m;
}
inline size_t size() const
{
return nIn;
}
inline bool empty() const
{
return nIn == 0;
}
inline void erase(const long unsigned int idx)
{
long unsigned int n_to_move = (nIn - idx) - 1;
if (n_to_move > 0)
memmove(&moves[idx], &moves[idx + 1], n_to_move * sizeof(Move));
nIn--;
}
void sort(int (*compare_func)(const void *m1, const void *m2, void *arg), void *arg);
};
void MoveList::sort(int (*compare_func)(const void *m1, const void *m2, void *arg), void *arg)
{
if (nIn)
qsort_r(moves, nIn, sizeof(Move), compare_func, arg);
}