7 ms·

Introduction to Memory Management (2018)

134 points by lrsjng 8y ago

pizlonator 8y ago
I get that it’s well intentioned but I wish folks stopped talking about the buddy allocator. It’s so obsolete. It’s not the fastest and it sure has some of the worst fragmentation due to very imprecise sizing.
- wuxb 8y ago
  I wish my professors talked more about their opinions on these textbook techniques, especially like you said that some are not that great so it belongs to a history lesson rather than something that you should get your hands on.
- twtw 8y ago
  Can something be obsolete if it is still extremely widely used? IIRC, Linux and FreeBSD both use a buddy allocator for physical memory, and I'm pretty sure it is used (in addition to other allocators) in jemalloc as well.
  - pcwalton 8y ago
    I don't think jemalloc uses any buddy allocators. It's a segregated free list allocator, like most C mallocs and tenured generation allocators.
- pcwalton 8y ago
  I agree that buddy allocators are bad, though they're charmingly simple. In any case, the glossary is up front about their disadvantages: https://www.memorymanagement.org/glossary/b.html#term-buddy-system https://www.memorymanagement.org/glossary/b.html#term-buddy-...
dataking 8y ago
Expected to see Rust's approach mentioned since it occupies an interesting point in the design space, i.e., automatic memory management where lifetimes are (mostly) determined at compile-time vs. at run-time (RC and/or GC).
mattnewport 8y ago
From what I've skimmed so far this isn't a very good or accurate resource. In particular it doesn't mention RAII in its discussion of C++, doesn't mention Rust at all, neglects the role of stack allocation, glosses over the common use of object pooling in GC languages as a workaround for performance issues, has little on the extra issues introduced by multithreaded code and understates the performance issues of GC.
- lrsjng 8y ago
  do you know some good resources on the things you mentioned?
  - mattnewport 8y ago
    I don't know of one central resource that covers all of these topics. There are good articles on jemalloc and tcmalloc that discuss modern allocation strategies for general purpose allocators. There are articles from games development that discuss object pooling both in the context of C++ and in the context of optimizing GC languages like C# and Java as well as other specialized strategies like bump allocators, frame allocators, etc. Resources on learning modern C++ cover RAII and resources on learning Rust cover its approach. There are good talks on the fairly new polymorphic allocator model for C++ that cover the motivations for it and use cases. Experience with modern C++ is valuable for understanding how much you can do with mostly stack allocation and how you can write non library code without ever writing a raw new or delete.
- pcwalton 8y ago
  It's actually a great resource. The glossary covers all these issues, except for Rust, which the site content predates. It tends to use more academic terminology instead of the current industry terminology, but the academic terminology is often more precise anyway. Yes, it's opinionated in favor of GC, but that's a perfectly defensible position (which may sound odd coming from me as a Rust developer, but I actually like GC in many—just not all—circumstances). RAII is covered under "smart pointer": https://www.memorymanagement.org/glossary/s.html#term-smart-pointer https://www.memorymanagement.org/glossary/s.html#term-smart-... Stack allocation is here: https://www.memorymanagement.org/glossary/s.html#term-stack-allocation https://www.memorymanagement.org/glossary/s.html#term-stack-... Object pooling is covered under "segregated free list": https://www.memorymanagement.org/glossary/s.html#term-segregated-free-list https://www.memorymanagement.org/glossary/s.html#term-segreg... Multithreaded GC is covered under "parallel garbage collection": https://www.memorymanagement.org/glossary/p.html#term-parallel-garbage-collection https://www.memorymanagement.org/glossary/p.html#term-parall...
