6 ms·
This is not really an article about "How the D garbage collector works", rather an article "How to avoid garbage in D". More tips and tricks are at: https://bit
by rurban 10y ago
This is not really an article about "How the D garbage collector works", rather an article "How to avoid garbage in D". More tips and tricks are at: https://bitbucket.org/infognition/dstuff https://bitbucket.org/infognition/dstuff
Here is the better explanation of the GC: https://dlang.org/spec/garbage.html https://dlang.org/spec/garbage.html, which is basically a very slow and conservative stop the world Mark & Sweep, which runs at every allocation. Basically a simple version of BoehmGC.
Due to the unfortunate C ABI, a fast copying collector is not really doable. One cannot track all the internal and external pointers. Well, one could, but has to pessimize the locals on every external pointer reference.
- p0nce 10y agoA fast copying collector for D would require write barriers: using memory barriers everytime a pointer is written. This has a runtime cost. > which runs at every allocation. The article explains in great depth that this is not the case.
- dbaupp 10y ago> This has a runtime cost. As does using a conservative/"very slow" GC. I'm sceptical, but it may be that D's situation means trading a pervasive slowness (if the parent is true, I don't know) for no write barriers is the right choice, differing to the conventional wisdom from other languages, but that's the argument you need to make, not just that write barriers are slow.
- atilaneves 10y agoThe slow GC is only a runtime cost if it ever runs. If no garbage is created in inner loops and stack allocation is preferred there's no reason it _has_ to run.
- p0nce 10y agoThe case against write barriers is pretty simple: the slowness of the GC can be workarounded, while memory barriers cannot. If they are needed, no other way to copy pointer values (which are quite pervasive in system programming).
- pcwalton 10y ago> The case against write barriers is pretty simple: the slowness of the GC can be workarounded, while memory barriers cannot. What workaround do you have in mind, and how does it not apply to write barriers?
- p0nce 10y agoYou can always use less of the GC, but there are no way not to use pointers. For example, I sell products in D which disable the GC completely, I certainly don't want write barriers.
- pcwalton 10y agoIf you can safely disable the GC, then you can safely disable write barriers.
- p0nce 10y agoAnd if I use only a bit of the GC, can I use only a bit of write barriers? Walter Bright was right about segmented stacks, I'm tempted to think he's right about write barriers too.
- pcwalton 10y agoIf the compiler can statically tell which pointers point to GC memory (something it usually needs to know anyway), yes.
- p0nce 10y agoIn D this is indeed known only at runtime, one of the decision was that "there should be only one type of pointers". immutable(T) doesn't guarantee it isn't in the GC heap from what I can gather. shared(T) could perhaps do it, but it's rather unpopular.
- pcwalton 10y ago> A fast copying collector would require write barriers: using atomics everytime a pointer is written. No, for two reasons: 1. Write barriers are not necessary if an object is in a nursery, which is true for most objects per the generational hypothesis. This is trivial to check based on the pointer value. 2. You can have thread local remembered sets.
- p0nce 10y agoI read this in http://www.infognition.com/blog/2014/the_real_problem_with_gc_in_d.html http://www.infognition.com/blog/2014/the_real_problem_with_g... better ask the author of the article if you have a way for a better D GC. > To make fast GC it needs to be generational, but generational GC means write barriers: you can't just freely mutate memory, every pointer mutation must be accompanied by additional bookkeeping. I guess that in the context of D generations are not possible or practical. If you have any idea why it should be possible, you may write a DIP.
- WalterBright 10y agoIt's possible to do generational collection in D. I've written one before and was careful to design the semantics of D to allow for it. It just needs someone to spend the time to implement it (the core language doesn't need to change). I'm skeptical, however, if it will offer a real improvement.
- rurban 10y agoAnd 3rd: use forwarding pointers. Every good implementation uses #3.
- rurban 10y agoAnd 3rd: use forwarding pointers. Every good implementation uses #3.
- valarauca1 10y ago>Write barriers are not necessary if an object is in a nursery, which is true for most objects per the generational hypothesis. This is trivial to check based on the pointer value. Yes but what when it leaves it? You have to update all pointers to another location. When it passes to the Gen2 slab all references that point to it need to be updated, and those changes need to propagate to all threads, and all cores. The simplest way to do this is a memory barrier. Well the real simplest way is just "never multi-thread" and this is OCaml's GC is so fast. No write barriers, 1 thread only, final destination.
- rbehrends 10y ago> A fast copying collector would require write barriers: using atomics everytime a pointer is written. This is not how garbage collectors work. At all.
- p0nce 10y agoLet me amend then: "A fast copying collector _in D_ would require write barriers". Of course with other languages you can have GC without that limitation.
- rbehrends 10y agoNo, unless there's some subtle semantic detail about D that I am missing. This is just not how GCs work. Write barriers, yes. Write barriers that require atomic instructions every time a pointer is written, no.
- p0nce 10y agoI meant "memory barriers". Atomics embed memory barriers.
- rbehrends 10y agoIt sounds like you're confusing two types of "write barriers" that happen to share the same name, but have otherwise little in common. Memory barriers for atomic instructions are essential for giving them sane semantics, but have nothing to do with GC. GC write barriers deal with the needs of generational or incremental collections, but are a totally different thing.
- p0nce 10y agoYes I thought GC write barriers were always implemented with memory barrier instructions. Probably a trap because the same word is used. Still I wonder how they are implemented then.
- stcredzero 10y agoThis is not really an article about "How the D garbage collector works", rather an article "How to avoid garbage in D". I think the latter is of greater interest to the general programmer, however. Initial hubris seems to be the rule for new tools in programming, and in retrospect, this seems to have been true for GC technology. The original motivation was to offload the most painful part of memory management work from the coder, but it somehow morphed into, "Takes care of everything to do with memory management." This resulted in a misguided quest for a "magical" GC that had super throughput, or super low latency. (Or somehow both.) This in turn resulted in numerous GC knobs that were hard to understand and tune. A recent trend seems to take the approach that GC allows development to get to a correctly running program faster, at which point, good profiling and language/library tools can be used to minimize memory churn. To this end, GC should be optimized by default for latency -- as this is the most likely optimization for a better development environment.
- pcwalton 10y ago> The original motivation was to offload the most painful part of memory management work from the coder, but it somehow morphed into, "Takes care of everything to do with memory management." I don't understand the difference. GC was invented for Lisp. Lisp was fully automatically memory managed, just as GC'd languages are today. John McCarthy never conceived of Lisp as a language with malloc and free. > To this end, GC should be optimized by default for latency -- as this is the most likely optimization for a better development environment. I don't see how that follows. Throughput is just as important as latency in most scenarios, development included. There's nothing about development that makes latency more desirable than throughput—if anything, I would think the opposite would be true, as running batch testing jobs usually demands good throughput.
- stcredzero 10y agoThroughput is just as important as latency in most scenarios, development included. There's nothing about development that makes latency more desirable than throughput Having sluggish, unresponsive, wonky tools, and a sluggish, unresponsive, wonky prototype just sucks. All of those little uncomfortable pauses wear you down and nickel-and-dime you to death. I would think the opposite would be true, as running batch testing jobs usually demands good throughput. Running batch testing is exactly the kind of scenario where profiling and optimization can score big wins -- and most often, those wins also apply to the production version. IMO, making your development environment uncomfortable for edit/test/debug just so you can have faster batch testing is a misguided reversal of priorities! Not having the latter provides you with less timely information, but is easily fixed. Not having the former is constantly fatiguing!
- bachmeier 10y ago> a very slow and conservative stop the world Mark & Sweep, which runs at every allocation It doesn't run on every allocation. It can only run during an allocation, but that doesn't mean it will, and it's hard to think of a standard use case in which it would run on every allocation. FTA: "The first thing to understand about D’s garbage collector is that it only runs during allocation, and only if there is no memory available to allocate."
- dang 10y agoOk, we changed the title to use your suggestion. If people object, we can change it again. (But please suggest a better—i.e. more accurate and neutral—title if you do.)
- rbehrends 10y ago> Due to the unfortunate C ABI, a fast copying collector is not really doable. One cannot track all the internal and external pointers. Well, one could, but has to pessimize the locals on every external pointer reference. Note that a GC does not have to be copying in order to be fast. What makes or breaks performance for most GCs is whether they are generational [1]. A non-generational copying GC will generally not have impressive performance, either. A copying GC allows you to have a bump allocator, but a non-copying generational GC can still have a pool allocator. Using a pool allocator does not share all of the benefits of a bump allocator (such as good memory locality for successive allocations), but still allows for very fast allocations for small objects. Also, mostly copying GCs are still an option even if you scan roots conservatively. See Joel Bartlett's mostly copying GC from the late 1980s. [1] Not counting non-tracing approaches, such as deferred reference counting, which achieve similar goals through other means.
- robochat42 10y agoI thought that they were going to replace the garbage collector in D but I haven't heard anything about it recently. Does anybody know whether that is going to happen?