How Memory Management Works

Abstract

This is a short introduction to memory management in programming languages. Any examples will be taken from the programming language "C", making this text especially useful for beginners in that language who feel overwhelmed by the arcane concept that is the "pointer". It assumes a general familiarity with programming and variables, but you don't have to be a guru to understand this text.

Why can't I just use variables?

The mean part about memory management in many programming languages - such as C - is that they do some of your memory management for you. This is very convenient, but also poses a stumbling block for people with moderate to advanced needs, who are frequently surprised by the seemingly arbitrary limits of variables. To make these comprehensible, I will quickly illustrate the basic workings of memory, then how they apply to variables. This will make the limitations of variables obvious, and from there it will be a small step towards pointers.

What is memory?

It helps if you think of computer memory (aka RAM) as something akin to a piece of coarse graph paper, with those boxes on it.Computer memory is one huge sheet of such paper, with each box representing one byte in memory.

As you may or may not already know, a byte can hold a number from 0 to 255. If you want memory to hold anything else than such a number, you have to re-interpret that number. E.g. if you want to store some text in memory, what you do is use a number for each character. E.g. 65 could be "A", 66 could be "B"etc.

Now, just as you start writing on a piece of graph paper in the upper left and then keep writing towards the right, and then you wrap to the next line and continue writing from left to right again, the computer will write each variable into memory in sequence. To be able to later refer to the different pieces in memory, each box on the paper has an address. The first one in the upper left has the number one, the second one just to its right has the number two, the last one on that line may have the number 1000, and the first one on the second line has the number 1001, and so on, and so forth.

So, whenever you declare a variable named "myCharacter", the computer picks the first empty box on the paper (e.g. box number 32), and makes a note that whenever you're saying "myCharacter", you're actually referring to the contents of box no. 32.

There's one peculiarity you should be aware of, though: Since a byte inside computer memory can only hold numbers from 0 to 255, and has no value for "empty", the computer keeps track of the first unused byte in memory by simply remembering its address, in the so-called "stack pointer", which "points" at the end of our used memory. So, if you had 32 variables which each take up one byte, and thus numbered 1 to 32, the computer would remember the number 33 in its "stack pointer".

Why "stack"? Well, since we are only remembering the end of our used memory, there may be no "holes" in our unused memory. After all, how would the compiler know that these "holes" are unused and available? We'd be wasting precious memory. Since there are no holes in our block of unused memory, our variables appear "nicely stacked up one on top of the other".

Can you already see the problem? Imagine you had a function that has three variables. Two of them (A and C) were one byte in size, the other (B) would be variable in size. Imagine the one of dynamic size had been declared second, thus being in the middle of the other two. They would maybe all start out being one byte in size. Then comes the time where the second variable needs to be resized. You stack looks like this:

Now, you enlarge B to be four bytes long. You'd get:

So far, so good. But now remember that your code doesn't remember variables by name. Instead, it remembers their address. What we just did is move "C" from address 3 to 6. The next time your code tries to change the variable "C", it will still write to memory location 3, and thus overwrite the second byte of "B". BANG!

To prevent you from doing things like that, the programmers decided that variables needed to have a fixed size that was known at compile-time.

In reality, we'd also have to store the stack pointer somewhere. So, what the computer actually does is reserve some special place, e.g. the first four bytes of memory, for the stack pointer. This in turn would mean that "A" would actually be at address 5, B would start at address 6, and C would start first at address 7, and at address 10 after B is resized.

One kind programmer of the GNU C Compiler has actually extended the compiler to allow creating - within limits - variables with variable sizes. However, this is simply a sleight of hand pretending to provide stack variables that can be resized, and will thus be ignored in this article.

Introducing: The heap

While the orderly stack is very convenient for fixed-size things like variables in calculations, and is also very fast and effective due to the fact that all you do to enlarge or shrink the stack is really just adding to or subtracting from the memory address in the "stack pointer", it is completely impractical if you want to work with dynamic memory.

Of course, the people who designed today's computers realized the same. So, in addition to the orderly stack that keeps fixed-size items, they invented the rather unordered "heap". While the stack starts at the top of the computer's memory and grows towards the bottom, the heap begins at the bottom of the memory (i.e. the lower-right corner of our piece of graph paper) and grows toward the top (towards the left, and then upwards on our piece of graph paper).

