在C语言中，使一个二维数组归零的最快方法是什么？

Question

我想在C语言中反复清零一个大的二维数组。目前我的代码如下：

// Array of size n * m, where n may not equal m
for(j = 0; j < n; j++)
{
    for(i = 0; i < m; i++)
    {  
        array[i][j] = 0;
    }
}

我尝试使用memset：

memset(array, 0, sizeof(array))

但是这只适用于1D数组。当我printf 2D数组的内容时，第一行是零，但之后我得到了很多随机的大数字，然后程序崩溃了。

- Eddy

Answer 1

memset(array, 0, sizeof(array[0][0]) * m * n);

m 和 n 分别代表二维数组的宽度和高度（在您的示例中，您有一个正方形的二维数组，因此 m == n）。

- James McNellis

---

它似乎不起作用。在CodeBlocks上我得到了“进程返回-1073741819”的错误，这是一个段错误，对吧？ - Eddy

@Eddy:请展示数组的声明。 - GManNickG

我敢打赌它在其他行崩溃，而不是在memset上，因为你提到仅清零一行时也会崩溃。 - Blindy

尝试声明一个数组 int d0=10, d1=20; int arr[d0][d1]，并使用 memset(arr, 0, sizeof arr); 进行了测试（使用 -std=c99 -Wall 标志进行编译，gcc版本为3.4.6），结果符合预期。我知道“在我的机器上能运行”这个说法并不靠谱，但是 memset(arr, 0, sizeof arr); 应该 能正常工作。sizeof arr 应该 返回整个数组所占用的字节数（即 d0 * d1 * sizeof(int)）。使用 sizeof array[0] * m * n 无法得出正确的数组大小。 - John Bode

@John Bode: 的确如此，但这取决于数组是如何获取的。如果你有一个函数，它接受一个参数 int array[][10]，那么 sizeof(array) == sizeof(int*)，因为第一维的大小未知。OP没有指定数组是如何获取的。 - James McNellis

Answer 2

如果 array 确实是一个数组，那么你可以使用以下方法将其“清零”：

memset(array, 0, sizeof array);

但是有两点需要注意：

• 这仅在array真正是“二维数组”时才有效，即已声明T array[M][N];，其中T为某种类型。
• 它仅在声明array的作用域内有效。如果将其传递给函数，则名称array会衰减为指针，并且sizeof将无法给出数组的大小。

让我们做一个实验：

#include <stdio.h>

void f(int (*arr)[5])
{
    printf("f:    sizeof arr:       %zu\n", sizeof arr);
    printf("f:    sizeof arr[0]:    %zu\n", sizeof arr[0]);
    printf("f:    sizeof arr[0][0]: %zu\n", sizeof arr[0][0]);
}

int main(void)
{
    int arr[10][5];
    printf("main: sizeof arr:       %zu\n", sizeof arr);
    printf("main: sizeof arr[0]:    %zu\n", sizeof arr[0]);
    printf("main: sizeof arr[0][0]: %zu\n\n", sizeof arr[0][0]);
    f(arr);
    return 0;
}

在我的电脑上，以上内容的输出为：

main: sizeof arr:       200
main: sizeof arr[0]:    20
main: sizeof arr[0][0]: 4

f:    sizeof arr:       8
f:    sizeof arr[0]:    20
f:    sizeof arr[0][0]: 4

尽管arr是一个数组，但当传递给f()时，它会衰减为指向其第一个元素的指针，因此在f()中打印的大小是“错误”的。此外，在f()中，arr[0]的大小是数组arr[0]的大小，它是一个“int数组[5]”。它不是int *的大小，因为“衰减”只发生在第一层，这就是为什么我们需要声明f()为接受正确大小的数组指针。

所以，像我之前说的，原来你做的只有在满足上述两个条件时才能起作用。如果不是，你将需要做其他人已经说过的事情：

memset(array, 0, m*n*sizeof array[0][0]);

最后，严格意义上来说，memset()和您发布的for循环并不等价。在某些类型（例如指针和浮点数值）中，“所有位都为零”可能不等于零，因此可能存在（并且确实存在）编译器。然而，我觉得你不需要担心这个问题。

