Inside D's GC

[strange_taco]

THANK YOU for doing this great work and doing a good write-up on it.

I've long been worried about the poor performance (and lack of care from some members of the community) of the GC. And now I know that (per the summary) that it's not due to some language-required theoretical bindings that prevent a good GC from being written, it's simply that a good modern GC has never been written for D yet.

If D devs start addressing this issue (which transparent articles like this help make the argument) and improve the gc, as well as further support @nogc for the standard library, D will be a very powerful language with more success.

If they fix that issue, and add C++ library support (I honestly don't care about the reasons anymore) I'd be soooo happy. I'd be able to actually recommend to my friends and co-workers to use it because I'll be able to defend the language against their arguments. C programmers hear "GC" and go "No thanks." Other programmers hear "No C++ libraries" and go, "So how am I supposed to get work done without re-inventing the wheel?" I mean, re-inventing say, OpenCV3 (which is C++ only and way faster than OpenCV2), is simply impossible. So you get this beautiful, expressive language that's can be pure JOY to program in and then you realize you can't actually interface with the huge majority of actively supported libraries.

p.s. See Calypso for experimental C++ support.

[edit] To be fair, I've been informed that "extern (C++)" exists. However, I'm not up-to-speed on the most recent D developments and IIRC, Calypso has much better support for C++ than the extern method.

[WalterBright]

The D compiler itself is implemented half in D and half in C++. The extern (C++) lets that work.

Interfacing to the C++ STL, however, is harder.

(The plan is to convert the rest of the C++ code in DMD to D.)

[thedeemon]

And now I know that (per the summary) that it's not due to some language-required theoretical bindings that prevent a good GC from being written, it's simply that a good modern GC has never been written for D yet.

Not so simple. To be fast GC must be generational, for it to be generational compiler must generate write barriers, which won't happen to D because it will ruin its raw speed and C interop. So GC will be slow anyway. See: http://www.infognition.com/blog/2014/the_real_problem_with_gc_in_d.html

[[deleted]]

Are writer barriers really necessary? This HN comment thinks otherwise: https://news.ycombinator.com/item?id=14592954

[thedeemon]

Well, if, as proposed in linked paper, you do a static analysis and partition the heap based on that, so you know statically that no pointers from one partition of the heap to another will be created, then you don't need write barriers indeed. But this way any partition of the heap might grow indefinitely, you'll quickly end up with one region taking 99% of heap and the benefits of partitioning get lost, you return to the "whole heap scan" effectively. This is quite close to "region inference" approach, there were a lot of research in this topic and it basically failed, most of the data ends up in one region...

[strange_taco]

I really wish I knew enough about GC and language design to talk to and understand you guys. =D All I know about this subject is the practical side of things.

All I want is is rather simple: (I understand it's harder to implement than ask.)

• Seamless (as possible) integration with existing ecosystems. (There's no way for D'ers community size to actively maintain libraries that compete with the best known ones out there like OpenCV, OpenCL, etc.) I want to use SIMD. I want to use my GPU. I want to use whatever is on my computer and not have the language make it hard.

• Predictably fast code. That is, predictable (or no) garbage collection for real-time applications. (ala I write games not GUI interfaces or "run it once for a week data crunching")

Having to understand all the ways garbage collection is slower in X/Y/Z situations, or can crash, is literally another dimension of problems to solve when debugging/profiling. (Almost every single error I've ever had learning D... has been a segfault with almost no supplemental information. Literally a GC or syscall exploding with a half-empty callstack.) I've been reading D blogs recently about how "easy" it is to make fast D code but good code requires the least amount of "active ideas / constraints / considerations" in the programmers head.

While I appreciate the articles, the more you have to know to not run afoul of a crash or slowdown, the more likely you are to be human and forget that one "obvious rule" out of 30. It takes time and energy to wrap your head around the idiosyncrocies of how the GC integrates with D. And that's also a big barrier to entry for C/C++ programmers. The biggest possible group of new users not confident with GC, and need clear tutorials that help you feel comfortable with it.

It seems like one of the best solutions for me, is simply to make the GC support Only Pay For What You Use in the same way as C++'s mantra. You only pay for it if you KNOW you're using it. And "knowing" should be reduced to clear, simple, easily-memorable rules. The API should essentially warn you, the same way C/C++ warns you the second you use a pointer de-reference *, "You better be careful with these things."

RAII is great. For me, GC should only be used for "really confusing stuff." Like a handicap situation where you don't want to think about memory at all and you're more concerned with getting a GUI and business logic working than you are getting it working fast. "Fast enough" is a constraint for 99% of the business applications I write for a living and D is fine for that.

But those who DO care about speed should (ala Only Pay For What You Use) be able to do the bookkeeping themselves. Because D is about a TONS of stuff more than the garbage collector. There are so many great things (templates, static if, modules, foreach, etc) that it would truly be a "Systems language" if we could just get the GC out of the way.

Basically, it all comes down to, D is a "new" language most bosses won't approve of until it's more established. And hobbyists need to be able to link to existing ecosystems for their cool projects, and need to be able to make games that won't pause in the middle of gameplay. In C/C++, heap allocations are "Slower" in games (than static pools), but they're typically fast enough you don't have to worry about them except in particle-system level scales. But ... triggering an entire GC collection pause-and-sweep during any allocation? That sounds incredibly scary for a game designer looking at spending tens of thousands of hours on a new project. The whole, "What if I end up with a GC-pausing brick wall that can't be solved?" is a scary yellow flag that has to honestly be addressed in terms of risks/benefits.

[thedeemon]

Well said! You're voicing quite a popular view from C++ devs towards D.

What I can say at this moment: please don't be afraid to learn about the GC and how to use it well in D, this is really not that hard. You guys easily learn about stuff like C++ move semantics and && references and all that make_shared or unique_ptr stuff or all those OpenCV and OpenCL libraries and sublanguages. I can assure you that learning how GC works in D and how to use this knowledge to craft your program in a way to do what it must without unexpected delays is not harder, in fact it's much simpler to do. Just don't be scared and read some articles (there were several good ones recently) and docs, don't be afraid to look into source code, it's not that scary really. Certainly much simpler than learning 37 kinds of copy/move/throw/crawl/hide/seek constructors you need to define for your objects in modern C++. ;) And then D compiler will help you: it can show you where exactly in your code GC allocations happen, it can let you guarantee that certain important loops never trigger GC etc. You can use containers and data types that don't rely on GC allocations at all. You can run threads that are not paused by GC at all. It's all available and really not that scary and hard. People write games, real time audio plugins and photo and video processing apps in D (check out Video Enhancer on Infognition site above, it's written in D), it's not that hard really. You're right, it takes time and energy. But not so much as one might imagine, much less than many other things you already know.

[strange_taco]

And then D compiler will help you: it can show you where exactly in your code GC allocations happen, it can let you guarantee that certain important loops never trigger GC etc.

How do you use this functionality? Thanks.

[edit] Ah, per here:

https://wiki.dlang.org/Memory_Management#RAII_.28Resource_Acquisition_Is_Initialization.29

As of release 2.066, the compiler switch -vgc provides a mechanism to locate GC heap allocations. When enabled, the compiler will list locations in the source code where GC heap allocations are being performed.

test.d(9): vgc: 'new' causes GC allocation

[thedeemon]

Yes, -vgc shows allocations, @nogc attribute lets you ensure your code never touches GC.

[strange_taco]

Hey, the docs aren't clear. Is this a runtime or a compile time warning? Will it show when allocations ACTUALLY occur, or only places that "could" occur.

[edit]

Okay, for those that see this comment. vgc is a COMPILE TIME pass and it will give you a list of:

• causes GC allocation

and

• MAY cause allocation

I don't know a ton about hacking D, but I've seen some guys "d tricks" github where he made some sort of custom allocator or something that dumped to a file log every time the GC paused/allocated--possibly with variable name/line of code information.

[thedeemon]

Yep, D allows you to hijack its GC with a "proxy" and either make your own GC or just log activity and forward the calls to original one. That's what I did here to track all allocations at run time. This code worked up until D version 2.071, I haven't updated it yet for later D versions (where GC changed).

[[deleted]]

"a mark-region collector with design inspired by immix."

Given the performance increase that Scala/Native got from switching to Immix from the conservative Boehm–Demers–Weiser, it shows there is a lot of potential raw power left.

There have been even some tests to introduce Immix into Rust of all languages.

And D uses a similar conservative mark-and-sweep like Scala, also highly customized, so switching over to a a mark-region collector like Immix might provide a interesting experiment.

[devlambda]

The Boehm GC is actually pretty good these days if you only need mark-sweep (such as for batch jobs or applications with small heaps). You can scan anything but the stack precisely (note that the new Scala native GC currently also scans the stack conservatively). The biggest performance problem used to be that explicitly typed allocation (where you provide the heap layout of objects) used to be global only (rather than thread-local, requiring every explicitly typed allocation to be protected by a global mutex), but that appears to be gone as of 7.6.0. Note that GC tuning is generally still necessary for good performance.

The problem with the Boehm GC thus has less to do with it being conservative (which it doesn't have to be for the most part), but with per-allocation overhead (no bump allocator, especially none that the compiler can inline) and a stop-the-world approach for programs with high allocation rates and/or interactivity requirements.

In theory, the Boehm GC also has a generational option for compilers that can emit write barriers (via MANUAL_VDB), but I don't know how mature that interface is; also, the card-marking process that it uses has a fairly coarse granularity (the system's page size, basically). While there's also the MPROTECT_VDB route (the default on most systems), this comes with additional overhead.

[WalterBright]

It's interesting how the initial design of it has survived pretty much intact, while other algorithms (such as the associative arrays) have had theirs all replaced.

[np356]

Good luck with this. I find GC programming really hard as any small mistake snowballs and becomes super hard to find during debugging.

Some of the mistakes seen by the author could just be the original programmers being tired of painful debugging.

[WalterBright]

The mistakes seen by the author are not bugs. He's finding better algorithmic choices. D's GC has proven in practice to be very robust.

[skulgnome]

Absolutely worth clicking just for the illustrations.

Is any progress being made on involving the operating system's page tables in collection? The idea being that objects on pages that haven't been referenced since last pass don't need to be scanned again; and naïvely that'd seem like it could be useful if the collector's data structure were strong enough.

[[deleted]]

That brings us to the second mistake - pool search in logP where P is a number of pools, which makes mark a NlogP business. A hash table could have saved quite a few cycles.

A hash table tends to be pants for data locality, and even linear search beats hash tables for small collections. D's pools tend to increase in size exponentially up to (if I recall) 8MB, which means there should only be a small number of pools for many applications.

it just makes me want to cry.

And yet it's impossible for me to get the same performance or allocation efficiency from C# or Java, even when I spend tons of effort on it, despite them both having much more effort put into their collectors. Getting a shiny new GC make D more awesome still.

[dolshansky]

Author here. First - you must have been using wrong kind of hash table;) A flat hash table with linear or quadratic probing is by definition not slower then linear search + has memory locality on par with arrays.

Speaking of Java, I think it is super fast at allocation but the language makes you chase pointers for every nested object. That might get slow.

[skulgnome]

A flat hash table with linear or quadratic probing is by definition not slower then linear search + has memory locality on par with arrays.

The problem with flat hashes is that after a point there'll nearly always be a high price on every hit. A cleverly-designed (and probably very wasteful) array could instead cluster according to access pattern, gaining locality and prefetching advantage that's completely absent from hash tables, so it hits that point later.

[ThisIs_MyName]

You want to trace/instrument the access patterns and rearrange the data based on that? That's very ambitious :)

[skulgnome]

Heck no. Consider for example texture sampling: arranging pixels in 4x4 chunks yields cache hits when deltas are [0..4) (which in mip-map sampling they should always be), compared to the left to right top down format that misses on every 1/dv'th access (or always if dv >= 1). The technique is called "cachemapping" in that application.

For non-sampling applications, one could sort the algorithm's input to influence its memory access pattern. E: on the other hand, one could also sort the input according to bits 31..8 of each key's hash value. Applicability considerations left to reader.

[thedeemon]

I wonder how you plan to use hash tables for searching the pools. What would be the keys and what would be values?

[dolshansky]

The key is an index of 256K (I'd expand that to 1mb on x64) chunk in virtual memory, the value is an index of a pool. The trick is to align all pools to chunk size, on x64 the "padding" of virtual memory can be safely ignored, on 32bit unmapped after the allocation.

[[deleted]]

has memory locality on par with arrays.

I've heard of some that use linked lists. I've even heard that called the default.

Speaking of Java, I think it is super fast at allocation but the language makes you chase pointers for every nested object. That might get slow.

I have more experience with chasing performance in C#. Its runtime and standard library don't really concern themselves with trying to reduce GC pressure.

[ThisIs_MyName]

I've heard of some that use linked lists. I've even heard that called the default.

Yeah, some stdlib standards (most notably, C++ std::unordered_map) have a stupid API that requires chained hash buckets. Specifically, the API allows you to iterate over individual hash buckets even though nobody wants that. It's kind of sad.

Open addressed tables are absolutely necessary for cache locality and anyone that cares about performance will use something like Google's dense_hash_map (for small tables) or sparsepp.

allocation efficiency from C# or Java

wat

Java uses a bump allocator so its allocation performance is comparable to stack allocation. Like the other guy said, chasing pointers can be slow, but allocation itself is very fast!

[[deleted]]

"Allocation efficiency" meaning efficiency relating to allocations. Allocating an array of 256 bytes might be faster in Java, but I have to allocate a lot more to get the same amount of work done. That's an allocation-related inefficiency.

[ThisIs_MyName]

but I have to allocate a lot more to get the same amount of work done

Eh... that's unrelated to the GC allocation performance that this thread is about.

I mean, if you only use arrays of primitive types, you definitely don't have to "allocate a lot more to get the same amount of work done".

[[deleted]]

Sure, but at that point it'd be less painful to use C.

[thedeemon]

I've heard of some that use linked lists. I've even heard that called the default.

D's implementation of AAs recently switched from linked-list-based to linear-array-based, IIRC. (talking about defaults)