C# Performance

[Richard Allbert]

Thanks Sven,

I'll answer tomorrow. Having spent the whole day more or less on this, I need to devote some Saturday time to my family!

mfg

Richard

[micron]

If GenerateMoves takes 99,44%, what is the remainder to 100%? Was it a "perft" test, or some specialized test containing movegen+make+unmake only (but no legality test or "in check")?

Evidently it's a profile of movegen alone, because make/unmake are not yet implemented.

In this circumstance I would write make/unmake, followed immediately by perft(). [Nobody ever said "I wish I had delayed writing perft", whereas many have wished they wrote it earlier].

Only then would I take a long hard look at performance.

[mcostalba]

unfortunately the results seemed to show that everything is slow in equal measure!

More than 40% of time spent generating castles seems a bit too much but it depends how you test it.

I'd guess you need to go inside the functions to understand where the bottlenecks are, simply checking the whole function does not seem to be enough. Just take one of them and look inside with the profiler to see where the worst offenders are in terms of single instructions / statements.

[Richard Allbert]

Ok,

Yesterday I implemented the Make / Unmake. (Verified with over 100 test positions to depth 5)

The following position

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

has 193690690 leafnodes to depth 5, which took the program 78s, or 2488kns.

I used the nprof profiler, here are the results:

Code: Select all

45,19% MoveMake.MakeMoveOnBoard(mdtTypeRef, mdtTypeRef, mdtTypeRef)
    -> 25.03% GetAttacks.SqIsAttackedBySide(int, int, mdtTypeRef)
	     -> 24,24% -> GetAttacks.SqAttackedByPiece(int, int, mdtTypeRef)  
	          -> 18,62% -> GetAttacks.AttackedByDark(int, mdtTypeRef)     
			       -> 0,41% BoardExtensions.GetPiece(Board, int)
				   -> 4,62% 0x3f423e 	
					     3,08 0x122434
					     1,50 0x12244b
					     0,03 0x122450
	          -> 0,46% -> GetAttacks.AttackedByLight(int, mdtTypeRef)  
    -> 4,74% BoardExtensions.MovePieceOnBoard(Board, int, int)	
          -> 2,5% BoardExtensions.MovePieceOnList(Board, int, int)	    
		  -> 0,6% BoardExtensions.GetPiece(Board, int)
    -> 2,82% EngeinBoard.Add(var) 
    -> 1,68% BoardExtensions.RemovePieceFromBoard(Board, int, int)	
          -> 1,25% BoardExtensions.RemovePieceFromList(Board, int, int)	    
		  -> 0,9% BoardExtensions.GetPiece(Board, int)
    -> 1,25% BoardExtensions.KingSQ(Board, int)
	-> 0,29% Pieces.IsPawn(int)
	rest is less than 0,29 %
	

25.03% GetAttacks.SqIsAttackedBySide(int, int, mdtTypeRef)
 -> 24,24% -> GetAttacks.SqAttackedByPiece(int, int, mdtTypeRef)  
	  -> 18,62% -> GetAttacks.AttackedByDark(int, mdtTypeRef)     
		   -> 0,41% BoardExtensions.GetPiece(Board, int)
		   -> 4,62% 0x3f423e 	
				 3,08 0x122434
				 1,50 0x12244b
				 0,03 0x122450
	  -> 0,46% -> GetAttacks.AttackedByLight(int, mdtTypeRef)  
	  

24,24% -> GetAttacks.SqAttackedByPiece(int, int, mdtTypeRef)  
	  -> 18,62% -> GetAttacks.AttackedByDark(int, mdtTypeRef)     
		   -> 0,41% BoardExtensions.GetPiece(Board, int)
		   -> 4,62% 0x3f423e 	
				 3,08 0x122434
				 1,50 0x12244b
				 0,03 0x122450
	  -> 0,46% -> GetAttacks.AttackedByLight(int, mdtTypeRef)  

