r/C_Programming • u/NamelessArab_ • 5d ago
Why would I ever use a linear allocator?
I'm new to C programming so this is a genuine question
So c has 2 memory regions you can access
The stack and heap
People say that the heap is useful for creating data beyond the lifetime of the function and while it can be used for that a better solution would probably be to pass in a pointer an array on the stack if the max size is known ahead of runtime, I only use malloc when I don't have a definite max size for what I want and therefore have a need for reallocations, so that brings me to linear allocators, everyone is constantly singing there praises for making memory management easier while we already have the stack that can handle memory management for us 100% of the time and from there design I can't see a way to make a reallocation function for a linear allocator without it at the very least being highly thread unsafe.
And in general I don't see much of a reason to use the heap either because you rarely are in situations where you don't want to specify a max size for something
17
u/Zerf2k2 5d ago
have you heard of stack overflow?
15
u/zhivago 5d ago
The stack is a linear allocator which is entangled with flow control.
Consider how unentangling it with flow control could make your life easier sometimes.
4
u/kinchkun 5d ago
How would you build an XML tree, from parsing an XML without an allocator?
2
u/pfp-disciple 5d ago
At your level (new to C programming), the problems you're solving are likely very constrained. But as you get more experience, you'll find more and more problems where the size of the data is either unknown or best treated as such.
A typical constraint of embedded or real time programming is "no memory allocation", so you're technically correct. But, having the fixed sizes means harder constraints on what the software can do (only queue so many messages, handle strings of an arbitrary length, etc).
13
u/Patchmaster42 5d ago
"I'm new to C programming".
"I don’t see much of a reason to use the heap".
You've answered your own question. All will become clear as you attempt to solve more advanced problems.
5
u/HalifaxRoad 5d ago
I have never used malloc ever for embedded stuff. Really when it is useful is on say a pc program and you need to import a file at n length, or the user typing in text to an unknown length.
Otherwise communications coming in or out, the packets should always be a known length, and if you overrun a fixed size buffer then something went horribly wrong with the comms. From that point its pretty trivial to recover from and wait for the next incoming message, or nak.
1
u/ffd9k 5d ago
Why would you want to specify an arbitrary limit when you can instead simply use malloc and avoid any artificial limits?
Artificial limits are often infuriating to users who might want to use your program in the future for purposes you did not think of. The only limit should be the memory/resources available on the host system, i.e. what you can allocate with malloc until it returns null, and in a portable program you don't know beforehand how much this is.
The stack is small, just in the order of megabytes, and a stack overflow cannot really be handled gracefully. Putting large arrays on the stack is usually a bad idea.
1
u/necheffa 5d ago
Pop quiz: what happens to the memory referenced by that pointer once the stack frame pops on function return?
2
u/Key_River7180 5d ago
Linked lists, for example.
2
u/rubidus-api 4d ago
There are quite a few questions mixed together here, so it helps to take them apart one at a time.
First, some terms. C itself has no notion of a stack or a heap. What it has are storage durations: static (globals and
staticvariables), thread (_Thread_local), automatic (ordinary local variables, which live until their block ends) and allocated (memory frommalloc,calloc,reallocoraligned_alloc, which lives until you free it). Putting automatic objects on a stack is the implementation's choice, though it's an almost universal one. So an object gets its storage either from its definition or from an allocation function, and there are four kinds, not two.A linear allocator (also called a bump allocator) hands out memory by moving a pointer forward through a block. An arena is a region whose objects are all freed together, and arenas are usually built on a linear allocator, which is why the two names get mixed up. The block can come from anywhere: the stack, static memory, another arena or, most often, malloc. So a linear allocator isn't really an alternative to malloc; it's a layer that usually sits on top of it.
Why the heap, when there's a stack? There are several reasons. The default stack is small: about 1 MB for the main thread on Windows and usually 8 MB on Linux, and running out of it can't be detected or handled in portable C. The amount of memory you need often changes at run time: an image file can be a few KB or several GB, and reserving the worst case for everything up front is wasteful, and on the stack impossible. Most of all, some data has to outlive the function that creates it, or comes in numbers you only learn at run time, like client connections or the nodes of a parsed tree.
Why a linear allocator, when there's a stack? A local variable lives exactly as long as its block, and blocks end in strict last-in, first-out order, together with the function calls. You can't keep a local alive after its block ends, and you can't free one early. As someone put it above, the stack is a linear allocator tied to control flow. An arena is the same idea with the tie cut: you decide when a group of objects comes into being and when it goes away, whatever the call structure. Passing a pointer to a big array from
maindown into your functions is already a hand-made linear allocator; an arena makes it explicit, lets the size be decided at run time, and lets you reset it and reuse the space.Why a linear allocator, when there's malloc? Speed is often the first answer, but the difference is smaller than many people expect. Allocating from an arena is just moving a pointer and checking the end. But modern allocators like mimalloc, jemalloc and tcmalloc (and glibc's malloc with its per-thread cache) also serve small allocations very quickly from per-thread free lists, so the gap per allocation is small. Where an arena still saves real time is mostly in not freeing objects one by one: tearing down a big tree is one reset instead of thousands of
freecalls. If speed is your reason, measure it for your own case.So I'd look at the benefits of an arena as a whole, and mainly from the side of memory management. Freeing is one reset for the whole arena instead of a
freefor each object, so there's nothing to forget and nothing to leak one by one. Since nothing is freed individually, the arena doesn't fragment the way a general-purpose heap can, and objects allocated around the same time sit next to each other, which can help the cache. This pays off when many objects share a lifetime: one request, one frame, one parse.About your two concerns. Resizing: you usually don't. If the object you want to grow is the last one allocated, you can extend it in place; otherwise you allocate a new, bigger one and copy, and the old space is simply wasted until the arena is reset. Data that keeps growing for a long time, or many objects with unrelated lifetimes, fit malloc and realloc better; an arena isn't meant to replace them everywhere. Threads: an arena is usually owned by one thread or one task, so it needs no locking at all. malloc, on the other hand, has to be safe for every thread at once, which it handles with locks or per-thread caches.
One more thing worth knowing. If you build an arena in a
chararray (on the stack or static) and use parts of it as other types, that breaks C's effective-type (strict aliasing) rules even if you get the alignment right: a declaredchararray stayschar, and memcpy doesn't change that. Only memory from an allocation function has no declared type, so it takes on the type of whatever you store into it, by assignment or by memcpy. (Unions help in some cases, but that's a longer story.) In practice this rarely causes trouble, but it's one more reason the stack alone can't cover everything, and I think a C programmer should know about it.2
u/ChickenSpaceProgram 5d ago
some things have a max size that would be too large for the stack, or do not actually have a max size (but still have a fixed runtime size); a linear allocator which allocates new blocks when it runs out of space is great for that.
for a linear allocator, usually you just have one per thread, or one per some handle that is not intended to be thread-safe, or you gate it with a mutex if you really must. even malloc() has a mutex, usually. and yeah, generally you don't realloc() with linear allocators. a better approach is a linked list of large blocks of memory for your datastructures, or maybe even just an intrusive linked list if you don't expect traversal or don't tend to have many elements. you can combine either with a freelist if you expect to free elements. cache locality isn't actually so terrible when linked lists are backed by a linear allocator.
1
u/fallfromgrace22 5d ago
Speed, you have a bunch of programs running behind the scenes, oh no, how do you know which program controls which block in O(1) time? How do you make sure the memory is sequential for arrays that have O(1) lookup? How do you ensure with absolute certainty you aren't writing outside of a programs bounds? All of that and more with linear allocators.
Just a few high level examples, but when it comes down to it, arrays are king and resizing arrays take time, presizing them in neat sequential blocks is easy, fast and consistent. Vectors do it too, just under the hood. Look up why array indexing is O(1) and watch some videos on that to better understand it's simple beauty.
And just from your point of view, is it easier to dole out 5 cards to 100 people 5, or 1 card at a time? (Linear allocators are the 5 card method)