c++ - 从连续的单词序列中提取任意范围的位的最有效方法是什么？

Question

假设我们有一个 std::vector ，或任何其他序列容器(有时是双端队列)，它存储 uint64_t元素。

现在，让我们将此 vector 视为 size() * 64 的序列连续位。我需要找到由给定 [begin, end) 中的位组成的单词范围，鉴于 end - begin <= 64所以它适合一个词。

我现在的解决方案是找到其部分将构成结果的两个词，并将它们分别屏蔽和组合。因为我需要它尽可能高效，所以我尝试在没有任何 if 的情况下编写所有代码。分支不会导致分支预测错误，因此例如，当整个范围适合一个词或跨越两个词时，代码在两种情况下都有效，而不采用不同的路径。为此，我需要对这些 shiftl 进行编码和 shiftr函数，除了将单词移动指定的量外什么都不做，比如 >>和 <<运算符，但优雅地处理了 n 时的情况大于 64，否则将是未定义的行为。

另一点是 get()现在编码的函数也适用于数学意义上的空范围，例如不仅如果 begin == end，而且如果 begin > end，这是调用此函数的主要算法所要求的。同样，在这种情况下，我尝试不简单地分支并返回零来执行此操作。

然而，再看看汇编代码，所有这些似乎都太复杂了，无法执行这样一个看似简单的任务。此代码在性能关键算法中运行，该算法运行速度有点太慢。 valgrind告诉我们这个函数被调用了 2.3 亿次，占总执行时间的 40%，所以我真的需要让它更快。

那么你能帮我找到一种更简单和/或更有效的方法来完成这项任务吗？我不太关心可移植性。使用 x86 SIMD intrinsics (SSE3/4/AVX ecc...) 或编译器内置的解决方案是可以的，就我可以用两者编译它们而言 g++和 clang .

我当前的代码如下:

using word_type = uint64_t;
const size_t W = 64;

// Shift right, but without being undefined behaviour if n >= 64
word_type shiftr(word_type val, size_t n)
{
    uint64_t good = n < W;

    return good * (val >> (n * good));
}

// Shift left, but without being undefined behaviour if n >= 64
word_type shiftl(word_type val, size_t n)
{
    uint64_t good = n < W;

    return good * (val << (n * good));
}

// Mask the word preserving only the lower n bits.
word_type lowbits(word_type val, size_t n)
{
    word_type mask = shiftr(word_type(-1), W - n);

    return val & mask;
}

// Struct for return values of locate()
struct range_location_t {
    size_t lindex; // The word where is located the 'begin' position
    size_t hindex; // The word where is located the 'end' position
    size_t lbegin; // The position of 'begin' into its word
    size_t llen;   // The length of the lower part of the word
    size_t hlen;   // The length of the higher part of the word
};

// Locate the one or two words that will make up the result
range_location_t locate(size_t begin, size_t end)
{
    size_t lindex = begin / W;
    size_t hindex = end / W;
    size_t lbegin = begin % W;
    size_t hend   = end % W;

    size_t len = (end - begin) * size_t(begin <= end);
    size_t hlen = hend * (hindex > lindex);
    size_t llen = len - hlen;

    return { lindex, hindex, lbegin, llen, hlen };
}

// Main function.
template<typename Container>
word_type get(Container const&container, size_t begin, size_t end)
{
    assert(begin < container.size() * W);
    assert(end <= container.size() * W);

    range_location_t loc = locate(begin, end);

    word_type low = lowbits(container[loc.lindex] >> loc.lbegin, loc.llen);

    word_type high = shiftl(lowbits(container[loc.hindex], loc.hlen), loc.llen);

    return high | low;
}

非常感谢。

Answer 1

这取代了 get() 和 get() 使用的所有辅助函数。它包含一个条件分支并节省了大约 16 个算术运算，这意味着它通常应该运行得更快。经过一些优化编译后，它还会生成非常短的代码。最后，它解决了在 end==container.size()*W 的情况下导致访问 container[container.size()] 的错误。

最棘手的部分是“hi-(hi>0)”，它从 hi 中减去 1，除非 hi 为 0。减去 1 不会改变任何东西，除非 hi 仅指向单词边界，即 hi%64 ==0。在那种情况下，我们需要来自上层容器条目的 0 位，因此仅使用下层容器条目就足够了。通过在计算 hi_off 之前减去 1，我们确保了条件“hi_off==lo_off”，并且我们遇到了更简单的情况。

在这种更简单的情况下，我们只需要一个容器入口并在两边切掉一些位。 hi_val 是那个条目，高位已经被切掉，因此唯一剩下要做的就是删除一些低位。

在不太简单的情况下，我们还必须读取较低的容器条目，去除其中未使用的字节，然后合并两个条目。

namespace {
  size_t   const upper_mask = ~(size_t)0u << 6u;
  unsigned const lower_mask = (unsigned)~upper_mask;
}

word_type get ( Container const &container, size_t lo, size_t hi )
{
  size_t lo_off = lo       >>6u;  assert ( lo_off < container.size() );
  size_t hi_off = hi-(hi>0)>>6u;  assert ( hi_off < container.size() );
  unsigned hi_shift = lower_mask&(unsigned)(upper_mask-hi);
  word_type hi_val = container[hi_off] << hi_shift >> hi_shift;
  unsigned lo_shift = lower_mask&(unsigned)lo;
  if ( hi_off == lo_off ) return hi_val >> lo_shift; // use hi_val as lower word
  return ( hi_val<<W-lo_shift | container[lo_off]>>lo_shift ) * (lo_off<hi_off);
}