如果在C中为null，检查海量数据的最快方法是什么？
我有大量的数据，可能是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字节可能更快。
所以我想知道最快的方法是什么？
您可以一次处理多个字节并展开循环：
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累加器中并仅在结束时进行测试。 - 如果全零情况很少，则应更频繁地检查非零值。
上面展开的版本是一种折衷方案，它根据size_t的大小每隔64或128个字节测试非零值。
根据您的编译器和处理器，您可以通过展开更少或更多来获得更好的性能。 您还可以使用可用于特定体系结构的内部函数来利用矢量类型，但它的可移植性会降低。
请注意，代码不validationdata指针的正确对齐：
- 它无法轻松完成。
- 它假定数据是通过
malloc或类似方式分配的，因此适合任何类型。
与往常一样，对不同的解决方案进行基准测试，看看它是否真正产 这个函数可能根本不是瓶颈，编写一个复杂的函数来优化一个罕见的情况会产生反作用，它会使代码的可读性降低，更容易包含错误，而且可维护性更低。 例如，如果更改内存分配方案或者使用静态数组，则数据对齐的假设可能不成立，该函数可能会调用未定义的行为。
以下检查第一个字节是否是您想要的，并且所有后续字节对都是相同的。
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 ，并手动检查剩余的块而不是第一个字节。
当然，您必须在特定硬件上进行分析，以了解此方法与其他方法相比是否有任何速度优势。
如果有人怀疑这是否有效，那就是想法 。
我曾经写过以下函数供我自己使用。 它假设要检查的数据是常量块大小的倍数，并且对于机器字的缓冲区正确对齐。 如果在您的情况下没有给出，则单独循环第一个和最后几个字节并不困难，只使用优化函数检查批量。 （严格来说，即使数组正确对齐，但是数据已经被任何与unsigned long不兼容的类型写入，它仍然是未定义的行为。但是，我相信你可以在这里仔细破坏规则。 ）
#include #include #include #include bool is_all_zero_bulk(const void *const p, const size_t n) { typedef unsigned long word_type; const size_t word_size = sizeof(word_type); const size_t chunksize = 8; assert(n % (chunksize * word_size) == 0); assert((((uintptr_t) p) & 0x0f) == 0); const word_type *const frst = (word_type *) p; const word_type *const last = frst + n / word_size; for (const word_type * iter = frst; iter != last; iter += chunksize) { word_type acc = 0; // Trust the compiler to unroll this loop at its own discretion. for (size_t j = 0; j < chunksize; ++j) acc |= iter[j]; if (acc != 0) return false; } return true; }
function本身不是很聪明。 主要思想是：
- 使用大型未签名机器字进行数据比较。
- 通过使用常量迭代计数分解内循环来启用循环展开。
- 通过将单词ORing到累加器中来减少分支数量，并且每隔几次迭代将其与零进行比较。
- 这也应该使编译器可以很容易地使用您真正想要的SIMD指令生成矢量化代码。
额外的非标准调整是使用__attribute__ ((hot))注释函数并使用__builtin_expect(acc != 0, false) 。 当然，最重要的是打开编译器的优化。