Consider following two cases of Array initialization in C or C++ :
Case 1:
int array[10000] = {0}; // All values = 0
Case 2:
int array[10000];
for (int i = 0; i < 10000; i++) {
array[i] = 0;
}
Do they both take same time ? what is the complexity of Case 1? and, Which one is better?
In the case of the array being of static duration (global variable), I'd say the first one is much preferrable, since it doesn't require any code - it is initialized by the runtime-environment.
If the variable is a of automatic duration (local variable), which one is better, if either is better than the other, depends on the compiler. Most likely, both will be very similar.
The comlexity for the automatic storage duration variable is O(n) for all cases. The first case is O(1) for a static storage duration variable.
Of course, if you wanted to fill array with the value 5, the second option is much better because it doesn't require writing 10000 5 in the source file.
You may also find that using memset(array, 0, sizeof(array)); is better than both - again, depending on the compiler. This is still O(n), but the actual time it takes to fill the array may be shorter, because memset may be better optimized than what the compiler generates for your loop case [and what it does for initialized variables]. memset won't work for filling the array with 5 either.
You could also use std::fill(array, &array[10000], 5); to set the value 5 in all the array, and the compiler will should a decent job of optimizing that.
Finally, I should point out that these sort of things only REALLY matter if they are doing in code that gets executed a lot. It's a long time since filling 40KB of data took long enough to really worry about on its own. Like 20+ years.
memset can't handle setting to 5, std::fill could do so nicely and can still be optimized intelligently when appropriate by a compiler.
memcpy or std::fill. The idea behind the loop unrolling is to perform as many assignment operations before the branch to the top of the loop. Branches may cause reloading of the instruction pipeline.
memset (which I'm sure I used about and I think you mean by memcpy) will be unrolled to some reasonable degree. Unrolling the loop ENTIRELY, even using SSE or AVX instructions will lead to 2500 or 1250 instructions, which is surely not worth the bloat vs. the saving of a few instructions that a well-unrolled loop will do. I challenge you to find a loop where manual unrolling beats -O3 in gcc.
-O3 doesn't unroll loops. Whether or not loop unrolling makes a difference is fairly implementation defined. Most implementations have opcode caches, which are fairly small compared to data caches. The opcode caches vary in size, so unrolling loops (whether manually or automatically) may work on some systems while it may appear to hamper performance on another. The answer to your challenge depends upon that system.gcc unroll loops, but maybe you need -funroll-loops or something like that for that to happen. And yes, it does depend on lots of machine dependant factors.In theory, both have the same time complexity: O(N), where N is the size of your array.
However, the first method should be better, since it's up to the compiler to choose how to initialize as faster as possible (for instance, it could be done through memset). For optimizations, the compiler is very often better than the programmer.
BTW, if your array has static storage duration (if you declare it as global variable, for example), it will be auto-initialized to 0.
std::fill for C++.
arrayof static or automatic duration?