- Alok Singhal

---

memset(array, 0, n*n*sizeof array[0][0]); 我猜你的意思是 m*n 而不是 n*n，对吗？ - Tagc

奇怪的是，这似乎不能处理像1和2这样的值，而不是0。 - Box Box Box Box

memset 在字节（char）级别上工作。由于 1 或 2 在底层表示中的字节不同，因此您不能使用 memset 进行操作。 - Alok Singhal

@AlokSinghal 可以在最小工作示例之前的某个地方指出“int在您的系统上是4字节”，这样读者就可以轻松计算总和。 - 71GA

Answer 3

嗯，最快的方法就是根本不做它。

听起来很奇怪，这是一些伪代码：

int array [][];
bool array_is_empty;


void ClearArray ()
{
   array_is_empty = true;
}

int ReadValue (int x, int y)
{
   return array_is_empty ? 0 : array [x][y];
}

void SetValue (int x, int y, int value)
{
   if (array_is_empty)
   {
      memset (array, 0, number of byte the array uses);
      array_is_empty = false;
   }
   array [x][y] = value;
}

实际上，它仍然会清除数组，但只有在向数组写入内容时才会这样做。在这里这并不是一个很大的优势。但是，如果使用四叉树（而不是动态四叉树）或一组数据行实现2D数组，则可以使布尔标志的影响局部化，但需要更多的标志。在四叉树中，只需为根节点设置空标志，在行数组中，只需为每行设置标志。

这就引出了一个问题：“为什么要重复将一个大的2D数组清零？” 数组是用来做什么的？是否有一种方法可以更改代码，使得数组不需要清零？

例如，如果你有：

clear array
for each set of data
  for each element in data set
    array += element 

也就是说，如果将其用于累积缓冲区，那么像这样更改它将极大地提高性能：

 for set 0 and set 1
   for each element in each set
     array = element1 + element2

 for remaining data sets
   for each element in data set
     array += element 

这不需要清除数组，但仍然有效。而且这比清除数组要快得多。像我说的那样，最快的方式是一开始就不要这么做。

- Skizz

---

有趣的另一种看待这个问题的方式。 - Beska

我不确定为每个读取添加额外的比较/分支是否值得推迟数组的初始化（尽管可能是你的）。如果数组真的很大，以至于初始化时间构成严重问题，那么他可以使用哈希代替。 - tixxit

Answer 4

如果你真的非常追求速度（并不太关心可移植性），我认为使用SIMD向量内在函数可能是绝对最快的方法。例如，在英特尔CPU上，你可以使用这些SSE2指令：

__m128i _mm_setzero_si128 ();                   // Create a quadword with a value of 0.
void _mm_storeu_si128 (__m128i *p, __m128i a);  // Write a quadword to the specified address.

每个存储指令将以一次操作将四个32位整数设置为零。 p必须是16字节对齐的，但这个限制也有助于提高速度，因为它将有助于缓存。另一个限制是p必须指向大小是16字节的分配大小，但这也很好，因为它使我们可以轻松展开循环。

将其放在循环中，并展开几次循环，您将拥有一个疯狂快速的初始化程序：

// Assumes int is 32-bits.
const int mr = roundUpToNearestMultiple(m, 4);      // This isn't the optimal modification of m and n, but done this way here for clarity.    
const int nr = roundUpToNearestMultiple(n, 4);    

int i = 0;
int array[mr][nr] __attribute__ ((aligned (16)));   // GCC directive.
__m128i* px = (__m128i*)array;
const int incr = s >> 2;                            // Unroll it 4 times.
const __m128i zero128 = _mm_setzero_si128();

for(i = 0; i < s; i += incr)
{
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
    _mm_storeu_si128(px++, zero128);
}

还有一种变体的_mm_storeu可以绕过缓存（即清零数组不会污染缓存），在某些情况下可以带来一些次要的性能优势。

请参见SSE2参考：http://msdn.microsoft.com/en-us/library/kcwz153a(v=vs.80).aspx

