C# Performance

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Richard Allbert
Posts: 778
Joined: Wed Jul 19, 2006 7:58 am

C# Performance

Post by Richard Allbert » Fri Jan 27, 2012 8:41 pm

Hi,

I started an engine in C# a while ago - the intention being to making it part of an XNA based game.

I've so far written the board structure and fen parsing. All in all it's in five class libraries with approx 200 unit tests. Progress has been slow, but thorough, after developing an obsession with getting unit tests to pass, and finding that I write 9 / 10 functions with bugs first time.

Also, working with very simple thread and string libraries (compared with C++) has been nice.


I was pretty pleased with progress, until I came to start move generation.

I just can't find a performance friendly way of adding moves to a list - even when declaring the list as an array of move objects, it's 5x (i.e. a lot) slower than the same thing in C++.

Are there some general tips or do's / dont's in C# when dealing with static or dynamic sizes collections of non primitive types?

Also, I've written Lot of functionality using extension methods - is this a bad idea?

Stripped down to its skeleton, the basics of the generation structure are

Code: Select all


public partial class Board
{
        public BoardPieceList[] PieceList = new BoardPieceList[Pieces.PieceTotal];
        public int[] boardPieces = new int[BoardConstants.BoardSquareCount];

.....  }


public partial class BoardPieceList
    {
        List<int> pieceList;
        public List<int> PieceList &#123; get &#123; return pieceList; &#125; &#125;

        int lastAliveIndex; // where the last alive piece is in the list &#40;index base is 0 here&#41;
        public int LastAliveIndex &#123; get &#123; return lastAliveIndex; &#125; set &#123; lastAliveIndex = value; &#125; &#125;

        public const int NoPieces = -1;

        // init with piece type and the list size

        public BoardPieceList&#40;int listLength&#41;
        &#123;
            Debug.Assert&#40;listLength >= BoardExtensions.KingLength && listLength <= BoardExtensions.NormalLength&#41;;

            pieceList = new List<int>&#40;listLength&#41;;
            InitList&#40;listLength&#41;;
        &#125;

        // add pieces to defined max length, and set the alive index to 0 as no pieces are alive yet, square is offboard

        private void InitList&#40;int listLength&#41;
        &#123;
            Debug.Assert&#40;listLength >= BoardExtensions.KingLength && listLength <= BoardExtensions.NormalLength&#41;;

            for &#40;int i = 0; i < listLength; ++i&#41;
            &#123;
                pieceList.Add&#40;Squares.OffBoard&#41;;
            &#125;

            lastAliveIndex = BoardPieceList.NoPieces;
        &#125;

        public void AddPiece&#40;int sq&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;sq&#41; == true&#41;;

            pieceList&#91;++LastAliveIndex&#93; = sq;

            Debug.Assert&#40;lastAliveIndex >= 0&#41;;
            Debug.Assert&#40;lastAliveIndex < pieceList.Count&#41;;
        &#125;

        public void MovePiece&#40;int from, int to&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;from&#41; == true&#41;;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;to&#41; == true&#41;;
            Debug.Assert&#40;lastAliveIndex > BoardPieceList.NoPieces&#41;;

            for &#40;int index = LastAliveIndex; index >= 0; --index&#41;
            &#123;
                if &#40;pieceList&#91;index&#93; == from&#41;
                &#123;
                    pieceList&#91;index&#93; = to;
                    return;
                &#125;
            &#125;

            Debug.Assert&#40;true == false&#41;; // reaching here means we didn't find the pce we were moving
            
        &#125;

        public void KillPiece&#40;int sq&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;sq&#41; == true&#41;;
            Debug.Assert&#40;lastAliveIndex < pieceList.Count&#41;;
            Debug.Assert&#40;lastAliveIndex > BoardPieceList.NoPieces&#41;;
         
            for &#40;int index = LastAliveIndex; index >= 0; --index&#41;
            &#123;
                if &#40;pieceList&#91;index&#93; == sq&#41;
                &#123;
                    if &#40;index != LastAliveIndex&#41;
                    &#123;
                        pieceList&#91;index&#93; = pieceList&#91;LastAliveIndex&#93;;
                        pieceList&#91;LastAliveIndex&#93; = Squares.OffBoard;
                    &#125;
                    else
                    &#123;
                        pieceList&#91;index&#93; = Squares.OffBoard;
                    &#125;

                    lastAliveIndex--;
                    return;
                &#125;
            &#125;

            Debug.Assert&#40;true == false&#41;; // reaching here means we didn't find the pce we were killing
        &#125;

        public int GetSquare&#40;int pieceIndex&#41;
        &#123;
            Debug.Assert&#40;pieceIndex >= 0 && pieceIndex <= lastAliveIndex&#41;;
            return pieceList&#91;pieceIndex&#93;;
        &#125;
    &#125;

public static class BoardExtensions
    &#123;
        #region Get Piece List Utility

        public static int KingLength = 1;
        public static int PawnLength = 8;
        public static int NormalLength = 10;

        public static void InitPieceListArray&#40;this Board board&#41;
        &#123;
            board.PieceList&#91;Pieces.wP&#93; = new BoardPieceList&#40;PawnLength&#41;;
            board.PieceList&#91;Pieces.wN&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.wB&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.wR&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.wQ&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.wK&#93; = new BoardPieceList&#40;KingLength&#41;;

            board.PieceList&#91;Pieces.bP&#93; = new BoardPieceList&#40;PawnLength&#41;;
            board.PieceList&#91;Pieces.bN&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.bB&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.bR&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.bQ&#93; = new BoardPieceList&#40;NormalLength&#41;;
            board.PieceList&#91;Pieces.bK&#93; = new BoardPieceList&#40;KingLength&#41;;
        &#125;

        public static BoardPieceList GetPieceList&#40;this Board board, int pce&#41;
        &#123;
            Debug.Assert&#40;Pieces.PieceIsValid&#40;pce&#41; == true&#41;;
            return board.PieceList&#91;pce&#93;;
        &#125;

        #endregion

        #region Add piece to board

        
        public static void AddPieceToBoard&#40;this Board board, int pce, int square&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;square&#41; == true&#41;;
            Debug.Assert&#40;Pieces.PieceIsValid&#40;pce&#41; == true&#41;;

            board.boardPieces&#91;square&#93; = pce;
            AddPieceToList&#40;board, pce, square&#41;;
        &#125;

        public static void AddPieceToList&#40;Board board, int pce, int square&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;square&#41; == true&#41;;
            Debug.Assert&#40;Pieces.PieceIsValid&#40;pce&#41; == true&#41;;

            board.GetPieceList&#40;pce&#41;.AddPiece&#40;square&#41;;
        &#125;        

        #endregion

        #region remove Piece from board

        public static void RemovePieceFromBoard&#40;this Board board, int square&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;square&#41; == true&#41;;
            Debug.Assert&#40;Pieces.PieceIsValid&#40;board.GetPiece&#40;square&#41;) == true&#41;;


            RemoveFromPieceList&#40;board, board.GetPiece&#40;square&#41;, square&#41;;
            board.boardPieces&#91;square&#93; = Pieces.NoPiece;
        &#125;

        private static void RemoveFromPieceList&#40;Board board, int pce, int square&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;square&#41; == true&#41;;
            Debug.Assert&#40;Pieces.PieceIsValid&#40;pce&#41; == true&#41;;

            board.GetPieceList&#40;pce&#41;.KillPiece&#40;square&#41;;
        &#125;

        #endregion

        #region move Piece on board

        public static void MovePieceOnBoard&#40;this Board board, int fromsq, int tosq&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;fromsq&#41; == true&#41;;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;tosq&#41; == true&#41;;
            Debug.Assert&#40;Pieces.PieceIsValid&#40;board.GetPiece&#40;fromsq&#41;) == true&#41;;


            MovePieceOnList&#40;board, board.GetPiece&#40;fromsq&#41;, fromsq, tosq&#41;;
            
            board.boardPieces&#91;tosq&#93; = board.GetPiece&#40;fromsq&#41;;
            board.boardPieces&#91;fromsq&#93; = Squares.OffBoard;

        &#125;

        private static void MovePieceOnList&#40;Board board, int pce, int fromsq, int tosq&#41;
        &#123;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;fromsq&#41; == true&#41;;
            Debug.Assert&#40;Squares.SquareOnBoard&#40;tosq&#41; == true&#41;;
            Debug.Assert&#40;Pieces.PieceIsValid&#40;pce&#41; == true&#41;;

            board.GetPieceList&#40;pce&#41;.MovePiece&#40;fromsq, tosq&#41;;
        &#125;

       

        #endregion

        #region get piece

        public static int GetPiece&#40;this Board board, int sq&#41;
        &#123;
            return board.boardPieces&#91;sq&#93;;
        &#125;

        #endregion

        #region get piece

        public static void ClearBoard&#40;this Board board&#41;
        &#123;
            for &#40;int i = 0; i < BoardConstants.BoardSquareCount; ++i&#41;
            &#123;
                board.boardPieces&#91;i&#93; = Pieces.NoPiece;
            &#125;

            board.InitPieceListArray&#40;);
            board.currentCastlePermission = 0;
            board.currentFiftyMoveRule = 0;
            board.currentHalfMoveCount = 0;
            board.currentSearchPly = 0;
            board.enPassantSqaure = Squares.OffBoard;
            board.sideToMove = Colour.None;
        &#125;

        #endregion

    &#125;

public class MoveList
    &#123;
        public Move&#91;&#93; MoveArray = new Move&#91;Moves.MaxMoveListMoves&#93;;
        public int moveCount = 0;
    &#125;

    public static class MoveListExtensions
    &#123;
        public static void AddMove&#40;this MoveList list, Move move&#41;
        &#123;
            Debug.Assert&#40;list.moveCount < &#40;Moves.MaxMoveListMoves - 1&#41;);

            list.MoveArray&#91;list.moveCount++&#93; = move;
        &#125;

        public static Move GetMove&#40;this MoveList list, int index&#41;
        &#123;
            Debug.Assert&#40;list.moveCount > index && index >= 0&#41;;

            return list.MoveArray&#91;index&#93;;
        &#125;
    &#125;

public class Move
    &#123;
        public int from;
        public int to;
        public int promotedTo;
        public int captured;
        public int flag;

        public Move&#40;)
        &#123;
            from = Squares.OffBoard;
            to = Squares.OffBoard;
            promotedTo = Pieces.NoPiece;
            captured = Pieces.NoPiece;
            flag = Moves.FlagNone;
        &#125;

        public Move&#40;int f, int t, int pr, int ca, int fl&#41;
        &#123;
            from = f;
            to = t;
            promotedTo = pr;
            captured = ca;
            flag = fl;
        &#125;

And adding a move in generation...

fromSq = pceList.GetSquare&#40;pceNum&#41;;

                    while &#40;Pieces.MoveDirections&#91;pce, moves&#93; != 0&#41;
                    &#123;
                        toSq = Pieces.MoveDirections&#91;pce, moves&#93; + fromSq;

                        if &#40;CanLandOrTake&#40;board, pce, toSq&#41; == true&#41;
                        &#123;
                            moveList.AddMove&#40;new Move&#40;fromSq, toSq, Pieces.NoPiece, board.GetPiece&#40;toSq&#41;, Moves.FlagNone&#41;);
                        &#125;

                        moves++;
                    &#125;



Anyway, I haven't been writing with any real optimisation in mind, but I didn't expect it to be so slow.

As a (very unreliable) indicator, I put together the above skeleton in C++ and ran Generate on the starting position for 2000000 loops. This took just over 2s for the C++ program but over 14s for the C#.

Should I be writing all of this as unsafe code, and fixing the arrays in the memory?

Or are my feeling misplaced?

I just don't want to invest a load of time over the next few months with the hard part, only to have something well tested, extensible but dog slow.

Thanks for any tips

Richard

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: C# Performance

Post by kbhearn » Fri Jan 27, 2012 9:01 pm

I have a hunch that "new Move(...)" might be a major culprit of the slowness. I'm not familiar with C# really, but after some quick looking it appears the new operator is the same as in C++. which is to say it's probably asking the system for memory in which it can create an object (as opposed to having a local Move variable which would be created on the stack). If this is the case, there would also be the issue of working the garbage collector (horrid creations) like mad since it has to handle disposing of all these move objects you're creating and then leaving hanging (again if i'm reading the code right the move variable you pass in just gets copied into your already existing static array of moves).

