确保内存区域为空（全部为NULL）的最快方法是什么？

Question

如果我有一个unsigned char *data指针，并且我想检查该指针处的size_t length数据是否为空，那么最快的方法是什么？换句话说，确认内存区域是否为空的最快方式是什么？

我正在iOS中实现，因此您可以假设iOS框架可用，如果有帮助的话，简单的C方法（例如memcmp之类）也可以。

请注意，我不尝试清除内存，而是尝试确认它已经清除（如果这有帮助的话，我正在尝试找出位图数据中是否有任何东西）。例如，我认为以下内容会起作用，尽管我还没有尝试过：

- BOOL data:(unsigned char *)data isNullToLength:(size_t)length {
    unsigned char tester[length] = {};
    memset(tester, 0, length);
    if (memcmp(tester, data, length) != 0) {
        return NO;
    }
    return YES;
}

虽然源数据可能非常大，我宁愿不创建一个测试数组，因为我想避免为测试分配内存，即使是暂时的。但是我可能有点太保守了。

更新：一些测试

感谢所有在下面提供出色回答的人。我决定创建一个测试应用程序来查看这些算法的性能，答案让我很惊讶，所以我想分享一下。首先，我将展示我使用的算法版本（在某些情况下，它们与提议的算法稍有不同），然后我将分享一些现场结果。

测试

首先，我创建了一些示例数据：

    size_t length = 1024 * 768;
    unsigned char *data = (unsigned char *)calloc(sizeof(unsigned char), (unsigned long)length);
    int i;
    int count;
    long check;
    int loop = 5000;

每个测试都包括一个循环运行 loop 次。在循环期间，随机数据被添加到和从 data 字节流中删除。注意，有一半的时间实际上没有添加任何数据，所以有一半的时间测试不应该找到任何非零数据。请注意，testZeros 调用是对下面测试例程调用的占位符。计时器在循环前启动并在循环后停止。

    count = 0;
    for (i=0; i<loop; i++) {
        int r = random() % length;
        if (random() % 2) { data[r] = 1; }
        if (! testZeros(data, length)) {
            count++;
        }
        data[r] = 0;
    }

测试 A: nullToLength。这更或多或少是我原先上面的公式，经过调试和简化。

- (BOOL)data:(void *)data isNullToLength:(size_t)length {
    void *tester = (void *)calloc(sizeof(void), (unsigned long)length);
    int test = memcmp(tester, data, length);
    free(tester);
    return (! test);
}

测试 B：allZero。由 Carrotman 提出。

BOOL allZero (unsigned char *data, size_t length) {
    bool allZero = true;
    for (int i = 0; i < length; i++){
        if (*data++){
            allZero = false;
            break;
        }
    }
    return allZero;
}

测试 C：is_all_zero。由 Lundin 提出。

BOOL is_all_zero (unsigned char *data, size_t length)
{
    BOOL result = TRUE;
    unsigned char* end = data + length;
    unsigned char* i;

    for(i=data; i<end; i++) {
        if(*i > 0) {
            result = FALSE;
            break;
        }
    }

    return result;
}

测试D：sumArray。这是来自几乎重复的问题的最佳答案，由vladr提出。

BOOL sumArray (unsigned char *data, size_t length) {
    int sum = 0;
    for (int i = 0; i < length; ++i) {
        sum |= data[i];
    }
    return (sum == 0);
}

测试E：lulz。由Steve Jessop提出。

BOOL lulz (unsigned char *data, size_t length) {
    if (length == 0) return 1;
    if (*data) return 0;
    return memcmp(data, data+1, length-1) == 0;
}

测试 F：NSData。这是一个我在处理所有这些时在 iOS SDK 中发现的使用 NSData 对象的测试。结果证明，苹果确实有一种比较字节流的方法，旨在与硬件无关。

- (BOOL)nsdTestData: (NSData *)nsdData length: (NSUInteger)length {
    void *tester = (void *)calloc(sizeof(void), (unsigned long)length);
    NSData *nsdTester = [NSData dataWithBytesNoCopy:tester length:(NSUInteger)length freeWhenDone:NO];
    int test = [nsdData isEqualToData:nsdTester];
    free(tester);
    return (test);
}

结果

那么这些方法的比较如何？以下是两组数据，每组数据表示通过检查5000次。首先我在相对陈旧的iMac上运行iPhone模拟器，然后我在第一代iPad上运行。

在运行iPhone 4.3模拟器的iMac上：

// Test A, nullToLength:  0.727 seconds
// Test F, NSData:        0.727
// Test E, lulz:          0.735
// Test C, is_all_zero:   7.340
// Test B, allZero:       8.736
// Test D, sumArray:     13.995

在第一代iPad上：

// Test A, nullToLength: 21.770 seconds
// Test F, NSData:       22.184
// Test E, lulz:         26.036
// Test C, is_all_zero:  54.747
// Test B, allZero:      63.185
// Test D, sumArray:     84.014

