Enter The Arena: Simplifying Memory Management (2023)
HTML-код
- Опубликовано: 23 ноя 2024
- This is a video of a talk I did in August 2023, aiming to teach the concepts described in my blog post at www.rfleury.co..., in a different format, with greater and more concrete detail.
The small sample program-along with many other projects and examples, all built using arenas as the core memory management primitive-is included in the Digital Grove codebase, which is available to paid subscribers at rfleury.com, which is where I primarily post content these days.
If you take audiences participation and they dont have mics, repeat what they say into the mic!
1:06:34
Plus, They had mics, but they were not working
Thank you. Not just for this video but as the whole Hidden Groove blog posts. It is no exageration to say that your online presence has been life changing for me.
Blows my mind to hear that! Thanks!
One of the top 10 videos about memory management in my opinion. Good explanations and informative graphics!
High praise! Much appreciated, thanks.
Agrred! What other videos you liked?
@@enkidughom2508 yeah please do share
What are some other ones you would recommend?
I'm curious about the other 9 videos.
the amount of times that even c# recommends, or internally implements and uses, some type of memorypool shows this is a reasonable direction for memory management, even when there is a quality GC present.
Yep. And if you are even working in a GC'd JIT'd language, arenas are a very common implementation detail to aid in garbage collection. The better you can predict those implementation details, the better you can organize your code to run with the GC.
Hey man. What happened to all your game dev video archive? I enjoyed watching your 2d game dev and I'm sad the backlog has disappeared.
A few reasons:
I had to shelf The Melodist because I found that I wasn’t skilled enough of a designer to really do it justice, and addressing that problem would require time and resources I couldn’t provide.
I unlisted the videos because they weren’t great informational quality w.r.t. programming (I’ve developed a lot as a programmer over the past 5 years), and I didn’t want to lead anyone on about the state of, or plans for, the project.
I have a new series in the works, and so that wasn’t the last you’ll see of my devlogs, but I’m being more careful about it this time, and preparing the majority of the game and series before I upload anything.
@@RyanFleury Fair enough. Thanks for the response.
@@RyanFleury Hiding your mistakes and resources from your community makes me not want to support your channel.
@@ska4dragons Okay, that’s fine. I don’t do anything that I do to please you. I don’t know who you are. Your approval is completely irrelevant to me.
@@RyanFleury While I personally quite enjoyed your devlogs and will miss em, the reasoning seems fair enough.
I am quite excited for more, though.
Hey Ryan, I watched this talk a while ago on the Handmade Cities' Vimeo page and really loved your insight into memory management and the lengths some us go through to not have to deal with it. The live demos were awesome. It's great that the talk is now also available and more accessible here, can't wait for what else you have in store!
Great talk! Allocators' composition is a fascinating way of thinking about programming.
Some questions:
- In the raddebugger codebase, the arena is implemented with a list of memory pages instead of using the "infinite virtual memory buffer" implementation. What are the tradeoffs here?
- Arena-aware APIs are great when you own the entire codebase, but what about when you're creating a generic library?
Do you have some tips about supporting custom allocators in generic code?
- I'm not very interested in other languages than C, but I find the Zig concept of "manage" and "unmanaged" containers interesting. Here, "manage" implies the allocator is owned by the object; while "unmanage" container requires the allocator to be passed at every API calls.
What do you think of managed containers as a programming pattern?
Thanks Ryan, it's a pleasure to read your thoughts on substack.
Can't speak for Ryan, but I have thoughts :P
IIRC, based on the last time I read through the raddbg codebase (a long while ago), it was actually using the virtual memory trick. Since virtual memory isn't actually infinite, it is set up to grow dynamically by chaining several contiguous chunks of virtual address space, on an as-needed basis. There's a flag you can use to suppress this growth behaviour, and an arena_alloc__sized function that lets you configure the size of the first chunk of virtual address space, so you can make it as large as you want. Therefore, no real tradeoff, strict superset in terms of functionality.
There's a bit of a question in my mind about whether the added complexity (even if relatively small) is worth it. With 48-52 bits of address space on a 64-bit platform, you could allocate something in the order of 130,000 2 GiB arenas (although would need to leave some address space for OS, C runtime, etc.) before running out of address space to reserve. I think the idea is that this could be an issue for a sufficiently complicated application, or on platforms with more limited address space (e.g. Nintendo Switch). I believe I've also read something of Ryan's saying that the idea behind the growable arena setup is that it allows the application programmer to more or less ignore how big each arena should be until further down the later (no crashes because arena is out of memory while in development), can tune arena sizes later on.
The reason for chaining over reallocing (like std::vector) is clear though, would invalidate all pointers to memory in the original memory region.
If you want to support local allocators in more of a C++ style, and continue to use STL containers, this is still possible. You can pass an `Allocator` reference into the contructor of e.g. a std::vector in C++ (though there is some template stuff to deal with). The "Local ('Arena') Memory Allocators" talk by John Lakos (CppCon 2017) is pretty good for learning a bit more about this (and arenas generally). That said, I prefer the syntax of what Ryan is using quite a bit more.
If designing a library, a helpful design constraint is to make no memory allocations internally, instead relying on the caller to pass in memory to use. Chris Wellons (nullprogram) has a great article on this called "Minimalist C Libraries", showcasing some examples.
Sorry I’m being distracted by the gun show. Way to make one of the most brutal topics in computer science fun to watch.
Love the first point. It was so funny to go from community college in which we used only C and C++ (used some other stuff too, but exaggerating for my point) for everything to my university using Java for everything
Everyone there didn't even know what pointers were, how to work with assembly. It was awful.
Great talk. Game devs need to come over to the EDA world and help fix all the terrible GUIs and slow algorithms.
Just started learning zig and I've been using arena memory management a lot there. Ever since I heard about buckets in a Jonathan Blow stream I've been wanting to try a language where I can do this.
EDIT: Oh, and in Unity's ecs system, with their Temp allocator and WorldUpdateAllocator. Forgot that's essentially a kind of arena allocator.
No need to wait for a new language. This technique is universal to all programming. You can do this in C or assembly.
Great memory management talk! Thanks
Great video, i had been hearing about arenas a lot ( from zig and a proposal from golang). I always guessed how it works from its name, but this lecture was illuminating, great job
When I saw this video, I thought it was about Zig at first.
Great talk, subtitles for questions would've been very useful, thank you!
the free list thing is the only part i have trouble understanding fully how to implement, i will need to revisit when i need it
awesome talk... thumps up
Good talk but I really hate it when questions are done on the fly and not kept at the end.
Nice talk, subbed immediately
we do need more content like this in modern programming world
and btw, what are you using for ur presentation?
thanks for this talk, just wish I could see what you were pointing at :D Anyway, thanks for reminding me that you can reserve big chunk and commit on demand. One question, when you said that on demand commit you still have contiguous memory due to having reserved big chunk initially and os handles the physical memory mapping, but does it still cause cache miss on contiguous address but on different pages in physical memory?
How did you implement your atlas arena? Did you just push linear chunks on the arena for each glyph (or a batch of glyphs), or was it more like you already allocated a big chunk and you just need to reserve the correct 2d coordinate of each glyph?
Very nice video. Discovered your blog a while back and its been my favorite resource ever.
I wanted to ask something unrelated to the video itself. How does one apply to RAD. Is it through epic games? Because I couldn't find anything related on RAD's linkedin or their website. Sorry if its inappropriate to ask.
I wonder how demo app was written, it has some cool visualization, animation when you type and erase, shadows. maybe it is some library in c++?
@@nescafezos4265 It was written within the Digital Grove codebase, which is my from-scratch C codebase for engines/tools/games.
Great talk!
Is there any reason you would stack arenas? Say you want an entity arena but you want contiguous memory for each subtype of entity, would you make a per subtype arena stacked on the entity arena?
Love the topic and presentation, but I still don't understand how an arena is different from another tree of scopes. It seems like scope reservation would be a simpler approach, unless that's a actually what this is lol. Like I said, I don't quite understand the arena unless it's a reserved scope conceptually.
Yep that's what it is, you define the scope of the arena then pass that arena to functions
dude, this slaps
What's the difference between your ArenaPop() and ArenaPopTo() calls? A few of the names are hard to figure out. I'm assuming AutoAlign is a field in the arena struct that's used for all the push calls with the exception of the ArenaPushAligner() call? ArenaPushNoZero() indicates that the memory isn't defaulted to zero?
ArenaPop -> Pops some # of bytes (measured from the back of the arena, before the pop).
ArenaPopTo -> Pops to some specific byte position (measured from the beginning of the arena).
ArenaPushNoZero -> Pushes onto the arena without zeroing any allocated memory.
Auto alignment is something I would change at this point; I would just pass the alignment for each push, and then hide it behind the PushArray macro. But yes, it just chooses the "default alignment" for each Push.
@@RyanFleury Alrighty then, I'm on the same page now I reckon. Do you zero by default then with all the other push calls? So at programme start would you use PushNoZero() as presumably you would use VirtualAlloc or similar in your arena initialisation function, and thus would have a zero buffer by default. But once memory may be non-zero you'd use the other calls which would then zero using memset or ZeroMemory() or a simd-ised version or whatnot first of all? I've used arenas but the idioms you use in your code base are slightly different to my own.
@@bryanwelsh6383 Yes, everything is zero by default to ensure consistent zero initialization, which is why the non-default naming scheme (Push*NoZero) is intended to specifically avoid that zeroing. I basically always zero the memory explicitly, even if in some circumstances it may not be zeroed (e.g. immediately after it is committed, when it will have been zeroed by the OS), although you're right that you could skip it in those cases. Another option, which I may switch to, is zero-on-pop.
@@RyanFleury Yes, zero on pop makes most sense to me. Zeroing the memory is pretty cheap on most user systems regardless.
Thanks for the quick replies! That's cleared up everything.
I didn't quite grasp the thing about arena per entity, when they are bigger then a page size.
Interesting. Anyways where is the means to host a private server for Dunlore?
Is that you, Charles? 1:23
Yo what was the theme you used at 38:44. Thank you.
it's his 4coder theme, i think it comes with 4coder in the themes folder
@@spiritwolf448 Thank you.
With the name arena, i didn't get how a string could be stored in chunks. Shouldn't it be a contiguous array in memory for the consumer? Maybe I'm missing something basic
it doesn't need to be contiguous, instead you can store a bunch of chunks.
Then when you use the string (for printing for example) you can decide whether to collect all the chinks into a single string or change the algorithm to account for the chunks that you have.
The string is stored contiguous in _virtual_ (address) memory. The hardware (MMU) and OS have translation tables of Virtual to Physical.
So physically it can cross a page boundary, but to your program it looks contiguous
@@adama7752 thanks for the response! But I'm still in , because I imagine that the arena is a higher level abstraction above the mmu, and should manage virtual addresses
@@adama7752 that's not what is happening here,
he explicitly said that the string is stored in a linked list of 56-byte string chunks (with 8-byte next pointer) and then reassembled when needed, paying the memcpy
@@ratchet1freak so there is an API for getting the string and at that moment the string is memcopied into one array?
A language should probably be requiring allocators for everything that should go to the heap so that you do the right thing and choose your life time.
Nah. Once you have mastery over building your own APIs and allocators, it isn’t hard to build the right thing in any language. Many codebase-internal systems don’t want to expose allocator control to the usage code. You don’t need the compiler to handhold you.
@@RyanFleury I have to many colleges which are on a opposition side to this.
I hope to see more safe languages take this general approach of group thinking :p
@@RyanFleury I agree that it's good to implement your own, especially to know how it works but also so that you can alter it to your specific needs. But compilers can be more useful tools to correct mistakes than a C compiler is, and a language/ecosystem that standardize a good and simple allocator API (with ability to provide own allocator, and overwrite the allocator of a library) would probably be a good thing.
Just use generational GC. These handle scoped allocation nicely, in addition to allowing advanced features like replacing frequently used string tokens with dictionary integers.
For small temporary allocations in some call stack (like create a list and return it from a function which is then used by the caller one time) why is this better than C++'s RAII where instead of allocating at all you can create on the stack and have the object be destroyed automatically when it goes out of scope? No you need to push/pop temporary arenas and pass around a reference to the arena which is an overhead in itself.
How is it not better?
- Like stack allocation, but much more flexible, and more broadly applicable, since the usage code controls the arenas
- Organizes objects, which would be individually managed via RAII, into groups, where things happen *per group* instead of *per object* - massively more performant, and explicitly encodes much more important details in the code
- A single tool to do all batch-freeing; there is no RAII per-object "cleanup" - all allocation-related cleanup happens with a single trivial operation
- 150 LOC to implement, does not require a C++ compiler; can be built with a much simpler C compiler which builds faster, is much less difficult to replace, and is much simpler for tools to work with
- No need to mark up all types with RAII constructors/destructors, which bloat not only type definitions, but introducing hidden "gotchas", due to implicit code generation rules when a type becomes non-POD. Much simpler, much easier-to-read and easier-to-debug code.
> where instead of allocating at all
Pushing onto the stack *is* allocating, in the same way that pushing onto an arena is allocating. There is no fundamental difference.
@@RyanFleury All good points, however the syntax of "declare and use" is most convenient for many temporary use-once structs like a dynamic array. I've used arenas for years in the Cocoa framework (macOS) and they're great but it's still manual work for something that could be automated. I think using both strategies is the best policy?
@@RyanFleury Another thing, doesn't the C++ approach of structs on the stack mean you don't need an allocation to wrap structures like std::vector? I guess if your allocator is fast it doesn't matter would be my guess. In other languages you'd get 2 allocations from malloc, one for the class on the heap and another for the array memory. C++ only has one of those if you declare it on the heap.
Can someone explain how arenas reserved multiple 64Gib, my windows 16 gb ram plus 48 gb virtual ram system cant reserve more than 50 gb with malloc in cpp program.
Edit: I was able to reserve 127 TB virtual address space with virtual alloc on windows 11 pro. I read the docs, the limit is 128 TB per user space process.
🧠🧠🧠🧠🧠🧠
rust developers in shambles
how come? arent you suppose to manage your own memory?
@@zyhru not really, since the borrow checker works like a compile-time garbage collector, so you go from managing your memory to coping in your submissive relationship with the borrow checker
Had to ask which colorscheme are you using for nvim| vim in your demos
This is cool. I mostly code in rust but I love C. I wonder if there is a way to use arenas as the primary allocator in a rust program? My domain is database management systems. Fragmentation is a general concern there.
I tried making my own arena in Rust. It's very much possible and you can even take advantage of its lifetime mechanism to make it safer to work with compared to C. However, there are a few caveats:
- for any fixed-size object that you want to allocate on the arena, you have to put it on the stack first, unless you want to deal with Rust's MaybeUninit API (and also lose Rust's ability to tell that you wrote to all fields of the struct, I think).
- if you want to implement arena checkpoints safely, you can't do it at compile-time. Rust's abstractions just can't get you there unfortunately. The best you can do is to introduce some kind of API that introduces a runtime check.
- Rust uses RAII pretty much everywhere, it's based on it. So arenas are kind of a bad fit to begin with, even though it's possible.
FYI, there's an existing Bumpalo crate which implements an arena allocator.
Rust is a toy language why would you code in it if you know C
@@rusi6219 the amount of static analysis guarantees it provides is very helpful, especially when multithreading with shared memory. Also, I like the type systems explicitness and inference. It's just a very ergonomic language for what I am doing, which is database systems. I probably wouldn't use it for games, there I generally use Odin.
@@grim5i I had posted a comment about me making my own arena in Rust and my thoughts on it and it got deleted :(
I'll try again anyways... So basically, making an arena in Rust is feasible. You can take advantage of its lifetime system to make it safe, although as soon as you want to implement checkpoints your only safe solution involves runtime checks.
That said, I find arenas quite unsuited for Rust unfortunately. Rust's whole ecosystem and language constructs revolve around RAII and malloc-free pairs, so custom allocators like these stick out like a sore thumb. You do have the bumpalo crate available if you don't want to implement it yourself though.
Nice talk! I just don't understand the example with the dynamically sized array/vector and on why does arena prevent the error of getting a pointer to an element and push to the vector when it will need to grow? If you have allocated vector and another object after it in the same arena, then the call to push must realloc and so it will alloc a new bigger chunk (and since another object is allocated after it, you can't just enhance the size of the alloc) in the arena memcpy the old content add the new one, and you still have an invalid pointer to freed data. Maybe your point is that we don't need to free the previous alloc and so the pointer is still valid ? But in that case we will use a lot of memory unnecessary, so I guess that's not what you intended.
I think in practice the value of the pointer gets re-assigned to the new memory location, like a pointer to a pointer.
The dynamically sized array _is the entire arena_ in this case. And since the arena itself is backed directly by page allocation, you can just reserve a big chunk of virtual memory space (say 64 GiB), and then commit the next virtual pages as you grow the arena. Since you're using virtual memory and that the OS can only use the memory you committed, requesting new virtual pages doesn't involve any kind of reallocation, and you'll end up with a contiguous chunk of pages that will never change its memory address.
if you know that you last pushed an array to the arena then you can keep growing that array (as long as you don't hit the chain boundary) and know that it will remain contiguous.
Yeah, that's why all of that discourse in some corners of the internet with how "unsafe" C/C++ is and how we should all just switch to Rust, always cracks me up.
Because all it shows is their limited understanding of memory management and systems programming, which also means that they aren't at the point of creating really good stuff.
Sure, I won't expect everyone to suddenly be an expert, but then they don't get to state opinions about such matters like they are facts.
The reality is every time we code something we code a very little amount functionality for which we need to allocate very little memory so keeping track of it is really not a problem; Rust people don't understand that because they never go beyond hello world and have this weird notion that you're supposed to code ten thousand lines of code over sixteen hours uninterrupted which is maybe possible for a bipolar dev in his manic phase but not a normal person.
Lee Edward Young George Johnson Steven
tldr
Who is this for? Like say something interesting?
TL;DR: “if you can’t watch an hour long lecture, you can’t be a programmer”
Mofo needs to get to the point faster.
If you can’t sit through a brief introduction to an hour lecture, you likely don’t have the attention span necessary to be any good at programming.
@nisonatic Not always true. Too many tutorials on RUclips take like 10 minutes introducing their channel and life story, and then spend a minute doing the actual thing you came to see.
Although, when someone is giving a talk in front of a crowd of people, I think it is acceptable.
Saying that someone is not going to be good at programming is just straight up toxic though.
Just watched the lecture again, and I agree with the responses to this comment now. He gets to the point pretty darn quickly.
@@RyanFleury Sounds like Copium.
Lmao I dont think I saw a single female in that room, just saying
Okay?
1:06:25
So what?
He's telling us how to program microcontrollers for missiles, great information for those who value knowledge 👍🏼 😂
wtf does that have to do with a topic of memory? 😭 you goofy for that
see what rpmalloc does