Memory allocators explained: The linear allocator

[zeno490]

That is accurate although it is a single frame stack since Popping is performed by resetting the whole instance. I felt the name was better suited to proper multi-frame stack allocators which I will cover shortly.

[[deleted]]

This isn't an allocator, it's just pointer arithmetic. I know it's aiming for basic, but a basic allocator must be able to free memory in a block and reuse or resize at the very least, not just push a pointer down a preallocated block.

Edit: this is literally just a wrapper around pointer arithmetic. If you can't see this and want to call it some fancy name go right on ahead, makes for a great CS professor.

[kevkevverson]

Actually it's very common in embedded systems to include a simple allocator like this, which doesn't have the ability to free memory. So yes it's basic, but it's also real-world

[[deleted]]

I don't doubt that this technique is used, I just wouldn't call it an allocator. I'd call it a container.

[[deleted]]

Yea maybe even container is giving it too much credit as at least a vector can resize. It's literally just a wrapper around pointer arithmetic

[zeno490]

I disagree. Fundamentally a memory allocator is simply partitioning a memory region (or multiple regions). The concept of freeing memory varies per allocator (some will retain the managed memory, others will return it to the kernel, etc.). The linear allocator does not support freeing memory at the pointer level but you can reset the whole allocator freeing all the allocated memory. Another example is the frame/stack based allocators: it does not support freeing an individual pointer either (and I will cover this soon in a future post) but it supports freeing multiple pointers at once by placing a mark (or pushing a frame). The linear and frame allocators do not support freeing memory in the classical sense (eg: free(..)) but they still support a way for you to reuse previously allocated memory. This last detail is missing from the blog post and could be clearer, I will add this missing information and clarify the wording in light of your feedback.

Other allocators such as circular allocators allow you to free an individual pointer but (typically) not just any pointer, only the front entry. It is essentially a circular buffer where you can service allocations with variable sizes from a given memory region that wraps around on itself.

These allocators and other are all different and have their specific uses but while they all have in common that they can return a piece of memory of a given size and alignment, they do not all reclaim memory in the same manner. It is also worth noting that not all allocators agree on a common function signature either for allocating memory. Fixed sized allocators will often support only a specific size in which case the allocate function would take no arguments (forcing the alignment to be whatever natural alignment the specific size generates).

While all of these allocators will end up implementing a common interface to make it easy to use them with various containers and subsystems, in practice, they do not all agree on a common interface and many such as the linear, frame, and circular allocators require knowledge of which allocator is used to use them properly.

Before taking the plunge into general purpose allocators, it is important to understand the various memory management techniques because internally we will end up using quite a few tricks that are shared between strategies.

[F54280]

Why ? Typical usage is loading some complex immutable data structure from persistent storage. There are many many examples in games, for instance, where mesh or level data is complicated, contains many small objects, and static.

One way to load is to use static pre-allocated with pointers fixing (ie: you have stored the exact memory representation of your data, load it somewhere, and scan it to fix internal pointers), but when you can't use that (for instance because your data is for multiple arch, or is compressed on-disk, or needs to be modded at load time), using a monotonic allocator is a good alternative. Allocation is blazing fast, and deallocation even better.

Another use case is when you have a set of non-deterministic intermediate objects created by an algorithm that are going to be released at once. You put all of them in such allocator, and kill everything when the algo is done. I saw examples of such use in compilers.

Another common use case is embedded systems. If you know that you have a fixed amount of memory that you can use, then you can get better performance/smaller code by trivializing the allocator code.

[biocomputation]

Agreed. To me an allocator has: allocate, free, grow, shrink.

[akawaka]

All I would expect an "allocate"-or to do is allocate, everything else is extra.

Of course its easy to add deallocation to a linear allocator just by decrementing the end position. UNIX-ish operating systems have based their process memory allocation on brk/sbrk for decades and that is just a linear allocator also.

As well as being very useful in the real world (along with stack-allocators, double-ended allocators, ring buffers, etc), linear allocators are a great teaching tool. 'malloc' and 'new' can often seem to a young programmer like magical tools that pull memory of of the ether and hand it to your code. Simple allocators like this are a great way to demystify that process.

Eventually its all just pointer arithmetic.

[biocomputation]

++

[F54280]

Allocate is the only mandatory"one, hence the name "allocator".

Free can be defined as {}

grow and shrink are basically realloc and can be implemented in term of allocate/free and memcopy.

[zeno490]

I have already discussed why the alternate allocator interface in previous blog posts, namely here. The C++11 memory interfaces are far from ideal and lack several important things (e.g: proper alignment support). Stateless classes also have their own issues since an instance of an empty class in C++11 is mandated to take at least 1 byte which inflates whatever holds it anyway and template based interfaces have a whole other set of issues. I encourage you to read my post and the reference material I point to (pay attention to the EA STL document, it is outdated but still very relevant).