keldaris 8y ago
Even though many of the technical points are highly debatable, my biggest issue is with the sentence "the programmer is freed to work on the actual problem" listed among the "advantages" of automatic memory management, and with how ubiquitous that mindset has become. Insofar as computer programming is concerned, the "actual problem" is always the transformation of specific data on a specific set of computing hardware. Automating memory management doesn't imply working on the actual problem, it's just outsourcing a part of the actual problem in the pursuit of other objectives - decreasing development time, reducing the likelihood of specific bugs, etc. I'm not arguing that people shouldn't use automatic memory management, it often makes perfectly good technical and business sense to do so - but pretending that memory management is not a crucial part of solving any real problem in computer programming (even if you're not doing it explicitly) does no good to anyone.
- marvy 8y ago
  I think maybe your definition of "actual problem" is not the same as their definition. Let me try to defend their definition with an analogy. If I write in C, I don't have to worry about register allocation (which variable goes in which register, when should I spill to the stack, etc.). I can just write things like (a+b+c)/3 and it "just works". Perhaps the compiler will do a bad job with allocating the registers, and a good assembly programmer would have done far better, even to the extent that the program goes from "way too slow" to "plenty fast". (Unlikely these days, but in the past knowing when to use the "register" keyword was worth knowing.) But even then register allocation is incidental complexity, in that they are an artifact of the solution, not of the problem itself. But even though C programmers don't have to worry which registers are callee-save vs caller-save every time they call of function, they do have to worry about who is supposed to free every allocated data structure. Java programmers don't; they can just write ("1+2="+3).getBytes() and it "just works". The garbage collector may be so inefficient that you wish it weren't there, but even then, deciding exactly when to deallocate every temporary string is incidental complexity, in that they are an artifact of the solution, not of the problem itself. Of course, just because the problem is incidental doesn't mean it need not be solved! You really do need to free those strings or else you'll run out of memory and crash. (but not too soon, or else you have a use-after-free problem.) And likewise, at the end of the day, the values better end up in the right registers. But whether you're writing a game or web app or an FPGA simulator, memory management is not the "actual problem" you care about solving. The proof is that you don't think about when you're writing the user guide to your software.
pcwalton 8y ago
I don't think this is from 2018; the contents are mostly unchanged since 2014 [1]. Even though it's a bit dated, memorymanagement.org is one of my favorite resources. It's opinionated, in a good way. The techniques that were developed in the 2000s, which this site thoroughly covers, are still the state of the art for garbage collection in my opinion. [1]: http://web.archive.org/web/20140616011030/https://www.memorymanagement.org/mmref/index.html http://web.archive.org/web/20140616011030/https://www.memory...
anitil 8y ago
When reading the language section [0] I was surprised to see that COBOL had no heap allocation until 2002. Searching around, the only comments I could find amounted to "We just didn't need it.". Can anyone fill me in? [0]: https://www.memorymanagement.org/mmref/lang.html https://www.memorymanagement.org/mmref/lang.html
- vajrabum 8y ago
  Historically, there weren't recursive procedures in Cobol and no concept of new(). Instead all the data was statically initialized at application start. The compiler did the storage allocation.
- adrianratnapala 8y ago
  What needs filling in? It didn't have a heap. It's not like you really need one.

134 points by lrsjng 8y ago

I get that it’s well intentioned but I wish folks stopped talking about the buddy allocator. It’s so obsolete. It’s not the fastest and it sure has some of the worst fragmentation due to very imprecise sizing.

wuxb 8y ago
I wish my professors talked more about their opinions on these textbook techniques, especially like you said that some are not that great so it belongs to a history lesson rather than something that you should get your hands on.
twtw 8y ago
Can something be obsolete if it is still extremely widely used? IIRC, Linux and FreeBSD both use a buddy allocator for physical memory, and I'm pretty sure it is used (in addition to other allocators) in jemalloc as well.
- pcwalton 8y ago
  I don't think jemalloc uses any buddy allocators. It's a segregated free list allocator, like most C mallocs and tenured generation allocators.
pcwalton 8y ago
I agree that buddy allocators are bad, though they're charmingly simple. In any case, the glossary is up front about their disadvantages: https://www.memorymanagement.org/glossary/b.html#term-buddy-system https://www.memorymanagement.org/glossary/b.html#term-buddy-...

dataking 8y ago

Expected to see Rust's approach mentioned since it occupies an interesting point in the design space, i.e., automatic memory management where lifetimes are (mostly) determined at compile-time vs. at run-time (RC and/or GC).

mattnewport 8y ago

From what I've skimmed so far this isn't a very good or accurate resource. In particular it doesn't mention RAII in its discussion of C++, doesn't mention Rust at all, neglects the role of stack allocation, glosses over the common use of object pooling in GC languages as a workaround for performance issues, has little on the extra issues introduced by multithreaded code and understates the performance issues of GC.

lrsjng 8y ago
do you know some good resources on the things you mentioned?
- mattnewport 8y ago
  I don't know of one central resource that covers all of these topics. There are good articles on jemalloc and tcmalloc that discuss modern allocation strategies for general purpose allocators. There are articles from games development that discuss object pooling both in the context of C++ and in the context of optimizing GC languages like C# and Java as well as other specialized strategies like bump allocators, frame allocators, etc. Resources on learning modern C++ cover RAII and resources on learning Rust cover its approach. There are good talks on the fairly new polymorphic allocator model for C++ that cover the motivations for it and use cases. Experience with modern C++ is valuable for understanding how much you can do with mostly stack allocation and how you can write non library code without ever writing a raw new or delete.
pcwalton 8y ago
It's actually a great resource. The glossary covers all these issues, except for Rust, which the site content predates. It tends to use more academic terminology instead of the current industry terminology, but the academic terminology is often more precise anyway. Yes, it's opinionated in favor of GC, but that's a perfectly defensible position (which may sound odd coming from me as a Rust developer, but I actually like GC in many—just not all—circumstances). RAII is covered under "smart pointer": https://www.memorymanagement.org/glossary/s.html#term-smart-pointer https://www.memorymanagement.org/glossary/s.html#term-smart-... Stack allocation is here: https://www.memorymanagement.org/glossary/s.html#term-stack-allocation https://www.memorymanagement.org/glossary/s.html#term-stack-... Object pooling is covered under "segregated free list": https://www.memorymanagement.org/glossary/s.html#term-segregated-free-list https://www.memorymanagement.org/glossary/s.html#term-segreg... Multithreaded GC is covered under "parallel garbage collection": https://www.memorymanagement.org/glossary/p.html#term-parallel-garbage-collection https://www.memorymanagement.org/glossary/p.html#term-parall...

keldaris 8y ago

Even though many of the technical points are highly debatable, my biggest issue is with the sentence "the programmer is freed to work on the actual problem" listed among the "advantages" of automatic memory management, and with how ubiquitous that mindset has become. Insofar as computer programming is concerned, the "actual problem" is always the transformation of specific data on a specific set of computing hardware. Automating memory management doesn't imply working on the actual problem, it's just outsourcing a part of the actual problem in the pursuit of other objectives - decreasing development time, reducing the likelihood of specific bugs, etc. I'm not arguing that people shouldn't use automatic memory management, it often makes perfectly good technical and business sense to do so - but pretending that memory management is not a crucial part of solving any real problem in computer programming (even if you're not doing it explicitly) does no good to anyone.

marvy 8y ago
I think maybe your definition of "actual problem" is not the same as their definition. Let me try to defend their definition with an analogy. If I write in C, I don't have to worry about register allocation (which variable goes in which register, when should I spill to the stack, etc.). I can just write things like (a+b+c)/3 and it "just works". Perhaps the compiler will do a bad job with allocating the registers, and a good assembly programmer would have done far better, even to the extent that the program goes from "way too slow" to "plenty fast". (Unlikely these days, but in the past knowing when to use the "register" keyword was worth knowing.) But even then register allocation is incidental complexity, in that they are an artifact of the solution, not of the problem itself. But even though C programmers don't have to worry which registers are callee-save vs caller-save every time they call of function, they do have to worry about who is supposed to free every allocated data structure. Java programmers don't; they can just write ("1+2="+3).getBytes() and it "just works". The garbage collector may be so inefficient that you wish it weren't there, but even then, deciding exactly when to deallocate every temporary string is incidental complexity, in that they are an artifact of the solution, not of the problem itself. Of course, just because the problem is incidental doesn't mean it need not be solved! You really do need to free those strings or else you'll run out of memory and crash. (but not too soon, or else you have a use-after-free problem.) And likewise, at the end of the day, the values better end up in the right registers. But whether you're writing a game or web app or an FPGA simulator, memory management is not the "actual problem" you care about solving. The proof is that you don't think about when you're writing the user guide to your software.

pcwalton 8y ago

I don't think this is from 2018; the contents are mostly unchanged since 2014 [1]. Even though it's a bit dated, memorymanagement.org is one of my favorite resources. It's opinionated, in a good way. The techniques that were developed in the 2000s, which this site thoroughly covers, are still the state of the art for garbage collection in my opinion. [1]: http://web.archive.org/web/20140616011030/https://www.memorymanagement.org/mmref/index.html http://web.archive.org/web/20140616011030/https://www.memory...

anitil 8y ago

When reading the language section [0] I was surprised to see that COBOL had no heap allocation until 2002. Searching around, the only comments I could find amounted to "We just didn't need it.". Can anyone fill me in? [0]: https://www.memorymanagement.org/mmref/lang.html https://www.memorymanagement.org/mmref/lang.html

vajrabum 8y ago
Historically, there weren't recursive procedures in Cobol and no concept of new(). Instead all the data was statically initialized at application start. The compiler did the storage allocation.
adrianratnapala 8y ago
What needs filling in? It didn't have a heap. It's not like you really need one.