ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

C# Performance
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Richard Allbert



Joined: 19 Jul 2006
Posts: 679
PostPost subject: C# Performance    Posted: Fri Jan 27, 2012 8:41 pm Reply to topic Reply with quote
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:


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 { get { return pieceList; } }

        int lastAliveIndex; // where the last alive piece is in the list (index base is 0 here)
        public int LastAliveIndex { get { return lastAliveIndex; } set { lastAliveIndex = value; } }

        public const int NoPieces = -1;

        // init with piece type and the list size

        public BoardPieceList(int listLength)
        {
            Debug.Assert(listLength >= BoardExtensions.KingLength && listLength <= BoardExtensions.NormalLength);

            pieceList = new List<int>(listLength);
            InitList(listLength);
        }

        // 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(int listLength)
        {
            Debug.Assert(listLength >= BoardExtensions.KingLength && listLength <= BoardExtensions.NormalLength);

            for (int i = 0; i < listLength; ++i)
            {
                pieceList.Add(Squares.OffBoard);
            }

            lastAliveIndex = BoardPieceList.NoPieces;
        }

        public void AddPiece(int sq)
        {
            Debug.Assert(Squares.SquareOnBoard(sq) == true);

            pieceList[++LastAliveIndex] = sq;

            Debug.Assert(lastAliveIndex >= 0);
            Debug.Assert(lastAliveIndex < pieceList.Count);
        }

        public void MovePiece(int from, int to)
        {
            Debug.Assert(Squares.SquareOnBoard(from) == true);
            Debug.Assert(Squares.SquareOnBoard(to) == true);
            Debug.Assert(lastAliveIndex > BoardPieceList.NoPieces);

            for (int index = LastAliveIndex; index >= 0; --index)
            {
                if (pieceList[index] == from)
                {
                    pieceList[index] = to;
                    return;
                }
            }

            Debug.Assert(true == false); // reaching here means we didn't find the pce we were moving
           
        }

        public void KillPiece(int sq)
        {
            Debug.Assert(Squares.SquareOnBoard(sq) == true);
            Debug.Assert(lastAliveIndex < pieceList.Count);
            Debug.Assert(lastAliveIndex > BoardPieceList.NoPieces);
         
            for (int index = LastAliveIndex; index >= 0; --index)
            {
                if (pieceList[index] == sq)
                {
                    if (index != LastAliveIndex)
                    {
                        pieceList[index] = pieceList[LastAliveIndex];
                        pieceList[LastAliveIndex] = Squares.OffBoard;
                    }
                    else
                    {
                        pieceList[index] = Squares.OffBoard;
                    }

                    lastAliveIndex--;
                    return;
                }
            }

            Debug.Assert(true == false); // reaching here means we didn't find the pce we were killing
        }

        public int GetSquare(int pieceIndex)
        {
            Debug.Assert(pieceIndex >= 0 && pieceIndex <= lastAliveIndex);
            return pieceList[pieceIndex];
        }
    }

