3 ms·

but it's completely valid to have something like a 4GB linked list, if that's what your application calls for. there's nothing wrong with having a linked list w

but it's completely valid to have something like a 4GB linked list, if that's what your application calls for. there's nothing wrong with having a linked list whose nodes you allocate in an arena and then free all at once (or mark as "free" & reuse yourself if needed) later! I'm not familiar with how ropes work beyond the surface level so I can't comment on that, but in general, it's helpful to recognize that memory allocation and struct initialization don't have to be coupled. it's only when you go "full RAII" that you have the recursive-traversal free() issue. if you sidestep RAII (or override operator new or whatever), then you can allocate memory in pools or arenas or whatever, instantiate structs within that memory, and then later free the whole thing at once. the whole idea of garbage collection seems to me to be predicated upon the idea of not wanting to have to worry about what is going on "under the hood" in memory and instead wanting to be able to say, with code, "get me a new Foo—I don't care where you put it, figure it out yourself—and when I'm done with it, get rid of it as you see fit." and it's easy to see how one gets there, because languages like C++ encourage you to use new and delete to construct and destruct objects, allocating them in memory wherever. but by putting a little bit of thought into your program's structure and how the memory is going to be handled under the hood, you can not only get better performance but also just a better understanding about what the computer is doing with the code you write. I used C# before I learned C/C++ and it was great to muddle my way through things with garbage collection until it wasn't. then when I learned C & C++ it was like ok, malloc()/free()/new/delete all the things, sure. but there's plenty of middle ground between the two extremes that is often overlooked when it comes to memory management, in favor of "garbage collection, yes or no?"

Karrot_Kream 5y ago
Yeah but then you're allocating 4 GB on app startup. Now sure, most of that memory will be unused and so the OS has potential to keep the memory "unallocated" until you write to a particular page, but this depends on the OS and architecture's implementation of paging. In embedded systems where the system is being used for only a single thing (or mostly a single thing), arena allocation is common. In desktop applications where the user can run heterogeneous workloads or long-lived network applications where the application could be allocating memory on every request, you run up against memory limits quite fast. If you squint closely, you can see that Java's NIO libraries basically sidestep the Java GC altogether and manage buffers in "native memory" which are essentially small arena allocators. There's certainly room for more than just "yes GC" or "no GC". Regardless it's good to know about arena allocation because it's one of many effective techniques in a toolbelt. If you find yourself writing a CLI utility in an unmanaged language, it's often simplest to just allocate and never deallocate, because the application will only run for a small amount of time and the OS will deallocate resources on app exit.
- _gabe_ 5y ago
  You can allocate 4GB of virtual memory which will ensure that it doesn't get allocated until you actually hit a new page. Heck, you can, and OurMachinery has a great blog post on this, allocate 100GB of virtual memory and then use pointers as immutable ids and your app will only use as much physical memory as needed and the OS will take care of the rest. https://ourmachinery.com/post/virtual-memory-tricks/ https://ourmachinery.com/post/virtual-memory-tricks/
dragontamer 5y ago
The main problem with more precise strategies is that they only work in precise situations. New/delete and RAII and malloc/free (be it either unique_ptr source/sink pattern or RAII pattern) are basically universal techniques, albeit at a performance cost. There are many other strategies but they require more thought. ------- Personally, I'm a big fan of vector + swap with the end, which covers most of my common needs. When looking at linked structures: linked list, trees, and graphs... It's often common that your specific application has patterns that a more specific strategy (arena allocation, stack allocation/bump allocation) works out. But there is also the chance it doesn't work out, and prototyping with generic methods (new/delete/RAII or garbage collection) is a good first step.

Karrot_Kream 5y ago

Yeah but then you're allocating 4 GB on app startup. Now sure, most of that memory will be unused and so the OS has potential to keep the memory "unallocated" until you write to a particular page, but this depends on the OS and architecture's implementation of paging. In embedded systems where the system is being used for only a single thing (or mostly a single thing), arena allocation is common. In desktop applications where the user can run heterogeneous workloads or long-lived network applications where the application could be allocating memory on every request, you run up against memory limits quite fast. If you squint closely, you can see that Java's NIO libraries basically sidestep the Java GC altogether and manage buffers in "native memory" which are essentially small arena allocators. There's certainly room for more than just "yes GC" or "no GC". Regardless it's good to know about arena allocation because it's one of many effective techniques in a toolbelt. If you find yourself writing a CLI utility in an unmanaged language, it's often simplest to just allocate and never deallocate, because the application will only run for a small amount of time and the OS will deallocate resources on app exit.

_gabe_ 5y ago
You can allocate 4GB of virtual memory which will ensure that it doesn't get allocated until you actually hit a new page. Heck, you can, and OurMachinery has a great blog post on this, allocate 100GB of virtual memory and then use pointers as immutable ids and your app will only use as much physical memory as needed and the OS will take care of the rest. https://ourmachinery.com/post/virtual-memory-tricks/ https://ourmachinery.com/post/virtual-memory-tricks/

dragontamer 5y ago

The main problem with more precise strategies is that they only work in precise situations. New/delete and RAII and malloc/free (be it either unique_ptr source/sink pattern or RAII pattern) are basically universal techniques, albeit at a performance cost. There are many other strategies but they require more thought. ------- Personally, I'm a big fan of vector + swap with the end, which covers most of my common needs. When looking at linked structures: linked list, trees, and graphs... It's often common that your specific application has patterns that a more specific strategy (arena allocation, stack allocation/bump allocation) works out. But there is also the chance it doesn't work out, and prototyping with generic methods (new/delete/RAII or garbage collection) is a good first step.