在C中将2d数组归零的最快方法？

Question

我想在C中反复清零一个大的2d数组.这就是我现在所做的:

// 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阵列.当我打印2D阵列的内容时,第一行是零,但随后我得到了一大堆随机大数字,它崩溃了.

Answer 1

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

凡m和n是二维数组的宽度和高度(在你的榜样,你有一个正方形的二维数组,这样m == n).

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],这是"数组[5] int".它不是一个大小int *,因为"衰减"只发生在第一级,这就是为什么我们需要声明f()为一个指向正确大小的数组的指针.

所以,正如我所说,只有满足上述两个条件,你原来所做的才会奏效.如果没有,你需要做别人说的话:

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

最后,你发布memset()的for循环在严格意义上并不等同.可能存在(并且已经)编译器,其中"所有位零"对于某些类型不等于零,例如指针和浮点值.我怀疑你需要担心这一点.

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数组,那么您可以本地化布尔标志的效果,但是您需要更多的标志.在四叉树中,只需为根节点设置空标志,在行数组中只为每行设置标志.

这引出了一个问题"你为什么要反复归零大型二维阵列"？用于什么数组？有没有办法更改代码,以便数组不需要归零？

例如,如果你有:

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 

这不需要清除阵列但仍然有效.这比清除阵列要快得多.就像我说的,最快的方法是不要首先做到这一点.

Answer 4

如果你真的非常痴迷于速度(而不是可移植性),我认为绝对最快的方法就是使用SIMD矢量内在函数.例如,在Intel 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

Answer 5

如果使用初始化数组malloc,请calloc改用; 它将免费归零您的阵列.(显然与memset相同,只需更少的代码.)