Initializing C++ array in constant time

char buffer[1000] = {0};

This initializes all 1000 elements to 0. Is this constant time? If not, why?

It seems like the compiler could optimize this to O(1) based on the following facts:

1. The array is of fixed size and known at compile time
2. The array is located on the stack, which means that presumably the executable could contain this data in the data segment of the executable (on Windows) as a chunk of data that is already filled with 0's.

Note that answers can be general to any compiler, but I'm specifically interested in answers tested on the MSVC compiler (any vers开发者_C百科ion) on Windows.

Bonus Points: Links to any articles, white papers, etc. on the details of this would be greatly appreciated.

If it's inside a function, no, it's not constant time.

Your second assumption isn't correct:

"The array is located on the stack, which means that presumably the executable could contain this data in the data segment of the executable (on Windows) as a chunk of data that is already filled with 0's."

The stack isn't already filled with zeros. It's filled with junk leftover from previous function calls.

So it's not possible to do it in O(1) because it will have to zero it.

It can be O(1) only as a global variable. If it is a local variable (on stack) it is O(n) where n is the size of array.

Stack is a shared memory, you need to actively zero always you want to have 1000 zeros in there. An array like you defined is not implemented as a pointer to data segment, it is 1000 variables on the stack and must be initialized in O(1000).

EDIT: Dani is right, I have to fix my statement: If it is a global array, it is initialized when program starts. And it is O(n) as well.

It will never be constant time, global or not. its true the compiler initializes that, but the operating system must load all the file into memory, which takes O(n) time.

The array is located on the stack, which means that presumably the executable could contain this data in the data segment of the executable (on Windows) as a chunk of data that is already filled with 0's.

What if you recurse into the function that defines array? The global DATA segment would need to have a copy of this array for each function call to allow each function to have its own array to work over. The compiler would have to run your code to decide the maximum recursions are going to happen.

Also what happens when you have multiple threads in your program and each calls foo? All the sudden you have shared stuff in DATA that has to be locked. The locking might cause more performance problems than getting rid of the initialization.

I wouldn't worry about it too much too. Most platforms have fairly efficient ways of zero filling memory. Unless you profile it and find a problem, don't sweat it.

As others have pointed out, assumption 2 is wrong. Stack variables are allocated at run-time in O(1) time but are not normally initialised unless you're running a debug build.

PUSH ebp
MOV  ebp, esp
SUB  esp, 10
// function body code goes here

Here, the stack pointer 'esp' is decremented by 10 to make room for some local function variables. They are not initalised... that would require a loop.

This article seems friendly enough.

If it's a global static, the "constant" here is ZERO - initialization is done at COMPILE TIME.