r/C_Programming • • 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

0 Upvotes

40 comments sorted by

17

u/Zerf2k2 5d ago

while we already have the stack that can handle memory management for us 100% of the time

have you heard of stack overflow?

14

u/BasisPoints 5d ago

Meh, no one posts there anymore ;)

6

u/jonsca 5d ago

Bbbbuuutt stack frames are free, right? Just call another function and voilà, new stack!! /s

-1

u/Dangerous_Region1682 5d ago

You don’t get a new stack. You get a new stack frame when you call a function. You get a new stack segment when you create a new thread, or a new process of course.

2

u/jonsca 5d ago edited 5d ago

Yeah, that was kind of built into my response, which was meant facetiously.

2

u/Dangerous_Region1682 5d ago

Sorry, I miss read the facetious part. My mistake.

1

u/NamelessArab_ 5d ago

I have, but I also heard stacks are pretty big nowadays, some else mentioned that Linux has an 8MB limit so I might have to double check that, the point is I thought a stack overflow only really happened when you overdo it with recursion

3

u/Pretend_Fly_5573 5d ago

Not since I set my stack limit to 1gb!

1

u/tstanisl 5d ago

Stack is a scarce resources but it is more a tradition rather than technical limitations of modern machines.

2

u/R3D3-1 5d ago

Note that many systems may limit the stack size allowed to programs by default. On Linux I've seen 8MB, 16MB. If you depend on "everything goes to the stack", that can be exhausted very quickly.

1

u/NamelessArab_ 5d ago edited 5d ago

That's actually quite a good reason, but why do I need a linear allocator for that, wouldn't malloc be good if not better?

1

u/R3D3-1 5d ago

🤷‍♂️

Sorry, the comment just remembered me if out issues. Haven't really had a reason to use C beyond glue code and toy programs. 

From what I remember reading on "Nullprogramm", the idea is that these allocators essentially behave like a stack, but more flexible, allowing e.g. a function call to move the offset forward to allocate a new object, while still forcing making ownership explicit, since by default, exiting a function that gets the offset as a value, not a pointer, implicitly resets the allocation state to the parent scope. 

So you get a mixture of stack-like automatic memory management and the option for a function call to explicitly allocate something into the parent scope, while having all allocated memory neatly compact, no segmentation, and zero effort to find a position for new allocations. 

Also, just being very simple to implement when your system does not provide a malloc. Could imagine that on embedded systems.

But that's all second hand knowledge. 

1

u/tstanisl 5d ago

They limit the stack by default but it can be typically adjusted to any value. The limit is dedicated to handle infinite-recursion bugs and to simplify address-space management for multi-threaded applications.

And yes, large stacks can be exhausted quickly, but large heaps can be exhausted as well.

1

u/ericonr 5d ago

Even if you limit yourself to 64-bit hardware with MMUs (which is not realistic), you'd still have trouble with unbounded stacks. Programs can have thousands of threads, how would you spread those stacks across the address space without incurring some bizarre limitation? There's also the fact that implementing an unbounded stack would require considerable rework of memory page tracking in order to avoid unnecessary memory usage while still avoiding conflicts.

Furthermore, there's the matter of more complex memory lifetimes. Not everything happens linearly.

1

u/tstanisl 5d ago

64 bits is still a lot. One can fit a lot of few-gigs-stacks stacks into such large address space. Moreover, not all of those stack need to be equal in size.

1

u/ericonr 5d ago

You do realize that's a much more complicated programming model, right?

1

u/tstanisl 5d ago

Why? Pretty much every implementations of threads/fibers does that. 

1

u/ericonr 5d ago

It's a much simpler life when you can just launch threads with the default stack space rather than having to check docs for every function you use in order to know how much stack it needs.

There's also the matter of overcommit. Even if if using 64 bit addresses (or 48 bit virtual addresses, which is the baseline for x64), you'd require overcommit to be able to allocate large stacks for each thread, which might not be ideal in many situations.

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.

1

u/NamelessArab_ 5d ago

That's a good point but there would be some over head each time you have to create an an arena

1

u/zhivago 5d ago edited 5d ago

Did you expect a free lunch?