Now, keeping track of the stack was easy. We just put the items one after the other, and since we knew their position and their size when we wrote our program, we don't need any more info than where they end, which we kept in the stack pointer. Since "keeping track of anything" on a computer requires reserving memory for it, we simply went and reserved the first four bytes on the stack to keep the stack pointer there.

But how do we keep track of the separate chunks of memory scattered all throughout the heap? And how do we remember where the heap has "holes" which can still be used when the program needs some memory?

Well, just as we reserved some memory for the stack pointer, we reserve some for the start of our heap. If the heap is empty, the heap start-pointer is zero. But that's not enough. So, what we do in addition to that is we add a "header" in front of every chunk of memory. This header notes the size of our block of memory, as well as the address of the next block of memory on the heap.

What we have now, is like a game of 'Telephone': You start at the end of your memory, where the heap-start-pointer is. You read the pointer and now you know where the first block is. Then you go to the address the first pointer points to, and there you find a pointer to the second block, follow that, and there you also have a pointer to the third one, and so on. This is commonly called a linked list.

Obviously, this is very wasteful for small amounts of data. Typically, to keep track of a single chunk of memory requires four bytes to hold the size, and four bytes to hold the pointer to the next block of memory. For each additional chunk, even if it is only one byte long, these eight bytes are required again, in addition to the one byte actually needed to store the chunk itself. That is the reason why we still have the stack, even though the heap is much more flexible.

Now, when you need to resize a chunk of memory that is stuck between two others, the computer can simply "punch a hole" in the heap, removing the small memory chunk and instead creating a second one that is larger, which you can now use. Since the computer knows where and how large each memory chunk on the heap is, it doesn't have a problem with holes, and it can even re-use the "holes" when somebody else needs that much memory.

Of course, since the memory chunk moves when it is resized, you can't use the old address to refer to it anymore. The computer will let you know the new one, and the program will need to be written to always use the current address.

You may be wondering why the stack starts at the top, while the heap starts at the bottom. There is a simple rationale for that: By making them start at the opposite ends of the computer's memory, you prevent them from accidentally colliding. After all, if we just decided that the heap started 1000 bytes after the start of the stack, there would be a very strict size limit on the stack. If the stack grew to 1000 bytes, it couldn't grow any further without overwriting the heap. The same could happen the other way round.

Of course, there is still a possibility of the stack and the heap colliding, but now the user can avoid it by installing more memory in their computer.

What I described above is basically what the C memory management functions do. malloc() looks at the memory and reserves a chunk of memory with the proper size, and realloc() reserves a new, larger part of memory and gets rid of the old one. However, the pointer they give you always points to your data, so you don't have to worry about those 8 additional bytes when using it.

Many modern computers are smart enough to keep the stack and the heap from colliding, and thus do not really keep them at opposite ends of memory anymore. Still, the way they do it would involve lots of information about page tables and virtual memory, and aren't really relevant to understanding the basics of memory.

What does that have to do with pointers?

As the attentive reader will have realised, a pointer is nothing else than the address of a chunk of memory. It doesn't matter whether it points to memory on the stack or on the heap. Memory is memory, and in most cases we needn't be choosy. Take note of the implications this has: A memory address is simply a number. As such, we can store it in a regular variable on the stack, and we can do maths with it. We can add to it, we can subtract from it, etc.

Now, why would we want to add something to a memory address? Well,imagine you wanted to keep a range of text, e.g. 'Atkinson', in memory, on the stack. Since every byte is a character, and 'Atkinson' is 8 characters long, you would reserve 8 bytes of memory for it. Now, to be able to access each character in this range of text, you'd have to remember the eight addresses of the eight characters. What a waste!

So, what you do instead is take a step back, and look at the memory:

Since we just reserved the memory for one character after the other (and on the stack), they happen to be in a single row. Also, their addresses are in sequence. So, what we can now do is simply remember the address of the first character, in our example 7. Now, whenever we want to access one of the other characters, we simply add to the pointer to the first character we kept. The first character is at address 7 + 0,the second character is at address 7 + 1, the third is at 7 + 2 ...notice a pattern? The character with the number n is always at address 7 + (n-1). So, by remembering the address of a block of memory and an "offset" of "index" (i.e. n-1), we can easily manage lists in memory.