public static class BoardExtensions
    {
        #region Get Piece List Utility

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

        public static void InitPieceListArray(this Board board)
        {
            board.PieceList[Pieces.wP] = new BoardPieceList(PawnLength);
            board.PieceList[Pieces.wN] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.wB] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.wR] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.wQ] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.wK] = new BoardPieceList(KingLength);

            board.PieceList[Pieces.bP] = new BoardPieceList(PawnLength);
            board.PieceList[Pieces.bN] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.bB] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.bR] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.bQ] = new BoardPieceList(NormalLength);
            board.PieceList[Pieces.bK] = new BoardPieceList(KingLength);
        }

        public static BoardPieceList GetPieceList(this Board board, int pce)
        {
            Debug.Assert(Pieces.PieceIsValid(pce) == true);
            return board.PieceList[pce];
        }

        #endregion

        #region Add piece to board

       
        public static void AddPieceToBoard(this Board board, int pce, int square)
        {
            Debug.Assert(Squares.SquareOnBoard(square) == true);
            Debug.Assert(Pieces.PieceIsValid(pce) == true);

            board.boardPieces[square] = pce;
            AddPieceToList(board, pce, square);
        }

        public static void AddPieceToList(Board board, int pce, int square)
        {
            Debug.Assert(Squares.SquareOnBoard(square) == true);
            Debug.Assert(Pieces.PieceIsValid(pce) == true);

            board.GetPieceList(pce).AddPiece(square);
        }       

        #endregion

        #region remove Piece from board

        public static void RemovePieceFromBoard(this Board board, int square)
        {
            Debug.Assert(Squares.SquareOnBoard(square) == true);
            Debug.Assert(Pieces.PieceIsValid(board.GetPiece(square)) == true);


            RemoveFromPieceList(board, board.GetPiece(square), square);
            board.boardPieces[square] = Pieces.NoPiece;
        }

        private static void RemoveFromPieceList(Board board, int pce, int square)
        {
            Debug.Assert(Squares.SquareOnBoard(square) == true);
            Debug.Assert(Pieces.PieceIsValid(pce) == true);

            board.GetPieceList(pce).KillPiece(square);
        }

        #endregion

        #region move Piece on board

        public static void MovePieceOnBoard(this Board board, int fromsq, int tosq)
        {
            Debug.Assert(Squares.SquareOnBoard(fromsq) == true);
            Debug.Assert(Squares.SquareOnBoard(tosq) == true);
            Debug.Assert(Pieces.PieceIsValid(board.GetPiece(fromsq)) == true);


            MovePieceOnList(board, board.GetPiece(fromsq), fromsq, tosq);
           
            board.boardPieces[tosq] = board.GetPiece(fromsq);
            board.boardPieces[fromsq] = Squares.OffBoard;

        }

        private static void MovePieceOnList(Board board, int pce, int fromsq, int tosq)
        {
            Debug.Assert(Squares.SquareOnBoard(fromsq) == true);
            Debug.Assert(Squares.SquareOnBoard(tosq) == true);
            Debug.Assert(Pieces.PieceIsValid(pce) == true);

            board.GetPieceList(pce).MovePiece(fromsq, tosq);
        }

       

        #endregion

        #region get piece

        public static int GetPiece(this Board board, int sq)
        {
            return board.boardPieces[sq];
        }

        #endregion

        #region get piece

        public static void ClearBoard(this Board board)
        {
            for (int i = 0; i < BoardConstants.BoardSquareCount; ++i)
            {
                board.boardPieces[i] = Pieces.NoPiece;
            }

            board.InitPieceListArray();
            board.currentCastlePermission = 0;
            board.currentFiftyMoveRule = 0;
            board.currentHalfMoveCount = 0;
            board.currentSearchPly = 0;
            board.enPassantSqaure = Squares.OffBoard;
            board.sideToMove = Colour.None;
        }

        #endregion

    }

public class MoveList
    {
        public Move[] MoveArray = new Move[Moves.MaxMoveListMoves];
        public int moveCount = 0;
    }

    public static class MoveListExtensions
    {
        public static void AddMove(this MoveList list, Move move)
        {
            Debug.Assert(list.moveCount < (Moves.MaxMoveListMoves - 1));

            list.MoveArray[list.moveCount++] = move;
        }

        public static Move GetMove(this MoveList list, int index)
        {
            Debug.Assert(list.moveCount > index && index >= 0);

            return list.MoveArray[index];
        }
    }