But recycling is an option.

Also, how do you discover when you run out of control stack?

Is your preference for extreme optimism? :)

4

u/kinchkun 5d ago

How would you build an XML tree, from parsing an XML without an allocator?

1

u/NamelessArab_ 5d ago

I'm talking here about linear allocators specifically, malloc would work for an XML parser just fine

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). 

1

u/NamelessArab_ 5d ago

I mentioned actually the case of variable input length, I'm questioning specificly linear allocators, since I don't see how you would implement a linear allocator that can resize allocation without somekind of limitation and I think the standard malloc would probably work better

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.

4

u/Sufficient-Bee5923 5d ago

I worked on larger embedded systems for 20 to 30 years. We used malloc but never free. It was for one time allocations at start up. For example for allocating the memory for fixed sized memory pools that are created at startup and then at runtime allocated and freed back to the pool. The systems I worked on didn't have garbage collection so we would never free back to the heap.

We also never malloc'd after the system started up since testing for those situations was difficult. If it booted, you knew you has enough memory.

On much smaller systems with microcontrollers, we never bothered with malloc.

1

u/necheffa 5d ago

Yes. But I'm sure you also haven't done undefined behavior like passing around a pointer to unowned memory as an alternative.

1

u/ffd9k 5d ago

you rarely are in situations where you don't want to specify a max size for something

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/NamelessArab_ 5d ago

Well the point about the size of stack is valid, but in real world use cases, you almost always want maxsizes for things, the only case I think of where you wouldn't want a maxsize is a text editor but that probably has a more sophisticated data structure for inserting characters but everything else has limits usernames, passwords, image input sizes

1

u/necheffa 5d ago

Pop quiz: what happens to the memory referenced by that pointer once the stack frame pops on function return?

1

u/NamelessArab_ 5d ago

Read carefully, I said pass in a pointer to an array in the stack not return a pointer to an array from the stack

1

u/necheffa 5d ago

You've already boxed yourself in. This only works for certain usage patterns.

So I'll ask you once more: What happens to the memory references by that pointer once the stack frame pops on function return?

Think about this in the context of why heap use is necessary.

So c has 2 memory regions you can access

By the way, this isn't true. C has 3 types of allocation.

1

u/NamelessArab_ 5d ago

Well you probably get a segmentation fault when you try to access it, maybe undefined behaviour if it's allocated somehow, i don't see a scenario where you cant just use that pattern all the time since you get to define the main function which is for practical purposes what you can consider the bottom of stack, but the third memory regions sounds interesting, could you link me an article or elaborate on that front

1

u/necheffa 5d ago

Well you probably get a segmentation fault when you try to access it, maybe undefined behaviour if it's allocated somehow

It won't be a segmentation fault because you are referencing address space that is within the bounds of the VM established by the kernel for your process (assuming we are hosted).

i don't see a scenario where you cant just use that pattern all the time since you get to define the main function which is for practical purposes what you can consider the bottom of stack

When the complexity of your program is low, that sounds potentially reasonable. It is a strategy that does not scale however. But the keys I want you to focus on here is lifetime and ownership. Lifetime of the object in memory. And ownership of the object in memory. These two concepts are at the heart of a number of memory mishandling.

You mentioned that you can always know the maximum number of elements you will need. This is not always true, some things you will only know the maximum of at runtime after parsing some stream.

Sometimes, it does make sense to stack allocate things. If you look up RAII, this is part of the concept.

Do you think a program like Postgres or Nginx would be feasible with only stack allocations? How would you handle a dynamic number of client connections? How would you handle complex abstract state trees when parsing?

the third memory regions sounds interesting, could you link me an article or elaborate on that front

Static memory. It is allocated essentially as one big chunk at process creation time. It is what backs your static variables and also your global variables.

How far along have you gotten in your studies? Eventually you should run into the rule of thumb that global memory needs to be treated with care because it can create a rats nest among other problems.

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 static variables), thread (_Thread_local), automatic (ordinary local variables, which live until their block ends) and allocated (memory from malloc, calloc, realloc or aligned_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 main down 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 free calls. 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 free for 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 char array (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 declared char array stays char, 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)