Slow writing to array in C++

Question

Hi everyone, I was just wondering if this is expected behavior in C++. The code below runs at around 0.001 ms:

for(int l=0;l<100000;l++){
        int total=0;
        for( int i = 0; i < num_elements; i++) 
        {
            total+=i;
        }
    }

However if the results are written to an array, the time of execution shoots up to 15 ms:

int *values=(int*)malloc(sizeof(int)*100000);
        for(int l=0;l<100000;l++){
            int total=0;
            for( unsigned int i = 0; i < num_elements; i++) 
            {
                total+=i;
            }
            values[l]=total;
        }

I can appreciate that writing to the array takes time but is the time proportionate?

Cheers everyone

Answer 1

It looks like the compiler is optimizing that loop out entirely in the first case.

The total effect of the loop is a no-op, so the compiler just removes it.

Answer 2

I would suspect that what you are seeing is an effect of virtual memory and possibly paging. The malloc call is going to allocate a decent sized chunk of memory that is probably represented by a number of virtual pages. Each page is linked into process memory separately.

You may also be measuring the cost of calling malloc depending on how you timed the loop. In either case, the performance is going to be very sensitive to compiler optimization options, threading options, compiler versions, runtime versions, and just about anything else. You cannot safely assume that the cost is linear with the size of the allocation. The only thing that you can do is measure it and figure out how to best optimize once it has been proven to be a problem.

Answer 3

The first example can be implemented using just CPU registers. Those can be accessed billions of times per second. The second example uses so much memory that it certainly overflows L1 and possibly L2 cache (depending on CPU model). That will be slower. Still, 15 ms/100.000 writes comes out to 1.5 ns per write - 667 Mhz effectively. That's not slow.

Answer 4

It's very simple. In first case You have just 3 variables, which can be easily stored in GPR (general purpose registers), but it doesn't mean that they are there all the time, but they are probably in L1 cache memory, which means thah they can be accessed very fast.

In second case You have more than 100k variables, and You need about 400kB to store them. That is deffinitely to much for registers and L1 cache memory. In best case it could be in L2 cache memory, but probably not all of them will be in L2. If something is not in register, L1, L2 (I assume that your processor doesn't have L3) it means that You need to search for it in RAM and it takes muuuuuch more time.