How to clone arrays faster?

Question

In a chess AI program, I have a function that has to do and then undo a move.

In order to do this, I need to save a backup of a bunch of arrays containing data about the current situation on the board (like where the pieces are, which pieces are under attack or if a king is in check, for example), then make the move and finally reset the arrays.

The code I'm using is like this:

int[] piecesBackup = pieces.Clone() as int[];

MakeMove();

pieces = piecesBackup.Clone() as int[];



// I've also tried this



int[] piecesBackup = new int[pieces.Length];
pieces.CopyTo(piecesBackup, 0);

MakeMove();

pieces = new int[piecesBackup.Length];
piecesBackup.CopyTo(pieces, 0);

This code is repeated thousands of times and it takes very long to do so. I suspect that the time consuming operation here is the cloning/copying operation.

I can't think of any better approach to this problem: is this really the only way to copy the contents of an array? Is there any way I could simply use int[] piecesBackup = pieces and then pieces = piecesBackup?

Answer 1

I would guess that most of your time is spent allocating objects or cleaning up garbage. While the GC handles most scenarios quite well, very high frequency allocation can be problematic. But as always, I would recommend some profiling to confirm that this is actually the case. It is very easy to guess incorrectly with regards to performance.

I would try to fit the board state within an immutable struct. Since this is a value type you could get away with removing any heap allocations at all.

My chess knowledge is a bit rusty, but if I'm not mistaken there can be max 32 pieces in play at any time, and 64 possible positions for each piece. So we should be able to represent the entire board with 32 bytes, with some bits left over for other possible uses. 32 bytes is not an unreasonable size for a struct, and should be very fast to create a copy of.

Using a struct might require adding all 32 pieces as separate fields, and this might be more code to write, but well optimized code is often not pretty. I would also recommend reading Eric Lipperts articles on Game of Life for some perspective on game state optimization.

Answer 2

Consider reusing the arrays instead of allocating new arrays each time the copy is performed. Allocating a new array takes time and then there is also the garbage collection that will come along at some point to clear away the old array no longer being used.

Array reuse is an approach that I have used with good performance result. Here is example code to that demonstrates code reuse taking about half as much time as allocating new arrays.

var stopwatch = new System.Diagnostics.Stopwatch();
var innerIterations = 1000000;

int[] pieces = new int[32];
for (int i = 0; i < pieces.Length; i++)
{
    // Put some fake data in the array
    pieces[i] = i * 3;
}

int[] piecesReuse = new int[32];
for (int i = 0; i < piecesReuse.Length; i++)
{
    // Put some fake data in the array
    piecesReuse[i] = i * 3;
}

for (int j = 0; j < 10; j++)
{ 
    Console.WriteLine($"Begin newAllocate round {j} ...");
    stopwatch.Restart();
    for (int i = 0; i < innerIterations; i++)
    {
        int[] piecesBackup = new int[pieces.Length];
        pieces.CopyTo(piecesBackup, 0);

        MakeMove();

        pieces = new int[piecesBackup.Length];
        piecesBackup.CopyTo(pieces, 0);
    }
    stopwatch.Stop();
    Console.WriteLine($"...completed newAllocate round {j} at {stopwatch.ElapsedMilliseconds} ms.");

    Console.WriteLine($"Begin reusedArray round {j} ...");
    stopwatch.Restart();
    int[] piecesBackupReused = new int[piecesReuse.Length];
    for (int i = 0; i < innerIterations; i++)
    {
        piecesReuse.CopyTo(piecesBackupReused, 0);

        MakeMove();

        piecesBackupReused.CopyTo(piecesReuse, 0);
    }
    stopwatch.Stop();
    Console.WriteLine($"...completed reusedArray round {j} at {stopwatch.ElapsedMilliseconds} ms.");
}

void MakeMove()
{
    // Make some change to the arrays
    pieces[0] = 100;
    piecesReuse[0] = 200;
}

The resulting output from my machine (ymmv).

Begin newAllocate round 0 ...
...completed newAllocate round 0 at 98 ms.
Begin reusedArray round 0 ...
...completed reusedArray round 0 at 28 ms.
Begin newAllocate round 1 ...
...completed newAllocate round 1 at 54 ms.
Begin reusedArray round 1 ...
...completed reusedArray round 1 at 27 ms.
Begin newAllocate round 2 ...
...completed newAllocate round 2 at 50 ms.
Begin reusedArray round 2 ...
...completed reusedArray round 2 at 27 ms.
Begin newAllocate round 3 ...
...completed newAllocate round 3 at 51 ms.
Begin reusedArray round 3 ...
...completed reusedArray round 3 at 30 ms.
Begin newAllocate round 4 ...
...completed newAllocate round 4 at 50 ms.
Begin reusedArray round 4 ...
...completed reusedArray round 4 at 26 ms.
Begin newAllocate round 5 ...
...completed newAllocate round 5 at 49 ms.
Begin reusedArray round 5 ...
...completed reusedArray round 5 at 24 ms.
Begin newAllocate round 6 ...
...completed newAllocate round 6 at 47 ms.
Begin reusedArray round 6 ...
...completed reusedArray round 6 at 23 ms.
Begin newAllocate round 7 ...
...completed newAllocate round 7 at 45 ms.
Begin reusedArray round 7 ...
...completed reusedArray round 7 at 24 ms.
Begin newAllocate round 8 ...
...completed newAllocate round 8 at 48 ms.
Begin reusedArray round 8 ...
...completed reusedArray round 8 at 32 ms.
Begin newAllocate round 9 ...
...completed newAllocate round 9 at 40 ms.
Begin reusedArray round 9 ...
...completed reusedArray round 9 at 22 ms.

Answer 3

I suspect that the time consuming operation here is the cloning/copying operation.

You are correct only in that you are using an astronomically bad representation of a chess board. What possible reason would you possibly have to store an array of integers that can go up to 4 billion in a chess game? You have 64 squares and up to 32 pieces total.

As to your analysis, the most time is probably taken by allocating and freeing (GC) all those gigantic arrays. You should be using ArrayPool<> or MemoryPool<> instead, or just plain old structures that have the correct size.