public class Move
    {
        public int from;
        public int to;
        public int promotedTo;
        public int captured;
        public int flag;

        public Move()
        {
            from = Squares.OffBoard;
            to = Squares.OffBoard;
            promotedTo = Pieces.NoPiece;
            captured = Pieces.NoPiece;
            flag = Moves.FlagNone;
        }

        public Move(int f, int t, int pr, int ca, int fl)
        {
            from = f;
            to = t;
            promotedTo = pr;
            captured = ca;
            flag = fl;
        }

And adding a move in generation...

fromSq = pceList.GetSquare(pceNum);

                    while (Pieces.MoveDirections[pce, moves] != 0)
                    {
                        toSq = Pieces.MoveDirections[pce, moves] + fromSq;

                        if (CanLandOrTake(board, pce, toSq) == true)
                        {
                            moveList.AddMove(new Move(fromSq, toSq, Pieces.NoPiece, board.GetPiece(toSq), Moves.FlagNone));
                        }

                        moves++;
                    }





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
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
C# Performance Richard Allbert Fri Jan 27, 2012 8:41 pm
      Re: C# Performance Kevin Hearn Fri Jan 27, 2012 9:01 pm
            Re: C# Performance Richard Allbert Fri Jan 27, 2012 9:13 pm
      Re: C# Performance Gary Fri Jan 27, 2012 9:07 pm
            Re: C# Performance Richard Allbert Fri Jan 27, 2012 9:17 pm
                  Re: C# Performance Gary Fri Jan 27, 2012 10:09 pm
      Re: C# Performance Mark Pearce Sat Jan 28, 2012 12:59 am
            Re: C# Performance Richard Allbert Sat Jan 28, 2012 8:44 am
                  Re: C# Performance Sven Schüle Sat Jan 28, 2012 9:48 am
                        Re: C# Performance Richard Allbert Sat Jan 28, 2012 10:25 am
                              Re: C# Performance Richard Allbert Sat Jan 28, 2012 11:41 am
                  Re: C# Performance Mark Pearce Sat Jan 28, 2012 11:44 am
            Re: C# Performance Richard Allbert Sat Jan 28, 2012 10:31 am
      Re: C# Performance Marco Costalba Sat Jan 28, 2012 1:09 pm
            Re: C# Performance Lucas Braesch Sat Jan 28, 2012 1:52 pm
            Re: C# Performance Richard Allbert Sat Jan 28, 2012 2:05 pm
                  Re: C# Performance Marco Costalba Sat Jan 28, 2012 2:30 pm
                        Re: C# Performance Richard Allbert Sat Jan 28, 2012 5:22 pm
                              Re: C# Performance Sven Schüle Sat Jan 28, 2012 6:02 pm
                                    Re: C# Performance Richard Allbert Sat Jan 28, 2012 6:12 pm
                                    Re: C# Performance Robert Purves Sat Jan 28, 2012 10:17 pm
                              Re: C# Performance Marco Costalba Sat Jan 28, 2012 10:25 pm
                  Re: C# Performance Thomas Petzke Sat Jan 28, 2012 4:21 pm
      Re: C# Performance Richard Allbert Mon Jan 30, 2012 12:52 pm
            Re: C# Performance Marco Costalba Mon Jan 30, 2012 6:37 pm
                  Re: C# Performance Richard Allbert Wed Feb 01, 2012 6:55 pm
                        Re: C# Performance Marco Costalba Wed Feb 01, 2012 7:18 pm
            Re: C# Performance Mark Pearce Mon Jan 30, 2012 9:55 pm
                  Re: C# Performance Richard Allbert Wed Feb 01, 2012 6:57 pm
                        Re: C# Performance Mark Pearce Wed Feb 01, 2012 9:59 pm
            Re: C# Performance Mark Pearce Fri Feb 03, 2012 1:34 am
                  Re: C# Performance Robert Purves Fri Feb 03, 2012 3:26 am
                        Re: C# Performance Mark Pearce Fri Feb 03, 2012 9:28 am
                              Re: C# Performance Sven Schüle Fri Feb 03, 2012 9:45 am
                                    Re: C# Performance Mark Pearce Sat Feb 04, 2012 7:57 pm
                                          Re: C# Performance Sven Schüle Sat Feb 04, 2012 10:36 pm
                                                Re: C# Performance Mark Pearce Sat Feb 04, 2012 11:49 pm
                                                      Re: C# Performance Sven Schüle Sun Feb 05, 2012 12:51 am
                                                            Re: C# Performance Mark Pearce Sun Feb 05, 2012 1:05 am
                              Re: C# Performance Sven Schüle Fri Feb 03, 2012 10:04 am
                                    Re: C# Performance Mark Pearce Fri Feb 03, 2012 11:40 am
                                          Re: C# Performance Richard Allbert Sat Feb 04, 2012 7:10 pm
                                                Re: C# Performance Lucas Braesch Sat Feb 04, 2012 8:31 pm
                                                      Re: C# Performance Mark Pearce Sat Feb 04, 2012 10:23 pm
                                                            Re: C# Performance Mark Pearce Sun Feb 05, 2012 12:23 am
                                                                  Re: C# Performance Lucas Braesch Sun Feb 05, 2012 2:57 am
                                                                        Re: C# Performance Mark Pearce Sun Feb 05, 2012 11:40 am
                                                                              Re: C# Performance Richard Allbert Mon Feb 06, 2012 6:29 pm
                                                                                    Re: C# Performance Richard Allbert Mon Feb 06, 2012 6:29 pm
                                                                                          Re: C# Performance Richard Allbert Mon Feb 06, 2012 6:30 pm
                                                                                          Re: C# Performance Richard Allbert Mon Feb 06, 2012 6:45 pm
                                                                                          Re: C# Performance Gary Mon Feb 06, 2012 7:00 pm
                                                                                          Re: C# Performance Richard Allbert Mon Feb 06, 2012 7:12 pm
                                                                                          Re: C# Performance Sven Schüle Mon Feb 06, 2012 10:50 pm
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 9:52 am
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 9:53 am
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 9:53 am
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 9:54 am
                                                                                          Re: C# Performance Mark Pearce Tue Feb 07, 2012 1:59 pm
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 2:54 pm
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 3:06 pm
                                                                                          Re: C# Performance Mark Pearce Tue Feb 07, 2012 5:17 pm
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 6:10 pm
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 6:20 pm
                                                                                          Re: C# Performance Mark Pearce Tue Feb 07, 2012 8:02 pm
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 9:19 pm
                                                                                          Re: C# Performance Mark Pearce Tue Feb 07, 2012 10:20 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 7:47 am
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 7:57 am
                                                                                          Re: C# Performance Sven Schüle Wed Feb 08, 2012 10:09 am
                                                                                          Re: C# Performance Mark Pearce Wed Feb 08, 2012 12:16 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sat Feb 18, 2012 10:03 pm
                                                                                          Re: C# Performance Mark Pearce Wed Feb 08, 2012 9:30 am
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 12:02 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 12:34 pm
                                                                                          Re: C# Performance Mark Pearce Wed Feb 08, 2012 12:56 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 1:18 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 2:30 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 2:34 pm
                                                                                          Re: C# Performance Mark Pearce Wed Feb 08, 2012 3:02 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 3:27 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 3:29 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 3:59 pm
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 4:04 pm
                                                                                          Re: C# Performance Mark Pearce Wed Feb 08, 2012 6:07 pm
                                                                                          Re: C# Performance Richard Allbert Thu Feb 09, 2012 10:41 am
                                                                                          Re: C# Performance Mark Pearce Thu Feb 09, 2012 1:47 pm
                                                                                          Re: C# Performance Richard Allbert Thu Feb 09, 2012 2:56 pm
                                                                                          Re: C# Performance Mark Pearce Sat Feb 11, 2012 4:41 pm
                                                                                          Re: C# Performance Richard Allbert Sun Feb 12, 2012 8:34 am
                                                                                          Re: C# Performance Lucas Braesch Sun Feb 12, 2012 10:52 am
                                                                                          Re: C# Performance Richard Allbert Sun Feb 12, 2012 12:26 pm
                                                                                          Re: C# Performance Ron Murawski Mon Feb 13, 2012 5:26 am
                                                                                          Re: C# Performance Lucas Braesch Mon Feb 13, 2012 5:52 am
                                                                                          Re: C# Performance Richard Allbert Mon Feb 13, 2012 6:27 am
                                                                                          Re: C# Performance Ron Murawski Tue Feb 14, 2012 6:38 am
                                                                                          Re: C# Performance Lucas Braesch Tue Feb 14, 2012 8:22 am
                                                                                          Re: C# Performance Mark Pearce Tue Feb 14, 2012 11:30 pm
                                                                                          Re: C# Performance Richard Allbert Thu Feb 16, 2012 10:49 am
                                                                                          Re: C# Performance Mark Pearce Sat Feb 18, 2012 12:34 pm
                                                                                          Re: C# Performance Richard Allbert Mon Feb 20, 2012 9:19 pm
                                                                                          Re: C# Performance Mark Pearce Tue Feb 21, 2012 8:33 am
                                                                                          Re: C# Performance Richard Allbert Tue Feb 21, 2012 6:37 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sat Feb 18, 2012 10:19 pm
                                                                                          Re: C# Performance Mark Pearce Sun Feb 12, 2012 2:01 pm
                                                                                          Re: C# Performance Richard Allbert Sun Feb 12, 2012 4:40 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sat Feb 18, 2012 10:06 pm
                                                                                          Re: C# Performance Mark Pearce Sun Feb 19, 2012 1:01 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sun Feb 19, 2012 5:25 pm
                                                                                          Re: C# Performance Mark Pearce Sun Feb 19, 2012 7:04 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sun Feb 19, 2012 9:17 pm
                                                                                          Re: C# Performance Mark Pearce Sun Feb 19, 2012 11:33 pm
                                                                                          Re: C# Performance Richard Allbert Sun Feb 19, 2012 9:22 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sun Feb 19, 2012 9:32 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sun Feb 19, 2012 9:37 pm
                                                                                          Re: C# Performance Vincent Diepeveen Sun Feb 19, 2012 10:06 pm
                                                                                          Re: C# Performance Lucas Braesch Wed Feb 08, 2012 10:56 am
                                                                                          Re: C# Performance Mark Pearce Wed Feb 08, 2012 11:30 am
                                                                                          Re: C# Performance Richard Allbert Wed Feb 08, 2012 12:04 pm
                                                                                          Re: C# Performance Tony Soares Tue Feb 07, 2012 3:47 am
                                                                                          Re: C# Performance Richard Allbert Tue Feb 07, 2012 9:55 am
                                          Re: C# Performance Mark Pearce Sat Feb 04, 2012 8:37 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads