在C++中击打memcmp

Question

我再次决定击败system memcmp函数。这一次，我决定使用一个模板，并“预编译”从0到31字节的所有情况。

结果改善400% --从1:15到0:25 min。

最后，我用朴素的语句重写了memcmp_fixed_，我注意到编译器也可以优化它。

但是，我没有使用随机数据进行测试，所以我不确定缓存行和分支预测器在测试中扮演了什么角色。

以下是代码：

#include <cstdint>
#include <cstring>

namespace{

template<size_t SIZE>
int memcmp_fixed_(const unsigned char *s1, const unsigned char *s2){
    for(size_t i = 0; i < SIZE; ++i)
        if (s1[i] != s2[i])
            return s1[i] - s2[i];

    return 0;
}

template<>
int memcmp_fixed_<1>(const unsigned char *s1, const unsigned char *s2){
    return *s1 - *s2;
}

template<size_t SIZE>
int memcmp_fixed_(const void *a1, const void *a2){
    const unsigned char *s1 = (const unsigned char *) a1;
    const unsigned char *s2 = (const unsigned char *) a2;

    return memcmp_fixed_<SIZE>(s1, s2);
}

}

inline int fast_memcmp(const void *a1, const void *a2, size_t const size){
    switch(size){
        case  0: return 0;

        case  1: return memcmp_fixed_< 1>(a1, a2);
        case  2: return memcmp_fixed_< 2>(a1, a2);
        case  3: return memcmp_fixed_< 3>(a1, a2);
        case  4: return memcmp_fixed_< 4>(a1, a2);
        case  5: return memcmp_fixed_< 5>(a1, a2);
        case  6: return memcmp_fixed_< 6>(a1, a2);
        case  7: return memcmp_fixed_< 7>(a1, a2);
        case  8: return memcmp_fixed_< 8>(a1, a2);
        case  9: return memcmp_fixed_< 9>(a1, a2);
        case 10: return memcmp_fixed_<10>(a1, a2);
        case 21: return memcmp_fixed_<21>(a1, a2);
        case 22: return memcmp_fixed_<22>(a1, a2);
        case 23: return memcmp_fixed_<23>(a1, a2);
        case 24: return memcmp_fixed_<24>(a1, a2);
        case 25: return memcmp_fixed_<25>(a1, a2);
        case 26: return memcmp_fixed_<26>(a1, a2);
        case 27: return memcmp_fixed_<27>(a1, a2);
        case 28: return memcmp_fixed_<28>(a1, a2);
        case 29: return memcmp_fixed_<29>(a1, a2);
        case 30: return memcmp_fixed_<30>(a1, a2);
        case 31: return memcmp_fixed_<31>(a1, a2);

        default: return memcmp(a1, a2, size);
    }
}

#include <cstdio>

#include <algorithm>    // min

size_t const MAX = 10000000000;

int main(int argc, char **argv){
    if (argc != 3){
        printf("Usage:\n");
        printf("\t%s [string1] [string2]\n", argv[0]);
        return 1;
    }

    const char *s1 = argv[1];
    const char *s2 = argv[2];

    size_t const size1 = strlen(s1);
    size_t const size2 = strlen(s2);
    size_t const size  = std::min(size1, size2);

    volatile int x = 0;
    for(volatile size_t i = 0; i < MAX; ++i)
        x += fast_memcmp(s1, s2, size);

    printf("%d %d\n", fast_memcmp(s1, s2, size), x );
}

基线是：

#include <cstdint>
#include <cstring>

#include <cstdio>

#include <algorithm>    // min

size_t const MAX = 10000000000;

int main(int argc, char **argv){
    if (argc != 3){
        printf("Usage:\n");
        printf("\t%s [string1] [string2]\n", argv[0]);
        return 1;
    }

    const char *s1 = argv[1];
    const char *s2 = argv[2];

    size_t const size1 = strlen(s1);
    size_t const size2 = strlen(s2);
    size_t const size  = std::min(size1, size2);

    volatile int x = 0;
    for(volatile size_t i = 0; i < MAX; ++i)
        x += memcmp(s1, s2, size);

    printf("%d %d\n", memcmp(s1, s2, size), x );
}

Answer 1

由于我们使用的是标准C函数的C++包装器(这很好--我喜欢它！)，我们需要std::size_t和std::memcmp的命名空间限定。尽管您的实现显然利用了许可证来包含不合格的名称，但是依赖它是不可移植的。

在将a1转换为s1，将a2转换为s2时，我们不必重复这种类型，我们只需使用auto (让我们弄清楚cast -偏好reinterpret_cast而不是catch-所有C风格的强制转换)。

通过使用递归模板，我设法简化了memcmp_fixed_。对于我(使用g++ -03)来说，这给出了大致相同的执行速度(我猜循环展开使生成的二进制非常相似)。我摆脱了单独的void*和unsigned char*重载--这只是编译时的开销，与运行时的速度没有什么不同，运行时的速度是9行，而不是14行(计算包含字母数字的物理行数)。

template<std::size_t SIZE>
int memcmp_fixed_(const void *a1, const void *a2)
{
    auto const s1 = reinterpret_cast<const unsigned char*>(a1);
    auto const s2 = reinterpret_cast<const unsigned char*>(a2);
    auto const diff = *s1 - *s2;
    return diff ? diff : memcmp_fixed_<SIZE-1>(s1+1, s2+1);
}

template<>
int memcmp_fixed_<0>(const void*, const void*)
{
    return 0;
}

我稍微简化了测试程序，使其成为一个单字符更改，以构建基线测试(并发送它们所属的错误消息)，并大量减少重复代码：

#if 1
#define test_memcmp fast_memcmp
#else
#define test_memcmp std::memcmp
#endif

int main(int argc, char **argv)
{
    if (argc != 3) {
        std::fprintf(stderr, "Usage:\n\t%s [string1] [string2]\n", argv[0]);
        return 1;
    }

    const char *s1 = argv[1];
    const char *s2 = argv[2];
    auto const size  = std::min(strlen(s1), strlen(s2));

    volatile int x = 0;
    for (volatile std::size_t i = 0;  i < MAX;  ++i)
        x += test_memcmp(s1, s2, size);

    std::printf("%d %d\n", test_memcmp(s1, s2, size), x);
}