C# Performance

[RoadWarrior]

I've been through all functions with the IL DASM and box is not used anywhere - I looked in Attacks, Perft, MoveGen, MoveMake

From Eric Lippert's very useful essay [1] on value type storage:

It is frequently the case that array elements, fields of reference types, locals in an iterator block and closed-over locals of a lambda or anonymous method must live longer than the activation period of the method that first required the use of their storage. And even in the rare cases where their lifetimes are shorter than that of the activation of the method, it is difficult or impossible to write a compiler that knows that. Therefore we must be conservative: all of these storage locations go on the heap.

So if my understanding is correct, using an array or List to store the moves will always mean heap allocations. Therefore it looks like you don't have a performance issue caused by boxing. We need to look elsewhere. For example, Sven's stack-based suggestion seems like a promising approach.

[1] http://blogs.msdn.com/b/ericlippert/arc ... types.aspx

[Richard Allbert]

Yes, I think so too.

If you downloaded the Solution file, please do so again, as I've condesnsed it down properly into one main ENgine lib, and a console and perft lib.

Thanks

Richard

[Richard Allbert]

Ok, implemented using a movelist created on startUp -

Code: Select all

public class Board
{
        public int[] FirstMoveAtPly = new int[SearchConstants.MaxPly];
        public Move[] MoveList = new Move[Moves.MaxMoveListMoves];
..
}

in MoveGen class..

private static void AddMove(Board board, int f, int t, int prom, int cap, int fl)
        {
            int index = board.GetMoveIndex();
            board.MoveList[index].from = f;
            board.MoveList[index].to = t;
            board.MoveList[index].promotedTo = prom;
            board.MoveList[index].captured = cap;
            board.MoveList[index].flag = fl;
            board.IncrementMoveIndex();
        }

this yielded

Code: Select all

Preinitiliased moveList + struct Move
3000 knps, 900kB Heap Allocations 

So a MASSIVE reduction in heap allocation, but slower than the Array + class Move version. There were no GC collections!

[Richard Allbert]

Profile is below:

[RoadWarrior]

Ok, implemented using a movelist created on startUp -

Code: Select all

public class Board
{
        public int[] FirstMoveAtPly = new int[SearchConstants.MaxPly];
        public Move[] MoveList = new Move[Moves.MaxMoveListMoves];
..
}

in MoveGen class..

private static void AddMove(Board board, int f, int t, int prom, int cap, int fl)
        {
            int index = board.GetMoveIndex();
            board.MoveList[index].from = f;
            board.MoveList[index].to = t;
            board.MoveList[index].promotedTo = prom;
            board.MoveList[index].captured = cap;
            board.MoveList[index].flag = fl;
            board.IncrementMoveIndex();
        }

this yielded

Code: Select all

Preinitiliased moveList + struct Move
3000 knps, 900kB Heap Allocations 

So a MASSIVE reduction in heap allocation, but slower than the Array + class Move version. There were no GC collections!

No collections because the move list is now anchored to the Board class, and won't be collected until the Board class goes out of scope.

The AddMove and IncrementMoveIndex methods are taking 8% of your time, with nearly 2% taken just incrementing the move index! Can you get line timings for these methods, because it might be related to the slowdown you're seeing versus the previous local move list.

Can you make FirstMoveAtPly and MoveList internal and static, rather than instance fields?

[Richard Allbert]

ok!

One thing I noticed from the profiler was in MakeMove, the Historylist.Add() was taking a lot of the time.

I changed it from

Code: Select all

public List<MoveHistory> gameHistory = new List<MoveHistory>&#40;SearchConstants.MaxMovesInGame&#41;;

to

Code: Select all

        public MoveHistory[] gameHistory = new MoveHistory[SearchConstants.MaxMovesInGame];
        public int HistoryMoves = 0;

and made the changes needed to makeMove, and the speed went from the 3000knps to 3700knps.....

[Richard Allbert]

One thing about making those static... if I ever get to SMP, I'll need more than one copy of the position, won't I? If so, then the movelist can't be static? Or am I missing something?

[Richard Allbert]

Some more changes, from the profiler.

I took out unnecessary Reference / Variable definitions in Make and Unmake,
and I changed the board piecelist defintion to hold an index on the piece list for a given square: (As Sven suggested)

Code: Select all

        public int[] pceListIndexFromSq = new int[BoardConstants.BoardSquareCount];

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

            int end = (BoardConstants.StartIndex[pce] + board.pceCount[pce]) - 1;
            int index = board.pceListIndexFromSq[square];

            board.pceListIndexFromSq[square] = Squares.OffBoard;
          

            if (index != end)
            {
                board.pceLst[index] = board.pceLst[end];
                board.pceListIndexFromSq[board.pceLst[index]] = index;
            }

            board.pceLst[end] = Squares.OffBoard;
            board.pceCount[pce]--;
        }

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);

            int start = BoardConstants.StartIndex[pce];
            int end = (start + board.pceCount[pce]) - 1;

            int index = board.pceListIndexFromSq[fromsq];
            board.pceLst[index] = tosq;
            board.pceListIndexFromSq[fromsq] = Squares.OffBoard;
            board.pceListIndexFromSq[tosq] = index;
        }

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

            int newIndex = board.pceCount[pce] + BoardConstants.StartIndex[pce];
            board.pceListIndexFromSq[square] = newIndex;
            board.pceLst[newIndex] = square;
            board.pceCount[pce]++;
        }

Test run showed 4100 knps, so things are moving in the right direction!

[Richard Allbert]

And the profile...



And the source....

Source

[RoadWarrior]

Test run showed 4100 knps, so things are moving in the right direction!

This is promising as you've more than doubled the speed. Are you profiling the optimised release build with all the settings set for max speed? The only non-optimal setting you might need is /pdbonly so that the profiler can measure performance at the line level.

Making stuff static might indeed interfere with later SMP work. The idea is to test whether it makes a significant difference. If it does make a difference, then you need to make a decision about when the SMP work is going to happen. In my engine, I'm kicking that can down the street for at least a year, given my 1-2 hours a day of development time.