转置表示为 ulong 值的 4x4 矩阵（尽可能快）

Question

为了实施强化学习，我一直在研究 2048 的 C# 实现。

每次移动的"slide"操作需要根据特定规则移动和组合方块。这样做涉及对二维值数组的许多转换。

直到最近我还在使用 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 ~15 倍快：

    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

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

例如，12 和 24 向左移动可以这样完成：

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

这将 6 次运算减少到 4 次。乘法应该不会很慢，在现代处理器上它需要 3 个周期，并且在处理乘法时，处理器也可以继续处理其他步骤。作为奖励，在 Intel 上，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;
}

转置表示为 ulong 值的 4x4 矩阵（尽可能快）

Transposing a 4x4 matrix represented as a ulong value(as fast as possible)

c#

64-bit

bit-manipulation