gladius
Posts: 568
Joined: Tue Dec 12, 2006 9:10 am
Full name: Gary Linscott

Re: C# Performance

Post by gladius » Fri Jan 27, 2012 9:07 pm

Couple of quick things that may help:
- 2d arrays are slow in c#
- No allocations at all during search
- unsafe can end up being slower than safe (not as heavily optimized)
- c# will be slower than c++ :). Shouldn't be 10x though

Richard Allbert
Posts: 778
Joined: Wed Jul 19, 2006 7:58 am

Re: C# Performance

Post by Richard Allbert » Fri Jan 27, 2012 9:13 pm

I thought this to, and I changed it for a test to use a static movelist, and fill with Move() objejts in the constructor. Then, I just reset the move counter to 0 each loop,


Having this:

Code: Select all

moveList.AddMove&#40;fromSq, toSq, Pieces.NoPiece, board.GetPiece&#40;toSq&#41;, Moves.FlagNone&#41;;

and

public static void AddMove&#40;int f,...) 
        &#123; 
            
            MoveArray&#91;list.moveCount++&#93;.from = f;

etc... 
        &#125; 
And it made no difference!

:)

Richard Allbert
Posts: 778
Joined: Wed Jul 19, 2006 7:58 am

Re: C# Performance

Post by Richard Allbert » Fri Jan 27, 2012 9:17 pm

