Dynamic Memory Allocation

Stack Memory

So far we’ve been playing around with using pointers to point to individual bytes of an int or to access indices of an array. We also discussed how pointers can be used to implement a function like scanf. Let’s look at another application of pointers: dynamic memory allocation. Normally, C++ code will only be able to access around 1-2 megabytes of memory depending on the operating system and the specs of the computer. We can verify this by testing the following code:

  1. #include <stdio.h>
  2. int total_allocated = 0;
  3. void go_deeper() {
  4. char arr[10000];
  5. total_allocated += 10000;
  6. printf("I have allocated %d bytes of memory.\n", total_allocated);
  7. go_deeper();
  8. }
  9. int main() {
  10. go_deeper();
  11. }

On my computer, this code goes deep enough to allocate about 8 megabytes before it crashes. But my computer has several gigabytes of memory. So what happened? And how do we access the rest of our several gigabytes of memory?

The malloc Function

Let’s first discuss the question of how to access the rest of our memory. There's a function called malloc that asks the operating system for some number of bytes, and the function will return a pointer to the start of that chunk of memory. It's up to you to decide what you want that memory region to mean. The operating system only cares that you asked for N bytes so it’ll give you N bytes. If you point an int pointer to it, your program will think of it as an array of integers. If you turn it into a char pointer, it’ll think it's an array of characters. Let's have a look at some sample code:

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. int total_allocated = 0;
  4. void go_deeper() {
  5. char* arr = (char*)malloc(10000);
  6. // This malloc call gives you 10000 bytes to play with.
  7. // It doesn't have any idea of the meaning of this chunk of memory,
  8. // so it's your job to convert it to a pointer of the correct type.
  9. total_allocated += 10000;
  10. printf("I have allocated %d bytes of memory.\n", total_allocated);
  11. go_deeper();
  12. }
  13. int main() {
  14. go_deeper();
  15. }

If you open Task Manager while this program is running, you’ll notice that it’s slowly eating up more and more of your memory. You might want to kill it before it goes too far and your computer starts lagging. :)

The free Function

Now that we know how to allocate memory, we have to know how to de-allocate it. This is done through the free function. Just call it and pass the memory address given by malloc and it’ll return the memory back to the operating system.

The sizeof Operator

Many times, you’re too lazy to manually compute the number of bytes you need. For example, you know that you want enough space for an array of int with 12345 elements. Doing the math yourself is such a pain. Of course you can type malloc(4 * 12345); since you know that int takes 4 bytes. But in case you forget or you want to make the code more readable, we’ll introduce a new operator called sizeof. Using this operator actually looks like a function call, but the compiler evaluates it while your code is compiling to compute sizes. Here is some sample code.

  1. #include <malloc.h>
  2. int main() {
  3. int* arr = (int*)malloc(sizeof(int) * 10000);
  4. }

sizeof is also really useful for when you define our own custom data types. One day you might want to make our data type take 16 bytes, but then you update it so it needs 24 bytes. In that case, you don't want to go through all our code to replace all the references of malloc(16 * x); with malloc(24 * x);. Instead we can just do malloc(sizeof(custom_data_type) * x);.

The Null Pointer

malloc makes a guarantee that it will never return an address below 4096 for modern operating systems. The value of 4096 changes based on computer specs and operating system, but it's guaranteed that it will never allocate you the memory address 0. So if you want to say that a pointer points to nowhere, set its value to 0. If you want to check if a pointer is uninitialized, check if it points to 0. Later on if you find any references to a null pointer, it means a pointer that points to memory address 0.

Memory Errors

Lastly, here are some common errors you might encounter when playing around with memory.

Segmentation Fault

When you access a memory location that does not belong to you, you get something called a segmentation fault. Usually this happens in three scenarios. One, you allocate 100 bytes, but try to access the 101th byte. Two, you access memory that you have not even allocated yet. Three, you access memory that you have already freed. Sometimes, it’s possible that your code continues on. But this kind of scenario is very bad.

Memory Leak

When you allocate memory, you are given a pointer to the address of the memory you requested. If you update your pointer to something else, say you request a new chunk of memory, and you forget to free the first block of memory, you will never again be able to recover that memory address. Since you can’t access that memory address, that memory is lost forever until your program stops. This situation is called a memory leak. Some software and video games are notorious for this and they will gradually eat up more memory until you kill them. For programming contests, if you allocate, say, 100MB per test case but fail to free your memory, you will likely hit a memory limit exceeded error after a few cases.