Move list in stack vs heap ?

[Patrice Duhamel]

I have a class for staged move generation data and I declare an array of this class for each ply, in the engine class.
The informations in this class are used only for current ply and I could declare it inside the search function (allocated in stack).
But I found it's slower to declare it in the search function, why so much difference in speed between the two versions ?

Default position search to depth 20 :

version A : 3 470 138 N/s
version B : 2 736 985 N/s

Code: Select all

class ChessMoveOrder {
	u32 phase;
	u32 phaseNext;
	u32 ply;
	u32 position;
	u32 pos_capture;
	ChessMove moveHash;
	ChessMove moveKiller1;		
	ChessMove moveKiller2;
	u32 count;
	ChessMoveSort movelist[MAX_PLAY_MOVES];
	// ...		
};

/////////////////////////
// * version A :

class ChessEngine {
	// ...
	ChessMoveOrder moveOrderList[MAX_DEPTH];
	// ...
	int search(int alpha, int beta, int depth, int ply);
	// ...
};

int ChessEngine::search(int alpha, int beta, int depth, int ply)
{
	// ...
	moveOrderList[ply].init( ... );
	while ((movePhase = movegen.getNextMove(moveOrderList[ply], move)) != ORDERMOVE_END) {
		// ...
	}
	// ...
}

/////////////////////////
// * version B :

int ChessEngine::search(int alpha, int beta, int depth, int ply)
{
	// ...
	ChessMoveOrder moveOrder;
	moveOrder.init( ... );
	while ((movePhase = movegen.getNextMove(moveOrder, move)) != ORDERMOVE_END) {
		// ...
	}
	// ...
}

[AlvaroBegue]

I keep the staged move generation object in the stack, as in your version B, and I don't think it's slow at all.

How big is your class ChessMoveOrder?

[Patrice Duhamel]

How big is your class ChessMoveOrder?

ChessMoveOrder size is 2084 bytes.
(ChessMove is 32 bits, ChessMoveSort 2*32 bits, and MAX_PLAY_MOVES = 256)

[AlvaroBegue]

How big is your class ChessMoveOrder?

ChessMoveOrder size is 2084 bytes.
(ChessMove is 32 bits, ChessMoveSort 2*32 bits, and MAX_PLAY_MOVES = 256)

That seems reasonable. Are you by any chance doing needless work in the constructor (like memsetting the array) or in the destructor?

[Sven]

How big is your class ChessMoveOrder?

ChessMoveOrder size is 2084 bytes.
(ChessMove is 32 bits, ChessMoveSort 2*32 bits, and MAX_PLAY_MOVES = 256)

What does the constructor of class ChessMoveOrder do? Does it perhaps zero the whole move list array? In the latter case it would make the difference already since the constructor is run only once per array element in case of solution A, in contrast to once per node for B ...

(I now see that Álvaro has had exactly the same idea at the same time.)

[Patrice Duhamel]

That seems reasonable. Are you by any chance doing needless work in the constructor (like memsetting the array) or in the destructor?

No destructor, and the constructor is empty, I only use initialization list to set other variables to zero but do nothing with the list.

[kbhearn]

Do you have an initialiser list for ChessMoveSort? there are 256 of those every time you make a ChessMoveOrder - the constructor needs to be entirely empty including initialiser list.

[Patrice Duhamel]

Do you have an initialiser list for ChessMoveSort? there are 256 of those every time you make a ChessMoveOrder - the constructor needs to be entirely empty including initialiser list.

Yes, for ChessMoveSort and ChessMove, I didn't realized the cost of initializer list.

But now I have to fix some problems with non initialized value for these classes.

[kbhearn]

or you can keep your preallocated structures - there shouldn't be much of a cost to that - just a bit of unused memory between the depth your search reaches and MAX_DEPTH. since it's unused it won't be in cache.

[Patrice Duhamel]

or you can keep your preallocated structures - there shouldn't be much of a cost to that - just a bit of unused memory between the depth your search reaches and MAX_DEPTH. since it's unused it won't be in cache.

Yes I could do this, but for smp I will need to preallocate it for each threads, nothing to copy between threads but more wasted memory.