News for hackers. Stuff that matters.
Re:Garbage Collection for Systems Programmers by pron on Saturday March 30, 2024 @03:44PM (#39877959)
Reference counting does not have lower latency than a tracing GC nor is it more generally predictable. In terms of performance, it is usually worse than a modern tracing GC by most performance metrics. Its benefits are, indeed, lower memory footprint and that it can achieve reasonable latency even using a crude implementation. In other words, you'd reach for refcounting either if you mostly care about footprint or if you don't have a lot of resources to invest in implementing the GC.

Modern concurrent tracing has very little impact on latency. First, compared to refcounting, the barriers are rarely invoked. Second, they compact the heap concurrently in the background, and like all mark-compact GCs, their amortized cost drops to zero as the RAM increases (the work is linear with the size of the working set, which is roughly constant for a given program, but it needs to be done less frequently the more RAM you have). That's why high-performance languages that rely heavily on a GC -- Java, C#, Go -- prefer tracing.

Re:Garbage Collection for Systems Programmers by lll-o-lll on Saturday March 30, 2024 @04:04PM (#39878125)
> nor is it more generally predictable

Can you explain what you mean here? This does not match my experience or intuition.

Re:Garbage Collection for Systems Programmers by pron on Saturday March 30, 2024 @04:20PM (#39878240)
In theory, refcounting and tracing can behave similarly [1], but assuming we're speaking about their implementations in the industry (rather elaborate tracing GCs; rather crude refcounting GCs) then a refcounting GC would do some work as soon the refcount for a particular object drops to zero. When exactly that happens and how much work there is to do (and sometimes, what the fragmentation effect on heap is) are local properties that are not very predictable. In contrast, the amount of work a tracing GC needs to do when compacting is directly proportional to the program's working set and the frequency in which it needs to do that work is proportional to the allocation rate -- both of which are fairly regular and predictable global properties for a given program. For stop-the-world GCs there was then the matter of the highly unpredictable exact timing of a large STW pause, but modern concurrent GCs don't collect anything in STW pauses anymore. They only have very short (sub 1ms) and constant-time pauses and no surprise throttling as long as the allocation rate is within an acceptable range. So all in all, you pay a fairly fixed tax on the CPU (and if you want to pay less, just add more RAM) and virtually no impact on latency.

[1]: https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unifie...

Re:Garbage Collection for Systems Programmers by lll-o-lll on Saturday March 30, 2024 @04:44PM (#39878465)
Thanks for responding. My experience with tracing GC at scale is exclusively in the realm of .Net, and RC exclusively with C++ smart pointers. That matches your “sophisticated vs crude” contrast.

The experience with .Net is that GC impact was difficult to profile and correct, and also “lumpy”, although that may have been before GC tuning. GC would dominate performance profiling in heavy async code, but these days can be corrected by value tasks and other zero alloc methods.

For C++ style ref counting, the impact was a continuous % load and simple to profile (and therefore improve). Although here, the ref counting needed to be stripped from the hot paths.

The biggest issue I’ve hit between the two modes though, is how they behave when hitting memory limits. Tracing GC appears to have an order of magnitude perf hit when memory becomes scarce, while ref counting does not suffer in this way. This is enough for me to personally dislike tracing GC, as that failure state is particularly problematic.

Re:Garbage Collection for Systems Programmers by neonsunset on Saturday March 30, 2024 @04:53PM (#39878548)
When you hit memory limits, .NETs GC implementation would perform much more frequent, invasive and aggressive collections, including LOH compaction to reduce memory watermark which leads to greater GC pauses, though this is rarely seen in such a bad way on modern versions with e.g. SRV GC.

The most scaling way to address this is usually to just allocate less and use valuetasks with pooling where applicable (frequent asynchronous yields), I'm certain if you built a .NET 8 based solution you would see user-written code dominate heap allocations profile, as most hot internal paths of async utilize said state machine box pooling+ValueTask<T>[0] and may be entirely allocation-free.

[0] Example: https://github.com/dotnet/runtime/blob/cc7bf831f02cad241547e...

Re:Garbage Collection for Systems Programmers by lll-o-lll on Saturday March 30, 2024 @05:51PM (#39879022)
> When you hit memory limits, .NETs GC implementation would perform much more frequent, invasive and aggressive collections, including LOH compaction to reduce memory watermark which leads to greater GC pauses, though this is rarely seen in such a bad way on modern versions with e.g. SRV GC.

The trouble with server GC mode is that then there is no natural back pressure. If the processing is not CPU bound, then memory allocation can grow unbounded. This is not something that happens with RC as, again, the GC performance hit is inlined with task processing. The service may not be capable of as much throughput, but it doesn’t take out the entire server either.

> The most scaling way to address this is usually to just allocate less and use valuetasks with pooling where applicable (frequent asynchronous yields), I'm certain if you built a .NET 8 based solution you would see user-written code dominate heap allocations profile, as most hot internal paths of async utilize said state machine box pooling+ValueTask<T>[0] and may be entirely allocation-free.

Absolutely; I think it’s relatively simple to write servers that scale using modern .net; the memory allocation foot-guns when dealing with asynchronous code are now well understood, and tooling is good. I am compressing ~15 years of experiences in that previous post.

It’s probably the case that a tracing GC is the better choice for most modern applications, excepting memory constrained devices (like phones), and so long as you design with memory in mind.

Re:Garbage Collection for Systems Programmers by neonsunset on Saturday March 30, 2024 @06:13PM (#39879187)
Ah, I see where you are coming from.

You are correct, sustained load heap size of SRV GC has been a known pain point that had been particularly exacerbated after beefy Windows Server hosts fell out of fashion and got replaced by 512Mi Linux containers.

There has been work conducted on this each release throughout Core 2.1, 3.1, and then 5, 6, 7 and 8 versions to make it play nicer with more constrained memory limit systems.

The two major features that address this are Regions[0] (.NET 6/7) and DATAS[1] (.NET 8). The former is enabled by default everywhere except macOS and the latter is available opt-in either via env var DOTNET_GCDynamicAdaptationMode=1 or msbuild poperty GarbageCollectionAdaptationMode: 1 (see more in [1]).

The latter has shown to significantly reduce sustained (or, especially, idling) heap size for some particularly problematic workloads (but not all, sometimes you just have a lot of live objects). I definitely recommend giving it a try if this is something still relevant to you.

TLDR of what DATAS does is dynamic heap count scaling and much smarter heap up/downsizing depending on allocation rate/frequency and anticipated throughput impact of adjusting those.

[0] https://itnext.io/how-segments-and-regions-differ-in-decommi... / https://devblogs.microsoft.com/dotnet/put-a-dpad-on-that-gc/

[1] https://maoni0.medium.com/dynamically-adapting-to-applicatio...

Re:Garbage Collection for Systems Programmers by pkolaczk on Monday April 01, 2024 @01:27AM (#39891165)
Same experience with doing database system programming in Java. The number of performance issues caused by GC and the amount of code complication introduced in order to avoid them is mind-blowing. We’re managing memory manually in critical parts. But Java ergonomics around manual memory management (cake off-heap) is just terrible. There are moments I think I’d be more productive in pure C because of that. Not C++, not Rust, but pure C.
Re:Garbage Collection for Systems Programmers by cesarb on Sunday March 31, 2024 @09:48AM (#39884225)
> but assuming we're speaking about their implementations in the industry (rather elaborate tracing GCs; rather crude refcounting GCs)

That might be because a tracing GC needs to be rather elaborate to get good performance and avoid bad behaviors.

> When exactly that happens and how much work there is to do (and sometimes, what the fragmentation effect on heap is) are local properties

It being a local property is a good thing. It means it won't affect or be affected by how the rest of the program is behaving.

Re:Garbage Collection for Systems Programmers by bluGill on Saturday March 30, 2024 @05:06PM (#39878668)
when the reference count can only be zero or one reference counts have different performance than when it can be more, and it is much easier to reason about. This is most cases.
Re:Garbage Collection for Systems Programmers by rbehrends on Saturday March 30, 2024 @06:05PM (#39879128)
What happens if a large std::unordered_map<std::string, std::string> has its destructor called?

The maximum number of references is a red herring. While having a RC capped at 1 allows you to elide the actual reference count and makes pointer assignment cheaper, it does not materially affect the primary source of latency in a reference counting implementation, namely cascading deletions.

Re:Garbage Collection for Systems Programmers by bluGill on Saturday March 30, 2024 @06:19PM (#39879231)
Don't do that. good data design and architecture is always needed.
Re:Garbage Collection for Systems Programmers by rbehrends on Saturday March 30, 2024 @10:36PM (#39880844)
1. Such data structures (or more generally, std::vector<std::string, std::vector<std::string>> or something like that) are the natural way to represent e.g. dictionaries. So, you absolutely often need to do that and "don't do that" doesn't help here.

2. This general issue extends to virtually all collections. The idea that you should avoid large collections is not a practical solution to real world problems.

3. An alternative solution would be lazy destruction, but that comes with its own issues, such as a really bad worst-case memory overhead or making RC sufficiently more complex that it's not really a win over tracing GC anymore [1].

[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

Re:Garbage Collection for Systems Programmers by pkolaczk on Sunday March 31, 2024 @09:29AM (#39884060)
It’s not an issue in practice because, contrary to tracing GC, it doesn’t affect the other threads. So it doesn’t really count as pausing.
Re:Garbage Collection for Systems Programmers by rbehrends on Sunday March 31, 2024 @08:45PM (#39889708)
It would then follow that a stop-the-world collector is A-OK for single-threaded programs, because that doesn't count as pausing?
Re:Garbage Collection for Systems Programmers by pkolaczk on Monday April 01, 2024 @01:19AM (#39891137)
Still no, because STW GC can pause innocent code in arbitrary unexpected moments.

If you’re pausing the thread because the thread is doing some work eg calling into system to do I/O, this is not considered a pause (even though technically it is, as the thread may be simply paused and waiting for data) but rather just the cost of the operation. If the thread is being interrupted and paused because some unrelated operation has to run - now that’s bad and considered a true pause.

Re:Garbage Collection for Systems Programmers by rbehrends on Monday April 01, 2024 @03:21AM (#39891619)
> Still no, because STW GC can pause innocent code in arbitrary unexpected moments.

Well, yes, that's the problem, isn't it? And that's the point I was making. Pauses in the main thread absolutely count for latency purposes. Note that in most stop-the-world GCs you also can have pretty good control over when the GC is invoked, and that doesn't make things better.

The idea that you can always predict when cascading deletes happen in RAII code is also misleading. They can easily be hidden behind an abstraction barrier. Do you exactly know what's happening under the hood in all third-party libraries that you use, just for an example?

> If you’re pausing the thread because the thread is doing some work eg calling into system to do I/O, this is not considered a pause

In real-time scenarios (soft or hard), it absolutely is. "Regular" operations are absolutely part of your latency budget, and if "regular" operations can exceed it, you absolutely have a problem. See e.g. pretty much any of Gil Tene's talks on the subject.

Re:Garbage Collection for Systems Programmers by pron on Wednesday April 03, 2024 @06:10AM (#39915474)
The kernel (as long as it's not realtime) also pauses innocent code in arbitrary, unexpected moments, and modern concurrent collectors like ZGC pause such "innocent" code for no longer than the OS does. These synchronisation pauses are of roughly constant duration (regardless of working set/heap size) and overall introduce unexpected latency to a lesser degree than the freeing work done by refcounting collections.
Re:Garbage Collection for Systems Programmers by bluGill on Sunday March 31, 2024 @06:41PM (#39888804)
There is a lot in that statement and it deserves challenge. Note two things: there is no universal right answer here, sometimes you are correct, sometimes you are wrong; my responses will be contradictory (and also contradict things I didn't think to write) each project will need to figure out which of the combinatorical points is important their project to come up with the right also. Not doing this is premature pessimization - getting your data structures wrong up front will force slow runtime on you in a way that no micro-optimization (which is what premature optimization is really referring to) can ever fix and getting out will cost a very expensive rewrite.

> 1. Such data structures (or more generally, std::vector<std::string, std::vector<std::string>> or something like that) are the natural way to represent e.g. dictionaries.

They are natural, and easy but that doesn't mean they are the right way.

Often I find with a little thinking that there is a enum key under it all that I can hard code - and the enum key is also type safe so that the compiler can prove my code is correct against some class of bugs in a way a string as key cannot.

Why are your keys and values std::string which (baring small string optimization) will allocate more? Often you can place a maximum length on one of both that is small enough that you can replace std::string with a struct containing a char array (or std::string_view - I still have to support C++14 so I haven't been able to try it) and avoid a lot of allocations.

Failing that, often the correct data structure is a database (I reach for sqlite first, but there are plenty of options with pros and cons) which is fast lookup, allows for more complex structures easially, it persists the data to disk so that next startup I don't have to spend all the time reconstructing all that data (realistically performance of creating that large data dictionary is of far greater concern that getting rid of it).

> 2. This general issue extends to virtually all collections. The idea that you should avoid large collections is not a practical solution to real world problems.

This article is about systems programming. In systems programming you rarely have such a large dictionary in that format. You often will in something like the filesystem, but there the point is to have the data persisted from disk and typically you only read the subset you care about. You may have a copy in cache (and cache invalidation becomes an issue), but the in memory portion of data itself is never in a dictionary of that format.

> 3. An alternative solution would be lazy destruction, but that comes with its own issues, such as a really bad worst-case memory overhead or making RC sufficiently more complex that it's not really a win over tracing GC anymore [1].

That is one option, there are more.

Intentionally leak that whole dictionary. There is no reason to care if all the destructors run for any of the examples you presented and realistically if you are getting rid of the whole thing you are probably in shutdown anyway so who cares if you leak memory? Many systems programs and libraries do this.

Move the data to a different thread that only handles reclaiming memory and then don't worry about it. (in discussion we talk about making that thread idle time priority so it won't affect performance - but in practice all schedulers I'm aware of do this poorly in some way)

Finally, if after reading all that and consideration all your options (including things I didn't think of!) if you still conclude a large dictionary of strings to strings is your correct answer, then you probably should demand good tracing garbage collector. I'm not against using them where they are appropriate - I'm just arguing that if you think about your data a little more you will discover they are not needed nearly as much as it seems - and this time spending thinking is usually worth it because it results in much faster programs anyway (even if there is one large dictionary in the code how many others did you get rid of?).

Re:Garbage Collection for Systems Programmers by rbehrends on Sunday March 31, 2024 @08:44PM (#39889702)
> They are natural, and easy but that doesn't mean they are the right way.

> Often I find with a little thinking that there is a enum key under it all that I can hard code - and the enum key is also type safe so that the compiler can prove my code is correct against some class of bugs in a way a string as key cannot.

There's a fundamental misunderstanding here, I think. By dictionaries I mean language dictionaries, e.g. English -> French. You won't find an underlying "enum key" here. Nor am I sure how an enum would ever get large.

> This article is about systems programming. In systems programming you rarely have such a large dictionary in that format.

First, the article is, but the subthread that started this discussion was more general than that.

Second, even in systems programming, you will commonly have arrays or other collections. Caches are a very common thing in systems programming, after all.

> That is one option, there are more.

It is trivially true that there are alternative options, but all these are workarounds around the problem, i.e. you have to complicate your design or make silent assumptions that may not hold in the future (e.g. when disposing of memory at process exit does no longer work because you now need the code as a library).

Re:Garbage Collection for Systems Programmers by bluGill on Tuesday April 02, 2024 @05:04PM (#39910829)
> By dictionaries I mean language dictionaries, e.g. English -> French. You won't find an underlying "enum key"

That is a niche case not a common one though. There are a lot of niches each either different requirements.

>It is trivially true that there are alternative options, but all these are workarounds around the problem, i.e. you have to complicate your design

This attitude of non-systems programmers is why people argue garbage collection is slow. Garbage collection can be faster, but people who work in garbage collected languages think that solves all problems and so they don't build efficient data structures. Sure they are not leaking memory, but garbage collection is not enough more efficient than reference counted as to make up for thousands of destruction's when the more complex reference counted version only had a couple. Yes the code is more complex, but it is also faster and that is a trade off I'll take.

Re:Garbage Collection for Systems Programmers by rbehrends on Wednesday April 03, 2024 @02:22AM (#39914213)
> That is a niche case not a common one though.

It was an example meant as an illustration. The general case of "collection of objects" is hardly niche.

> This attitude of non-systems programmers is why people argue garbage collection is slow.

I started programming writing Z80 assembler in the 1980s, counting T-states in order to make hard realtime code work. I wrote a graphics driver for Atari ST/TT hardware not to soon after. I think I have a pretty good idea what working in a real-time and/or resource-constrained environment means.

> This attitude of non-systems programmers is why people argue garbage collection is slow.

That is an incorrect generalization. In fact, I see plenty of inefficient code in C++ and Rust (e.g. because a lot of the workarounds for not having GC require additional copying).

> Sure they are not leaking memory, but garbage collection is not enough more efficient than reference counted as to make up for thousands of destruction's when the more complex reference counted version only had a couple.

This is some really unclear statement. If you're trying to make a connection between absence of (tracing) GC and having value types, they are not inherently related. You can have tracing GC and value types (e.g. C#) or reference counting and a lack of value types (e.g. Python).

What is true is that in general memory allocation is relatively expensive, so you want to avoid unnecessarily allocating objects, but that's true regardless of whether you use malloc()/free() or a garbage collector and the strategies for dealing with that are the same in both cases.

> Yes the code is more complex, but it is also faster and that is a trade off I'll take.

Again, this is an untrue generalization.

Re:Garbage Collection for Systems Programmers by neonsunset on Wednesday April 03, 2024 @07:29AM (#39916044)
C# has structs with generics/explicit layout/object references/fixed buffers/etc. and byrefs which are special pointers that can point to managed memory, stack or unmanaged one yet are still tracked by GC despite allowing pointer arithmetic on them, and regular C pointers yet successfully uses GC.

Much damage has been dealt to non-JVM languages by stereotypes and perception that the way JVM languages work is the way all GC languages work.

Re:Garbage Collection for Systems Programmers by tomp on Sunday March 31, 2024 @08:21AM (#39883607)
delaying cascading deletion us much easier to implement than a high-performance tracing GC
Re:Garbage Collection for Systems Programmers by bluGill on Tuesday April 02, 2024 @05:05PM (#39910839)
That isn't a choice though. The high performance garbage collector is implemented by the language implementers and comes for free, while the delayed cascading deletion has to be done by the individual programmer not the language designers.
Re:Garbage Collection for Systems Programmers by rbehrends on Wednesday April 03, 2024 @02:24AM (#39914236)
Delaying deletions can result in significant memory overhead [1].

TANSTAAFL, as they say.

[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

Re:Garbage Collection for Systems Programmers by pron on Saturday March 30, 2024 @06:19PM (#39879227)
And yet, the reason tracing GCs are chosen by virtually all high-performance languages that heavily rely on GC is that they've been found to be faster in practice for the common workloads.

One of the reasons why your intuition is not so straightforward is that a tracing GC needs to do no work whatsoever when the number of references is zero. One of the common ways to teach the basics of GC is by starting out as looking at tracing and refcounting as duals: refcounting needs to work to free objects, while tracing works to keep them alive. If you thinking in terms of what work needs to be done to promptly determine when an object becomes garbage, then you're already not thinking in terms of tracing, because tracing never actually needs to learn about when an object becomes garbage (this isn't actually true when they do reference processing, but that's another story).

Or, if you want to think about it another way, in a tracing collector there are already only two cases no matter how many pointers there are to an object: reachable or not, i.e. the same one and zero as in your case, only there isn't even a need to ever set the counter to zero.

However, in principle tracing and refcounting can be quite similar (https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unifie...) in their behaviour, but in practice most refcounting GCs in industry use are crude, and don't match the performance of tracing GCs in common use, which are quite sophisticated.

Re:Garbage Collection for Systems Programmers by tomp on Sunday March 31, 2024 @08:19AM (#39883591)
> And yet, the reason tracing GCs are chosen by virtually all high-performance languages that heavily rely on GC is that they've been found to be faster in practice for the common workloads.

I disagree.

IMO the reason is simplicity, most languages don’t want to burden programmers with lifetimes and/or soft references.

Rust and Swift, both high-performance languages targeting specific niches, chose differently. Both largely for reasons of predictability, lower latency, lower memory use (which you admitted above) as well as lower memory trashing.

Re:Garbage Collection for Systems Programmers by pron on Sunday March 31, 2024 @09:43AM (#39884177)
> IMO the reason is simplicity, most languages don’t want to burden programmers with lifetimes and/or soft references.

I'm talking about languages that already use a GC as the primary heap management mechanism. Any kind of GC algorithm, whether tracing or refcounting, frees developers from thinking about lifetimes, but languages that primarily rely on GC and care about performance almost always pick tracing.

The only languages that choose a refcounting GC are either those that care little about performance (Python) or those that don't rely heavily on GC (Rust).

> Both largely for reasons of predictability, lower latency, lower memory use

Refcounting offers worse latency, worse predictability [1] (compared to modern low-latency tracing GCs, like ZGC), and worse throughput; it does offer a significantly lower memory footprint. The reason Rust chose refcounting is primarily because it doesn't rely on the GC heavily and so it might as well use a crude GC (and enjoy the lower effort of implementing it as well as the lower footprint), as a crude refcounting GC is usually better than a crude tracing GC.

Furthermore, an sophisticated tracing GC is not a great fit for languages like Rust or C++ because it requires a more elaborate code generation and some "magical" mutator thread behaviour, when low-level languages like the generated code to be as close to the source code as possible. This isn't so much predictability of performance, but predictability of the generated code and the behaviour of mutators (in terms of lowering the surprise of "why is my thread doing _that_ now?" when observed at a low level). For example, with ZGC, a mutator thread may find itself moving an object when accessing it; this is surprising at a low level -- which may not be a good fit for a low-level language -- even though it ends up offering better performance predictability overall. On the other hand, a mutator thread doing work freeing memory with a refcounting GC when it's dropping a reference to it may offer worse latency and worse predictability overall, but it's not as surprising at a lower level in the sense that it's easy to understand why it's doing that.

As for Swift, I think it picked a refcounting algorithm because it cares about memory footprint (most Swift applications run in memory-constrained environments) and because some unique language features allow to reduce the cost of refcounting sufficiently for a simple refcounting GC to be acceptable.

[1]: Again, not in principle (as both refcounting and tracing can converge to a similar behaviour) but as practiced by most refcounting GCs in industry use.

Re:Garbage Collection for Systems Programmers by pkolaczk on Monday April 01, 2024 @01:09AM (#39891095)
> The only languages that choose a refcounting GC are either those that care little about performance (Python) or those that don't rely heavily on GC (Rust).

Not true. The creators of Swift chose RC exactly for performance reasons: low memory footprint AND low latency.

//edit: ah, you actually admitted it at the end. So you’re contradicting yourself.

Re:Garbage Collection for Systems Programmers by pron on Monday April 01, 2024 @06:51AM (#39892689)
Refcounting's latency is worse, not better than modern tracing. Swift chose refcounting not because it performs as well as tracing, but because they managed to get it to perform acceptably for their needs (with special language features), and they really care about footprint.

If someday there's some advancement in refcounting that makes it better (or even as good but with significantly lower footprint), you'll see all languages that currenly use tracing switch quickly. For the time being, though, tracing is winning.

Re:Garbage Collection for Systems Programmers by pkolaczk on Tuesday April 02, 2024 @07:11AM (#39904409)
Refcounting introduces zero latency into code that doesn't allocate / free. Tracing can pause such code. Zero latency is better than non-zero.
Re:Garbage Collection for Systems Programmers by pron on Tuesday April 02, 2024 @01:50PM (#39908691)
Modern concurrent collectors like ZGC only pause threads to synchronize state transitions -- there is no collection work done in STW pauses (or any work that grows with the size of the working set or total heap) -- and not for a longer duration than the OS does for various things. Certainly the average impact on latency is lower for concurrent tracing collectors.

These days, tracing collectors offer better throughput, latency and predictability than refcounting, while refcounting offers better footprint. That's the main tradeoff, and I mentioned some secondary ones (re ease of implementation and low-level "surprises") before.

Re:Garbage Collection for Systems Programmers by anamax on Sunday March 31, 2024 @06:00PM (#39888455)
Not so fast.

A tracing GC, by definition, traces. (Not to mention that tracing keeps the live objects alive.)

My important-to-me application has a large amount of "live forever" memory and, at any one time, a fairly small amount of memory used by short-lived objects. However, it allocates and then discards those objects very frequently.

Let's say that it has 100MB of "live-forever" and, at any one time, 1MB of transient objects. Moreover, the vast majority of the pointers in the 100MB are to other parts of "live-forever."

A GC-based approach will allocate Nx1MB of transient objects and then trace the pointers in that 100MB to free all but the currently in use 1MB of transient objects. The vast majority of the traces are a waste of time, but GC can't know that. Moreover, it will tromp through the address space, trashing the cache.

A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache.

It's not clear that those RMWs will cost more than tracing that 100MB.

Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy. (Remember that the 100MB is also subject to caching.) That 1MB won't use more pages than the Nx1MB.

Re:Garbage Collection for Systems Programmers by pron on Sunday March 31, 2024 @08:52PM (#39889754)
> The vast majority of the traces are a waste of time, but GC can't know that

It can, it does, and you've basically described generational collection. Generational GCs try to only trace through recently allocated objects, and only bother with old ones if they can't free enough memory. Not wasting time on unnecessary traces is much of the point of generational GCs.

More modern GCs like OpenJDK's G1 go some steps further. They're region-based, and they keep track of inter-region pointers that tell them the likelihood that a region may benefit from compaction.

> A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache.

A tracing GC does that without any bookkeeping. An object born and dead between young-gen collections will never even make its existence known to the GC (generational GCs usually only need to learn about an object's existence once it's promoted); it will never have been visited and traced. The old objects would not have been traced either (in that interim) if few enough young objects survive.

In fact, in such ideal situation where some fixed number of objects live forever and some large number of objects are continuously allocated and die, a generational GC will effectively need to do nothing: the old objects will have been promoted into the old generation, and the GC won't have to ever look at them again if there's always sufficient RAM, while the young objects will be allocated by a pointer bump, and when it reaches the end the GC will wake up and want to start tracing, but will find that all the roots still point into the old generation, so the young generation will simply disappear (i.e. the allocation pointer will be reset to the beginning). The GC in this case requires zero operations (well, except for some fixed number required to notice it has nothing to do).

> It's not clear that those RMWs will cost more than tracing that 100MB.

It's clear that they cost more than not tracing it, which is what a generational GC won't do.

> Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy

That prompt reclamation has some benefits on locality is true, but so does compaction. The problem isn't so much cache faults (because we're talking about writes, which fill up the write buffer, not reads that cause stalls) but exhausting the memory buffer. This can and does happen with super-high allocation rates (which makes it an interesting problem), and indeed the memory bus's bandwidth is sometimes the limiting factor on throughput, but we're talking about allocation rates that far exceed those that common refcounting GCs can deal with anyway.

It's been well established by now that tracing GCs offer better performance than (crude) refcounting GCs, which is why they're the choice of every high-performance language that heavily relies on GC. The price you pay for modern tracing GCs is in memory footprint and in cost of implementation. There is, however, constant research in GC, and some advances in refcounting might make it more appealing, but we're talking about sophisticated implementations that are comparable in complexity to tracing.

Re:Garbage Collection for Systems Programmers by pkolaczk on Monday April 01, 2024 @01:05AM (#39891079)
Generational hypothesis fails pretty miserably for some very practical and common workloads - e.g. caching. The real world is way more complex than short lived vs forever. There are many objects with midterm lifetimes as well.

Hence, generational collection is in practice only a constant factor improvement. That’s why not even all state of art uses it. E.g. Golang doesn’t.

Generations do not fundamentally fix the property of GC mentioned by the parent poster you’re replying to, because eventually the full heap will be scanned anyways, as it is virtually impossible to keep the promotion rate down to zero. It only delays that moment.

There is also non zero price to pay for maintaining generations. And also tuning generational GCs is much harder than non generational. It’s not a clear win.

Re:Garbage Collection for Systems Programmers by pron on Monday April 01, 2024 @06:49AM (#39892678)
> because eventually the full heap will be scanned anyways, as it is virtually impossible to keep the promotion rate down to zero. It only delays that moment.

But the whole point of tracing collectors is that even then scanning the whole heap is proportional in cost to the size of the working set, and so the amortized cost goes to zero with increase in RAM. Scanning the working set is still cheaper than tracking all references constantly. In fact, throughput wise it's a winning algorithm -- a doubling of RAM leads to a halving of cost.

I'm not claiming that tracing collectors always lead to optimal memory management, but the ones that are in common use are, in practice, much better than the refcounting collectors in common use except for footprint.

> And also tuning generational GCs is much harder than non generational.

There's no more tuning on the collectors of the last couple of years (I'm talking about ZGC and generational ZGC).

Re:Garbage Collection for Systems Programmers by bluGill on Monday April 01, 2024 @07:48AM (#39893102)
> Scanning the working set is still cheaper than tracking all references constantly.

that is why you need to be careful not to needlessly update your reference count for temporaries. managing memory is not free. generational garbage collection avoids a lot of thought but it demands more memory.

Re:Garbage Collection for Systems Programmers by pron on Monday April 01, 2024 @10:24AM (#39894460)
Yes. As I said repeatedly, the one thing that tracing sacrifices is memory footprint. It effectively turns RAM into performance. If you want a smaller footprint you either have to sacrifice performance or pay with more development effort.
Re:Garbage Collection for Systems Programmers by pkolaczk on Tuesday April 02, 2024 @07:20AM (#39904456)
In languages like C++ and Rust the majority of objects have trivial lifetimes and don't need reference counting at all. It is less than 0.1% of heap objects that need to be tracked by Rc/Arc, and even for them the reference updates are usually rare - like only at the moment of creating a new thread / task / request etc.

Hence, even if per object the cost of RC may be higher than tracing, the fact that there are 1000x fewer objects to manage makes RC a huge win. I guess Swift is also not that stupid and doesn't update the references every time a temporary is created, etc.

Re:Garbage Collection for Systems Programmers by pron on Thursday April 04, 2024 @05:36AM (#39928276)
> In languages like C++ and Rust the majority of objects have trivial lifetimes and don't need reference counting at all.

Sure, that's why they can get away with an inefficient GC.

> Hence, even if per object the cost of RC may be higher than tracing, the fact that there are 1000x fewer objects to manage makes RC a huge win.

The "win" here is not RC at all but the fact that there's little reliance on GC and, of course, it's not really a "win" but something you buy by giving up on something else (i.e. a tradeoff), in this case abstraction ability (memory management details cannot be hidden as implementation details), and giving that up increases maintenance costs. So to get the footprint savings you have to pay -- either with performance, if you rely heavily on a refcounting GC, or with maintenance cost, if you don't. To get the performance you can choose to pay for RAM or for more development hours, but either way -- you have to pay.

Tracing GCs manage not to do any work for the vast majority of objects, those with trivial lifetimes -- they, too, don't manage the vast majority of objects (the allocator just bumps a pointer and the GC is never even aware of the existence of most of objects) -- by not freeing dead objects promptly which comes at the cost of spending more RAM.

In other words: good footprint, good performance, good abstraction (i.e. lower maintenance costs) -- pick two and pay by giving up on the third. C++/Zig/Rust pick the first two, Java/C#/Go pick the last two, and I guess Python picks the first and last.

There are, of course, other nuances; e.g. most refcounting GCs in common use leak memory as they are too crude to handle cycles, and not all tracing GCs are state-of-the-art.

Re:Garbage Collection for Systems Programmers by pebal on Thursday April 04, 2024 @06:11AM (#39928476)
You don't have to choose in C++ because you can have optional tracked pointers managed by the pause-free GC engine.
Re:Garbage Collection for Systems Programmers by pron on Thursday April 04, 2024 @07:44AM (#39929085)
That "pause-free" GC engine performs worse than modern tracing collectors, so by using C++ you've already chosen lower footprint, and then you have to choose between worse performance or more work. I think many people are unaware of the advancements in tracing GCs over the past few years, but modern concurrent collectors don't do any collection in stop-the-world pauses.
Re:Garbage Collection for Systems Programmers by pebal on Thursday April 04, 2024 @08:33AM (#39929593)
Not true. Visit the repositorium and see the benchmark results: https://github.com/frol/completely-unscientific-benchmarks

The SGCL repository contains the source code for this benchmark that uses the tracked pointers: https://github.com/pebal/sgcl/blob/main/examples/treap/treap...

Only D language is close to the result, the rest of the GC languages are several times slower.

(clang on Windows)

raw pointers: 149ms

tracked pointers: 181ms

Re:Garbage Collection for Systems Programmers by neonsunset on Thursday April 04, 2024 @12:55PM (#39932953)
The results seem to be old. Numbers might have changed quite a bit (e.g. .NET core 3.1 -> .NET 8 is a big performance jump).
Re:Garbage Collection for Systems Programmers by pron on Thursday April 04, 2024 @09:59AM (#39930490)
Putting aside the fact that the compilation time is not included in the C++ result but is included in the Java result, the Java implementation allocates many more objects than the C++ implementation, that the GC used is old, and that there seems to be no interesting GC activity (shown by the fact that the results are similar with a 50MB heap, not to mention that in the C++ implementation, there is only a small number of objects all of the same size, and the code is single-threaded), I have to wonder: you see the result of a self-proclaimed "completely unscientific" benchmark and conclude that a 100-line GC using a decades-old algorithm beats decades of research and five generations of 100KLOC GCs done by the top garbage collection experts in the world spent and think, "this must be right"?

All the people working on Java at Sun/Oracle, on Go at Google and at C# at Microsoft (who, BTW, have written most of these languages' runtimes in C++) spent years and years designing elaborate and sophisticated algorithms that are worse than a crude implementation of a 50-year-old GC algorithm because we want to spend tens of millions of dollars and decades of work to give our users worse results? In your mind, what was it that possessed everyone designing high-performance language runtimes for non-memory-constrained environments over the past three decades, at unrelated projects that compete with one another, to all choose variants of a worse algorithm despite all of those variants being several orders of magnitude more costly to develop than what you believe is the better algorithm?

When someone comes up with a more performant GC algorithm than tracing -- we'll all switch to it. Who knows? It may be some sophisticated form of refocounting, but it ain't simple refcounting.

Re:Garbage Collection for Systems Programmers by pebal on Thursday April 04, 2024 @11:09AM (#39931380)
Java needs to generates a lot of garbage, whereas C++ does not. Therefore, GC for C++ can be simpler and generate lower overhead than GC for Java.

I'm not interested in the amount of money companies invest in developing garbage collection systems, I'm interested in code performance. Are you aware of any other absolutely zero pause GCs?

Re:Garbage Collection for Systems Programmers by pron on Thursday April 04, 2024 @01:20PM (#39933314)
> Java needs to generates a lot of garbage, whereas C++ does not. Therefore, GC for C++ can be simpler and generate lower overhead than GC for Java.

You mean lower footprint overhead; higher performance overhead. But that was my point: Higher-level, high-performance languages that rely on good abstraction -- like Java, C# and Go -- need a better-performing GC, which is why they choose tracing, and pay for it with more footprint. In terms of performance, tracing used in industry beats refcounting as used in industry.

> I'm interested in code performance

Sure, but you have to pay for: either with a higher footprint or with higher maintenance costs.

> Are you aware of any other absolutely zero pause GCs?

The ones I know of are ZGC and Azul's C4, which preceded ZGC by some years but was not open-sourced. ZGC isn't some obscure technology, BTW. It is currently running most of Netflix's workload, and probably other very large companies.

(Also, ZGC, does no collection work in pauses; it does pause threads to synchronise a state transition but for durations similar to those that the OS also pauses threads for).

Re:Garbage Collection for Systems Programmers by pebal on Thursday April 04, 2024 @03:06PM (#39934538)
Java generates a lot of garbage because its designers thought that the stack is unnecessary and GC is enough for everything. They were wrong.

Both ZGC and Azul C4 pause threads. SGCL never pause threads, so it can collect garbage more often and more efficiently.

Re:Garbage Collection for Systems Programmers by pron on Thursday April 04, 2024 @05:13PM (#39935879)
> They were wrong.

As their goal was a language that would be very popular, and given that languages that heavily rely on GC have many times more users than languages that don't, it doesn't seem that they were wrong, at least not about the centrality of GC (although, "value types" and arrays-of-structs are coming to Java).

> SGCL never pause threads, so it can collect garbage more often and more efficiently.

I can't examine the algorithm right now and I couldn't find a paper describing it (so I can't tell you if it's one of the algorithms we've tried), but if you believe you have a more efficient GC than those in the JDK, feel free to plug it in and test. If you're right, you'll have many millions of users and the overall impact of that algorithm on the software industry would be much greater than it would as a C++ GC.

Re:Garbage Collection for Systems Programmers by dmurray on Saturday March 30, 2024 @05:31PM (#39878871)
This sounds intuitively true. So...what if GC languages could introduce an optional annotation for an object to say that only one reference to it can exist, and use that as a hint to the GC?

I don't see how this could be implemented in a safe and performant way - either you check for existing references at runtime, or you risk some use-after-free bug. But perhaps your project is already in a GC language and you're happy with that, but just want to optimise GC for this critical component. And we already have the concept of "unsafe" code blocks in many languages.

Does anything like this exist? I Googled "smart pointers in Java" but just got a bunch of mid-quality answers where people explained that I'm stupid for even asking this and they're unnecessary because Java manages its own memory. But hasn't someone smarter thought of this?

Re:Garbage Collection for Systems Programmers by kaba0 on Sunday March 31, 2024 @11:09AM (#39884956)
> This sounds intuitively true. So...what if GC languages could introduce an optional annotation for an object to say that only one reference to it can exist, and use that as a hint to the GC

Tracing GCs fundamentally look at what is still reachable, while ref counting tracks deadness. They are actually the “yin-and-yang” of each other, with different tradeoffs, tracing being more practical on current hardware/usage pattern.

There is no practical difference in whether a tracing GC can reach an object from multiple place, or just a single one - but there might be some other analogue feature in tracing corresponding to 0-1 only ref count.

Re:Garbage Collection for Systems Programmers by bluGill on Sunday March 31, 2024 @06:58PM (#39888962)
Can only be one is easy on current hardware because that means it lives on the stack and in turn is destructed at the end of the current scope using the standard machine code to change stack size. The only part that is hard is if the system supports exceptions not the compiler needs to somehow jump back to each scope to run those - I can think of several ways to do this, but none are hardware supported (exceptions are not hardware supported - at least not on any architecture I know of - so it is up to the compiler to deal with this either way - it ends up looking as a catch and rethrow block)

> There is no practical difference in whether a tracing GC can reach an object from multiple place, or just a single one

The real gain would be deterministically run finalizers in this case. Many languages have looked at C++'s RAII and realized they need a deterministic way to do things like close file handles. As such they already have all the parts in place.

It doesn't gain anything else though as the tracer still needs to go through all the pointers in the 0-1 reference count as they might point to something that is sometimes shared but currently is not (and thus the tracer wouldn't reach that memory otherwise - if the memory is never shared it could also be marked 0-1).

I'm not convinced it is a good idea though. Manual memory management is hard. I write C++ every day, std::unique_ptr makes my life much easier, but it has limits (shared_ptr is in my experience a sign you don't understand your memory and so I will have to figure out some rare bug when you stored a reference to the underlying thing). If you always have garbage collection it is easy as you don't have to worry (though you can run into problems: either over allocating when a reference would work; or storing a reference in some data structure after the data isn't needed). If you never have garbage collection you know you need to think about object lifetimes. The 0-1 makes it too easy to have a situation where you didn't think enough and now 0-1 memory cleaned up even though it is still reached.

Re:Garbage Collection for Systems Programmers by carry_bit on Sunday March 31, 2024 @09:31AM (#39884078)
The state-of-the-art in refcounting[1] greatly improves the barrier situation over a naïve implementation: no read barrier, and the write barrier only uses atomics when mutating an (apparently) unmodified field in an old generation object.

[1] https://dl.acm.org/doi/pdf/10.1145/3519939.3523440

Re:Garbage Collection for Systems Programmers by pkolaczk on Monday April 01, 2024 @12:55AM (#39891039)
And, additionally, reference counting on a single thread doesn’t need barriers at all.
Re:Garbage Collection for Systems Programmers by pron on Tuesday April 02, 2024 @02:02PM (#39908852)
Certainly improvements in refcounting can bring its performance closer to that of tracing (and there are constant improvements in tracing, too), but one of the main reasons some languages choose refcounting is due to simplicitly of implementation, and these improvements bring the complexity of tracing and refcounting closer to each other. Currently, tracing leads in performance, but if that changes we'll see a shift in the algorithm for languages that depend heavily on GC performance.

BTW, our GC team investigated the implementation in that paper, and it is still significantly behind that of tracing in too many relevant workloads to be considered for adoption in production.

Re:Garbage Collection for Systems Programmers by pkolaczk on Monday April 01, 2024 @12:53AM (#39891031)
> That's why high-performance languages that rely heavily on a GC -- Java, C#, Go -- prefer tracing.

And yet, despite 30+ years of compiler and GC research, they are still in the second performance league. All languages in the first league (C, C++, Rust, Zig) use manual management and occasional reference counting.