Rendered at 12:42:37 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
kazinator 21 hours ago [-]
> Think of a service that keeps a large cache in memory, or an index built out of millions of small objects that all point at each other. Every one of those pointers has to be followed on every cycle, for as long as the process is up.
That's a strange thing to assert, having acknowledged the existence of generational GC.
Someone 20 hours ago [-]
Similarly, the statement
> Reference counting also has its own running cost, paid on every copy of a pointer you make and every time you drop one.
isn’t 100% true. It’s not necessarily on every copy or drop. Compilers can (and do) elide reference count updates if they can proof they aren’t needed, and can even skip allocating room for reference counts if they can proof it isn’t needed (example: a local object that doesn’t escape its scope)
I also find it a miss that the article doesn’t discuss memory usage. A garbage-collected program needs more memory to match the performance of the equivalent manually managed language.
Only if reference counting is exposed in the type system, or the standard library types are blessed to the compiler, otherwise there is no way for the compiler to know what to elide.
The smart pointer passed reference isn't copy-constructed and so no refcount is bumped. It has a scoped lifetime. The calling function owns a reference (baseline correctness assumption or else we are screwed). That caller is suspended while the callee executes.
deathanatos 18 hours ago [-]
It's still done. It's not uncommon to see that in Rust:
fn foo(x: &Arc<T>)
…quite literally borrows the count in the refcount-ed thing.
I think you can find similar things in CPython, on the C side of things.
deathanatos 20 hours ago [-]
It occurs to me that I have never seen any description of generational GC that actually notes how that works, though.
If we have two generations, young and old, we obviously can't simply "just collect in the young generation" — which I feel like is exactly what most generational GC descriptions say. If we only traced young objects, we could very well miss an old object pointing at a young one, collect the younger object, and now we've got a dangling pointer.
So there must be some book-keeping to avoid tracing everything (or what'd be the point of generations), but I have no idea of what that book-keeping is, or its cost.
> Show me your code and conceal your data structures, and I shall continue to be mystified. Show me your data structures, and I won't usually need your code; it'll be obvious.
wbl 19 hours ago [-]
That's where write barriers and the like come in. The cost varies by implementation and language.
aw1621107 19 hours ago [-]
> If we only traced young objects
Careful; just because you only collect in the new generation doesn't mean that you only trace the new generation. From my understanding a rudimentary generational GC design is to include the old generation in the GC roots so you don't need to examine everything in the new generation - if it's not reachable from the roots it's implicitly dead, and the latter category is assumed to apply to most objects in the new generation under the generational hypothesis.
deathanatos 18 hours ago [-]
> just because you only collect in the new generation doesn't mean that you only trace the new generation.
Well, then I suppose you're saying the up-thread comment is wrong?
TFA:
> Every one of those pointers has to be followed on every cycle
The comment:
> That's a strange thing to assert, having acknowledged the existence of generational GC.
Which would imply that's not the case, i.e., that we're not considering every pointer in every GC sweep. (Which, again, I thought was largely the point of generational GCs: to make sweeps cheap by not considering every pointer.)
I guess if it's really the sweep that's the expensive part, then perhaps doing a full walk is fine.
> generational GC design is to include the old generation in the GC roots so you don't need to examine everything in the new generation
I'm assuming roots (stack references to objects) are separate from generations (which heap objects belong to).
I suppose if you added old objects to the set of roots, that'd also solve it, but that's the same as "every one of those pointers has to be followed on every cycle".
The sibling post thinks writes are made more expensive by tainting/young-ifying objects that get written to. In that way, we prevent an old object from ever pointing at a new one — at the cost of writes now being more than a write.
> Which would imply that's not the case, i.e., that we're not considering every pointer in every GC sweep.
I think "every one of those pointers has to be followed on every cycle" as a blanket statement is not correct. It's true for some GC designs and not true for others.
> I'm assuming roots (stack references to objects) are separate from generations (which heap objects belong to).
Roots are just where you start tracing from. You can include older generations in them (or even subsets thereof), but you're by no means required to.
> but that's the same as "every one of those pointers has to be followed on every cycle".
Sure, but my point there was just that just collecting the new generation doesn't have to imply that you're only tracing the new generation. I guess I should have added a "necessarily" somewhere in my original comment.
> There is additional book-keeping and cost to writes.
From my understanding the bookkeeping there is effectively to be able to determine the set of roots to use when tracing/collecting the new generation.
kazinator 16 hours ago [-]
Generally speaking, whenever you trace into the old generation, you stop and back out. Given a young generation object with pointer fields, you don't know which of them are also young and which are old, unless you examine them, which is tracing. So the tracing pokes into the surface of the sediment generation, so to speak.
Then if the language allows mutation of objects, special consideration has to be given to old objects that were mutated to point to new ones. You can treat those as additional roots; the graph of young objects reachable from a mutated old object is reachable. (Considered so on the assumption of the old object being reachable, which we can only disprove by doing a full scan.)
kazinator 19 hours ago [-]
When you get it working, you will figure it out. (Or even well before then; the rest is just bugs.)
I wrote one for TXR Lisp which there are no generation heaps; but objects have a generation. In the same heap, you can have adjacent (unrelated) objects that are in different generations. Objects never move from their heap; they keep their position in the same heap over their lifetime.
The allocator therefore records the new generations in a fresh log, which serves as the nursery. When that log gets full, a pass is triggered.
Implementations with separate heaps (typically copying collectors) allocate in a nursery heap and promote objects from there, but it is conceptually similar.
In the marking phase, we do not process this nursery. We start at the usual root pointers: stack, globals and proceed with normal marking, like in a pure mark-sweep collector (or a full pass), with a small modification: whenever we hit an old gen object, we skip it. We assume that the old gen object is reachable, and every object reachable through it is similarly an old-gen object. This is where the generational algorithm wins, chopping down the graph of objects to be marked, possibly drastically so.
Where the nursery/fresh log comes in is the sweep phase. Because we know that we did not traverse any old generation objects, it would be wasteful to do a full sweep. In the case of the fresh log, we sweep just through the fresh log. Anything in the fresh log that is reachable is promoted to the old generation. Anything not reachable is reclaimed: either immediately or through the finalization treadmill, if applicable. The fresh log is then reset to empty. In the case of a nursery, we similarly just sweep through the nursery heap and promote (by copying) reachable objects to the old generation, reclaiming the rest. The nursery is empty.
There may be additional structures. Note that we have the assumption that old objects only point to old. But what if (it is allowed that) the program mutates an old object to point to a newly allocated new one? That would break the assumption. We can make the program (code generated by compiler or whatever) report whenever that happens.
In the TXR Lisp implementation of generational GC, mutation of old objects is handled via two strategies. A single value assignment of a young object to a field in an old one will cause the young object to be appended to a "check" log. In some cases, this is not practical for various reasons. For instance, an operation mutates a large number of fields of the same object (e.g. array). In such cases we add the old objects to a "mutated" log. The objects added to both arrays have their generation field reset to -1: neither young (0) nor old (1).
Both the check log and mutated log are marked during marking. The check log contains only young objects and so sweeping those is already taken care of by the freshlog, it needs not be visited during the sweep phase.
The mutated log is processed during sweep in order to reset the generations from -1 back to 1.
When the check and mutated logs fill up, GC is not triggered immediately then, but the flag is set for the next GC to be a full one. What that does is turn off the mechanism: since we know a full GC is coming, we don't have to record mutations of old objects pointing to new.
kev009 21 hours ago [-]
Even things built directly on underlying malloc and free typically have some form of "garbage collection" in the malloc implementation for efficiency and performance (geometric sizing, thread caching, etc).
It's best to think about lifetimes and lifecycles where possible. Immutability where sensible and things like pool allocation are examples of this.
GC languages can result in quite pessimistic code because they encourage people to NOT think about what is going on. But people have also built functional HFT engines on things like the JVM by thinking about lifetimes and lifecycles.
jerf 20 hours ago [-]
Ultimately, the entire problem of deallocation in general is a continuum, not a binary, and I tend to find it hard to take anyone seriously who is vigorously arguing about how awful GC is if they don't understand that and indicate some understanding of the concept. The closest you can get to real "manual" memory management on a modern system is to use nothing but arena allocations, and if you really want "manual" memory management, you need to allocate some small fixed number of arenas, because if you're constantly allocating and deallocating them that is itself probably an automated process that could go wrong, at least in theory. Malloc/free or new/delete isn't really "manual memory management".
The wide variety of options and tradeoffs, with fewer clear lines in the sand than most people seem to think, is already enough to call it a "continuum" but what really finishes the job is that they're all mixable and matchable. Something like Zig makes that really obvious, but most static languages have at least some sort of ability to mix in multiple strategies. There's nothing wrong with a C++ program that uses new & delete, and also uses arenas for some things, and also uses garbage collection for some things, and also has an integrated scripting language like Lua with its own memory strategies. Such programs are not that uncommon... that describes modern games nowadays, the supposed canonical case where you "can't afford GC". But it can... it just fences it in to a particular domain where it fits.
gwbas1c 19 hours ago [-]
Careful, this statement is misleading:
> The leaks that come from forgetting to free something go away entirely.
Not quite: In manually-managed and referenced counted languages with destructors, releasing resources, (open file handle, open socket, open connection to a database, ect,) happens when objects are cleaned up.
In a (tracing) garbage collected language, releasing resources is a very manual process. You might not have a memory leak, but leaking file handles or similar resources is a real problem with real consequence.
shivanshuag 5 days ago [-]
Agreed, for most real world softwares, the cost of GC is irrelevant. But there are still some programs like databases or game engines where the cost can start adding up. That's when you measure and optimize.
jayd16 21 hours ago [-]
Did you "Agreed" your own blog?
Sha1rholder 20 hours ago [-]
This is getting ridiculous.
pjmlp 23 hours ago [-]
Yet the three major game engines Unreal, Unity and Godot all have a GC on their infrastructure, and Capcom is quite happy with their .NET fork on RE Engine.
Also every single graphics application that uses Metal or DirectX, relies on reference counting as GC algorithm.
slopinthebag 22 hours ago [-]
I’m sure those three engines have had no issues with performance whatsoever right?
Oh shit…
jmull 22 hours ago [-]
Game developers are always trying to push the boundaries. The only game engines without performance issues are ones hardly being used.
slopinthebag 10 hours ago [-]
There is a difference between pushing more polygons or higher resolution, and trying to fix stutters caused by the GC…
jmull 6 minutes ago [-]
There isn’t though.
Garbage collectors aren’t magical black boxes with no levers, and you can use them how you like.
You address performance problems relating to GC the same as you do anything else: measure, analyze, optimize, repeat.
pjmlp 6 hours ago [-]
Alternatively they could be fixing stutters caused by using malloc() on the wrong place.
pjmlp 22 hours ago [-]
I am sure that many of the issues were a skills issue as well.
jayd16 21 hours ago [-]
What engine do you recommend?
slopinthebag 10 hours ago [-]
Depends on the game
21 hours ago [-]
izacus 22 hours ago [-]
Do you have any source taking about GC caused performance issues in those engines?
slopinthebag 21 hours ago [-]
Too many to post, you can just google “{engine} gc spike” for example.
Heck, there is a whole cottage profession of experts who get called into fix GC related performance issues with Unity.
jayd16 21 hours ago [-]
So are you saying this cottage industry achieves success or the industry formed around an impossible task?
A cottage industry is built around making rocks look good too. Is that an indicator that games are good or bad at making rocks?
dismalaf 19 hours ago [-]
I mean, you can always add enough triangles, shaders, entities, etc... to make any engine slow to a crawl... Anything that pushes state of the art will have more performance issues than something that doesn't.
marcosdumay 22 hours ago [-]
> That's when you measure and optimize.
How do you "optimize" the GC away after you wrote your entire database server in a language that uses it?
ApolloFortyNine 22 hours ago [-]
It's incredibly in common in game development, C# has a lot of features you can take advantage for this.
But the most naive example any language supports is simple object pooling.
If the language is Java which puts the GC in nearly everything you're f...,
other languages have GCs and nonGC'd data so you go to the wonderfull world of manually managed objects with its use-after-free..
marginalia_nu 21 hours ago [-]
Object pooling and bump allocators using persistent scratch buffers, mostly. The latter what you'd use for read buffers in I/O intensive applications like databases and the like.
jmull 22 hours ago [-]
GC languages typically have features of the language and/or standard library that make GC the default, not the only option.
marcosdumay 21 hours ago [-]
What doesn't save you from having to rewrite the entire system.
(Even though, no, that's not typical. That's a tiny minority of them.)
jmull 21 hours ago [-]
Not sure I understand the question, but it generally works like this:
Once you measure, you'll find a small fraction of the code is taking a large fraction of the time. When you zoom in on trouble-spots you may find, e.g. that the GC is taking the time (or you may find something else entirely is taking the time). If it's the GC, you might look and see, e.g., that it's spending its time tracing the objects in the 100K node graph you're creating several times a second, and realize you could, e.g., create it once and simply keep reusing it. Perhaps it might be as simple as using removeAll(keepingCapacity: true) instead of removeAll() (a Swift example).
The superficial details differ, but you generally just want to understand what the GC is working so hard on and lighten its load. If you haven't been measuring and optimizing throughout, there are almost certainly easy-to-pluck, low-hanging fruits, ripe for the taking.
pjmlp 20 hours ago [-]
Starting by using a GC language that is strongly typed, compiles to native code, supports value types, memory pools/arenas if required, which provides best of both worlds.
Where GC means any kind of GC algorithm from CS point of view.
jayd16 21 hours ago [-]
Lots of ways but an obvious and generic answer is to use pooling.
slopinthebag 21 hours ago [-]
This assumes that you’re only ever running a single software at a time. Sure, 2-10x slower/memory consumption might not matter in a vacuum, but when every software is like this, you get machines that feel slower than they did 2 decades ago.
220hertz 22 hours ago [-]
I used to write a lot of Javascript-like Extendscript scripts back when I was using InDesign a lot. The DOM's global object $ had a method to directly invoke the garbage collector. It made a difference certainly, but it was difficult to tell to what extent because InDesign itself gradually leaks memory and becomes more bloated the longer you use it in a single session.
miladyincontrol 5 days ago [-]
What does GC cost?
For Caddy with an incredibly synthetic http only benchmark it costs about 2ms of latency and somewhat less throughput.
Worth it in an incredibly artificial benchmark? Perhaps. However when it comes to real world usage the cost is a significantly smaller piece of the pie.
thomashabets2 22 hours ago [-]
> In Rust you pay for it by arranging your program in a way the compiler can verify.
I disagree with this. The sentence implies that this work is done in order to make the compiler happy, where my experience is that it forces the programmer to actually get it right.
I had an "aha moment" when I was frustrated at failing to express my intent to the compiler, and suddenly realised that the reason I couldn't "just say the magic words" was that my object ownership design was inherently flawed. I had to make large changes not to make the compiler happy, but to actually have a coherent design.
So no, it's not about what "the compiler can verify". That's like saying "my lawyer won't let me do this". No, your lawyer is your employee, not your boss. They're just saying that if you do this, then you may go to prison. It's not the same thing.
("unsafe" is the Rust way to go "thank you, legal department, but I'm making a business decision to take this risk. Your concern has been noted")
ron_k 22 hours ago [-]
I understand what you’re saying, but I read that phrase in a different way.
Let’s say you have two ways of doing the same thing: both work, both are legit and neither introduce GC bugs. The only difference between the two is that one can be verified by the compiler while the other can’t, so you are stuck with solution no. 1 although both would work.
To phrase it differently: the code that gets verified by the compiler is safe, but is all safe code verifiable by the compiler?
I’m not implying that’s the case, but that’s what I feel the author is saying.
thomashabets2 21 hours ago [-]
> To phrase it differently: the code that gets verified by the compiler is safe, but is all safe code verifiable by the compiler?
Right. And this reduces to the halting problem, so in theory the compiler cannot know that all safe code is safe.
In practice, I'm saying that not just syntactically, but in your code's design, the compiler is more likely to be right. It's a bit like Chesterton's fence. You can bypass the lifetime checks if you just have the confidence to say "yes, I'll use `unsafe` here and it's fine because these reasons". As you're writing your "SAFETY" comment, you may very well find yourself not so confident anymore. And indeed, often this compiler-induced "stop and think" prevented you steaming ahead with a bug.
Now, the borrow checker is not perfect. I don't know how far away from "all but NP-complete cases" it is. My experience is that it's almost always right, and I've only had to put a seemingly needless "drop" statement to placate it. But they're working on it. A new one is coming: https://daily.dev/posts/rust-s-new-borrow-checker-is-coming-...
In any case "by arranging your program in a way the compiler can verify" I think is not accurate, because the overlap between "correct" and "compiler can verify" is nearly complete, though yes the latter is a strict subset of the former. In other words I don't write Rust to make the compiler be able to verify it, but to make it correct. And nearly always that means the compiler can verify it too.
pjmlp 4 hours ago [-]
To the point Polonius is finally landing, and while it is better than current NLL, there are some issues it introduces, and it is still far from production.
Because of this "halting problem" compromise, I prefer the approach other languages are pursuing, keeping some form of automatic memory management, while improving their type systems, like Swift, Chapel, OxCaml, Scala 3, et al are pursuing.
21 hours ago [-]
bjourne 17 hours ago [-]
> I disagree with this. The sentence implies that this work is done in order to make the compiler happy, where my experience is that it forces the programmer to actually get it right.
Haskellers say the exact same thing. :P Personally, I'd much rather get shit done and don't appreciate tools "forcing" me.
thomashabets2 2 hours ago [-]
Which is why the software world is full of technical debt and frustrating buggy software.
But I agree that it's must faster to get the wrong answer than the right one.
convolvatron 21 hours ago [-]
I've had that moment in Rust too, where there was no composition that effected what I wanted, because supporting that model would have meant a very different backing data structure. However in that case I actually didn't care about the kind of correctness problem it was saving me from.
I've also had the converse experience, where I know full well that the structure I'm trying to impose is correct and quite efficient, but its part of the space that rust doesn't cover.
Rust is great. It's a noble attempt to bring a degree of correctness to a problem space that suffers from a great deal of slop. But to pretend that the model is complete, or that the design decisions that were made are perfect in every way, is just wrong. That the rust compiler and runtime can't support my construct isn't really an absolute value judgement on that idea in the first place. The rust compiler isn't really an oracle that tells you whether something is right or not in an arbitrary value system.
thomashabets2 20 hours ago [-]
Right. The borrow checker is not always right. Just almost always right. It's not perfect (because halting problem), but… well I already said the rest in https://news.ycombinator.com/item?id=49287460
Still, I don't write Rust code the way I do "to make the compiler happy", but to make it correct. And sometimes it's correct to drop some "unsafe" because gosh darn it, you know it's fine this time.
And you're probably right for the cases you're thinking of, where Rust wouldn't let you (at least without unsafe). And maybe you're 99% sure about that.
But for every 100 changes we’re 99% sure won’t cause an outage, one will…
(also future changes may invalidate assumptions you relied on, of course, making it no longer true)
Do you have some examples you can share where you think Rust prevents you doing the right thing? The ones I run into tend to force me to think of the edge cases, and usually those edge cases don't even have a right answer.
convolvatron 19 hours ago [-]
this one may actually be solvable, but I kinda timed out on it. okay, so I'm doing distributed systems, and my primary abstraction is a large stream that I'm using to connect components across machines. its kind of mandatory that I implement back pressure for these streams, because awful things can happen if I don't.
ok, I have a large local container of records that I want to stream over a back pressured channel. now we clearly have a problem that the iterator needs to be long lived, and I don't really want to serialize all accesses to the collection for a streaming operation that may never terminate.
for this particular domain I don't actually care about serializability of the iterators view of the collection. I clearly don't want the container to be left in an erroneous or inconsistent state, but otherwise anything goes.
all the iterators for all the standard rust containers have lifetimes bounded by the container (batch), and because they all represent internal state, they all have to be mutable. and in this case they need to be async also.
I don't think there is an 'idiomatic' way to represent that access pattern, and it kind of necessitates writing ones own container. if there is a good answer to this I'd be curious to hear it, but I consider this one of the major personal failure modes for rust, which is 'oh, yeah, well, in order to figure that out to need to understand [long list of compiler instristic property types and runtime behaviour], which isn't super pragmatic.
since I'm here, I've already wasted words here talking about the dismal async situation, but I think more important to me as a systems programmer is the lifetime abstraction. It think its great to put a name to it and try to put rules around lifetimes - these are traditionally implicit things that we reason about _outside the program text_, and that's a real bother. however everything I do is state management, and the lifetimes of those states (files, connections, higher level sessions) don't directly correspond to the lexical calling stack. the only tools that rust gives me is Arc, which some with a whole set of busy caveats, or trying to thread several lifetimes through the entire call path - a road that I've been down and abandoned for readability and maintenance.
now you can argue that rust would prefer that I use a thread per object, and while that might be workable, that a pretty strong and side-effecting constraint to apply to all of the programs in my domain.
anyways I ended up keeping the last key issued, and for every new record, paying the logn cost to get to approximately where I was perviously. which brings up another general complaint. as imperfect as it is, sometimes I want to just stand sometime up and look at it. I don't want to spend 3 weeks coming up with sharing policies and structures that work well with rust. I want to look at it and measure it and count its defects in my head and decide what to do next. in rust I kind of have to decide up front what I'm building, and while that might be an excellent thing to encourage in some contexts, I don't think it is in all contexts.
thomashabets2 15 minutes ago [-]
I think there's a lot of "the devil is in the details", here, and I'm going to be respectful enough to not start a bunch of "why don't you just…".
It does sound like a thing where if you'd written this in C++, then you could have done it much easier (which is my experience), and then either also, or later on when the state of the invariants are no longer in your working memory, one of those invariants would be violated and memory start corrupting (also my experience).
E.g. in a C++ vector you can push_back() without invalidating the iterators iff there's enough capacity in the vector. Though if some code saved the "end()" iterator (e.g. concurrent for_each), that's broken. std::vector doesn't permit that use case, but does not prevent it. I prefer it being prevented.
I would consider the extra work to be worth not finding that problem in production, later.
Ideally what you want could be accomplished by just (oh no, there I go) finding a single place to punch a hole, put an "unsafe" there, and explain why it's actually fine to create some inner mutability or whatever is needed there.
The huge complexity baggage, and the amount of working memory you need to reason about async, is unfortunate though, and I won't defend it. But at least it fails closed if you get it wrong.
pclowes 22 hours ago [-]
This is one of the best high-level survey explanations of GC I have seen, nice work.
bjourne 21 hours ago [-]
Props for using a correct nomenclature. Reference counting is a "kind of automatic garbage collection. Tracing garbage collection is also a kind of automatic garbage collection.
melodyogonna 20 hours ago [-]
Not really the point of the post, but there is a third memory allocation paradigm where you can do manual allocations and deallocations, but without the mental overhead of having to remember to free memory because the compiler will force you to properly handle it. Mojo has linear type support so you can do something like this: https://x.com/melodyogonna/status/2085089269484343725?s=20
amazingamazing 22 hours ago [-]
I rarely see a real use case bottle necked on garbage collection.
netbioserror 20 hours ago [-]
There's a third way here. It could be called many things: Single ownership by default, automatic stack lifetimes, hidden unique pointers, etc. The main idea is that the lifetime of dynamic heap data is treated no differently to primitive stack data: Clean it when it goes out of scope. Rust and C++ require you to specify this manually, but Nim is unique among native-compiled languages in that is does it by default, with tools to opt-out. An advantage of this approach is that combining immutable values and static analysis can reduce most parameter passing to borrows, again, without needing the programmer to specify, by default. The main cost being that some assignments, especially crossing the variable-to-immutable line or vice-versa, would require a copy.
TrustScoreAgent 5 hours ago [-]
[flagged]
EGreg 22 hours ago [-]
There is no need for garbage collection if you don’t form circular references. Just have a canonical direction and always keep weak references the other way.
thomashabets2 22 hours ago [-]
Reference counting is a different model. Many papers have explored the differences and similarities, and your comment leaves so much out that it cannot even be said to be true or false.
I'd say GC is always the fastest to free objects within the main code path. Literally zero instructions.
Someone 20 hours ago [-]
> I'd say GC is always the fastest to free objects within the main code path. Literally zero instructions
True, but reference counting or free need not be far behind. They can append the pointer being freed to a per-thread list (⇒ no locking needed) that a separate thread that does the actual freeing periodically claims and then iterates over to actually free the objects.
Disadvantage is that memory usage goes up a bit because the actual freeing is delayed, but that (likely) is less so than with a garbage collector.
thomashabets2 18 hours ago [-]
Yup. I don't have to like GC to name a benefit of it. Which is good, because I don't like GC.
Java is a particularly good example of GC being bad[1], but I've also found it to be a tech debt generator in Go.
Which GC? Java is like C and C++, plenty of implementations to chose from, including reference counted implementations in the past [0], arenas and real time GC for embedded deployments [1].
People love to complain about Java without understanding the ecosystem.
I don't claim to be an expert on it, but I'm not uninformed either. Yes, I'm aware of many implementations and variations. With various talks from vendors that rant about "a mostly-pauseless GC is one that sometimes pauses!! Ours is a pauseless compacting GC".
But per my linked blog post (that you did read?) I do go into Java language problems that make GC impact worse.
The care and feeding of the Java runtime environment, entirely a self inflicted problem, that goes from selecting one and tuning ALL its parameters, kind of proves my point. It's not just knobs, but whole runtime environments. If there had been "a best one" with no knobs, that "just works", then fine. But there isn't.
pjmlp 20 minutes ago [-]
Yes, I read it, hence the reply.
Ignores that Java had escape analysis years before Go happened, granted the quality depends on which JVM is actually used, e.g. GraalVM is better than OpenJDK, and there are others to chose from.
Ironically Go designers got educated why GC knobs are relevant, and why a single GC doesn't solve all use cases.
And it doesn't need an advanced GC, so Green Tea rewrite was wasted work?
You can do off heap allocation in Java with Unsafe, JNI, ByteBuffers, and more recently Panama. This not taking into account the APIs provided by real time Java specification.
Finally with Valhalla design now being merged into the language (Java 28+) we get explicit value types, while Go still needs to rely on compiler warnings for failed escape analysis.
And the remaining Java rant could be further deconstructed.
However your blog clearly points out where you stand in regards to Java, so maybe some unwillingness to learn the ecosystem was part of it.
JackSlateur 20 hours ago [-]
GC, zero instructions: that's funny; JVM used to "stop to world" to process that zero instructions;
thomashabets2 20 hours ago [-]
I was explicitly talking about exactly one very specific part a way to implement GC.
It was very clear that I was not talking about the active parts of the garbage collection.
It's really cheap to produce garbage.
EGreg 21 hours ago [-]
It doesn't leave anything relevant out.
Java pioneered this garbage collection stuff because you had cycles of references. You don't need to have cycles. WeakRef is a much better thing now. All you need is reference counting, and you don't need any garbage collection at all. When the reference count reaches 0, you destroy the object and free up its memory. It's far more predictable than GC, too.
And GC isn't "the fastest" to free objects, it has to walk a graph. The fastest is actually arena allocation and then just dropping the whole thing. But that's exactly what owning an entire container of objects can do. If you have a doubly linked list, for example, A[n] -> A[n+1] but also A[n+1] -> A[n] but neither of those should be a strong reference to prevent reclaiming. Instead, the container of that doubly linked list should be the one having a strong reference to its items.
pjmlp 4 hours ago [-]
Lisp pionered GC, and all its flavours, followed by CLU, Smalltalk, Cedar, BASIC and all its flavours, Modula-2+, Modula-3, Oberon, Oberon-2, Component Pascal, xBase/Clipper, Standard ML, Caml Light, Objective Caml (now OCaml), Miranda, Haskell,...
Long before Java was even an idea.
thomashabets2 20 hours ago [-]
I understood your first comment without expanding on it like this. You also don't need to explain what reference counting is.
> GC isn't "the fastest" to free objects, it has to walk a graph.
No, you don't inherently need to. And what I said is that it's super duper fast to produce garbage. I did not say that actually freeing the underlying memory, or any other cleanup, was fast.
I'm not even arguing for GCs, here. I even think GC languages tend to become tech debt generators, as garbage is not addressed until it's a really complex problem with no good solutions.
pjmlp 4 hours ago [-]
Same can be said for bad algorithms and data structures, it isn't hard to make slow C when one doesn't know their stuff.
That's a strange thing to assert, having acknowledged the existence of generational GC.
> Reference counting also has its own running cost, paid on every copy of a pointer you make and every time you drop one.
isn’t 100% true. It’s not necessarily on every copy or drop. Compilers can (and do) elide reference count updates if they can proof they aren’t needed, and can even skip allocating room for reference counts if they can proof it isn’t needed (example: a local object that doesn’t escape its scope)
I also find it a miss that the article doesn’t discuss memory usage. A garbage-collected program needs more memory to match the performance of the equivalent manually managed language.
https://dl.acm.org/doi/10.1145/1094811.1094836 says you need to give it 5 times the memory, but that’s from 2005 and likely outdated.
I think you can find similar things in CPython, on the C side of things.
If we have two generations, young and old, we obviously can't simply "just collect in the young generation" — which I feel like is exactly what most generational GC descriptions say. If we only traced young objects, we could very well miss an old object pointing at a young one, collect the younger object, and now we've got a dangling pointer.
So there must be some book-keeping to avoid tracing everything (or what'd be the point of generations), but I have no idea of what that book-keeping is, or its cost.
> Show me your code and conceal your data structures, and I shall continue to be mystified. Show me your data structures, and I won't usually need your code; it'll be obvious.
Careful; just because you only collect in the new generation doesn't mean that you only trace the new generation. From my understanding a rudimentary generational GC design is to include the old generation in the GC roots so you don't need to examine everything in the new generation - if it's not reachable from the roots it's implicitly dead, and the latter category is assumed to apply to most objects in the new generation under the generational hypothesis.
Well, then I suppose you're saying the up-thread comment is wrong?
TFA:
> Every one of those pointers has to be followed on every cycle
The comment:
> That's a strange thing to assert, having acknowledged the existence of generational GC.
Which would imply that's not the case, i.e., that we're not considering every pointer in every GC sweep. (Which, again, I thought was largely the point of generational GCs: to make sweeps cheap by not considering every pointer.)
I guess if it's really the sweep that's the expensive part, then perhaps doing a full walk is fine.
> generational GC design is to include the old generation in the GC roots so you don't need to examine everything in the new generation
I'm assuming roots (stack references to objects) are separate from generations (which heap objects belong to).
I suppose if you added old objects to the set of roots, that'd also solve it, but that's the same as "every one of those pointers has to be followed on every cycle".
The sibling post thinks writes are made more expensive by tainting/young-ifying objects that get written to. In that way, we prevent an old object from ever pointing at a new one — at the cost of writes now being more than a write.
Edit: Yeah, here's [a note](https://chromium.googlesource.com/v8/v8/+/refs/heads/13.3.25...) about how Chrome implements it. There is additional book-keeping and cost to writes.
I think "every one of those pointers has to be followed on every cycle" as a blanket statement is not correct. It's true for some GC designs and not true for others.
> I'm assuming roots (stack references to objects) are separate from generations (which heap objects belong to).
Roots are just where you start tracing from. You can include older generations in them (or even subsets thereof), but you're by no means required to.
> but that's the same as "every one of those pointers has to be followed on every cycle".
Sure, but my point there was just that just collecting the new generation doesn't have to imply that you're only tracing the new generation. I guess I should have added a "necessarily" somewhere in my original comment.
> There is additional book-keeping and cost to writes.
From my understanding the bookkeeping there is effectively to be able to determine the set of roots to use when tracing/collecting the new generation.
Then if the language allows mutation of objects, special consideration has to be given to old objects that were mutated to point to new ones. You can treat those as additional roots; the graph of young objects reachable from a mutated old object is reachable. (Considered so on the assumption of the old object being reachable, which we can only disprove by doing a full scan.)
I wrote one for TXR Lisp which there are no generation heaps; but objects have a generation. In the same heap, you can have adjacent (unrelated) objects that are in different generations. Objects never move from their heap; they keep their position in the same heap over their lifetime.
The allocator therefore records the new generations in a fresh log, which serves as the nursery. When that log gets full, a pass is triggered.
Implementations with separate heaps (typically copying collectors) allocate in a nursery heap and promote objects from there, but it is conceptually similar.
In the marking phase, we do not process this nursery. We start at the usual root pointers: stack, globals and proceed with normal marking, like in a pure mark-sweep collector (or a full pass), with a small modification: whenever we hit an old gen object, we skip it. We assume that the old gen object is reachable, and every object reachable through it is similarly an old-gen object. This is where the generational algorithm wins, chopping down the graph of objects to be marked, possibly drastically so.
Where the nursery/fresh log comes in is the sweep phase. Because we know that we did not traverse any old generation objects, it would be wasteful to do a full sweep. In the case of the fresh log, we sweep just through the fresh log. Anything in the fresh log that is reachable is promoted to the old generation. Anything not reachable is reclaimed: either immediately or through the finalization treadmill, if applicable. The fresh log is then reset to empty. In the case of a nursery, we similarly just sweep through the nursery heap and promote (by copying) reachable objects to the old generation, reclaiming the rest. The nursery is empty.
There may be additional structures. Note that we have the assumption that old objects only point to old. But what if (it is allowed that) the program mutates an old object to point to a newly allocated new one? That would break the assumption. We can make the program (code generated by compiler or whatever) report whenever that happens.
In the TXR Lisp implementation of generational GC, mutation of old objects is handled via two strategies. A single value assignment of a young object to a field in an old one will cause the young object to be appended to a "check" log. In some cases, this is not practical for various reasons. For instance, an operation mutates a large number of fields of the same object (e.g. array). In such cases we add the old objects to a "mutated" log. The objects added to both arrays have their generation field reset to -1: neither young (0) nor old (1).
Both the check log and mutated log are marked during marking. The check log contains only young objects and so sweeping those is already taken care of by the freshlog, it needs not be visited during the sweep phase.
The mutated log is processed during sweep in order to reset the generations from -1 back to 1.
When the check and mutated logs fill up, GC is not triggered immediately then, but the flag is set for the next GC to be a full one. What that does is turn off the mechanism: since we know a full GC is coming, we don't have to record mutations of old objects pointing to new.
It's best to think about lifetimes and lifecycles where possible. Immutability where sensible and things like pool allocation are examples of this.
GC languages can result in quite pessimistic code because they encourage people to NOT think about what is going on. But people have also built functional HFT engines on things like the JVM by thinking about lifetimes and lifecycles.
The wide variety of options and tradeoffs, with fewer clear lines in the sand than most people seem to think, is already enough to call it a "continuum" but what really finishes the job is that they're all mixable and matchable. Something like Zig makes that really obvious, but most static languages have at least some sort of ability to mix in multiple strategies. There's nothing wrong with a C++ program that uses new & delete, and also uses arenas for some things, and also uses garbage collection for some things, and also has an integrated scripting language like Lua with its own memory strategies. Such programs are not that uncommon... that describes modern games nowadays, the supposed canonical case where you "can't afford GC". But it can... it just fences it in to a particular domain where it fits.
> The leaks that come from forgetting to free something go away entirely.
Not quite: In manually-managed and referenced counted languages with destructors, releasing resources, (open file handle, open socket, open connection to a database, ect,) happens when objects are cleaned up.
In a (tracing) garbage collected language, releasing resources is a very manual process. You might not have a memory leak, but leaking file handles or similar resources is a real problem with real consequence.
Also every single graphics application that uses Metal or DirectX, relies on reference counting as GC algorithm.
Oh shit…
Garbage collectors aren’t magical black boxes with no levers, and you can use them how you like.
You address performance problems relating to GC the same as you do anything else: measure, analyze, optimize, repeat.
Heck, there is a whole cottage profession of experts who get called into fix GC related performance issues with Unity.
A cottage industry is built around making rocks look good too. Is that an indicator that games are good or bad at making rocks?
How do you "optimize" the GC away after you wrote your entire database server in a language that uses it?
But the most naive example any language supports is simple object pooling.
Then more fancy, zero allocations tasks in C# https://github.com/cysharp/unitask
(Even though, no, that's not typical. That's a tiny minority of them.)
Once you measure, you'll find a small fraction of the code is taking a large fraction of the time. When you zoom in on trouble-spots you may find, e.g. that the GC is taking the time (or you may find something else entirely is taking the time). If it's the GC, you might look and see, e.g., that it's spending its time tracing the objects in the 100K node graph you're creating several times a second, and realize you could, e.g., create it once and simply keep reusing it. Perhaps it might be as simple as using removeAll(keepingCapacity: true) instead of removeAll() (a Swift example).
The superficial details differ, but you generally just want to understand what the GC is working so hard on and lighten its load. If you haven't been measuring and optimizing throughout, there are almost certainly easy-to-pluck, low-hanging fruits, ripe for the taking.
Where GC means any kind of GC algorithm from CS point of view.
I disagree with this. The sentence implies that this work is done in order to make the compiler happy, where my experience is that it forces the programmer to actually get it right.
I had an "aha moment" when I was frustrated at failing to express my intent to the compiler, and suddenly realised that the reason I couldn't "just say the magic words" was that my object ownership design was inherently flawed. I had to make large changes not to make the compiler happy, but to actually have a coherent design.
So no, it's not about what "the compiler can verify". That's like saying "my lawyer won't let me do this". No, your lawyer is your employee, not your boss. They're just saying that if you do this, then you may go to prison. It's not the same thing.
("unsafe" is the Rust way to go "thank you, legal department, but I'm making a business decision to take this risk. Your concern has been noted")
Let’s say you have two ways of doing the same thing: both work, both are legit and neither introduce GC bugs. The only difference between the two is that one can be verified by the compiler while the other can’t, so you are stuck with solution no. 1 although both would work.
To phrase it differently: the code that gets verified by the compiler is safe, but is all safe code verifiable by the compiler?
I’m not implying that’s the case, but that’s what I feel the author is saying.
Right. And this reduces to the halting problem, so in theory the compiler cannot know that all safe code is safe.
In practice, I'm saying that not just syntactically, but in your code's design, the compiler is more likely to be right. It's a bit like Chesterton's fence. You can bypass the lifetime checks if you just have the confidence to say "yes, I'll use `unsafe` here and it's fine because these reasons". As you're writing your "SAFETY" comment, you may very well find yourself not so confident anymore. And indeed, often this compiler-induced "stop and think" prevented you steaming ahead with a bug.
Now, the borrow checker is not perfect. I don't know how far away from "all but NP-complete cases" it is. My experience is that it's almost always right, and I've only had to put a seemingly needless "drop" statement to placate it. But they're working on it. A new one is coming: https://daily.dev/posts/rust-s-new-borrow-checker-is-coming-...
And once again this old blog post of mine comes to mind: https://blog.habets.se/2020/12/Bypassing-safety-check-for-ob...
In any case "by arranging your program in a way the compiler can verify" I think is not accurate, because the overlap between "correct" and "compiler can verify" is nearly complete, though yes the latter is a strict subset of the former. In other words I don't write Rust to make the compiler be able to verify it, but to make it correct. And nearly always that means the compiler can verify it too.
https://blog.rust-lang.org/2026/08/04/enabling-polonius-alph...
Because of this "halting problem" compromise, I prefer the approach other languages are pursuing, keeping some form of automatic memory management, while improving their type systems, like Swift, Chapel, OxCaml, Scala 3, et al are pursuing.
Haskellers say the exact same thing. :P Personally, I'd much rather get shit done and don't appreciate tools "forcing" me.
But I agree that it's must faster to get the wrong answer than the right one.
I've also had the converse experience, where I know full well that the structure I'm trying to impose is correct and quite efficient, but its part of the space that rust doesn't cover.
Rust is great. It's a noble attempt to bring a degree of correctness to a problem space that suffers from a great deal of slop. But to pretend that the model is complete, or that the design decisions that were made are perfect in every way, is just wrong. That the rust compiler and runtime can't support my construct isn't really an absolute value judgement on that idea in the first place. The rust compiler isn't really an oracle that tells you whether something is right or not in an arbitrary value system.
Still, I don't write Rust code the way I do "to make the compiler happy", but to make it correct. And sometimes it's correct to drop some "unsafe" because gosh darn it, you know it's fine this time.
And you're probably right for the cases you're thinking of, where Rust wouldn't let you (at least without unsafe). And maybe you're 99% sure about that.
But for every 100 changes we’re 99% sure won’t cause an outage, one will…
(also future changes may invalidate assumptions you relied on, of course, making it no longer true)
Do you have some examples you can share where you think Rust prevents you doing the right thing? The ones I run into tend to force me to think of the edge cases, and usually those edge cases don't even have a right answer.
ok, I have a large local container of records that I want to stream over a back pressured channel. now we clearly have a problem that the iterator needs to be long lived, and I don't really want to serialize all accesses to the collection for a streaming operation that may never terminate.
for this particular domain I don't actually care about serializability of the iterators view of the collection. I clearly don't want the container to be left in an erroneous or inconsistent state, but otherwise anything goes.
all the iterators for all the standard rust containers have lifetimes bounded by the container (batch), and because they all represent internal state, they all have to be mutable. and in this case they need to be async also.
I don't think there is an 'idiomatic' way to represent that access pattern, and it kind of necessitates writing ones own container. if there is a good answer to this I'd be curious to hear it, but I consider this one of the major personal failure modes for rust, which is 'oh, yeah, well, in order to figure that out to need to understand [long list of compiler instristic property types and runtime behaviour], which isn't super pragmatic.
since I'm here, I've already wasted words here talking about the dismal async situation, but I think more important to me as a systems programmer is the lifetime abstraction. It think its great to put a name to it and try to put rules around lifetimes - these are traditionally implicit things that we reason about _outside the program text_, and that's a real bother. however everything I do is state management, and the lifetimes of those states (files, connections, higher level sessions) don't directly correspond to the lexical calling stack. the only tools that rust gives me is Arc, which some with a whole set of busy caveats, or trying to thread several lifetimes through the entire call path - a road that I've been down and abandoned for readability and maintenance.
now you can argue that rust would prefer that I use a thread per object, and while that might be workable, that a pretty strong and side-effecting constraint to apply to all of the programs in my domain.
anyways I ended up keeping the last key issued, and for every new record, paying the logn cost to get to approximately where I was perviously. which brings up another general complaint. as imperfect as it is, sometimes I want to just stand sometime up and look at it. I don't want to spend 3 weeks coming up with sharing policies and structures that work well with rust. I want to look at it and measure it and count its defects in my head and decide what to do next. in rust I kind of have to decide up front what I'm building, and while that might be an excellent thing to encourage in some contexts, I don't think it is in all contexts.
It does sound like a thing where if you'd written this in C++, then you could have done it much easier (which is my experience), and then either also, or later on when the state of the invariants are no longer in your working memory, one of those invariants would be violated and memory start corrupting (also my experience).
E.g. in a C++ vector you can push_back() without invalidating the iterators iff there's enough capacity in the vector. Though if some code saved the "end()" iterator (e.g. concurrent for_each), that's broken. std::vector doesn't permit that use case, but does not prevent it. I prefer it being prevented.
I would consider the extra work to be worth not finding that problem in production, later.
Ideally what you want could be accomplished by just (oh no, there I go) finding a single place to punch a hole, put an "unsafe" there, and explain why it's actually fine to create some inner mutability or whatever is needed there.
The huge complexity baggage, and the amount of working memory you need to reason about async, is unfortunate though, and I won't defend it. But at least it fails closed if you get it wrong.
I'd say GC is always the fastest to free objects within the main code path. Literally zero instructions.
True, but reference counting or free need not be far behind. They can append the pointer being freed to a per-thread list (⇒ no locking needed) that a separate thread that does the actual freeing periodically claims and then iterates over to actually free the objects.
Disadvantage is that memory usage goes up a bit because the actual freeing is delayed, but that (likely) is less so than with a garbage collector.
Java is a particularly good example of GC being bad[1], but I've also found it to be a tech debt generator in Go.
[1] A rant, which touches on GC stuff: https://blog.habets.se/2022/08/Java-a-fractal-of-bad-experim...
People love to complain about Java without understanding the ecosystem.
[0] - https://www.cs.utexas.edu/~mckinley/papers/rcix-oopsla-2013....
[1] - PTC and Aicas
But per my linked blog post (that you did read?) I do go into Java language problems that make GC impact worse.
The care and feeding of the Java runtime environment, entirely a self inflicted problem, that goes from selecting one and tuning ALL its parameters, kind of proves my point. It's not just knobs, but whole runtime environments. If there had been "a best one" with no knobs, that "just works", then fine. But there isn't.
Ignores that Java had escape analysis years before Go happened, granted the quality depends on which JVM is actually used, e.g. GraalVM is better than OpenJDK, and there are others to chose from.
Ironically Go designers got educated why GC knobs are relevant, and why a single GC doesn't solve all use cases.
And it doesn't need an advanced GC, so Green Tea rewrite was wasted work?
You can do off heap allocation in Java with Unsafe, JNI, ByteBuffers, and more recently Panama. This not taking into account the APIs provided by real time Java specification.
Finally with Valhalla design now being merged into the language (Java 28+) we get explicit value types, while Go still needs to rely on compiler warnings for failed escape analysis.
And the remaining Java rant could be further deconstructed.
However your blog clearly points out where you stand in regards to Java, so maybe some unwillingness to learn the ecosystem was part of it.
It was very clear that I was not talking about the active parts of the garbage collection.
It's really cheap to produce garbage.
Java pioneered this garbage collection stuff because you had cycles of references. You don't need to have cycles. WeakRef is a much better thing now. All you need is reference counting, and you don't need any garbage collection at all. When the reference count reaches 0, you destroy the object and free up its memory. It's far more predictable than GC, too.
And GC isn't "the fastest" to free objects, it has to walk a graph. The fastest is actually arena allocation and then just dropping the whole thing. But that's exactly what owning an entire container of objects can do. If you have a doubly linked list, for example, A[n] -> A[n+1] but also A[n+1] -> A[n] but neither of those should be a strong reference to prevent reclaiming. Instead, the container of that doubly linked list should be the one having a strong reference to its items.
Long before Java was even an idea.
> GC isn't "the fastest" to free objects, it has to walk a graph.
No, you don't inherently need to. And what I said is that it's super duper fast to produce garbage. I did not say that actually freeing the underlying memory, or any other cleanup, was fast.
I'm not even arguing for GCs, here. I even think GC languages tend to become tech debt generators, as garbage is not addressed until it's a really complex problem with no good solutions.