Stack vs Heap allocation. Is it worth it?
Published:
Is it worth to allocate things in the stack instead of in the heap? I kind of new the answer, but I didn’t know how much. Allocating things in the stack is super-cheap and, in most cases, uses a single instruction while allocating things in the heap is quite expensive (expensive system calls). Let’s do a simple example that proves this:
In the code below, I have created three implementations of the fibonacci series. In the first implementation, I allocated a long long in the heap (function fibonacci and helper function fib). The second implementation allocates a long_stack struct (contains two long long) in the stack (functions fib3 and fibonacci3). The third implemnentation allocates a long long in the stack (functions fib2 and fibonacci2). With these simple 3 functions we are going to measure how much time it takes to compute the 50th number in the fibonacci series.
The results couldn’t be clearer:
- Total time when allocating in the heap: 2.740 ms
- Total time when allocating in the stack (struct): 0.450 ms
- Total time when allocating in the stack: 0.340 ms
This represents a 6x speedup over the allocation in the heap.
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
static int NUMBER = 50;
typedef struct long_s {
long long num;
} long_s;
typedef struct long_stack {
long long p;
long long n;
} long_stack;
long long fib(long_s *p, long_s *n, int remaining){
if(remaining==0){
return n->num;
}else{
long_s *nn = malloc(sizeof *nn);
*nn = (long_s){.num = p->num + n->num};
return fib(n, nn, remaining-1);
}
}
long long fib2(long long p, long long n, int remaining){
if(remaining==0){
return n;
}else{
long long nn = p + n;
return fib2(n, nn, remaining-1);
}
}
long long fib3(long_stack s, int remaining){
if(remaining==0){
return s.n;
}else{
return fib3((long_stack){.p=s.n, .n=s.n+s.p}, remaining-1);
}
}
long long fibonacci(int initial){
long_s* prev = malloc(sizeof* prev);
long_s* next = malloc(sizeof* next);
*prev = (long_s) {.num = 1};
*next = (long_s) {.num = 1};
return fib(prev, next, initial-2);
}
long long fibonacci2(int initial){
return fib2((long long)1, (long long)1, initial-2);
}
long long fibonacci3(int initial){
return fib3((long_stack){.n = 1, .p = 1}, initial-2);
}
void chronos(struct timeval t1, struct timeval t2){
double elapsedTime;
// compute and print the elapsed time in millisec
elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0; // sec to ms
elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0; // us to ms
printf("Elapsed time: %e\n", elapsedTime);
}
int main(){
struct timeval t1, t2;
// Example that allocates in the heap
gettimeofday(&t1, NULL);
for(unsigned int i=0; i<1000; i++){
fibonacci(NUMBER);
}
gettimeofday(&t2, NULL);
chronos(t1, t2);
// Example that allocates in the stack a long
gettimeofday(&t1, NULL);
for(unsigned int i=0; i<1000; i++){
fibonacci2(NUMBER);
}
gettimeofday(&t2, NULL);
chronos(t1, t2);
// Example that allocates a struck in the stack
gettimeofday(&t1, NULL);
for(unsigned int i=0; i<1000; i++){
fibonacci3(NUMBER);
}
gettimeofday(&t2, NULL);
chronos(t1, t2);
}