How to quickly initialize with 1 really large array

Question

I have an enermous array:

int* arr = new int[BIGNUMBER]; 

How to do it with number 1 very quickly. I usually did

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

but I think it will take a long time.

Is it possible to use memcpy or the like?

Answer 1

You can try using the standard function std::uninitialized_fill_n :

 #include <memory> // ... std::uninitialized_fill_n(arr, BIGNUMBER, 1); 

In any case, when it comes to performance, the rule is to always take measurements to back up your assumptions - especially if you are going to abandon a clear, simple design to cover a more complex one due to the supposed performance improvement.

EDIT:

Note that - as Benjamin Lindley mentioned in the comments - for the trivial types std::uninitialized_fill_n does not bring any benefit to the more obvious std::fill_n . An advantage will exist for non-trivial types, since std::uninitialized_fill will allow you to allocate a memory area and then build objects in place.

However, you should not fall into the trap of calling std::uninitialized_fill_n for a memory area that is not uninitialized. For example, the following: undefined behavior:

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

Answer 2

An alternative to the dynamic array std::vector<int> with a constructor that takes an initial value for each element:

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

as already mentioned, performance must be measured. This approach provides the added benefit that memory will automatically free.

Answer 3

Some possible alternatives to the Andy Prowl std::uninitialized_fill_n() solution, only for posterity:

• If you're lucky and your value is made up of all the same bytes, memset will do the trick.
• Some implementations offer a 16-bit version of memsetw , but this is not everywhere.
• GCC has an extension for designated initializers that can fill ranges.
• I worked with several ARM systems, in which there were libraries in which the CPU and DMA options for filling words were accelerated, manual encoding in the assembly - you can look and see if your platform offers any of this if you do not know t terribly concerned about portability.
• Depending on your processor, even looking at the loops around the built-in SIMD functions may provide a boost; Some of the SIMD modules have load / storage pipelines that are optimized for moving data in this way. On the other hand, you can take severe penalties for moving between types of registers.

Last but not least, to repeat some of the commentators: you should check and see. Compilers, as a rule, recognize and optimize such patterns pretty well - you probably just trade with portability or readability with something other than a simple loop or uninitialized_fill_n .

You may be interested in previous questions:

• Is there a memset () that accepts integers greater than char?
• initialization of an array of ints
• How to initialize all elements of an array with the same value?

Answer 4

On Linux / x86 gcc with optimization enabled, your code will be compiled as follows:

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

Move immediate int(1) to rax + rdx

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

Incremental register rdx

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

Cmp rdi to rdx

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

If BIGNUMBER has been reached, go back to start.

It takes about 1 second per gigabyte on my machine, but most of this I swap in physical memory to return an uninitialized distribution.

Answer 5

Just expand the loop, say, 8 or 16 times. Functions like memcpy are fast, but they are really accessible for convenience, and not faster than anything you could write:

 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; 

The compiler can deploy a loop for you, but why take the risk?

Answer 6

Use memset or memcpy

 memset(arr, 0, BIGNUMER); 

Answer 7

Try using memset?

 memset(arr, 1, BIGNUMBER); 

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

Answer 8

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