c++ - 优化位 vector 检查是否是另一个位 vector 的真子集？

Question

我需要一些帮助来优化我程序中计算量最大的函数。目前，我发现基本(非 SSE)版本明显更快(高达 3 倍)。因此，我请求您帮助纠正这一问题。

该函数在无符号整数 vector 中查找子集，并报告它们是否存在。为了您的方便，我只包含了相关的代码片段。

首先是基本变体。它检查 blocks_ 是否是 x.blocks_ 的适当子集。 (不完全相等。)这些是位图，又名位 vector 或位集。

//Check for self comparison
    if (this == &x)
            return false;

//A subset is equal to or smaller.
    if (no_bits_ > x.no_bits_)
            return false;

    int i;

    bool equal = false;

//Pointers should not change.  
    const unsigned int *tptr = blocks_;
    const unsigned int *xptr = x.blocks_;

    
    for (i = 0; i < no_blocks_; i++, tptr++, xptr++) {
            if ((*tptr & *xptr) != *tptr)
                    return false;
            if (*tptr != *xptr)
                    equal = true;
    }

    return equal;

然后是 SSE 变体，唉，它的表现并不符合我的预期。这两个片段应该寻找相同的东西。

    //starting pointers.        
    const __m128i* start = (__m128i*)&blocks_;
    const __m128i* xstart = (__m128i*)&x.blocks_;
    
    __m128i block;
    __m128i xblock;

    //Unsigned ints are 32 bits, meaning 4 can fit in a register.
    for (i = 0; i < no_blocks_; i+=4) {

            block = _mm_load_si128(start + i);
            xblock = _mm_load_si128(xstart + i);

                    //Equivalent to  (block & xblock) != block
                    if (_mm_movemask_epi8(_mm_cmpeq_epi32(_mm_and_si128(block, xblock), block)) != 0xffff)
                            return false;

                    //Equivalent to block != xblock
                    if (_mm_movemask_epi8(_mm_cmpeq_epi32(block, xblock)) != 0xffff)
                            equal = true;
    }
    return equal;

关于如何改进 SSE 版本的性能，您有什么建议吗？难道我做错了什么？还是应该在其他地方进行优化？

我还没有添加 no_blocks_ % 4 != 0 的剩余计算，但是在性能提高之前这样做没有什么意义，而且此时只会使代码困惑点。

Answer 1

我在这里看到三种可能性。

首先，您的数据可能不适合广泛比较。如果 (*tptr & *xptr) != *tptr 在前几个 block 中的可能性很高，那么纯 C++ 版本几乎肯定会更快。在这种情况下，您的 SSE 将运行更多代码和数据来完成同样的事情。

其次，您的 SSE 代码可能不正确。这里还不是很清楚。如果 no_blocks_ 在两个样本之间是相同的，那么 start + i 可能具有索引到 128 位元素而不是第一个样本的 32 位元素的不良行为。

第三，SSE 真的喜欢指令可以流水线化，这是一个很短的循环，您可能无法理解。您可以通过一次处理多个 SSE block 来显着减少此处的分支。

这是一次处理 2 个 SSE block 的快速未经测试的镜头。请注意，我通过将状态保持在循环之外并仅在结束时进行测试，完全删除了 block != xblock 分支。总的来说，这将每个 int 1.3 个分支移动到 0.25 个。

bool equal(unsigned const *a, unsigned const *b, unsigned count)
{
    __m128i eq1 = _mm_setzero_si128();
    __m128i eq2 = _mm_setzero_si128();

    for (unsigned i = 0; i != count; i += 8)
    {
        __m128i xa1 = _mm_load_si128((__m128i const*)(a + i));
        __m128i xb1 = _mm_load_si128((__m128i const*)(b + i));

        eq1 = _mm_or_si128(eq1, _mm_xor_si128(xa1, xb1));
        xa1 = _mm_cmpeq_epi32(xa1, _mm_and_si128(xa1, xb1));

        __m128i xa2 = _mm_load_si128((__m128i const*)(a + i + 4));
        __m128i xb2 = _mm_load_si128((__m128i const*)(b + i + 4));

        eq2 = _mm_or_si128(eq2, _mm_xor_si128(xa2, xb2));
        xa2 = _mm_cmpeq_epi32(xa2, _mm_and_si128(xa2, xb2));

        if (_mm_movemask_epi8(_mm_packs_epi32(xa1, xa2)) != 0xFFFF)
            return false;
    }

    return _mm_movemask_epi8(_mm_or_si128(eq1, eq2)) != 0;
}

如果您有足够的数据并且在前几个 SSE block 中失败的可能性很低，那么这样的事情至少应该比您的 SSE 快一些。