Moreover, if you want to store this piece of text on the heap, we can just request one large block, and only have to "pay" the 8-byte penalty we need for the length byte and the "next" pointer once, and we don't need 9 bytes per character.

Any of you who have already used C strings or arrays will suddenly notice that this is exactly how indices into an array are specified.

The process of adding to/subtracting from a memory address is usually referred to as "pointer arithmetics".

What about * and &? And what does "de-referencing" mean?

Mind your language! ... err ... Well, when you keep a memory address (i.e. a pointer) in a variable, what you have in this variable is not the memory itself. Rather, you have a "reference" there. Now, the problem with this reference is that all operations you do (like add, subtract ...) work on the reference, i.e. they change the address, they perform pointer arithmetics.

De-referencing is the process of telling the computer to go to the memory address you have here, and to manipulate the memory itself. To do that in C, you use the "follow-address operator", "*". So, when you have a memory address in a pointer variable "m", "*m += 1" essentially tells the computer to first "walk over to that adress", and to then add 1 to whatever it finds there.

Of course, a pointer can point to any kind of variable, even to another pointer. So, "**m += 1" would mean

• follow the first pointer
• treat whatever is there as a pointer
• follow that second pointer
• add one to whatever the second pointer pointed to

which, again, could be an integer, a character, or even yet another pointer. Neat, huh?

And finally, the "&"-operator, also known as "address-of". The address-of-operator simply tells the computer to give you the memory address at which a particular variable is located. You can then stuff this address in a pointer variable and perform pointer arithmetics on it, or whatever you want.

Any additional questions?

Well, this concludes our short but hopefully insightful tour through the memory of your computer. I hope it has helped you.

Reader Comments: (RSS Feed)

Levi writes: Hi, Your article was really helpful! Thanks!

Ludwig writes: I'd like to hear something about you can manage memory in practice! For example in Obj-C.

Uli Kusterer replies: ★ Once I've finished Masters of the Void to cover the C basics, I'm thinking about going into more detail on Cocoa memory management (and especially on tracking down and avoiding memory bugs). Is that what you're looking for? "manage memory in practice" is a large topic, so if you're wondering about something in particular, it may be best to let me know in more detail.

mozart writes: My head hurts after reading that. I Don't even now my 8 times table.

Sid writes: Thank you for your clear description of an often misunderstood area of computer engineering!

Terry Heaford writes: Have read this a few times and found it really useful. Thank you. I would find more articles regarding Cocoa memory management and pointers regarding debugging (no pun intended) really useful for me and I'm sure others learning to programme objective-c with Cocoa would similarly benefit.

Ricky writes: Nice article Uli. I thought I would post a link to Peter Hosey's guide on C pointers as well: http://boredzo.org/pointers/ This might be good additional reference material.

Kim writes: why is memory always sold as a factor of 2? EX: 128mb, 256mb, 512mb, etc.

rakesh writes: 1)how mangge convential memory,higer memory .etc. how it is work .pls 2)DDR RAM called DDR SDRAM?

Uli Kusterer replies: ★ rakesh, I have no idea what you want from me, sorry. Maybe someone else understands his question?

Uli Kusterer replies: ★ Kim, I don't really know. It may have to do with the fact that, each time you add a digit to a binary number, its possible values double (so they might just double the size of each chip to make best use of the additional needed bit in the address), or it may be a physical reason, related to the manufacturing process of memory chips.

Byomkesh Das writes: Fantastic written , I understood clearly, Thanks. One thing Put some diagram explictely

Uli Kusterer replies: ★ @Byomkesh: Thanks for the praise. And what diagram should I put where? And why explicitly? Can you maybe re-phrase that, I think this sentence is missing some part...?

Magster writes: Really clear and unjargonised. Can I ask a question? When methods/subroutines/whatever are entered the variables declared there are pushed onto stack and popped off when the "function" is left. Is this simply to keep stack usage down or is there another reason? Thanks.

Uli Kusterer replies: ★ Well, I think "keeping the stack usage down" is a very good reason. Consider that you allocate some new stack space each time you call a function. That happens millions of times each second, so you'd better not leak even 10 bytes. That said, the end of the stack is also used to locate some stack data (like the return address to jump back to after a function has been called, any registers you save...). This can't be done with absolute addresses hard-coded in the source, because a function could be called concurrently from different threads, or recursively etc., and in those cases you'd e.g. need two different return addresses. One could probably reserve a register for such a purpose, but really this approach is much easier. In short: Yes, and there are other good reasons. :-)

