The D Garbage Collector
dlang.org
dlang.org
Here is the better explanation of the GC: 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.
> which runs at every allocation.
The article explains in great depth that this is not the case.
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.
What workaround do you have in mind, and how does it not apply to write barriers?
Walter Bright was right about segmented stacks, I'm tempted to think he's right about write barriers too.
However, if you don't know statically what kind of heap a pointer is in, you're going to have a poorly performing GC system no matter what.
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.
> 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.
I'm skeptical, however, if it will offer a real improvement.
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.
This is not how garbage collectors work. At all.
[1] http://blog.ragozin.info/2011/06/understanding-gc-pauses-in-...
Their purpose is to capture some information about the updated pointer that the GC can then use to avoid a full heap scan. Card marking marks a 'region' as dirty (such as 128/256/512 bytes of memory). This buffer recording the dirty/clean areas is rescanned as part of the evacuation of the generation being collected. Any pointers to the generation then being collected are updated.
Sequential store buffers (SSBs) can be used to record the address of the object being updated or a pointer to the pointer itself. Again rescanned during collection. SSBs can be easily thread-local avoiding the need for thread synchronisation, except during a collection cycle which already requires thread synchronisation.
Write barrier tend to be optimised heavily as they're used quite frequently. The use of atomic barriers or branch instructions (barring fast path exits) would inhibit performance.
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.
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.
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!
I agree. That's why you don't usually want extreme low-latency collectors that make your program slow by sacrificing throughput over latency.
> 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.
And that's why you should have a GC that balances throughput and latency.
Of course you know there's a difference between a slow program and a sluggish/unresponsive one. A user will forgive the former, but will abhor the latter. As a programmer, you're a kind of user. However, I note that many programmers have a kind of un-self-awareness when it comes to their own creations and favored, highly customized tools. If a programmer thinks something is nifty for another reason, they will often excuse much more latency than an ordinary user ever would. This is one of the biggest UX blind spots programmers have, generally.
Also, with an environment where it's easy to fix throughput, why not mostly eliminate latency? Fixing throughput is usually more straightforward and easier than fixing latency. (Pareto principle)
And that's why you should have a GC that balances throughput and latency.
In practice, due to programmer hubris and bias against perceiving flaws in our own creations, one has often ended up with GC that has better than needed throughput numbers to alleviate speed criticisms while having latency that is a little bit uncomfortable. I think it's a common programmer blindness with regards to UX.
No, because improving throughput requires a generational GC, which is something you need to design from the beginning. Once you do, it tends to be a massive win.
> In practice, due to programmer hubris and bias against perceiving flaws in our own creations, one has often ended up with GC that has better than needed throughput numbers to alleviate speed criticisms while having latency that is a little bit uncomfortable. I think it's a common programmer blindness with regards to UX.
Or maybe you don't notice any throughput problems because most mature GCs have good throughput, leading to the incorrect conclusion that throughput is unimportant. I highly suspect that if all apps were using extreme low-latency GCs, you would notice throughput problems.
Take JS, for instance: you know how JS-heavy apps are criticized all the time on HN for being slow to load? That's a throughput problem.
Not necessarily true. Often, the throughput issues can be improved by reducing memory pressure. (Though this may not cut it for situations with very high performance requirements.)
requires a generational GC, which is something you need to design from the beginning. Once you do, it tends to be a massive win.
Depending on the environment, you can switch to a higher throughput GC in production.
Or maybe you don't notice any throughput problems because most mature GCs have good throughput, leading to the incorrect conclusion that throughput is unimportant.
Maybe. Most of my experience working in GC environments was in VisualWorks, which had an excellent generational GC in its day. One of the points of pride with the VM was that it was common to see only around 2ms latency for GC pauses. There was quite a bit of work done to eliminate perceptible GC pause. For the initial experience, people would notice the GC pauses first.
In any case the words "extreme low latency GC" are yours, not mine, and I suspect you have a very particular subset in mind when you use that term, which perhaps isn't what I have in mind. Emphasis should be on low latency, to the point where the average programmer doesn't have to think about it very often, until it's time to optimize the program in general.
Take JS, for instance: you know how JS-heavy apps are criticized all the time on HN for being slow to load? That's a throughput problem.
I suspect you have a very good blog post about the details.
> No, because improving throughput requires a generational GC
Or more boxes. From the perspective of an end user or IT admin, if you have a throughput problem, you can (assuming the task lends itself) solve it with horizontal scaling. If you have a latency problem, you can only scale vertically. If scaling vertically doesn't do the trick, you're out of luck.
This is why when I have to make a choice between latency and throughput, if there's no obviously correct answer I default to latency. Intel will eventually solve my throughput problems, but they won't be able to do much about my latency problems.
But low-latency collectors have more pauses than low-throughput collectors, as well as spending more overall time collecting than low-throughput collectors. They also have a tendency towards higher memory pressure in the long run (though it's far less spiky than low-throughput collectors).
But if you never notice any of the pauses because you're very well optimized for latency, then no harm, no foul.
as well as spending more overall time collecting than low-throughput collectors.
But too-low throughput is usually only a problem in production, whereas too-high latency can increase cost (in harder to quantify ways) everywhere, including in development. Too-low throughput is also usually much easier to fix.
If you need high throughput, you need high throughput, but for most programmers, the correct default is low latency. High throughput for most programmers is like 150 mph top speed on a US sports car. In most cases, people are never going to need it, but if you need it (like, if you actually go to a track) it's relatively straightforward to implement. Whereas having unresponsive programs is like having an unreliable car that has squeaky brakes -- you're going to notice that relatively quickly, it's going to be a constant bother, and it's not so straightforward to correct.
This stuff was all heavily studied in the 90s and earlier, you know. The conclusions that researchers and engineers came to are equally valid today.
D is not popular enough so far, so there will not be much research invested into its GC. When Java gets value types, it might become interesting.
Outside this sub-field, another one that offers evidence of your opinion is static analysis vs dynamic checks. Full, memory safety for C programs originally required crazy overhead (300+% sometimes) with checks on all the things that could happen. Then, people started mixing static analysis with dynamic checks and clever architectures to reduce that overhead. They'd often use static analysis to determine when they could eliminate checks. I can see something similar happening with GC's where an analysis helps avoid bad operations. We already have a taste of it with Rust where we get some safety without GC.
For some reason people keep wanting to deny the generational hypothesis, in the hopes of not having to implement a generational GC. Frankly, this is wishful thinking. The generational hypothesis has been borne out again and again and again, in all kinds of different scenarios.
Which model is better ? I don't know but all the car I know are the second kind. What about GCs ? I don't know, but the majority of modern GC are the second kind …
If you had a bus like this, combined with autonomous self-driving, it might revolutionize travel in the US!
Of course you usually don't need that much speed and you'll end up having a lot of pauses on your SF to NYC trip, but you'll get there a lot quicker because you'll be able to drive at 70 mph all the time.
And when you arrive, all of the driving and stopping will leave you fatigued. The steady-state travel enabled by the robot nuclear super-bus would let people travel in sleeper compartments!
Which model is better ?
Clearly the 2nd!
I don't know but all the car I know are the second kind. What about GCs ? I don't know, but the majority of modern GC are the second kind …
You seem to be leaning rather heavily on the adjective "modern." Because if you use the colloquial definition of the term, there are a number of currently maintained and used GC that aren't the 2nd kind.
For the majority of applications, those GCs are inferior to generational GCs that balance throughput and latency.
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."
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.
One thing D and Nim are lacking is adoption by a large company, and I feel that's partly what's keeping them behind Go and Rust.
Learning D for real is as involved as any other language, but what people remark first is the low mental overhead and how absurdly practical it is.
Advantages I see would be: fast to edit, compile, and run. Non-controversial syntax, focus on power, and the fact you kind of already know it.
I mostly work with gdc from GNU/Linux, and basically, everything that works with g++ works with gdc. More precisely, I use, on a daily basis: - vim + ctags (editor + symbol lookup) - gdb (debugger) - gcov (code coverage) - valgrind (mostly callgrind (call-graph) and massif (memory profiler)) - oprofile (cpu profiler)
Unfortunately there's no ccache equivalent yet, and I'm missing it.
For the Windows people, there's VisualD, which basically is the integration in Visual Studio. At this point, you have an IDE and a debugger (I don't know about code completion).
There's also a build-tool (with package-managing abilities), called "dub" ; that handles fetching and building external dependencies (in the vein of npm).
Someone should do a Language Server Protocol (http://langserver.org/) implementation for D - that's clearly the way forward. Right now this will give you VSCode, Eclipse and NeoVim, with regular Vim and Emacs on the way.
VSCode also has something similar for debugging (https://code.visualstudio.com/docs/extensionAPI/api-debuggin...), but it hasn't been standardized in a similar fashion (yet?).
If you're going to use it, I highly recommend the D Programming Language (book). It's extremely well written, and remains once of my favourite technical books.
Nearly once per year, a blocking bug sneaks into the compiler and needs to be worked-around (crashes on invalid code are easy to avoid ; sometimes, it's a little more tricky, but we've never been blocked for more than 1 day). The maintainers are very active, though, and it's generally quickly fixed, provided that I report the bug myself. There's also been some friction when it came to cross-compilation (definitely doable, but not as easy at "apt install mingw-gcc").
In the team, the adoption went well ; coming from C++, switching to D feels natural. The syntax is more concise and consistent than C++14 syntax. The standard library handles so much stuff (md5, sending emails, command line parsing, filesystem, process creation) that most of our projects don't depend on any other external library (nor do they depend on any OS-specific stuff). The fact that all variables are initialized by default makes it hard to have non-deterministic behaviour ; and the fact that the "buffer" abstraction (aka "Span"/"Slice"/"string_view"/"ptr+len") is in the language makes it really easy to write code which is concise and secure.
C++ has been slowly catching up since 2011, however, why wait?
Is the idea that you can explicitly control the behavior of GC by tuning your allocations? Is it burdensome for the programmer to constantly think about this while writing code?
That way you don't need a dedicated thread for the GC (current one is hijecked).
> Is it burdensome for the programmer to constantly think about this while writing code?
Not really. I sell real-time software in D, you don't constantly think about this when writing code. It's no more burden that avoiding allocations in real-time software in C++.
The kids today are so indoctrinated in modern C++ that they don't stop to think that `vector<>::push_back()` potentially allocates behind the scenes.
Writing real-time code requires a certain mentality that is at odds with modern frameworks. I expect nice languages like D have similar cultural issues.
D is backed by companies like Sociomantic and Weka.io that operates in high-performance domains.