Ok, thanks

I'll have a look at. Just read some articles in the 2D array performance - it's a lot worse!!

A little slower is ok - so long as that's possible, then I'll press on. :)

gladius
Posts: 568
Joined: Tue Dec 12, 2006 9:10 am
Full name: Gary Linscott

Re: C# Performance

Post by gladius » Fri Jan 27, 2012 10:09 pm

One more thing, try converting your move class to a struct. Also, prefer using arrays instead of list<>.

To get the most speed, represent move as uint or ulong, and use uint[] to store.

RoadWarrior
Posts: 70
Joined: Thu Jan 12, 2012 11:39 pm
Location: London, England
Contact:

Re: C# Performance

Post by RoadWarrior » Sat Jan 28, 2012 12:59 am

Richard Allbert wrote:As a (very unreliable) indicator, I put together the above skeleton in C++ and ran Generate on the starting position for 2000000 loops. This took just over 2s for the C++ program but over 14s for the C#.
If I understand what you're saying (20 moves generated 2M times), that's 20M move generations per second for C++ and 2.86M for C#. My fledgling C# chess engine (using bitboards) on a single core (i7 2600K) does about 60M raw move generations per second, and that was with almost no optimisation.

So my feeling is that you should be able to go an order of magnitude faster. As Gary says, try using an immutable struct rather than class for Move. Mine looks like this:

Code: Select all

internal struct Move
&#123;
  internal Move&#40;byte squareFrom, byte squareTo, byte pieceMoved, byte pieceCaptured, byte piecePromoted&#41;
  &#123;
    this.SquareFrom = squareFrom;
    this.SquareTo = squareTo;
    this.PieceMoved = pieceMoved;
    this.PieceCaptured = pieceCaptured;
    this.PiecePromoted = piecePromoted;
  &#125;
  
  // The FROM square.
  // Bits 1-3 are the board file, bits 4-6 are the board rank, bits 7-8 are unused.
  internal readonly byte SquareFrom;

  // The TO square.
  // Bits 1-3 are the board file, bits 4-6 are the board rank, bits 7-8 are unused.
  internal readonly byte SquareTo;

  // The MOVED piece.
  // Bits 1-3 are the piece type, bit 4 is the piece colour, bits 5-8 are unused.
  internal readonly byte PieceMoved;
        
  // The CAPTURED piece.
  // Bits 1-3 are the piece type, bit 4 is the piece colour, bits 5-8 are unused.
  internal readonly byte PieceCaptured;
        
  // The PROMOTED piece.
  // Bits 1-3 are the piece type, bit 4 is the piece colour, bits 5-8 are unused.
  // NB Overloaded to represent EN-PASSANT capture if promoted piece is a pawn.
  // NB Overloaded to represent CASTLING if promoted piece is a king.
  internal readonly byte PiecePromoted;
