Recitation 5

Why Bother?

Many of you may be wondering why bother with this notion of dynamic memory allocation at all. Why not just statically allocate everything?

Here is the excerpt from the class notes pertaining to this question.

Memor[y] allocation functions allow programmers to dynamically allocate memory from the heap for variables, arrays, and structures; rather tha[n] statically allocating space on the stack. Many times it is not possible to know in advance of run time of a program what the memory demands for the program are. People that use static allocation somewhat have to second guess what the worst case memory needs are and statically allocation that at compile time. This is not a good programming principle. Better to make your program general and capable of dealing with a wide variety of demands – the message, but the smarts into the program and don’t second guess.

For many of you, this may not be a satisfying answer. What if I am smart enough to know the memory demands ahead of time? (Unlikely, I say, considering you haven’t used valgrind or gprof yet…) But let’s accept that premise for the time being.

What if the computer you’re using cannot support the memory requirements? Uh oh. Static allocations don’t return error codes! malloc, on the other hand, will return null upon failure, which is something your code can anticipate and account for. Not so with static allocation – here, your code will simply segfault without any helpful messages whatsoever.

Hmm, okay. What are the other differences? Statically allocated data are born from the stack, and this is where they reside, while dynamically allocated data are from the heap. What does this mean?

Here is an example of a standard process memory.

This diagram is very famous – it is the standard virtual memory diagram. Why is it called virtual and not actual memory? To understand that you will have to take the very excellent Operating Systems course taught by our own Professor Smith.

“Text” here stands for the source code that your program is running. It is at the bottom most layer and almost always in a read-only region of memory (we wouldn’t want to change the code while it was being run!). “Data” refers to global variables; some are initialized and some are not. You can ignore the environemnt section for now; simply pretend that this is indeed the stack or it does not exist. The stack, as all stacks do, grows downards. The heap, on the other hand, grows upwards. Of course, they cannot overlap.

Many operating systems have a harder limit on their stack size than their heap size for reasons we won’t discuss here. If you are curious, feel free to take cs58, Operating Systems. (They also have heap size limits.) This poses an inherent limitation on stack-based memory allocation. But even fundamental than just memory size is the scope.

Some memory has automatic storage duration. Have you ever wondered why it is that C, which does not have garbage collection, seems to be able to free memory like int a = 5;. Why is it that a never causes a memory leak? Or for that matter even statically allocated structures, like struct foo bar;. How does C know to free bar?

The answer is that C does not know. Rather, these structs reside in a stack frame for a particular function. Thus, when the function returns and the frame for it is popped off, all memory associated with that function is then automatically “freed”. Thus, the statically allocated memory is destroyed along with it.

This means that you only have access to a particular variable so long as it is within the function; hence, we derive our notion of scope. Memory in the heap, on the other hand, has dynamic storage duration, which means that it will continue to reside there until it is manually freed by the programmer. This is the real reason many programs have to use dynamic memory allocation, despite the difficulties with memory leaks.

One last tidbit regarding the virtual memory space. As we all know, stacks grow downwards. But when you statically create an array, C actually grows the array upwards. It calculates the size of the array, moves that far down, and that’s where it places the zeroeth element. With this information, you can predict what the output of the following program stack.c will be.

#include <stdio.h>
int main(int argc, const char *argv[]) {
  int a = 4;
  int b[3];
  printf("b[0]: %d b[1]: %d b[2]: %d\n", b[0], b[1], b[2]);
  printf("b[3]: %d\n", b[3]);
  return 0;
}

Yes, b[3], which is beyond the bounds of the array, actually accesses a! As the array grows upwards, it accesses the beginning of the stack. Sure enough, here is the output.

b[0]: 0 b[1]: 0 b[2]: 0
b[3]: 4

Of course, when you run it, the regular portion of the array may contain values other than 0 – it is uninitialized garbage memory, after all. But the key point is that b[3] will be equal to a. Pretty neat!

Allocating Memory

The lecture does a pretty good job of explaining how to allocate memory.

Deallocating memory is fairly simple: just call free. One function handles it all.

It has been mentioned repeatedly, but I cannot stress this point enough. It is paramount that you verify the return status of malloc. Do not be so carefree as to assume your Operating System will always have memory for you.

int *data = (int *) malloc(sizeof(int) * 10); // array of 10
if (NULL == data) {
    perror("Mallof failed for data! Program exiting.");
    return 1;
}

Seriously. Always check the return value. Make a macro for it. Whatever makes it easy, but have a check in there.

The other rule of thumb to avoid memory leaks is quite simple: however many allocations you have, you must have an equal number of deallocations.

Why No Garbage Collection?

Why doesn’t C have garbage collection? Java has it; heck, even interpreted languages like Ruby have it!

The answer is that garbage collection is not as easy as it seems. It’s an extremely difficult task, and optimizing garbage collection is a full time job. Seriously. People are paid hundreds of thousands of dollars to make GC occur faster and in a less painless manner.

Take a look at this.

Any guess as to why the server response time jumped five fold? Yup, that spike is when garbage collection happened. It doesn’t matter what company you’re working for – a five fold increase in response times is absolutely unacceptable. Ads won’t be served, customer requests will be denied, money will be lost. In the worst case, servers will have to be restarted.

Without proper tuning, you get performance that looks like this.

Not pretty. Not stable. Not acceptable.

Then there’s of course the question of which kind of GC you want, which is its own bag of worms. Do you do reference counting (Python), Out of Band (Ruby), Java’s version of young and old, or something completely different?

These questions miss the spirit of C. It is meant to be a language that has little to no abstraction and one in which the programmer is empowered completely, and part of being completely in control means that your memory shouldn’t be secretly deallocated without your knowledge.

Indexer Lab

Some thoughts about the lab.

  1. Testing! You’ll find that testing is an actual requirement for this lab, so I do hope you’ve been writing unit tests for your code like I suggested, because if that’s the case then this is no additional work for you.
  2. Memory leak extra credit - use valgrind, make sure there are no memory leaks. This is important. Next time it will be a requirement and not just extra credit.
  3. Refactoring code is mandatory. Look at the data structures and compare how they differ with the previous crawler implementation. Start here with refactoring. It builds your familiarity with the given code and at the same time gives you a better idea about what the indexer actually does.
  4. No segmentation faults. I will not grade any lab that seg faults. No exceptions. No sob stories. Start early; you have been warned.

Resources

Cool posts on dynamic memory allocation: