Timing array static array allocation vs array on stack in C

Question

I have the following code with two functions, one that allocates a static array and one that allocates an array on the stack. The functions are run many many times and their execution time calculated. The stack allocation is consistently (marginally) faster than the static allocation. I was under the impression that because a static variable is bound before run time that it would execute faster than the array that is allocated on the stack

 #include <stdio.h>

#include <stdlib.h>
#include <time.h>
#define MAX_ARRAY 8192 

void statArray()
{
static int statArray[MAX_ARRAY];
}
void stackArray()
{
int stackArray[MAX_ARRAY];
}

int main(int argc, char * argv[]) {
     clock_t start, end;
     double staticTime, stackTime;
     int i;
     int comparisons = 5000000;

     start = clock();
     for (i = 0; i < comparisons; i++) {
          statArray();
     }
     end = clock()-start;
     staticTime = (double)end / CLOCKS_PER_SEC;

     start = clock();
     for (i = 0; i < comparisons; i++) {
          stackArray();
     }
     end = clock() - start;
     stackTime = (double) end / CLOCKS_PER_SEC;

Thanks

disassembled statArray

 0x0000000000400594 <+0>:   push   %rbp
   0x0000000000400595 <+1>: mov    %rsp,%rbp
   0x0000000000400598 <+4>: leaveq 
   0x0000000000400599 <+5>: retq

disassembled stackArray

0x000000000040059a <+0>:    push   %rbp
   0x000000000040059b <+1>: mov    %rsp,%rbp
   0x000000000040059e <+4>: sub    $0x7f88,%rsp
   0x00000000004005a5 <+11>:    leaveq 
   0x00000000004005a6 <+12>:    retq

In order to know what is going on you will have to disassemble the two functions (statArray and stackArray). My guess is the stackArray allocation is removed by the optimizer. — Steen
– Steen, Commented Sep 28, 2014 at 20:24
The compiler may be taking advantage of instructions, or caching, which permit faster access to space on the stack than to space elsewhere in memory. Precomputed addresses are theoretically faster, sure, but that may be a one-time difference in loading a register with the array's base address. As @Steen said, if you want to know EXACTLY what's going on, look at the generated code. (Good example of why you shouldn't worry about micro-optimizing code until you know what's going to matter. Focus on algorithms, not on trickery, until you have traces & know what trickery will be worth the effort.) — keshlam
– keshlam, Commented Sep 28, 2014 at 20:57
@keshlam It's an exercise from Sebesta's Concepts of Programming Languages, it's not intended for any sort of micro optimization, but rather understanding of the concepts between stack, heap and static allocations. My results were differing from my expectations, so I was wondering if the results were wrong or my expectations. That said, i've added the disassembled functions to the question — IMerin
– IMerin, Commented Sep 28, 2014 at 21:06
lol, try turning off all optimizations and retry. Even then, you may have to actually touch the elements to ensure that the arrays actually get allocated. — Martin James
– Martin James, Commented Sep 29, 2014 at 0:54
When I turn on otimization with my compiler for your functions, both are exactly the same they do nothing at all, the only assembler statement of the functions is retq. — Jens Gustedt
– Jens Gustedt, Commented Sep 29, 2014 at 7:50

user3125367 · Accepted Answer · 2014-09-29 03:34:05Z

3

As you can see in assembly listing, statArray is an empty function, and stackArray contains single allocation instruction (sub rbp, imm). Time effect of that instruction is probably hidden by prologue/epilogue instruction's latencies and the difference can be measured only with cpu thermometer. Actual difference you encounter is due to slight time measurement error and may change if you swap the order of code blocks.

Edit: worth noting that stack allocation is nothing more than fixing stack top by subtracting from stack pointer register without any complex logic involved (opposed to malloc), and static vs stack "speed" seems to be a common misconception.

edited Sep 29, 2014 at 3:34

answered Sep 29, 2014 at 3:24

user3125367

3,0201 gold badge19 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Timing array static array allocation vs array on stack in C

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related