c++ - 有什么方法可以加快这个位列表代码的速度吗？

Question

我在列表中存储了可变数量的位。我需要查找 [i,j] 范围内的位。目前，我将这些位存储在无符号 32 位整数 vector 中。

这是我进行查找的方式:

std::uint32_t
Data::findInt3(const std::vector<std::uint32_t>& input, int size, int pos) {
    pos = pos*size;
    int firstc = pos >> 5;
    int ipos = pos & 31;
    int end = ipos+size;
    std::uint64_t t = input[firstc];

    std::uint64_t num = (t << 32) | input[firstc+1];
    std::uint64_t number = num >> (64-end);
    number = number & ((1 << size)-1);

    return number;
}

这段代码被调用了很多次。我想只是小的加速将是非常有益的。任何人都可以看到可以做得更好的东西吗？就像移动某物而不是 or'ing。或者哪个更快？

谢谢

Answer 1

这段代码执行了几件事:

1. 计算指数
2. 它访问一个 vector ，使用计算索引(我猜它是某种查找表)
3. 它使用 vector 的值计算结果

所以，仅仅看一下，如果不展示它的使用方式，并且不了解整个算法，它似乎无法优化。这些操作看起来已经达到最佳状态。

如果它真的在一个大循环中执行，这就是我会做的:

• 尝试在循环外预先计算一些值
• 尽量不要对 vector 进行这种随机访问，而是进行串行访问(如果是查找表，这可能是不可能的)
• 尝试向量化访问(使用 SIMD 或类似函数)
• 如果没有别的办法，在汇编中实现它