Introduction
As computers have progressed over the years they have been given more RAM, and processes and languages have become more complex. I`ll go through some of the machines and languages that I have used in the past to talk about how the methods used to look after the computer`s memory have changed.
I`ll have a separate page on computer languages I`ve used and what I think of them, but I will briefly talk about them with regards to memory.
COBOL on the mainframe
This is where I started in computers in 1979. We were given 3 months of training to learn the language, and understand what computers were capable of at the time. We often see tape decks spinning in old sci-fi movies and that was mostly what filled the computer room, along with hard drives as big as washing machines with maybe 50MB of space on them.
The CPU had 8MB of RAM, and again would have been an enormous wardrobe-size box. We had to share that 8MB between all of the running programs, which were a mix of batch programs, development testing, and terminal sessions for 30 or 40 users. The operating system was a DOS-type system and the CPU had 16 or so 32-bit registers, cunningly named r0 through r15. The address bus may have been restricted to a maximum of 16MB, not unlike the Amiga. Likely this whole machine cost millions of pounds at the time, plus the air-conditioned building to store it in and the team of operators to run it on a daily basis. The desktops we now own can be a thousand times bigger in RAM and hard drive storage and cost a thousandth as much, and are of course much, much faster.
Actually, they didn`t really want us knowing too much about assembler and machine code, they always locked those manuals away when they saw us developers heading for the technical services office. I only found out about the CPU by piecing together fragments of information, I never found the software to assemble code, in fact I was blissfully unaware of it for the first 3 years I was there. When a COBOL program crashed you got a massive printout of the memory at the time, the state of the registers, and a summary of the reason for the crash. The most common seemed to be the OC7 exception, which usually meant that a packed decimal variable was invalid because it hadn't been initialised to a valid value.
Doubtless the operating system on this machine did have to manage its 8MB of RAM memory. When it was running one of my COBOL programs, it would spawn an environment for the program to run in, and the program just thought it was running on its own, with its RAM starting from address zero. This kept it largely unable to see the operating system or any other running programs, which is good for security. That was until Splodge decided to read memory from his array using a negative index, he found all sorts of stuff that wasn`t his!
As a computer language, COBOL didn`t support any memory management, as such. You could not allocate yourself any space at run-time. You could define arrays of space in your "Data Division" and you would be given private space in your variables area. Whilst the language maintained a program stack for calls, there were no local variables for routines either which, in other languages such as C, are also kept on the program stack. The program stack is an area of memory reserved for the language to store return addresses. When you call a sub-routine, you need to remember where to come back to, and that is put on the stack, and then the stack pointer is advanced to the next unused slot. This all works nicely unless you recursively call too many times and run out of stack, at which point you`ll be terminated by the Operating System (OS). "Hasta La Vista... Baby!"
8-Bit Home Computers
In 1983 I started using assembler on home computers, specifically the Dragon 32, and the next year on the Commodore 64. I also knew a little about the ZX Spectrum. Being low-level languages there was no concept of allocating memory, and we had no need to consider writing any system to manage the memory. We needed to be fully aware of the memory and what we were using it for, but since we always used all of the machine and stopped the OS in its tracks to take full control, we just had everything. A page in the notepad was how we tended to write down the uses for the memory. You needed to know where the screen was, where your variables would go, and on the C64 where the sprites and character sets were. All the addresses were hard-coded, or made relative to each other.
If I had a small array of working variables I might try to position it over the startup code for the game which, once executed, was never going to be used again. That would be a last-minute change though, as restarts were commonly needed when debugging so I didn`t want to destroy the code while developing. Destroying your start-up code helps to keep your secrets safe. Don`t try this in high-level languages, writing over your code is forbidden. Self-modifying code is right out!
16-bit Home Computers
Now the story of memory management really begins. Dominic was writing a sort of mini-operating system for the Atari ST, with a view to running it on the Amiga too. It would manage the memory, the display, disk I/O and the objects he needed for the game he was also writing: Simulcra. The benefit of this would be that we would be able to implement a game on the ST and convert it to the Amiga easily. Remember that he was writing a 3D game with filled polygons, not smooth scrolling.
I don`t know how much of the technology he implemented was picked up from his university days and how much was from reading some enormous tome, but it was all new stuff to us. Not to worry, though, memory management is as safe as covering your head in barbecue sauce and then sticking your head in a hungry lion's mouth.
While C had been around for over 15 years, we hadn`t any need for any other language than assembler at this time. Assembler is a pure language, in that it doesn`t come with a library of calls that contain pre-written working code, for example random number generators and memory allocators. Don`t confuse those two, by the way! We were getting to grips with using more pointer registers than you can shake a stick at. With that came linked lists, and with that came the memory allocator.
What Does a Memory Allocator Do?
A memory allocator gives you access to your unused RAM in an orderly manner, which is especially useful for buffers that might vary in size, for example: loading documents. You don`t want a fixed buffer of the biggest file size you can think of, and in fact you might want to load more than one document at a time.
On a modern machine there is multi-tasking going on, we can`t take over the whole machine any more, we have to rely on the OS to supply us with resources. If we want memory for a file load we have to politely ask for it. Similar processes go on within the graphics card memory as this too needs to be allocated to applications. Not that anyone should try running half-a-dozen games at once.
On a modern machine there is multi-tasking going on, we can`t take over the whole machine any more, we have to rely on the OS to supply us with resources. If we want memory for a file load we have to politely ask for it. Similar processes go on within the graphics card memory as this too needs to be allocated to applications. Not that anyone should try running half-a-dozen games at once.
On the Amiga we would start off with one or two lumps of spare space in RAM. As memory is asked for, the system carves off a lump from one end of the spare space and passes the pointer to it back. The free space is adjusted to reflect that. When that memory is finished with, it is returned to the system and joined to any adjacent free blocks. You could direct permanently required blocks to come from the opposite end of free space, but just allocating the permanent buffers first works as well. Your Amiga screen buffers tend to be permanent to your game, for example.
Your memory manager might be provided by the Operating System, or be your own, which will necessarily call the OS one, at least these days. On the Amiga we needed to be sure we had all of the resources, so we took over managing everything. We checked both video memory and non-video "fast" memory and effectively defined the RAM that our code didn`t occupy as free memory. We start with one block of video memory, and one block of fast. If fast memory was available we would load our executable code into it and have the entire video RAM free. We could then ask for video RAM or fast RAM in our allocation calls. If you ask for video RAM and you`re out, the system goes bang! Anything that the blitter, sound or graphics chips needs to access has to go into video RAM. Character maps or object structures can go into fast RAM. If you ask for fast RAM and there isn`t any then you`ll get video RAM, unless you`re out, then... bang!
Therefore any game has to work in the machine`s minimum configuration. That gives us the advantage that we know that if there is any additional RAM of either type we can see how much there is and use it accordingly. A floppy disk only had 360KB on it, and RAM seemed to be added in 512KB lumps, so a single data disk could be cached on a 1MB system. We wouldn`t torture the player by loading all the levels in advance, that would take too long, so we cached the levels as they were accessed for the first time.
Therefore any game has to work in the machine`s minimum configuration. That gives us the advantage that we know that if there is any additional RAM of either type we can see how much there is and use it accordingly. A floppy disk only had 360KB on it, and RAM seemed to be added in 512KB lumps, so a single data disk could be cached on a 1MB system. We wouldn`t torture the player by loading all the levels in advance, that would take too long, so we cached the levels as they were accessed for the first time.
Why Do We Need a Memory Allocator?
Most tasks you need to do in a game with memory can just be implemented with a fixed size array in a fixed location. However, as games become more sophisticated you might want to use your available RAM for a couple of different purposes at different times. Again, you can do this with fixed arrays, but working out how big they need to be starts to get more complicated, and having different views of the same RAM gets more complex. A better way is to release the memory back to the system and allocate how much you actually need.
You can do things like record all the allocations and releases of memory so you can ensure you`re not accidentally leaving chunks allocated, otherwise known as leaks. Sometimes you can ask the OS how much RAM is available to be allocated, other times the OS wants to keep that a secret.
Another way to mess up memory allocation is to release memory and then go on using it! That gives you an opportunity to overwrite a block of memory that might be allocated to someone else later. Of course it might remain unallocated, in which case you get away with it today, but maybe not tomorrow.
The third way is to under-run or over-run your allocated amount of memory and start writing on another block., or again, free memory.
Even if you use the OS to get individual blocks of memory, you can write your own wrapper functions to call the OS and store additional info about the memory. It`s all about taking control.
Another way to mess up memory allocation is to release memory and then go on using it! That gives you an opportunity to overwrite a block of memory that might be allocated to someone else later. Of course it might remain unallocated, in which case you get away with it today, but maybe not tomorrow.
The third way is to under-run or over-run your allocated amount of memory and start writing on another block., or again, free memory.
Even if you use the OS to get individual blocks of memory, you can write your own wrapper functions to call the OS and store additional info about the memory. It`s all about taking control.
Some languages try to manage the memory for you, which is great until it goes wrong, and then you`re on your own. It`s better to dive in and understand what`s going on. I`ve watched some people familiar with Visual Basic try and write C functions and expect the memory to be managed for them. They run out of the stuff pretty quickly.
Ways to handle a memory allocator
Some of this may only be appropriate for a DEBUG mode assembly, as it will cost more memory and time for checks. The good thing is that if your game works in bloated DEBUG mode, when it gets trimmed down for RELEASE mode it will be fast and lean. Hopefully these examples work for assembler and C, but some of the things we did to strengthen our memory allocations were:
In DEBUG mode it`s worth spending a few bytes to identify what the memory is for so that if you are looking through your RAM you can identify allocated blocks. Don't leave clues in your RELEASE build that will help hackers though. Some disinformation might be good...
When you ask for, say 50 bytes, you actually get a buffer of a few more bytes than that. You receive a pointer to the 50 bytes you want, but before those bytes you put some marker bytes containing a known sequence, and the same after 50 bytes. These will be checked when you release the memory, and any corruption will cause a breakpoint to trip in. If it contains an array of structures, look for an extra element at the end that has overwritten the markers. It might not be your handling of this buffer that has caused the error. If it`s not then you might want to look at adjacent blocks, especially if they contain large structures whereby writes might skip over (or under) the marker bytes. Do make sure that you have allocated the correct size for your needs. We use sizeof(my_structure), but there's no guarantee that you used the correct name of "my_structure", you might really need "my_other_bigger_structure".
When you release the memory, program it so you you have to pass in the address of your pointer to the memory. This allows the release routine to clear your pointer so that you can`t use it again. It doesn`t help if you made a copy of the original pointer, but that`s your added complexity.
You can write various check routines to ensure that all of the memory is freed, and call them when you`re sure that you should have freed everything. If you want to allocate some memory permanently that isn`t included in this check then you might go for a different memory allocation routine and mark the memory block as permanent so you don`t flag it as an error.
You can put wrapper functions around the real C malloc() and free() calls to add this level of helpful debugging, and you can even create macros called malloc() and free() to do that, as the C compiler is smart enough to call the real call from within the macro.
When you receive some memory from the allocator, the buffer you ask for could contain absolutely anything. You can call a specific allocator that clears the buffer for you first, but these will take longer, and if you know you`re going to load a file into the buffer straight away, then there`s no point.
You can also write functions to check the memory allocations, including for corruptions of your pre and post bytes, and potentially print them out into a log file. C allows you to pass the file name and line number to a macro so that you can log which calls allocated the memory.
You can also write functions to check the memory allocations, including for corruptions of your pre and post bytes, and potentially print them out into a log file. C allows you to pass the file name and line number to a macro so that you can log which calls allocated the memory.
Memory Fragmentation
As I was putting Rainbow Islands together I had a discussion with Dominic about memory fragmentation. This is what happens when, for example, you allocate 3 big buffers that get placed in RAM one after the other and then you free up the first and last but not the middle one because you need it later. Now you have at least two lumps of free memory. If you then want a lump bigger than either of the two you released but not more than the total free, the allocator can`t comply.
Dominic immediately went into technical mode and suggested a more sophisticated system that performed effectively what a disk defragmenter does for files. Firstly, instead of receiving a pointer to your memory, you get the address of a pointer to your memory. Every time you want to use your memory you get the pointer from your given location. I was already grimacing at this as instead of using pointers you`re obliged to use pointers to pointers.
You are then given an additional call to re-gather the memory, which you can call when the game is not in full swing, and it will re-arrange your allocated memory blocks so that they are contiguous, and update your pointers to the blocks. That process could take a while if there are a lot of allocated blocks, and it might struggle if there isn`t much spare space. It might not be able to do the job at all if the space that is left is smaller than the smallest allocated block. We decided in the end that the best way to manage everything is to make darned sure that there are moments in the game where all the non-permanent blocks are released so that the memory doesn`t get fragmented. If you get all your permanent buffers sorted out first then they'll all be allocated together at one end of the memory.
You are then given an additional call to re-gather the memory, which you can call when the game is not in full swing, and it will re-arrange your allocated memory blocks so that they are contiguous, and update your pointers to the blocks. That process could take a while if there are a lot of allocated blocks, and it might struggle if there isn`t much spare space. It might not be able to do the job at all if the space that is left is smaller than the smallest allocated block. We decided in the end that the best way to manage everything is to make darned sure that there are moments in the game where all the non-permanent blocks are released so that the memory doesn`t get fragmented. If you get all your permanent buffers sorted out first then they'll all be allocated together at one end of the memory.
Dominic also briefly suggested that any memory allocation call could cause an automatic re-organisation of the allocated RAM, at which moment I pointed out that a 20-second memory re-organise taking place just to launch that extra bullet might be inconvenient to the game.
You have to be clever about your allocations. If you know you might need 200 objects then allocate space for 200 to start with and use an array or a linked list. Don`t allocate them one at a time. My new system uses an array declared at compile time and threads a linked list through the array elements. This way I can access the objects as a linked list or an array, depending on what I need to do.
PC Programming
Typically on a more modern PC an application might have 10MB of stack space reserved, since we now can put large arrays in local variables that are kept on the stack too that take up a lot of stack space. 10MB of stack space, that`s more than the entire mainframe had in 1979!
I discovered a line of code in one of our C programs like this:
char something_ind[1000000]; // Made big as they haven't decided its actual size
This allocates a space of 1 million bytes on the stack! Notwithstanding that the "programmer" (I use the term lightly) didn`t know the actual size of the string, it was coming from a database, which only supports up to 2000 bytes per string. Plus the name ends in ind, for indicator, which typically is only 1 byte long, as indeed was the database column it was reading. I changed it to be the 2 bytes it needed to be. Nice one to find in the production code. Whilst it didn`t cause any run-time issues, it was certainly slapdash on more than one level.
PCs Go 64-bit
When PCs adopted 64-bit architecture it meant that running out of addressable memory space isn't going to be an issue, for a long while, anyway. A 32-bit CPU can address 4GB, losing a bit to hardware ports, typically you can get 3.5GB of useable RAM. 64-bits of addresses gives us 4 GB squared potentially. I can`t contemplate exactly how much memory that is, or how big the case would need to be fully loaded, that would be 4 billion 4GB RAM sticks!
Going 64-bit caused certain decisions to be made as to how the OS was going to segregate 32-bit and 64-bit programs and dlls. The CPU has to know which it is dealing with, and ensure that 32-bit programs call 32-bit dlls. The changeover to new OS versions always causes some issues to software developers, but the arrival of 64-bit caused more trouble.
If you are writing software that uses other programs or libraries then you need to ensure that all of the components support the same architecture, Yet another issue with using 3rd party components. We never felt the need to get our 32-bit server programs running in 64-bit as we never needed more than 2GB of memory. We did have the client side running in 64-bit quite happily, right up until someone decided to launch our 64-bit application from a 32-bit environment. Needless to say, nothing connects up correctly and it all falls to pieces.
We found a problem with our C memory allocator when the OS went to 64-bit. Whilst our application was 32-bit, it needed to ask a 64-bit OS for memory. For some reason the function call started taking 100 times longer. 100, really? What on Earth was it doing in there? Steve Turner ran some metrics on it, and eventually sorted out our calls, though I never found out how, not that I needed to know.
Going 64-bit caused certain decisions to be made as to how the OS was going to segregate 32-bit and 64-bit programs and dlls. The CPU has to know which it is dealing with, and ensure that 32-bit programs call 32-bit dlls. The changeover to new OS versions always causes some issues to software developers, but the arrival of 64-bit caused more trouble.
If you are writing software that uses other programs or libraries then you need to ensure that all of the components support the same architecture, Yet another issue with using 3rd party components. We never felt the need to get our 32-bit server programs running in 64-bit as we never needed more than 2GB of memory. We did have the client side running in 64-bit quite happily, right up until someone decided to launch our 64-bit application from a 32-bit environment. Needless to say, nothing connects up correctly and it all falls to pieces.
We found a problem with our C memory allocator when the OS went to 64-bit. Whilst our application was 32-bit, it needed to ask a 64-bit OS for memory. For some reason the function call started taking 100 times longer. 100, really? What on Earth was it doing in there? Steve Turner ran some metrics on it, and eventually sorted out our calls, though I never found out how, not that I needed to know.
I have an old photo editor program called Picture It! that clearly a) suffers from the same problem and b) does a lot of memory allocating when doing just about anything. It worked fine on my 32-bit OS, but my under-powered netbook can take an age to save out a file, or crop a photo. What I don`t understand is why the underlying slow OS call in C, presumably hooked in from malloc(), was left alone. Surely you fix the issue so that all callers get the benefit, you don`t make every application have to change its call? You might make a new 64-bit call that 64-bit applications can use, but you don`t oblige updates on all your old 32-bit software, or otherwise render it virtually unusable.
The Nitty-Gritty
When you're writing a function or sub-routine, you may need some memory temporarily. The routine might allocate a buffer at the beginning, and release it again at the end. That's fairly straightforward, but what if you allocate the memory and then an error condition occurs, requiring you to bail out? You need to release the memory that you have allocated, otherwise it stays allocated but you have no record of it. I was always taught to have one exit point from a routine, i.e. at the end, and all routes through end up there, where you can correctly close everything down in one place. Sometimes though people will just bail out of a routine deep in the middle of some conditionals. Those exits also need to release any allocated memory.
Another type of function can allocate some memory for some data, and then want to pass that out for later processing. In this case you need to pass out the pointer to the memory, or pass in a variable address to store the pointer to the data, or store it somewhere more globally. Again, someone has to release this memory after the data has been used, and forgetting to do that repeatedly will also eventually expend all of your memory.
We wrote a C macro that checked that there was no outstanding unreleased memory at the end of each major function. You call it once before you start and it zeroises a count of blocks allocated. As you allocate memory; you count the block and record its address. As you free memory, you tick it off the list and decrement your count. At the end you call the macro again and it checks that all blocks have been released, and screams if you haven't, listing what you haven't released. Sometimes you might want to allocate some memory and keep it, in which case you have a call to allocate permanent memory, which gets logged in a way that is not expected to be released.
C macros can be passed the line number from where they've been invoked, and you can include helpful parameters in your memory allocations that can tell you what the memory is for.
Another way to bring your system down is to try to free up the same memory more than once. It is good practice to release memory and then zeroise your pointer to it, so that you can't use it again by accident. Using memory after you've freed it up is another great programming sin, and usually ends in tears. Keeping multiple pointers to an allocated memory block, whilst being useful, also requires clearing them all out when you're releasing that memory.
Managed Memory
Some more modern languages or variants thereof incorporate managed memory. This means that the system is monitoring your use of memory and will free it when it is no longer needed, auto-magically. Actually the OS is doing that anyway because if your program crashes out in the middle then the OS has to clean up after you, and release everything you allocated. One can never have too many lists!
The only time you get a problem is if you rely on managed memory when working in an environment that doesn't actually provide such a feature. If you've only ever worked in managed memory environments and you get put on a product that doesn't do it, you are going to litter like crazy. Worse than that, you'll likely have no idea why your program keeps complaining.
New Project
Whilst I am very familiar with C and memory allocation, I do know that tracking down issues can be rather messy and time-consuming. There's nothing worse than your call to get more memory being refused because it has all been used. Indeed some calls are rigged not to come back at all if they can't comply with the request!
I have been working on a new game engine, not a graphics engine, just the part that runs the objects, not display them. Thus far I have managed to write the code with all of the memory I need being declared in the variables area with arrays of structures. I am working on the principle that I can do everything I need in a 32-bit application with plenty of space to spare. If the footprint of my game can't load and get started because there's not enough memory then better to know at the start rather than half-way through level 3. Thus far I have made no calls to memory allocation myself, so there's nothing needing to be freed up later. I`m feeling quite pleased with myself so far.
I`m using SFML to display all of my objects in the game, and play all of the sounds. I haven`t seen any explicit calls to memory allocations done by SFML, it`s managing all of that behind the scenes, so I haven`t had to worry about memory at all, other than to wonder what will happen when there's none left. I note that with the project almost completed my DEBUG version is using about 85MB of RAM, it`s not in any danger of falling off the cliff.
I`m using SFML to display all of my objects in the game, and play all of the sounds. I haven`t seen any explicit calls to memory allocations done by SFML, it`s managing all of that behind the scenes, so I haven`t had to worry about memory at all, other than to wonder what will happen when there's none left. I note that with the project almost completed my DEBUG version is using about 85MB of RAM, it`s not in any danger of falling off the cliff.
Finally
Memory allocation is a necessary part of many PC programming environments these days, and can now be used for main CPU RAM, graphics memory that may be on the card or private to it, and shared memory that both the CPU and graphics card can see. Graphics card memory is going to be managed by graphics calls, and it all requires to be monitored to ensure no leaks are occurring. Plus, you will be sharing the memory resources of your PC with other applications, so you don't have exclusive control of it, and nor do you have a fixed minimum available. Life for the programmer isn`t getting any simpler, that`s for sure.
