When I started learning C, I got taught to just call malloc and free everywhere and not worry about where memory comes from. When I went to university, they told me that's wrong and that I should use STL everywhere, adopt RAII for everything else, and not dirty my hands with memory if I can avoid it. After that, I got a job in web development (there's barely a software industry where I live), so memory doesn't even exist as a concept most of time (unless you OOM the interpreter/virtual machine, then memory suddenly becomes real).

So far in my programming life, memory management has always been presented as something difficult/dangerous that should be avoided altogether. So, I've never had the chance to develop an understanding of the strategies one can employ to manage memory. Before watching Handmade Hero, I didn't even think you could manage memory any other way than to grab pages from the OS and then hand off memory to the rest of the application by implementing your own version of a general purpose allocator (and maybe you don't want to implement your own, because it will become just as complex as all the other implementations).

Casey opened my eyes to the fact that, if you can bound the memory requirements in some way, you can implement a memory management scheme that's simple to understand/debug/profile and barely has to do any work. You can do this by answering a few questions:

• Do you have fixed sized allocations or do you need to allocate variable sized data each time?
• Do you know the max number of structs you would want to allocate at compile or runtime before you start allocating?
• Do you know the lifetime of the things you want to allocate?
• Do you know the order you will do the allocations in/traverse the allocated structs/deallocate the memory?
• Do you know whether the order of the structs in memory is important or unimportant to the rest of the program?

All this may be obvious to people who have been doing systems programming for a while, but we don't have much of a software community where I live, so thinking about memory management is new to me. For context, there weren't even any programming jobs around her 10-15 years ago, and all the jobs we _do_ have now involve interpreted/"web" languages.

So, I'm looking for a book on "memory management strategies" I can use as a reference. Basically, a list of techniques that are simpler than implementing a general purpose allocator along with their pros and cons.

Here's an example of the type of content I'm looking for:

If you:

• Know the total number of individual allocations and the max size of each allocation
• Don't have a uniform lifetime of allocations
• The program will iterate over all allocations it has made at some point, but it doesn't care about the order in which it will read it. Meaning, it's acceptable to allocate 1 2 3 4, then read 2 4 3 1.

You can allocate a memory block, and use it as an array. Keep a pointer to the last full element in the array. When you want to delete an item from the "array", simply move the last full element into the slot you're vacating and decrement the pointer to the last full element.

--
If you:

• Know the total number of individual allocations and the max size of each allocation
• Don't have a uniform lifetime of allocations
• The program needs to be able to iterate over all allocations in the order that it made them. Meaning that if you allocate [1 2 3 4], then delete 2, you must be able to iterate over [1 3 4] order

You can divide the memory block into two linked lists. One is the active set/list, another is the free list. When you allocate new records, you take from the free list and append to the active list. When you deallocate, you unlink an object from the active list and link it to the head of the free list. The tradeoff is that iteration is potentially slower than indexing an array, but the order is preserved if you deallocate data in the middle of the memory block.

--
If you:

• Want to allocate a known max number of sturct X
• Struct X has a known max amount of struct Y as children, but you don't know how many childer each instance of the struct would have before allocation
• The ordering of struct X's in memory is important
• You will not add nor delete child structs Y from individual struct X's

You can add a member to struct X that is:

1 2 3 4

typedef struct { Y my_children[MAX_Y_IN_X] } X;

and allocate in an arena fashion. This is simple but increases the size of X, and pull in unused memory every time you read an X. So if you are iterating X's you will read a lot of useless data.

Or, you can do:

1 2 3 4 5

typedef struct { Y *my_children; int my_children_count; }

Allocate a block that is MAX_NUM_X*sizeof(X) + MAX_Y_IN_X*sizeof(Y), then allocate X's from the start of the block, and allocate Y's from the end of the block. This slims down the X structs, so you should only pull relevant data from memory if you're iterating X's. You will need to dereference to get to the children, though.

Choosing the first or second approach depends on if the the MAX_Y_IN_X*sizeof(Y) is large, and how you want to read the data (say, iterating through all Xs and accessing all children of each X on every iteration)

Obviously, the book/blog/<resource> doesn't have to be written in this particular format, but I do want something that explores memory management strategies and when they're applicable, instead of trying to sweep the whole concept under the rug. So far, all I've found are:

• A bunch of random articles on the internet that cover one technique or another.
  
  These are useful if you have some idea about what you need and want to get into the details. They're not so great when you don't even know what you're looking for. Think of it like trying to teach yourself core CS algorithms and data structures if NO websites existed that collect all of them in one place vs just reading a book that's designed to introduce concepts to you in a meaningful order.
  
  
• A bunch of books about how to implement a general purpose allocator.
  
  These are interesting, but not what I'm after. General purpose allocators can't make any assumptions about the memory usage, which makes them complex. I want a list of strategies for situations where I know the memory requirements I have to obey. I could certainly learn something from books about general purpose allocators, but I would prefer to start from a list of simpler strategies. Later on, maybe I can learn how a collection of simpler strategies can build a general memory management system.
  
  
• Books about RAII or some other way to hide memory management from the programmer - These just go in the opposite direction of what I'm after

What I'm not looking for:

• An introduction to C - I understand the language and programming in general. I can write programs that use new/delete or malloc/free everywhere without issue, but I want to focus on simpler memory management techniques that could be applied in general programming. Where "simpler" means both less complicated to implement and "do less work at runtime" than a general purpose allocator. I know there are cases where you can't constrain your allocations in any way and you have to fall back to a general purpose allocator.
• Resources that teach what pointers are - I know what they are. My problem is "where do I store data and how do I order it so that I can work with it efficiently", not "what is memory and how do I get to it"
• Resources that teach how the OS and processor implement virtual memory - I know what virtual memory is and how paging works.

Apologies for the long post. I don't know enough about the problem to express myself in fewer words, so I had to resort to repetition and examples to frame my question. Hopefully it makes sense. I also didn't know if this is the correct section in the forum to post this, but I didn't find any other obvious place for this question after some browsing.

Ginger Bill wrote several blog posts about memory managements techniques, it's a great starting point : https://www.gingerbill.org/article/

Hello VROOM,

There's a chapter about it in Game Engine Architecture 2nd Edit...st likely in the 3re edition too), which cover a number of custom allocators and their use-cases (stack allocators, pool allocators, single-frame allocators...), and also cover fragmentation and how to optimize defragmentation if it is necessary, and alignment.
The book is oriented for games, so there may be other useful allocation techniques that are not covered.

From your examples it looks to me that you are looking for explanation/guide how to organize data, which is not always about memory allocations. So basically data structures.

I can see why you would think that. What I mean is, given the problem statement of:

I want to store a list of FOO objects such that I can efficiently insert and delete from the list while preserving its order.

There's a difference between:

Implement a linked list. Call new and delete every time you want to add or remove a list node. Then you can add to any part of the list by linking a newly allocated node in, and remove by unlinking and calling delete.

and:

Implement a linked list. If you know the max amount of node items you want to use, allocate that much memory. Have the linked list functions use that memory by doing XYZ. If you don't know the total amount of items, but you do know <blah>, you can use this other scheme that trades off <foo> for <bar>

If you can point me to data structure books that actually take memory seriously, then that would be helpful as well. The ones I learned from said things like "We'll call malloc here and never free" because they wanted to highlight the algorithm, and not how to manage memory.

Also, thanks, forkingpaths and Guntha.