std::vector<> considered harmful

[flok]

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.

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);
}

[kinderchocolate]

Well, each operation to std::vector involves a copy operation. It's only efficient if T is a primary type. I also did a simple static allocation of arrays of moves. Simple and much faster.

[BeyondCritics]

Hi Folkert,

thank you for sharing, but frankly i don't got the point. Could you point out the difference, why do you think std:vector is slow in this case?
Thank you

[jdart]

stl::vector does dynamic memory allocation. So replacing it with a fixed allocation on the stack will be faster.

I use my own <vector> replacement (https://github.com/jdart1/arasan-chess/ ... /arasvec.h) largely for historical reasons, but it's not used in time-critical code: it stores the global list of moves made in the game, for example. I use straight arrays in the search.

--Jon

[flok]

stl::vector does dynamic memory allocation. So replacing it with a fixed allocation on the stack will be faster.

Well that is true normally but after instantiating the vector object, I used to call reserve() on it so that it did not need to constanly call realloc on it.

[Bloodbane]

Did you do something like this:

std::vector<Move> moveList(128);

or something like this:

std::vector<Move> moveList;
moveList.reserve(128);

There can be a big difference between them, depending on if Move(or whatever the vector consists of) is initialized or not. Still, that's probably going to be slower than the custom MoveList.

EDIT: and the answer comes two minutes before I post my message, brilliant.

[flok]

thank you for sharing, but frankly i don't got the point. Could you point out the difference, why do you think std:vector is slow in this case?
Thank you

I'm not sure. Maybe because it calls the constructor of each element that it adds (but I'm adding structs so not likely to be that problem) or maybe the reserve() is a no-op and it is doing a realloc with one more element, frankly I don't know.

http://stackoverflow.com/questions/3664 ... ain-arrays

[AlvaroBegue]

There is no mystery here. std::vector will always use dynamic memory allocation. If you use `reserve' at the beginning you won't need any reallocations, but you still need the one dynamic memory allocation. Besides the cost of allocating and freeing memory, you may also end up with worse cache coherence than if your move list lived on the stack.

The only place where I use std::vector in my engine is in the transpositions table. I certainly don't do any dynamic memory allocation in the search functions, because it is expensive and because it is not needed.

[BeyondCritics]

To be sure you could use e.g. Zoom (http://www.rotateright.com/) or Callgrind and then compare the differences on differenct sources.
Many would be interested...

[Henk]

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)