如果C中为null,检查海量数据的最快方法是什么？

Question

我有大量的数据,可能是4MB.现在想检查它中的所有位是否为0.

例如:这是数据:

void* data = malloc(4*1024*1024);
memset(data, 0, 4*1024*1024);

检查它中的所有位是否为0.这是我的解决方案不够快:

int dataisnull(char* data, int length)
{
    int i = 0;
    while(i<length){
        if (data[i]) return 0;
        i++;
    }
    return 1;
}

此代码可能在性能方面有一些改进.例如,在32/64位机器中,一次检查4/8字节可能更快.

所以我想知道最快的方法是什么？

Answer 1

您可以一次处理多个字节并展开循环:

int dataisnull(const void *data, size_t length) {
    /* assuming data was returned by malloc, thus is properly aligned */
    size_t i = 0, n = length / sizeof(size_t);
    const size_t *pw = data;
    const unsigned char *pb = data;
    size_t val;
#define UNROLL_FACTOR  8
#if UNROLL_FACTOR == 8
    size_t n1 = n - n % UNROLL_FACTOR;
    for (; i < n1; i += UNROLL_FACTOR) {
        val = pw[i + 0] | pw[i + 1] | pw[i + 2] | pw[i + 3] |
              pw[i + 4] | pw[i + 5] | pw[i + 6] | pw[i + 7];
        if (val)
            return 0;
    }
#endif
    val = 0;
    for (; i < n; i++) {
        val |= pw[i];
    }
    for (i = n * sizeof(size_t); i < length; i++) {
        val |= pb[i];
    }
    return val == 0;
}

根据您的具体问题,提前或延迟检测非零值可能更有效:

• 如果全零情况是最常见的情况,则应计算累计所有位累加到val累加器中并仅在结束时进行测试.
• 如果全零情况很少,则应更频繁地检查非零值.

上面展开的版本是一个折衷方案,它根据大小来测试每64或128字节的非零值size_t.

根据您的编译器和处理器,您可以通过展开更少或更多来获得更好的性能.您还可以使用可用于特定体系结构的内部函数来利用矢量类型,但它的可移植性会降低.

请注意,代码不会验证data指针的正确对齐方式:

• 它无法轻松完成.
• 它假定数据是通过malloc或类似分配的,因此适合任何类型.

与往常一样,对不同的解决方案进行基准测试,看看它是否真正产 这个函数可能根本不是瓶颈,编写一个复杂的函数来优化一个罕见的情况会产生反作用,它会使代码的可读性降低,更容易包含错误,而且可维护性更低.例如,如果更改内存分配方案或使用静态数组,则数据对齐的假设可能不成立,该函数可能会调用未定义的行为.

Answer 2

以下检查第一个字节是否是您想要的,并且所有后续字节对都是相同的.

int check_bytes(const char * const data, size_t length, const char val)
{
    if(length == 0) return 1;
    if(*data != val) return 0;
    return memcmp(data, data+1, length-1) ? 0 : 1;
}

int check_bytes64(const char * const data, size_t length, const char val)
{
    const char * const aligned64_start = (char *)((((uintptr_t)data) + 63) / 64 * 64);
    const char * const aligned64_end = (char *)((((uintptr_t)data) + length) / 64 * 64);
    const size_t start_length = aligned64_start - data;
    const size_t aligned64_length = aligned64_end - aligned64_start;
    const size_t end_length = length - start_length - aligned64_length;

    if (!check_bytes(data, start_length, val)) return 0;
    if (!check_bytes(aligned64_end, end_length, val)) return 0;

    return memcmp(aligned64_start, aligned64_start + 64, aligned64_length-64) ? 0 : 1;
}

这个函数的更复杂的版本应该可以将缓存行对齐的指针传递给memcmp,并手动检查剩余的块而不仅仅是第一个字节.

当然,您必须在特定硬件上进行分析,以了解此方法与其他方法相比是否有任何速度优势.

如果有人怀疑这是否有效,那就是想法.