Initialize a dynamic array in O(1) time in C/C++

Question

Is there any way to initialize a whole dynamic array in O(1) time? Is there something similar to bool a[10] = {false} in the case of a static array?

Answer 1

For a dynamic array, each element you want to set must be individually considered by the CPU, so the time complexity is O(N).

Or is it?

But that's not really how big-oh works. It is also not really how CPUs work.

Big-oh notation concerns itself with the asymptotic behavior of a system as the number of elements grows towards infinity. Which is to say: we should take it with a grain of salt when we apply it to small numbers of elements!

CPUs also behave differently for small versus large numbers of elements because they have different cache levels which imply different access latencies. And you see this all the time in designing high-performance algorithms. See, for instance, this page describing how to optimize matrix multiplication: the section on "Blocking to maintain performance" is all about rearranging computations so they stay in the CPU's cache.

Now, let's talk about your question more specifically.

Consider below the handy chart of Latency Numbers Every Computer Scientist Should Know (source).

The salient point here is that a (random) main memory reference costs about 100ns, whereas references to the L1 cache cost 0.5ns and to the L2 cache cost 7ns. Due to caching effects, reading sequentially from RAM gives a significant speed boost.

This means that, all else being equal, you can read 200 numbers from L1, or 14 numbers from L2, in the time it takes to read a single number from RAM.

And this gets us into cost models.

Consider initializing two dynamic arrays like so:

std::vector<int> a(20,1);
std::vector<int> a(21,1);

From the foregoing, we expect that the additional element takes ~0.5ns to deal with (since the whole array fits into the cache) whereas storing the array to memory takes 100ns. That is, the marginal cost of adding an additional element is negligible. In fact, the marginal cost of adding even many elements would be negligible (how many depends on the processor).

Let's apply these ideas. Consider these two statements.

int m = array1[20];
std::vector<int> a(900,1);

If you're thinking about this from a O(1) vs. O(N) perspective you might think something silly, like "the second statement will take 900x longer than the first". A more sophisticated thought you might have is that "the hidden coefficients of the O(N) second statement may be small, so it is difficult to know which will be faster".

With some knowledge of caching you might instead say to yourself "for these small N values an asymptotic analysis is not appropriate". You might further think "these statements may take the same time" or "the second statement may run faster than the first due to caching effects".

An Experiment

We can use a simple experiment to demonstrate this.

The following program initializes arrays of different lengths:

#include <vector>
#include <iostream>
#include <chrono>
#include <string>

int main(int argc, char **argv){
  const int len = std::stoi(std::string(argv[1]));
  auto begin = std::chrono::high_resolution_clock::now();
  for(int i=0;i<10000;i++){
    std::vector<int> a(len,1);
    (void)a;
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count() << std::endl; //Nanoseconds
}

The program runs many initializations of the dynamic array to average over fluctuations due to other programs running on the machine.

We run this program many times:

for n in {1..100}; do ./a.out 1; done | awk '{print "1 "$1}' | xclip

To deal with differences in the program's start-up and the machine's memory-state due to other programs running.

On my Intel(R) Core(TM) i5 CPU M480 @ 2.67GHz with a 32K L1 cache, 256K L2 cache, and 3072K L3 cache, the result is this:

Note that the increase in time for small arrays is sublinear (when combined with the later behavior on larger arrays) through about 1000 elements. This is not O(N) behavior. After this, adding 10x more elements leads to about 10x more time consumed. This is O(N) behavior.

Trying the same test on my Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz with a 32K L1 cache, 256K L2 cache, and 30720K L3 cache yielded very similar results:

Bottom Line

Array initialization is in O(N) since it grows with the number of elements. However, in practice, due to caching, the cost does not rise linearly. Therefore, an "O(1)" command may take the same time as an "O(N)" command, depending on the magnitude of N.

Answer 2

No, there is not, not in c++, nor in c, not in any language or CPU I know of. But it can be done with 1 line of code.

in C: for a array of char:

char a[N];
memset(a, '1', N);  // only works for data 1 byte long

in C++

std::vector<T> v;
std::fill(v.begin(), v.end(), value);