Using piece lists to generate moves

[bhlangonijr]

I had some spare time in the Christmas and tried to squeeze some speedup in the move generation function of my engine. So I did that almost the same way Stockfish does:

Code: Select all

pieceList[color][piece_type][16]

In my case I have an enumeration with color and piece type (ex.: WHITE_BISHOP) and the array look like:

Code: Select all

pieceList[piece_type_and_color][16]

I've added into the doMove() and undoMove() functions a minimum amount of code necessary to keep the array update (2 lines of code in each one). Then I changed all move generation functions to use the piece lists for iterating though the pieces in the board:

Code: Select all

                Square from;
		Square* list = board.pieceList[WHITE_PAWN];
		while ((from=*list++) != NONE) {
                attacks = getPawnCaptures(from,mask) ;
                 ...

Instead of:

Code: Select all

       Square from = extractLSB(board.getPieces(WHITE_PAWN));

	while ( from!=NONE ) {
		attacks = getPawnCaptures(from,mask) ;
		Square target = extractLSB(attacks);
                ...
		from = extractLSB(pieces);
	}

After making all the changes and testing the overall performance, using my engine' s perft function, it is in average 5% slower than the previous version which uses bit scan for retrieving the index of each piece.

I thought it would get slightly faster when using piece lists by saving some millions of bit scans. Well I guess I was wrong. Or am I doing something wrong? Any thoughts?

[jwes]

It could be because you can generate moves for all pawns at one time.

[mcostalba]

Are you testing on a 64 or on a 32 bit binary ?

BTW as already reported, pawns are generated in a different way in SF....

[bhlangonijr]

Are you testing on a 64 or on a 32 bit binary ?

BTW as already reported, pawns are generated in a different way in SF....

Good point. I was testing using a 64 bit binary. I disabled the intrinsic BSF (to use debrujn instead, which is the common compilation for 32 bit machines) in the previous version which uses bit scans but even then the version using piece lists was slower. But after testing in a windows 32 bit it gets a bit faster... Why is that?

[JuLieN]

Maybe because you can only stuff half has many 64bits code in the CPU's cache than you'd stuff 32 bits code?

[bhlangonijr]

Maybe because you can only stuff half has many 64bits code in the CPU's cache than you'd stuff 32 bits code?

I don't know if I get you right, but what I am comparing here is the performance of the program with/without piece lists in the same environment, using both 32 and 64 bit binaries. Obviously I am not comparing the performance between different platforms.

[mcostalba]

But after testing in a windows 32 bit it gets a bit faster... Why is that?

Check the two versions of software bit scan for 32 and 64 bits and you'll see that 64's one is smaller and faster (when we have available a 64 bits integer ALU).

[JuLieN]

Yes, you didn't get me. What I meant was : x64 exes tend to use more memory than x32 exes do. (For instance, addresses are twice the sizes) So you can nearly stuff twice has many x32 code in the CPUs cache than you would with x64 code. So there's a chance for a x64 code to be slower than an x32 code if :
1) your x64 function doesn't totally fit in the CPU's cache while your x32 function would, and
2) it doesn't compensate by using code that is faster in x64 mode than in x32 codes (for instance 64bits-wide variables, like bitboards engine do).

Now if your CPU has a huge cache that let your whole engine fit in it, then the problem comes from somewhere else, of course.

EDIT: I found another reason why 64bits code sometimes can be slower than 32bits code, still because of the cache (copy/paste from stackoverflow.com) :
"To confuse matters more, the CPU caches can change results as well. Usually when you read one value from memory, a "line" of several memory locations are read into the cache, so that subsequent reads can be supplied from fast cache memory instead of requiring a full fetch from RAM. In which case using 32 bit values will work out faster if you are accessing many values in sequence, as twice as many of them will be cached, resulting in fewer cache misses."