数组引用速度与按位运算符
Array referencing speed vs bitwise operators
我目前正在制作国际象棋游戏，我将我的信息存储在两个 8 x 8 数组中。第一个存储团队类型（1 代表白色，0 代表无，-1 代表黑色），第二个存储棋子类型（1 代表兵，2 代表车，等等）。由于我正在为游戏编写 AI，我想知道是否可以将这两张地图组合在一起，形成一个 8 x 8 阵列。信息将存储在一个字节中，如下所示：
00 A BC DEF
其中A代表是否移动，BC代表队伍：
00 A 01 DEF for white,
00 A 10 DEF for black,
00 A 00 DEF for nothing
和DEF以类似的方式表示棋子类型。我将通过 & 使用字节掩码来访问这些值。所以这是我的问题。计算机是否能够使用较小的数组更快地访问信息，或者按位函数是否会使它 运行 太慢？内存对我来说不是问题。
这里的答案是"yes, no and maybe"。这真的取决于编译器有多好，它是什么处理器 运行，以及哪个是最重要的，space 或时间。
我的直觉是在位掩码中存储会更慢，无论是一次存储一个字节还是按位模式，检索都差不多。
原因是该店涉及：
value = (value & ~ bits) | new_value;
其中 bits 是您要使用的位的掩码（例如，对于颜色，它将是 0x18 或 00011000。
检查值涉及单个和操作：
value & bits;
另一方面，如果您使用三个 [或四个] 字节来存储每个值，您将获得单个字节存储和每个元素的单个字节加载。这与现代机器上的任何东西一样快。
处理器有多少高速缓存也会对此产生影响 - 从主内存中获取数据甚至执行 L2 cache-fetch 都比两三个额外的简单指令慢。
但对于此类问题的真正答案是：编写一些代码并测量速度。确保你这样做是真实的，这样你就有了正确数量的其他指令，正确数量的数据（处理 5 个字节与构建可能的移动 6 步不同，计算了 100000 个选择[全板]每个 move-level).
您选择 DEF 作为后 3 位是明智的。您可能想使用它们来索引 table，因此只需要掩码，而不是移位和掩码就很好。
如果您想用 BC 位索引 table，将它们作为高 2 位意味着您只需要移位，而不需要掩码。
或者，如果您经常要测试 A 位，将其作为 MSB 可以节省少量代码大小。 test al,al/js（符号位上的分支）比 test al, 0x20 / jnz（第 5 位上的分支）稍短，因为是立即字节。不过，唯一的速度差异在于 x86 代码大小，因此非常小。
利用了类似的技巧，编译器可以使用算术右移将符号位广播到整个寄存器。然后可以将其用作 AND 掩码。
按位运算很便宜。如果您经常需要这两种信息（块类型和颜色），将您的地图打包在一起可能会更好，而不是使用两个单独的数组。四个 16B 向量寄存器可以容纳一整块板。从 L1 缓存中的内存加载在 x86 上非常便宜，如果有很多并行性并且您的代码已经在每个时钟 3 或 4 个 ALU 操作上遇到瓶颈，甚至可能比寄存器中的几个 ALU 操作便宜。 （英特尔 SnB / Haswell）。因此，单独存储它可能是一个胜利，但前提是 L1 中的所有内容都非常热。否则，每次都去争取数据密度。
许多国际象棋程序将棋盘位置存储为 Bitboard，其中 64 位 int 的每个位置代表一个棋盘位置。所以你可能有 "black pawns" 和 "white pawns" 的掩码。您可以将它们组合在一起以获得多块位板。您可以 AND 它们以查看它们相交的位置。
我认为你可以使用聪明的按位的东西来检查主教可以攻击的对角线，等等。 32 位和 64 位立即数很便宜。
我目前正在制作国际象棋游戏，我将我的信息存储在两个 8 x 8 数组中。第一个存储团队类型（1 代表白色，0 代表无，-1 代表黑色），第二个存储棋子类型（1 代表兵，2 代表车，等等）。由于我正在为游戏编写 AI，我想知道是否可以将这两张地图组合在一起，形成一个 8 x 8 阵列。信息将存储在一个字节中，如下所示：
00 A BC DEF
其中A代表是否移动，BC代表队伍：
00 A 01 DEF for white,
00 A 10 DEF for black,
00 A 00 DEF for nothing
和DEF以类似的方式表示棋子类型。我将通过 & 使用字节掩码来访问这些值。所以这是我的问题。计算机是否能够使用较小的数组更快地访问信息，或者按位函数是否会使它 运行 太慢？内存对我来说不是问题。
这里的答案是"yes, no and maybe"。这真的取决于编译器有多好，它是什么处理器 运行，以及哪个是最重要的，space 或时间。
我的直觉是在位掩码中存储会更慢，无论是一次存储一个字节还是按位模式，检索都差不多。
原因是该店涉及：
value = (value & ~ bits) | new_value;
其中 bits 是您要使用的位的掩码（例如，对于颜色，它将是 0x18 或 00011000。
检查值涉及单个和操作：
value & bits;
另一方面，如果您使用三个 [或四个] 字节来存储每个值，您将获得单个字节存储和每个元素的单个字节加载。这与现代机器上的任何东西一样快。
处理器有多少高速缓存也会对此产生影响 - 从主内存中获取数据甚至执行 L2 cache-fetch 都比两三个额外的简单指令慢。
但对于此类问题的真正答案是：编写一些代码并测量速度。确保你这样做是真实的，这样你就有了正确数量的其他指令，正确数量的数据（处理 5 个字节与构建可能的移动 6 步不同，计算了 100000 个选择[全板]每个 move-level).
您选择 DEF 作为后 3 位是明智的。您可能想使用它们来索引 table，因此只需要掩码，而不是移位和掩码就很好。
如果您想用 BC 位索引 table，将它们作为高 2 位意味着您只需要移位，而不需要掩码。
或者，如果您经常要测试 A 位，将其作为 MSB 可以节省少量代码大小。 test al,al/js（符号位上的分支）比 test al, 0x20 / jnz（第 5 位上的分支）稍短，因为是立即字节。不过，唯一的速度差异在于 x86 代码大小，因此非常小。
按位运算很便宜。如果您经常需要这两种信息（块类型和颜色），将您的地图打包在一起可能会更好，而不是使用两个单独的数组。四个 16B 向量寄存器可以容纳一整块板。从 L1 缓存中的内存加载在 x86 上非常便宜，如果有很多并行性并且您的代码已经在每个时钟 3 或 4 个 ALU 操作上遇到瓶颈，甚至可能比寄存器中的几个 ALU 操作便宜。 （英特尔 SnB / Haswell）。因此，单独存储它可能是一个胜利，但前提是 L1 中的所有内容都非常热。否则，每次都去争取数据密度。
许多国际象棋程序将棋盘位置存储为 Bitboard，其中 64 位 int 的每个位置代表一个棋盘位置。所以你可能有 "black pawns" 和 "white pawns" 的掩码。您可以将它们组合在一起以获得多块位板。您可以 AND 它们以查看它们相交的位置。
我认为你可以使用聪明的按位的东西来检查主教可以攻击的对角线，等等。 32 位和 64 位立即数很便宜。