3 ms·
I've spent some time really studying memory allocation. It seems to me that almost any high-performance application will take advantage of the fine-details of m
by dragontamer 6y ago
I've spent some time really studying memory allocation. It seems to me that almost any high-performance application will take advantage of the fine-details of memory allocators to optimize themselves.
There's something to be said about garbage collection as an actual strategy (!!). I know people think that garbage collection is slow, but... very smart people have put their minds on the memory problem.
A generational garbage collector is designed to tackle fragmentation head-on. Every "generation", the garbage collector recompacts all the data, "squeezing" your fragmentation out of the memory area.
Because some data is "longer lived" than other data, the compacted data is placed into a new generational-pool, where it is left alone for the next collection. IE: All data that survived a collection at time T will be left alone at collect time T+1. Maybe at time T+2 will it be re-checked... and those that survive the check at T+2 will be left alone until T+6.
--------------
This generational strategy minimizes the copying / moving of data around the fragmentation issue. Still though: moving / copying data is the singular catch-all solution to fragmentation.
- jerf 6y agoThis sort of thing is why I'm generally not impressed by the perennial "GC vs. manual memory management" debate. Manual memory management usually isn't. Simply using "malloc" isn't manual memory management, there's still a lot of stuff going on behind the scenes that may or may not match your program's use case. Both GC and "manual" memory management aren't single points, they're suites of options, which you can often mix and match beyond that. Statements like "Manual memory management is better than GC" is roughly like saying "Pie tastes better than cake!"... it doesn't even really make sense, there's so many pies and so many cakes that there's no way to universally order them like that, even for a specific person; add in the subjectivity of taste (in this metaphor, the different needs various programs have of memory in the first place) and it's beyond absurd. (To my mind, "manual memory management" is when you get a big slab of memory from something, doesn't much matter what, and everything else is managed in your application code. If you're not doing that, you've got some sort of "automation" involved, and that automation can mismatch your program's memory needs every bit as much as a "GC" can.)
- dragontamer 6y ago> "Pie tastes better than cake!" Indeed. And is Cheesecake a pie or a cake? You bake cheesecake in pie-crust, but it has cake in the name. The memory-management "its both" scheme is reference-counting. In some contexts, its ref-counts are considered manual (C++ shared_ptr, Rust). In other contexts, its considered automated garbage collection (Python, Lisp). In all cases: tons of atomic add/subtract + memory-barriers to strictly order reference counts between many threads... making it actually kind of bad for multithreaded code compared to other garbage collection schemes. (Each shared_ptr<> = blah() requires an atomic add and atomic-subtract. So you actually have escalating costs the more you use the shared_ptr). I think the circular-issue is kind of overblown: it certainly happens (doubly-linked lists, graphs, trees which store a "root pointer" or even an "iterator" somewhere inside of them) but people know how to use weak_ptr<> these days and avoid most issues. (Well... except for arbitrary graphs. No way to know where to put weak_ptr<> there. But most "graph heavy" algorithms use other representations: dense matrix or sparse matrix forms... and probably should avoid slow / low-performance general purpose memory allocators anyway) ----------- Once you recognize the multithreaded-sync issues associated with shared_ptr<> / RefCount, you start building a thread that "centralizes" the ref-counts in a reader/writer queue to ensure that objects are deleted at the right time. Oh wait, that's called a garbage collector thread and you've suddenly moved to mark&sweep accidentally. Once you get a garbage collector thread, its not too big of a leap to start thinking about multiple garbage-collector threads (scaling to higher garbage collection performance). I mean, yeah, I'm glossing over all sorts of high-performance multithreaded lock-free datastructures here, but lets pretend those implementation details are solved. Lol. ----------- As usual: its not really the garbage collection or memory-management parts that are hard. Its the multithreaded high-performance (and provably correct!) portion that's really, really hard. Even for simple ideas like ref-counts or even "manual" malloc/free.
- tssva 6y ago"And is Cheesecake a pie or a cake? You bake cheesecake in pie-crust, but it has cake in the name." I tried to follow the rest of your comment but I was too disturbed by you thinking all cheesecake is baked in pie-crust.
- vmchale 6y agoI read such a statement from Andras Kovacs re: compilers https://www.reddit.com/r/haskell/comments/gok70o/simple_haskell_is_best_haskell/frj9hty/ https://www.reddit.com/r/haskell/comments/gok70o/simple_hask... One needs different allocation strategies for immutable (and strict/lazy) languages.
- AtlasBarfed 6y agoRust is probably close to a good idea: have the programmer give directions as to the lifetime/behavior of the data and allocated memory, rather than having to guess. Compilers might be able to do some of that, but at least the standard libraries should be able to do the hints, and almost all dynamic allocations on day-to-day code uses dynamic structures in standard libraries like hashmaps and variable-length lists/vectors/arrays.