这只是两个样本，我运行了很多次测试，结果略有不同。性能的顺序总是相同的：A&F非常接近，E稍微落后，C、B和D。我会说A、F和E是虚拟并列的，在iOS上我更喜欢F，因为它利用了苹果对处理器更改问题的保护，但A和E也非常接近。从memcmp方法显然比简单的循环方法胜出，在模拟器上快近十倍，设备本身上快两倍。奇怪的是，在另一篇帖子中获胜的答案D在这个测试中表现非常差，可能是因为当它遇到第一个不同之处时没有跳出循环。

- EFC

---

可能是 快速检查字符数组是否为零的方法 的重复。 - DarkDust

为什么同时标记了C和Objective-C？您使用的是哪种语言？ - Lundin

是的，对我来说看起来也是重复的。抱歉。在发布我的问题之前我搜寻了很久，但没有找到那个。唉。 - EFC

@DarkDust，除非发帖人使用与您链接的那个32位x86问题中完全相同的硬件，否则这不是重复。 - Lundin

我正在使用Objective-C，但任何C代码都可以在Objective-C中工作，因此我为两者都打了标签。我主要将ObjC标签放在那里，以防有什么东西或iOS框架可以提供解决问题的新方法。例如，我对像加速框架这样的东西知之甚少，但它可能是适用的。 - EFC

@Lundin：链接问题的最佳答案没有使用任何架构相关代码，也可以在ARM上工作（包括小端和大端）。即使ARM也有SIMD（称为NEON）。 - DarkDust

Answer 1

我认为你应该使用显式循环来完成，但仅仅是为了好玩：

if (length == 0) return 1;
if (*pdata) return 0;
return memcmp(pdata, pdata+1, length-1) == 0;

与memcpy不同，memcmp不要求两个数据段不重叠。但是由于输入指针的未对齐性，它可能比循环更慢，因为实现memcmp的方式可能没有太多优化的空间，并且它正在将内存与内存进行比较，而不是将内存与常量进行比较。很容易对其进行分析并找出答案。

- Steve Jessop

Answer 2

我不确定这是否是最好的方法，但我可能会这样做：

bool allZero = true;
for (int i = 0; i < size_t; i++){
    if (*data++){
        //Roll back so data points to the non-zero char
        data--;
        //Do whatever is needed if it isn't zero.
        allZero = false;
        break;
    }
}

如果您刚刚分配了这块内存，您可以随时调用calloc而不是malloc（calloc要求所有数据都被清零）。（编辑：根据您在第一篇帖子中的评论，您实际上并不需要这个。我只是留下它以防万一）

- Carrotman42

---

是的，这种方法可行，而且不需要分配测试数组，我很喜欢。循环是最快的方法吗？我希望有一些C调用或更快的框架工具。 - EFC

我从未使用过Objective-C进行编程（只用过C/C++），但我认为循环是仅使用该语言（无调用）完成此操作的最快方法。我不知道是否有任何C调用可以完成此操作，但如果有人知道这样的调用，我很乐意听取建议。 - Carrotman42

@Carrotman：根据CPU的不同，循环体内不进行任何条件检查，只需通过“OR”内存内容累加一个int，然后在循环后检查该int可能会更快。这样，编译器可以进行各种优化，如循环展开和使用SIMD指令，从而理论上使平均情况更快。 - DarkDust

@DarkDust：该尝试优化的有效性还取决于输入是否通常为全0，如果不是，则第一个非零字节在哪里。显然，如果您正在OR 1GB的内存，但第一个差异在第二个字节中，则无论使用多少SIMD都无济于事。基本上，输入越大，提前退出就越好，因此您的建议的一个改进是使用两个循环-一个内部循环，如您所描述的一次处理中等大小的数据块，然后是可以提前退出的外部循环。 - Steve Jessop

Answer 3

如果您正在自行分配内存，我建议使用calloc()函数。 它与malloc()非常相似，只是首先将缓冲区清零。 这是用于为Objective-C对象分配内存的原因，并且是所有实例变量默认为0的原因。

另一方面，如果这是静态声明的缓冲区或者您没有自己分配的缓冲区，则memset()是简单实现此操作的方法。

- Dave DeLong

Answer 4

这是在C语言中首选的方法：

BOOL is_all_zero (const unsigned char* data, size_t length)
{
  BOOL result = TRUE;
  const unsigned char* end = data + length;
  const unsigned char* i;

  for(i=data; i<end; i++)
  {
    if(*i > 0)
    {
      result = FALSE;
      break;
    }
  }

  return result;
}

（请注意，严格来说，包含空指针的内存单元不一定必须为0，只要将空指针强制转换为值为零，并将零强制转换为指针结果为NULL指针即可。实际上，这并不重要，因为所有已知的编译器都使用0或(void*) 0表示NULL。）

- Lundin

Answer 5

获取一个值、检查它并设置它的逻辑操作，所需开销至少与仅简单设置相同。你想要它为空，因此只需使用memset()将其设置为null。

- djna

---

不，我不希望它为空，我需要检查它是否为空。换句话说，我从其他地方获取了数据，我只想找出它是否为空或者有任何非空值。 - EFC

Answer 6

请注意上面对初始问题的编辑。我进行了一些测试，很明显使用memcmp方法或使用苹果的NSData对象及其isEqualToData:方法是速度最快的方法。简单的循环对我来说更清晰，但在设备上速度较慢。

- EFC