3 ms·

in the "jai" programming language there's this thing called Temporary_Storage, which is basically an arena allocator, which lives in the "context", which is som

in the "jai" programming language there's this thing called Temporary_Storage, which is basically an arena allocator, which lives in the "context", which is something that you can "push" to to make it different per-thread if needed, or anything else (like per-request in a web server). you can allocate anything you want in Temporary_Storage, and then when you call reset_temporary_storage() it does what is says and resets it. for a video game you will call this every frame, but for different contexts like web development you could reset this after resolving a request or whatever. you could use this exact same system in C++ even though there's no built-in language feature for it, but it probably wouldn't play nice with RAII or whatever (unless your data structures were aware of the existence of your hand-rolled Temporary_Storage system and knew not to call free() in the destructor). after learning about the costs associated with using malloc()/free(), then being exposed to long-term arena allocators, then being exposed to a "temporary storage" system like this, when people talk about garbage collection being absolutely necessary for developer productivity or whatever plus also a way of avoiding malloc()/free() costs, I can't help but wonder if anyone who promotes garbage collection as a borderline necessity has ever tried something like Temporary_Storage. I find it to be pretty wild that instead of figuring out better memory management models like this, we collectively decided to punt on the whole issue, declare it an unsolvable problem, and decide that increasingly complex garbage collection systems are the only way forward. with Temporary_Storage in place, you can do whatever small allocations you need at any point in time (parse an integer from a string, etc.), and you don't have to worry about free()ing the result, because it's taken care of for you, without Actually Being Garbage Collection. this entirely solves both "1." and "2." above, without the uncertainty of not knowing when exactly the garbage created by the thing you're free()ing and all of its substructures will be cleaned up. instead, you know exactly when it's going to be cleaned up, once per frame at the end of the frame (or whenever you call reset_temporary_storage()). everything below the line break above sounds crazy to me. why are your linked list nodes all being malloc()d randomly on the heap, instead of in an arena allocator that you can also just flush all at once that's what you want to do? why would you ever traverse a complex nested structure to free it all, when you could just free() the entire hunk of memory at once (or, if you're going to be reusing that chunk of memory, just reset the arena allocator pointer to the beginning)?

dragontamer 5y ago
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?"

dragontamer 5y ago

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?"