&#125;
A generic List<Move> with a pre-defined maximum length for holding moves can be just as fast as using arrays, as List uses an array internally:

Code: Select all

List<Move> moveList = new List<Move>&#40;48&#41;;
And definitely avoid 2-dimensional arrays!

In case it's of any use to you, here's a fragment showing my bitboard-oriented code for generating all the moves for the White knights:

Code: Select all

// White KNIGHTS.
UInt64 remainingPieces = this.WhiteKnights;

// Generate the moves for each knight...
while &#40;remainingPieces != 0&#41;
&#123;
  squareFrom = BitOperations.BitScanForward&#40;remainingPieces&#41;;
  generatedMoves = Constants.ATTACKS_KNIGHT&#91;squareFrom&#93; & eligibleSquares;
  while &#40;generatedMoves != 0&#41;
  &#123;
    squareTo = BitOperations.BitScanForward&#40;generatedMoves&#41;;
    moveList.Add&#40;new Move&#40;squareFrom, squareTo, Constants.WHITE_KNIGHT, this.Squares&#91;squareTo&#93;, Constants.EMPTY&#41;);
    generatedMoves ^= Constants.BITSET&#91;squareTo&#93;;
  &#125;
  // Finished with this knight - move on to the next one.
  remainingPieces ^= Constants.BITSET&#91;squareFrom&#93;;
&#125;
Not a man to mince words. People, yes. But not words.

Richard Allbert
Posts: 778
Joined: Wed Jul 19, 2006 7:58 am

Re: C# Performance

Post by Richard Allbert » Sat Jan 28, 2012 8:44 am

Thanks for the reply - I'll have a look at your suggestions today.

I wasn't expecting what I did to be so slow "out of the box" :).

Also, the 2D array is an interesting point - and my piece lists are all 2D arrays. Seeing as it's mentioned here as bad, and all over the web also, I guess that needs to be changed!

It does make the two 'mantras'

1. Don 't code for performance first
2. Build unit tests first, code after

a little conflicting, though.

Due to amount of tests I've built in, there will be a lot of time going into making changes!

Regards

Richard

Sven
Posts: 3969
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: C# Performance

Post by Sven » Sat Jan 28, 2012 9:48 am

Richard Allbert wrote:Due to amount of tests I've built in, there will be a lot of time going into making changes!
Unit tests should not be affected too much by changing implementation of the real code, unless you are using assumptions about internal data structures and algorithms on the unit test level. So if you really think that changing the implementation will create a huge effort to also change the test code then your unit tests probably "know" too much about the real code, instead of just testing on the interface level.

Sven

Richard Allbert
Posts: 778
Joined: Wed Jul 19, 2006 7:58 am

Re: C# Performance

Post by Richard Allbert » Sat Jan 28, 2012 10:25 am

Hi Sven,

If I have 100 calls in a test to a certain method in a class, and then I move this method to a static class (to be able to implement the structure suggested above), then I have to change 100 calls... I don't see how this could be prevented.

I'm sure there's a clever way around this, but I find if you get too clever with the tests, you end up debugging those as well.


Richard

Post Reply