如何优化C++中基于PEXT的国际象棋车移动查表性能？

我正在开发一款国际象棋AI，采用位棋盘（bit-boards）表示棋盘与棋子。查阅资料得知使用PEXT指令可加速滑动棋子的移动查表，但自行实现后，该方案反而比原逻辑运算实现慢约25%。

PEXT实现的车移动攻击范围代码 #

uint64_t Move_lookup::get_rook_moves(int index, uint64_t all_pieces) {
    int index2 = _pext_u64(all_pieces, rook_masks[index]);
    return rook_moves[index][index2];
}

查表表的定义：

std::vector<std::vector<uint64_t>> rook_moves;

原逻辑运算实现（未使用） #

uint64_t Board::get_rook_moves(uint64_t* b, pieceColour colour, int n) {
    // We must perform the operation on the set the function was called with
    uint64_t rooks = *b;
    isolate_piece(&rooks, n); // This gets rid of all the 1's we are not interested in in rooks
    
    // Get all enemy pieces
    uint64_t enemy_pieces = all_pieces(invert_colour(colour));
    
    // Combined pieces for obstacle detection
    uint64_t black_white_pieces = all_pieces(colour) | enemy_pieces;
    
    uint64_t attacks = 0ULL;
    
    // We need to look in all four straight directions (N,E,S,W) until we hit the edge of the board or another piece
    // North
    uint64_t move = rooks;
    while (move & NOT_RANK_8) {  // Continue while not on the last rank
        move <<= 8;  // Move one rank up
        if (move & black_white_pieces) {  // Stop if a piece is encountered
            if (move & enemy_pieces) attacks |= move;  // If enemy piece, include in attacks
            break;
        }
        attacks |= move;  // Add square to attacks
    }
    
    // East
    move = rooks;
    while (move & NOT_H_FILE) {  // Continue while not on the H file
        move >>= 1;  // Move one file right
        if (move & black_white_pieces) {  // Stop if a piece is encountered
            if (move & enemy_pieces) attacks |= move;  // If enemy piece, include in attacks
            break;
        }
        attacks |= move;  // Add square to attacks
    }
    
    // South
    move = rooks;
    while (move & NOT_RANK_1) {  // Continue while not on the first rank
        move >>= 8;  // Move one rank down
        if (move & black_white_pieces) {  // Stop if a piece is encountered
            if (move & enemy_pieces) attacks |= move;  // If enemy piece, include in attacks
            break;
        }
        attacks |= move;  // Add square to attacks
    }
    
    // West
    move = rooks;
    while (move & NOT_A_FILE) {  // Continue while not on the A file
        move <<= 1;  // Move one file left
        if (move & black_white_pieces) {  // Stop if a piece is encountered
            if (move & enemy_pieces) attacks |= move;  // If enemy piece, include in attacks
            break;
        }
        attacks |= move;  // Add square to attacks
    }
    
    return attacks;
}

填充车攻击范围查表的代码（仅启动时执行一次） #

void Move_lookup::fill_rook_moves() {
    uint64_t i = 1ULL;
    for (auto& mask : rook_masks) {

        int count = count_set(mask);
        std::vector<uint64_t> perms = bin_n_perms_asc(count); // Get all permutations of the bits
        std::vector<uint64_t> temp;

        for (const auto& perm : perms) {
            uint64_t blockers = _pdep_u64(perm, mask); // Put the permutations on to the blockers
            uint64_t attacks = 0ULL;

            // We need to look in all four straight directions (N,E,S,W) until we hit the edge of the board or a blocker
            // North
            uint64_t move = i;
            while (move & NOT_RANK_8) {  // Continue while not on the last rank
                move <<= 8;  // Move one rank up
                attacks |= move;  // Add square to attacks
                if (move & blockers) break;
            }

            // East
            move = i;
            while (move & NOT_A_FILE) {  // Continue while not on the A file
                move >>= 1;  // Move one file right
                attacks |= move;  // Add square to attacks
                if (move & blockers) break;
            }

            // South
            move = i;
            while (move & NOT_RANK_1) {  // Continue while not on the first rank
                move >>= 8;  // Move one rank down
                attacks |= move;  // Add square to attacks
                if (move & blockers) break;
            }

            // West
            move = i;
            while (move & NOT_H_FILE) {  // Continue while not on the H file
                move <<= 1;  // Move one file left
                attacks |= move;  // Add square to attacks
                if (move & blockers) break;
            }

            temp.push_back(attacks);
        }   

        rook_moves.push_back(temp);
        i <<= 1;
    }
}

我猜测查表速度慢可能是因为表的规模过大（包含超10万个元素），但所有未做尺寸优化的PEXT查表实现都需要这样的表规模。请问有什么方法可以提升我的查表速度？

优化建议 #

• 优化内存布局，提升缓存命中率
  二维vector的内层容器内存不连续，会导致CPU缓存命中率低。可以将查表数据改为一维连续数组，通过index * 单位置最大排列数 + index2计算索引，让数据更好地利用CPU缓存行；也可以用std::array替代内层vector（若每个位置的排列数可提前确定），编译期固定内存布局，减少运行时内存访问开销。

• 确保PEXT指令的硬件支持与编译优化
  确认CPU支持BMI2指令集（PEXT属于BMI2），编译时开启对应优化选项：GCC用-mbmi2，MSVC用/arch:AVX2（包含BMI2）。若未开启，编译器会用软件模拟PEXT，速度大幅下降。可通过__builtin_cpu_supports("bmi2")（GCC）或CPUID检测（MSVC）判断硬件支持，运行时选择PEXT查表或原逻辑实现的分支。

• 减少索引计算开销
  统一使用size_t作为索引类型，避免int与容器索引类型的转换开销；提前计算每个位置掩码对应的排列数并缓存，减少运行时额外计算。

• 预计算并静态初始化查表
  用脚本预计算所有攻击范围数据，生成头文件直接编译进程序。这样既避免启动时初始化耗时，还能让数据放在只读数据段，提升缓存效率。

• 优化掩码设计
  检查rook_masks是否为最小必要掩码——标准滑动棋子掩码只包含棋子到棋盘边缘的关键位置，不包含棋子本身所在格子。若掩码包含无关位，会增加PEXT计算量和查表规模。

内容的提问来源于stack exchange，提问作者Michael