Sunyana writes: Thanks a lot... this article was very much helpful to me.. it make me very clear on heap and stack concepts... Sunyana

F.Daouk writes: Excellent article. This is the most useful information I've read about the stack and the heap. Thanks

ginni writes: good .. bt short .. still .. every thin explained is in a gud n clear way !!

Nikhil writes: hey, great article.. can u plz 'point' to toward further material on memory mnagement? i am also a little confused about the type casting in c, especially the (void *).. i need something that will elucidate the topics mentioned above.. Thanx!

Uli Kusterer replies: ★ @ Nikhil: I don't know what an 'u plz' is, but if you're looking for info on void* and the likes, have a look at my Masters of the Void tutorial (http://www.zathras.de/masters-of-the-void.htm), particularly chapters 5 and 6 delve a little deeper into the C side of things. If that still isn't enough, I'll add something when I next revise the tutorial, but I don't know when that will be.

hachu writes: Kim and Uli, here's the reasons why memory is sold as a factor of 2. In hardware, everything is in binary because each wire can only be on or off. To ask for a location, we need to specify the location by turning individual address lines (also called the address bus) on or off. (hence ones and zeros.) Say for example we have a 16 bit addressing bus. This means we can specify a memory location from 0 to 2^16-1 because those are the numbers that be expressed with 16 bits. Hence 64k. This also means, when making a memory chip, the most space-efficient design is also a grid of these 16 bits. In the future, if we can make the memory chip denser, we add one more address line so now it's 17 bits. Therefore 128k. Adding one more past that, you get 18 bits. 256k. Eventually these keep getting bigger and we end up with the 512MB and 1024MB ones we have now. Because hardware design is quite difficult, memory controllers will have limitations on what configurations of memory can be supported. But memory management units, in cooperation with the virtual memory support of the OS, make it possible to take the little bits and chunks of non-contiguous memory and make it look like one continuous piece to us programmers. Another interesting fact. Because chips often don't come out perfect when manufacturing, the factory can take a chip, test it, and then disable an address line to permanently shut down one side of the chip. Then it's used and marked as if it were manufactured as a smaller chip. You might consider it quite wasteful to disable half a chip because one byte is broken, especially one of the big ones, but consider that the effort to design a way to support non-multiple-of-2 memory modules and memory controller and the OS support for this is so much more expensive. Taking one line and disabling it is the least complex, cheapest, and most reliable way to go.

Jack writes: Hai, Really Nice article.Understood the basic concept of memory management in our computer systems.Also pointer concepts.superp..!Can you please provide another detail article in pointers and data structures.I am very much interested in learning data structures.Thankz...!!

Uli Kusterer replies: ★ @Jack: Thanks. Have you checked out "Masters of the Void"? Chapter 7 concerns itself with data structures, is there anything more you'd like to know than that?

nico writes: Wow, I google'd 'memory management' and 'stack heap' and read about 5 articles before yours. Very clear, useful, and to the point. Thanks so much!!! BTW, although I'm interested in C, I'm currently studying for a java certification and just wanted a high level understanding of the stack,heap, and memory management as much of this is automated in java. However, I was still able to read this article, including the pointers section, and get exactly what I need. Much praise!

Uli Kusterer replies: ★ @nico: Thank you :-) There are also "runtime time" and "I'm not recycling, I collect garbage" postings in my blog that may clear up some additional things that may interest you in Java. I.e. the latter has a short explanation on how a garbage collector works, and the first explains how objects are laid out in memory in a typical OO programming language and also includes sample code. Some of this goes into the nitty gritty details, though.

sudesh kumar writes: Memory management is possible in C lang? Give the ans in true or false.plzzzzzzz If yes, then how.

Uli Kusterer replies: ★ @sudesh: Of course memory management in C is possible, why would it not? You use malloc(), free(), realloc() and the * and & operators.

Comment on this article: Name: E-Mail: (not shown, hashed for Gravatar) Web Site URL: (optional) Comment: (plain text only) Please Enter the following word:

Or E-Mail Uli privately.