20,24% MoveMake.MakeMoveOnBoard(mdtTypeRef, mdtTypeRef)
     -> MoveGen.RemoveAt(int)
	 -> 4,99% BoardExtensions.MovePieceOnBoard(Board, int, int)	
          -> 2,36% BoardExtensions.MovePieceOnList(Board, int, int)	    
		  -> 0,97% BoardExtensions.GetPiece(Board, int)
    -> 2,91 PerftTesting.get_Item&#40;<UNKNOWN>0&#41;
	-> 0,58% BoardExtensions.AddPieceToBoard&#40;Board, int, int&#41;	
          -> 0,46% BoardExtensions.AddPieceToList&#40;Board, int, int&#41;
    -> 0,21 System.get_Count&#40;)

	
18,62% -> GetAttacks.AttackedByDark&#40;int, mdtTypeRef&#41;     
   -> 0,41% BoardExtensions.GetPiece&#40;Board, int&#41;
	
12,48% MoveGenerator.GenerateMoves &#40;mdtTypeRef, mdtTypeRef&#41;
    -> 6,79% MoveGenerator.GenerateSliderMoves&#40;mdtTypeRef, mdtTypeRef, mdtTypeRef, int, int&#41;
	    -> 2,03% MoveGen.Add&#40;var&#41;
		-> 1,25 MoveGenerator.CanLandOrTake&#40;mdtTypeRef, int, short&#41;
		-> 0,17% Move..ctor &#40;int,int,int,int,int&#41;
    -> 3,15% MoveGenerator.GenerateNonSliderMoves&#40;mdtTypeRef, mdtTypeRef, mdtTypeRef, int, int&#41;
		-> 0,97 MoveGenerator.CanLandOrTake&#40;mdtTypeRef, int, short&#41;
	    -> 0,44% MoveGen.Add&#40;var&#41;
		-> 0,05% Move..ctor &#40;int,int,int,int,int&#41;
    -> 2,07% MoveGenerator.GenerateWhitePawnMoves&#40;mdtTypeRef, mdtTypeRef, mdtTypeRef&#41;
		-> 0,97 MoveGenerator.AddWhitePawnMove&#40;mdtTypeRef, mdtTypeRef, mdtTypeRef&#41;
	        -> 0,3% MoveGen.Add&#40;var&#41;
		    -> 0,1% Move..ctor &#40;int,int,int,int,int&#41;    
		-> 0,19% BoardExtensions.GetPiece&#40;Board, int&#41;   
		-> 0,14% Pieces.PieceColourIs&#40;int&#41;
	    -> 0,12% MoveGen.Add&#40;var&#41;
		

9,73% BoardExtensions.MovePieceOnBoard&#40;Board, int, int&#41;	
	  -> 4,85% BoardExtensions.MovePieceOnList&#40;Board, int, int&#41;	    
	  -> 1,87% BoardExtensions.GetPiece&#40;Board, int&#41;
	  
9,52% PerftTesting..ctor &#40;int&#41;
	-> 9,5 Hex Key?
		-> 9,13% CoUnitilializeEE this breaks down into GetMetaDataFromInternalPublic
		
		
6,79% MoveGenerator.GenerateSliderMoves&#40;mdtTypeRef, mdtTypeRef, mdtTypeRef, int, int&#41;
	-> 2,03% MoveGen.Add&#40;var&#41;
	-> 1,25 MoveGenerator.CanLandOrTake&#40;mdtTypeRef, int, short&#41;
	-> 0,17% Move..ctor &#40;int,int,int,int,int&#41;
	
4,99% MoveGenerator.RemoveAt&#40;int&#41;
4,85% Board Extensions.MovePieceOnList&#40;Board, int, int, int&#41;;
3,98% EngineBoard.MoveNext&#40;);
3,42% BoardExtensions.GetPiece&#40;Board, int&#41;  

3,15% MoveGenerator.GenerateNonSliderMoves&#40;mdtTypeRef, mdtTypeRef, mdtTypeRef, int, int&#41;
	-> 0,97 MoveGenerator.CanLandOrTake&#40;mdtTypeRef, int, short&#41;
	-> 0,44% MoveGen.Add&#40;var&#41;
	-> 0,05% Move..ctor &#40;int,int,int,int,int&#41;
	
	

2488kns wasn't as bad as I thought it would be, but it's still pretty slow - for example, there is no hashing of the position key here, or any updating of material counters.

Also, the move generation at 12% is less than I thought it would be.

A couple of things have changed since the last post - I was doing SQ Attacked detection for castling in the movegen, I moved this to makemove, seeing as it's wasted in the search if a beta cutoff is found before the castle move is made. Hence fewer SqIsAttackedBySide calls in the MoveGen.

Another suprose was that the act of creating a new move object and adding it to the list also takes very little of the performance.

The biggest performance hogger is SqIsAttackedBySide(), correct?

As above, any feedback is really appreciated, and I can post any of the code you'd like to see

Thanks

Richard

[mcostalba]

As above, any feedback is really appreciated, and I can post any of the code you'd like to see

Of course the first thing to look at is the code below:

Code: Select all

25.03% GetAttacks.SqIsAttackedBySide(int, int, mdtTypeRef)
 -> 24,24% -> GetAttacks.SqAttackedByPiece(int, int, mdtTypeRef)  
	  -> 18,62% -> GetAttacks.AttackedByDark(int, mdtTypeRef)    

But it could also be that code is ok and you simply call the function too much. Are you sure you really need to know for each square if it is attacked ?

IOW also the callers of the function are important to investigate, to verify if the work of SqIsAttackedBySide() is really needed.

[RoadWarrior]

The following position

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

has 193690690 leafnodes to depth 5, which took the program 78s, or 2488kns.

2488kns wasn't as bad as I thought it would be, but it's still pretty slow - for example, there is no hashing of the position key here, or any updating of material counters.

Also, the move generation at 12% is less than I thought it would be.

.......

The biggest performance hogger is SqIsAttackedBySide(), correct?

My program shows the same number of perft 5 leaf nodes for that position as yours. It also shows the total number of nodes to be 197,876,242. This would make your moves-per-second number look a little better, as I think it should be based on total nodes rather than just leaf nodes.

My program is also C#, and my IsAttacked routine (presumably roughly equivalent to your SqIsAttacked* routines) shows a slightly smaller percentage than yours. But my move generation percentage is significantly higher than yours, possibly because I'm doing copy-make-restore rather than make-unmake .

I agree with Marco looking at the detailed line timings of a few routines such as SqIsAttacked is the right approach.

[Richard Allbert]

Hi Marco

The function is called in MakeMoveOnBoard() - in the case of a castel move to cehck that the king hasn't moved across an attakced square, and in general to say whether the king has been placed in check after the move has been made (in which case it's illegal)

The name is misleading here - the kingsq(side) is passed as an argument.

However, I will look at the code this weekend and try to understand if it can be improved

Thanks

Richard

[Richard Allbert]

Hi Mark,

Thanks for the reply.

I agree also - a positive surprise was how little time is used by the List<T>Add() operations - so much for that being C#'s bottleneck!

I ran this on 2.5ghz Intel - what nps do you get for your program?

Richard

[mcostalba]

Hi Marco

The function is called in MakeMoveOnBoard() - in the case of a castel move to cehck that the king hasn't moved across an attakced square, and in general to say whether the king has been placed in check after the move has been made (in which case it's illegal)

The name is misleading here - the kingsq(side) is passed as an argument.

However, I will look at the code this weekend and try to understand if it can be improved

Thanks

Richard

A possible optimization could be to first check for free path for king and rook (and this would discard already a lot of positions) and then, only as last thing to check for king under attack that is the slowest part.

I haven't read the code, so perhaps what I am suggesting is already implemented, please do ignore the post in this case.

[RoadWarrior]

I ran this on 2.5ghz Intel - what nps do you get for your program?

For perft 5 in that position (with no incremental updates), my program processes a total of 197,876,242 nodes in 12.72 seconds, which is about 15.56M nodes per second. That node total includes the aforementioned leaf nodes.

As HGM pointed out to me recently, perft is really counting moves rather than nodes, as no node processing is done.

If I switch-on full incremental updates (material and PST values), that number drops to around 12.3M per second.

If I also switch-on my (currently very skeletal) evaluation at leaf nodes, that number drops further to around 6.5M per second.

I found no real alternative yet to just hard work with the profiler and setting specific performance targets.