3 ms·

There's a time and place for all techniques. Obviously, the "most efficient" form of memory allocation is none-at-all. If you can statically allocate everythin

There's a time and place for all techniques. Obviously, the "most efficient" form of memory allocation is none-at-all. If you can statically allocate everything at the beginning, then that wins. My example of 3999MBs of mallocs() followed by garbage collection is overly simplified. In the real world, if you knew such a common pattern existed, then you'd use a 3999MB vector/array instead. (or if a linked-list were really needed, perhaps Knuth's "Dancing Links" example is best). -------- The issue is that the programmer nay not know the patterns of malloc/free for their code, and yet still wants O(1) performance for insertions / deletions to the middle of the chain. EX: the "Rope" data-structure for text editors is a glorified linked list. Each link has variable length, and represents a "cut" portion of the text that the user has entered. You can move the cursor and "insert" new text anywhere in the rope rather easily. For example, the sentence "This is a sample sentence" could be represented as: "Thi" -> "s is a sam" -> "ple sente" -> "nce". If the user changes it to "This is a silly sample sentence", you'd split "s is a sam" into "s is a " -> "silly " -> "sam" ->... "moving" the cursor left-or-right traverses the linked list. Since the "cursor" of the text-editor only exists in one location, its not very difficult to handle. > when you could just free() the entire hunk of memory at once In this rope example, you don't know which bits of the text will be free'able ahead of time. Only the human knows what parts they plan to delete.

adamrezich 5y ago
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.
kragen 5y ago
That's a piece chain, not a rope. In a binary rope your sample sentence might be (("Thi" . "s is a sam") . ("ple sente" . "nce")) and get edited to (("Thi" . ("s is a " . ("silly " . "sam"))) . ("ple sente" . "nce")), except that you'd probably consolidate some of those small leafnodes in practice. (The (A . B) thing is a Lisp notation for a binary tree node whose left child is A and whose right child is B.)

adamrezich 5y ago

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.

kragen 5y ago

That's a piece chain, not a rope. In a binary rope your sample sentence might be (("Thi" . "s is a sam") . ("ple sente" . "nce")) and get edited to (("Thi" . ("s is a " . ("silly " . "sam"))) . ("ple sente" . "nce")), except that you'd probably consolidate some of those small leafnodes in practice. (The (A . B) thing is a Lisp notation for a binary tree node whose left child is A and whose right child is B.)