- Jarrod Smith

Answer 5

如果你使用malloc初始化数组，请改用calloc，它会免费为你清零数组。(与使用memset相比性能相同，但代码更简洁。)

- Ben Zotto

---

如果我想重复清零数组，这个方法比memset更快吗？ - Eddy

calloc在初始化时会将内存清零，但很可能不会比调用malloc后再调用memset更快。在此之后，您可以使用memset将其再次清零。除非你的数组真的非常庞大，在任何合理的机器上，性能都不是一个考虑因素。 - Ben Zotto

Answer 6

int array[N][M] = {0};

...at least in GCC 4.8.

- Engineer

Answer 7

你的二维数组是如何声明的？

如果它的声明方式类似于：

int arr[20][30];

你可以通过以下方式将其归零：

memset(arr, sizeof(int)*20*30);

- Pablo Santa Cruz

---

我使用了一个char[10][10]数组。但我得到了错误：函数'memset'的参数太少，然后 memset(a, 0, sizeof(char)*10*10); 对我有效。它是怎么发生的？ - noufal

Answer 8

请使用calloc代替malloc。calloc会将所有字段初始化为0。

int *a = (int *)calloc(n,sizeof(int)) ;

//a的所有单元格都已经初始化为0

- DUDE_MXP

Answer 9

你可以尝试这个。

int array[20,30] = {{0}};

- Călin Calin

---

请添加更多细节。 - Marko Popovic

Answer 10

我没有足够的声望来发表评论，但是...

我有些同意Skizz的答案，即"最快速完成任务的方法通常是不去做它"，但有一个非常重要的警告。如果你要像这样过滤访问，你真的需要考虑每个周期的浪费。

例如，Skizz提到：

void ClearArray ()
{
    array_is_empty = true;
}

int ReadValue (int x, int y)
{
   return array_is_empty ? 0 : array [x][y];
}

我想指出条件运算符“?:”是一个不必要的分支。为了消除这个问题，您可以使用一个整数array_is_empty，其值为0或1，然后...

int ReadValue (int x, int y)
{
   return array_is_empty * array [x][y];
}

这将去除条件，但添加了一个不必要的乘法，编译器不会优化掉它，因为它不知道array_is_empty是否会有除0或1之外的值。

因此，我建议使用全1的AND掩码。这可以是有符号类型中的“-1”表示，也可以是任何简单类型中的~0（零，位翻转）。

int ReadValue (int x, int y)
{
   return array_is_empty & array [x][y];
}

这将产生一个更干净、更快的解决方案，没有不必要的分支预测和缓慢的乘法操作。AND非常快，如果您对数组进行大量查找并执行此过滤，则这一点非常重要。

我要补充的最后一个警告是相当严重的：

当大多数人将数组清零时，他们希望每个元素都为零。使用“单标志”方法，设置单个元素将删除过滤器并公开所有未初始化的数据...这几乎从来不是用户所期望的。这可能会在以后引起很多麻烦。

另一种选择（如Skizz所示）是在第一次写入时将数组清零。这会撤消该方法的所有潜在好处，只留下缺点和性能损失。

因此，我只会在完全初始化或根本不初始化的数组上使用它。而且，说实话，这严重地限制了它的用途。

它的用处在于数组在块中使用时，例如行……特别是当稀疏占用时。如果每个行或块都有这样的标志，那么它就成为了一种非常有效的方法。第一次写入时的单个通用“memset”（请参见Skizz的示例）会撤销任何潜在的好处，并且是一个大警报，表明您应该在构建时将数组清零;）

此外，虽然是小事，但我个人会避免像“ClearArray”这样的方法名称……我谦虚地建议，“MarkUninitialised”或“MarkUnused”可能看起来很丑陋，但可以避免混淆。

尽管如此，还是要感谢Skizz的回答。如果有意义，那么值得做。避免不必要的工作就像优化重构一样好;）

对于让这成为答案，我表示歉意。考虑到数组访问期间额外工作的迅速增加以及memset-on-first-write的问题，我认为这很值得指出。

- Gary C