转换表示为ulong值的4x4矩阵(尽可能快)

Question

我一直在研究2048的C#实现，目的是实现强化学习。

每次移动的"滑动"操作都需要根据特定规则移动和组合瓷砖。这样做需要对值的2d数组进行多次转换。

直到最近，我还在使用4x4字节矩阵：

var field = new byte[4,4];

每个值都是2的指数，因此0=0、1=2、2=4、3=8等等。2048瓦片将由11表示。

因为给定瓦片的(实际(最大值是15(只需要4位(，所以可以将这个4x4字节数组的内容推送到ulong值中。

事实证明，使用这种表示，某些操作的效率要高得多。例如，我通常必须反转这样的数组：

//flip horizontally
const byte SZ = 4;
public static byte[,] Invert(this byte[,] squares)
{
var tmp = new byte[SZ, SZ];
for (byte x = 0; x < SZ; x++)
for (byte y = 0; y < SZ; y++)
tmp[x, y] = squares[x, SZ - y - 1];
return tmp;
}

我可以更快地将ulong~15x转化为

public static ulong Invert(this ulong state)
{
ulong c1 = state & 0xF000F000F000F000L;
ulong c2 = state & 0x0F000F000F000F00L;
ulong c3 = state & 0x00F000F000F000F0L;
ulong c4 = state & 0x000F000F000F000FL;
return (c1 >> 12) | (c2 >> 4) | (c3 << 4) | (c4 << 12);
}

注意使用十六进制，这非常有用，因为每个字符代表一个瓦片。

我遇到最大麻烦的操作是Transpose，它翻转了二维数组中值的x和y坐标，如下所示：

public static byte[,] Transpose(this byte[,] squares)
{
var tmp = new byte[SZ, SZ];
for (byte x = 0; x < SZ; x++)
for (byte y = 0; y < SZ; y++)
tmp[y, x] = squares[x, y];
return tmp;
}

我发现最快的方法是使用这种荒谬的东西：

public static ulong Transpose(this ulong state)
{
ulong result = state & 0xF0000F0000F0000FL; //unchanged diagonals
result |= (state & 0x0F00000000000000L) >> 12;
result |= (state & 0x00F0000000000000L) >> 24;
result |= (state & 0x000F000000000000L) >> 36;
result |= (state & 0x0000F00000000000L) << 12;
result |= (state & 0x000000F000000000L) >> 12;
result |= (state & 0x0000000F00000000L) >> 24;
result |= (state & 0x00000000F0000000L) << 24;
result |= (state & 0x000000000F000000L) << 12;
result |= (state & 0x00000000000F0000L) >> 12;
result |= (state & 0x000000000000F000L) << 36;
result |= (state & 0x0000000000000F00L) << 24;
result |= (state & 0x00000000000000F0L) << 12;
return result;
}

令人震惊的是，这仍然比循环版本快了近3倍。然而，我正在寻找一种更高性能的方法，要么利用换位中固有的模式，要么对我移动的比特进行更有效的管理。

Answer 1

你可以通过组合跳过6个步骤，我把它们注释出来给你看结果，应该会让它快一倍：

public static ulong Transpose(this ulong state)
{
ulong result = state & 0xF0000F0000F0000FL; //unchanged diagonals
result |= (state & 0x0F0000F0000F0000L) >> 12;
result |= (state & 0x00F0000F00000000L) >> 24;
result |= (state & 0x000F000000000000L) >> 36;
result |= (state & 0x0000F0000F0000F0L) << 12;
//result |= (state & 0x000000F000000000L) >> 12;
//result |= (state & 0x0000000F00000000L) >> 24;
result |= (state & 0x00000000F0000F00L) << 24;
//result |= (state & 0x000000000F000000L) << 12;
//result |= (state & 0x00000000000F0000L) >> 12;
result |= (state & 0x000000000000F000L) << 36;
//result |= (state & 0x0000000000000F00L) << 24;
//result |= (state & 0x00000000000000F0L) << 12;
return result;
}

Answer 2

另一个技巧是，有时可以使用乘法将不相交的位组集向左移动不同的量。这就要求部分产品不能"重叠"。

例如，12和24左边的移动可以按以下方式进行：

ulong t = (state & 0x0000F000FF000FF0UL) * ((1UL << 12) + (1UL << 24));
r0 |= t & 0x0FF000FF000F0000UL;

这将6次操作减少到4次。乘法不应该很慢，在现代处理器上，它需要3个周期，当它进行乘法运算时，处理器也可以继续进行其他步骤。另外，在英特尔上，imul将转到端口1，而移位则转到端口0和6，因此用乘法节省两个移位是一笔不错的交易，为其他移位腾出了更多空间。AND和OR操作可以到达任何ALU端口，在这里并不是真正的问题，但它可能有助于延迟拆分依赖OR链：

public static ulong Transpose(this ulong state)
{
ulong r0 = state & 0xF0000F0000F0000FL; //unchanged diagonals
ulong t = (state & 0x0000F000FF000FF0UL) * ((1UL << 12) + (1UL << 24));
ulong r1 = (state & 0x0F0000F0000F0000L) >> 12;
r0 |= (state & 0x00F0000F00000000L) >> 24;
r1 |= (state & 0x000F000000000000L) >> 36;
r0 |= (state & 0x000000000000F000L) << 36;
r1 |= t & 0x0FF000FF000F0000UL;
return r0 | r1;
}