The stack and the heap

Lesson 19 of 30 · Part 4 · Memory · about 15 minutes

Once a program runs, its variables live in memory. A C program's memory has two places you need to tell apart: the stack and the heap. Every variable we've written so far has been on the stack. Press Step: the memory picture under the code is split into a Stack area and a Heap area.

1#include <stdio.h>2 3int add(int a, int b) {4    int sum = a + b;5    return sum;6}7 8int main(void) {9    int price = 30;10    int total = add(price, 12);11    printf("Total: %d\n", total);12    return 0;13}

Total: 42

At first the stack holds only main's box, with price and total in it. When add is called, a new box appears on top with a, b and sum; as soon as add returns, that box is gone. The heap area stays empty the whole time.

The stack: gone when the function ends

Each function call adds a box to the stack (lesson 8 called it a stack frame), and each return takes it away. So a local variable lives only until its function ends. In lesson 18, a pointer to a local variable was left dangling as soon as its function returned. Arrays are no different: if you want a function to build an array and hand it back, returning a local array doesn't work:

1#include <stdio.h>2 3int *make_scores(void) {4    int scores[3] = {78, 85, 90};5    return scores;6}7 8int main(void) {9    int *p = make_scores();10    printf("%d\n", p[0]);11    return 0;12}

main.c: In function 'make_scores':
main.c:5:12: warning: function returns address of local variable [-Wreturn-local-addr]
    5 |     return scores;
      |            ^~~~~~
load of null pointer

gcc warns first: the function returns the address of a local variable. It still compiles it, and since that address is useless once it's handed out, gcc simply makes make_scores return NULL. So when line 10 reads through p, our engine stops: p is NULL. Press "see how it went wrong" and go through it step by step: when make_scores's box is removed, the array inside it goes too.

The heap: ask for it, give it back

When you want memory that doesn't vanish with a function, ask the heap for it. malloc lives in <stdlib.h>: tell it how many bytes you want, and it finds a block that big on the heap and hands you its address. When you're done, give it back with free:

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int *p = malloc(sizeof(int));6    *p = 42;7    printf("On the heap: %d\n", *p);8    free(p);9    return 0;10}

On the heap: 42

Press Step past line 5: a block appears in the heap, labeled "4 bytes · line 5", which is how big it is and which line asked for it. p itself is on the stack, a pointer in main's box, and an arrow runs from it to the block. Step past the free on line 8 and the block turns gray, marked "freed": that memory has been given back and can't be used again. The details of malloc (how many bytes to ask for, what if there aren't any) come in the next lesson.

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    double *price = malloc(sizeof(double));6    *price = 9.5;7    printf("%.1f\n", *price);8    free(price);9    return 0;10}

Outliving the function

A heap block doesn't belong to any function, so it's still there after the function returns. When a function needs to build a set of numbers and hand them back, it builds them on the heap:

1#include <stdio.h>2#include <stdlib.h>3 4int *make_scores(void) {5    int *scores = malloc(3 * sizeof(int));6    scores[0] = 78;7    scores[1] = 85;8    scores[2] = 90;9    return scores;10}11 12int main(void) {13    int *p = make_scores();14    printf("%d %d %d\n", p[0], p[1], p[2]);15    free(p);16    return 0;17}

78 85 90

It's almost the program from the last section, but the array is now a heap block. Press Step: when make_scores returns, its box is gone, and the scores pointer with it, but the "12 bytes" block on the heap is still there, and p in main points at it. make_scores asked for the block and main gives it back. Anyone can give it back, as long as it happens once.

A size you only know at run time

The arrays in this course so far all have a size fixed when you write the code, like int a[7]. Often, though, you don't know how many values you'll have until the program runs: say you pick the passing scores out of a list, and only know how many there are once you've picked them. Then you ask the heap for exactly that many:

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int scores[6] = {58, 72, 91, 45, 60, 83};6    int count = 0;7    for (int i = 0; i < 6; i++) {8        if (scores[i] >= 60) {9            count++;10        }11    }12    int *passed = malloc(count * sizeof(int));13    int k = 0;14    for (int i = 0; i < 6; i++) {15        if (scores[i] >= 60) {16            passed[k] = scores[i];17            k++;18        }19    }20    printf("%d passed: ", count);21    for (int i = 0; i < count; i++) {22        printf("%d ", passed[i]);23    }24    printf("\n");25    free(passed);26    return 0;27}

4 passed: 72 91 60 83 

count is 4, so the heap block is 4 × 4 = 16 bytes, no more and no less.

Tip: C also allows arrays like int a[n] whose size is a variable (variable-length arrays), but they live on the stack, a large n causes trouble, and since C11 compilers don't have to support them. This page doesn't. When the count is a variable, use malloc.

A small stack, a big heap

The stack is small, usually just a few MB on a typical computer. Declare an array of a few million elements inside a function and you can blow the stack, and the program crashes. The heap can be far bigger, up to most of the computer's memory. So very large arrays go on the heap too:

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int count = 1000000;6    int *steps = malloc(count * sizeof(int));7    for (int i = 0; i < count; i++) {8        steps[i] = 5000;9    }10    printf("%d days, %d steps on day one\n", count, steps[0]);11    free(steps);12    return 0;13}

1000000 days, 5000 steps on day one

A million int values take 4000000 bytes, about 4 MB: risky on the stack, no problem on the heap. (This loop goes around a million times, so don't step through it one loop at a time; just press Run.)

Remember three cases for the heap:

• You only know how many you need once the program runs.
• The memory has to outlive the function that asked for it.
• It's big, too big for the stack.

The rest of the time, use plain local variables: there's nothing to give back, so you can't forget to.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

Price: 19.50

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5 6    return 0;7}

1 4 9 16 25 

1#include <stdio.h>2#include <stdlib.h>3 4int *make_squares(int n) {5 6}7 8int main(void) {9    int *squares = make_squares(5);10    for (int i = 0; i < 5; i++) {11        printf("%d ", squares[i]);12    }13    printf("\n");14    free(squares);15    return 0;16}

12 8 25

1#include <stdio.h>2#include <stdlib.h>3 4int *make_prices(void) {5    int prices[3] = {12, 8, 25};6    return prices;7}8 9int main(void) {10    int *p = make_prices();11    printf("%d %d %d\n", p[0], p[1], p[2]);12    return 0;13}

What you learned

• Function parameters and local variables are on the stack: a call adds a box, a return removes it, and its variables go with it.
• Don't return the address of a local variable: once the function returns, that memory isn't yours.
• Heap memory is asked for with malloc and given back with free; it's still there after the function returns.
• A pointer can sit on the stack while the block it points at is on the heap.
• Use the heap in three cases: the count is only known at run time, the memory must outlive the function, or it's too big for the stack.