c++ - How to fast initialize with 1 really big array

Question

I have enermous array:

int* arr = new int[BIGNUMBER];

How to fullfil it with 1 number really fast. Normally I would do

for(int i = 0; i < BIGNUMBER; i++)
    arr[i] = 1

but I think it would take long.

Can I use memcpy or similar?

score 14 · Accepted Answer

您可以尝试使用标准功能std::uninitialized_fill_n：

#include <memory>

// ...

std::uninitialized_fill_n(arr, BIGNUMBER, 1);

无论如何，在性能方面，规则是始终进行测量以支持您的假设——尤其是如果您因为所谓的性能改进而放弃一个清晰、简单的设计而采用更复杂的设计时。

编辑：

请注意，正如 Benjamin Lindley 在评论中提到的那样，对于琐碎的类型std::uninitialized_fill_n并没有比更明显的类型带来任何优势std::fill_n。非平凡类型的优势将存在，因为std::uninitialized_fill它允许您分配内存区域，然后在适当的位置构造对象。

但是，不应陷入调用未初始化std::uninitialized_fill_n的内存区域的陷阱。例如，以下将给出未定义的行为：

my_object* v = new my_object[BIGNUMBER];
std::uninitialized_fill_n(my_object, BIGNUMBER, my_object(42)); // UB!

score 4 · Accepted Answer

动态数组的替代方法是std::vector<int>使用接受每个元素的初始值的构造函数：

std::vector<int> v(BIGNUMBER, 1); // 'BIGNUMBER' elements, all with value 1.

如前所述，需要衡量绩效。这种方法提供了额外的好处，即内存将被自动释放。

score 2 · Accepted Answer

Andy Prowl 解决方案的一些可能替代std::uninitialized_fill_n()方案，仅供后代使用：

如果您很幸运并且您的值由所有相同的字节组成，那么memset就可以了。
一些实现提供 16 位版本memsetw，但并非无处不在。
GCC 有一个可以填充范围的指定初始化器扩展。
我曾使用过一些 ARM 系统，它们的库具有加速 CPU 和 DMA 字填充变体的库，在汇编中手工编码——如果你不是非常担心的话，你可以看看你的平台是否提供这些关于便携性。
根据您的处理器，即使查看 SIMD 内在函数的循环也可能会提供提升；一些 SIMD 单元具有加载/存储管道，这些管道针对像这样移动数据进行了优化。另一方面，您可能会因在寄存器类型之间移动而受到严厉惩罚。

最后但同样重要的是，回应一些评论者：你应该测试并看看。编译器往往非常擅长识别和优化这样的模式——您可能只是在使用除简单循环或uninitialized_fill_n.

您可能对之前的问题感兴趣：

score 1 · Accepted Answer

在启用优化的 Linux/x86 gcc 下，您的代码将编译为以下内容：

rax = arr
rdi = BIGNUMBER

400690: c7 04 90 01 00 00 00    movl   $0x1,(%rax,%rdx,4)

立即移动int(1)到 rax + rdx

400697: 48 83 c2 01             add    $0x1,%rdx

递增寄存器 rdx

40069b: 48 39 fa                cmp    %rdi,%rdx

Cmp rdi 到 rdx

40069e: 75 f0                   jne    400690 <main+0xa0>

如果已达到 BIGNUMBER，则跳回开始。

在我的机器上每 GB 大约需要 1 秒，但我敢打赌，其中大部分是在物理内存中分页以支持未初始化的分配。

score 1 · Accepted Answer

只需将循环展开 8 或 16 次。像这样的函数memcpy很快，但它们确实是为了方便，而不是比你可能写的任何东西都要快：

for (i = 0; i < BIGNUMBER-8; i += 8){
  a[i+0] = 1; // this gets rid of the test against BIGNUMBER, and the increment, on 7 out of 8 items.
  a[i+1] = 1; // the compiler should be able to see that a[i] is being calculated repeatedly here
  ...
  a[i+7] = 1;
}
for (; i < BIGNUMBER; i++) a[i] = 1;

编译器可能会为您展开循环，但为什么要冒险呢？

score -2 · Accepted Answer

-2

使用 memset 或 memcpy

memset(arr, 0, BIGNUMER);

于 2013-05-05T14:30:33.223 回答

score -2 · Accepted Answer

尝试使用 memset？

memset(arr, 1, BIGNUMBER);

http://www.cplusplus.com/reference/cstring/memset/

score -2 · Accepted Answer

-2

memset(arr, 1, sizeof(int) * BIGNUMBER);

于 2013-05-05T15:08:56.787 回答

c++ - How to fast initialize with 1 really big array

8 回答 8

Related

Reference