14 ms·

I built a garbage collector for a language that doesn’t need one

320 points by claytonwramsey 3y ago

SeniorMars 3y ago
Honestly, this is a very cool project. I would suggest you publish this as a formal paper to a pl journal.
senkora 3y ago
Always remember: a garbage collector is a theorem prover that proves that objects are unreachable, over and over, so that they can be destroyed. It is in general undecidable whether an object is unreachable, but we can get good performance with heuristics.
- convolvatron 3y ago
  I'm not sure this is right. the classic gc approach is dynamic, not static, and it discovers the reachable set, not the unreachable one. please elaborate?
  - Filligree 3y ago
    There's garbage collection algorithms that do one, the other, or a combination. It depends mostly on what constraints you have, though yes, high-performance GC mostly looks for the reachable set.
- KRAKRISMOTT 3y ago
  Why is it undecidable? Is it not just a graph traversal/coloring problem?
  - zer8k 3y ago
    To put it simply it's very difficult to determine what objects (in the C term) are garbage. Hence why we have things like reference counting. We need extra data to hint to the collector what is, in fact, garbage.
    - bruce343434 3y ago
      Okay, so you need to set up some scaffolding/bookkeep some metadata. Still not impossible.
      - papruapap 3y ago
        No an expert, but afaik the problem is not the complexity but the performance cost.
        robertlagrant 3y ago
        Sure, but that's not "undecidable"?
        hypertele-Xii 3y ago
        Technically the halting problem is a performance cost issue, because you can always tell whether a program stops by just running it. The performance cost is having to actually run it and wait and see, rather than find some quicker way to the answer.
        myk9001 3y ago
        I don't think it can be boiled down to a performance cost issue. If a program is going to run forever, how do you measure the forever has passed to conclude the program doesn't halt?
        hypertele-Xii 3y ago
        By waiting forever. I understand that "forever" is a nebulous term, but it works both ways. We both know that no computer program could actually run forever.
        myk9001 3y ago
        > I understand that "forever" is a nebulous term, but it works both ways. So, at what point in time the person who is observing a running program is going to declare it doesn't halt? What if they conclude the program doesn't halt, just for it to actually complete execution the very next second? In practical terms, that's why we have timeouts. And in some cases relying on a reasonable timeout is fundamentally the best we can do -- exactly because we can't deterministically answer if a program ever halts. > We both know that no computer program could actually run forever. No program can actually run forever, of course. But any program will stop eventually due to external factors -- me hitting Ctrl + C or pulling the power plug or whatever. The halting problem asks whether it's possible to tell if a program will ever stop or not according to its internal logic. Here's a (likely dumb) analogy off the top of my head regarding a program stopping due to external reasons. Imagine, I toss a coin, lightning strikes and evaporates the coin while its midair. Do I get to say it was heads or tails? Guess, it's impossible to claim either way.
  - fweimer 3y ago
    The case that arises quite often in practice is when a reference is retained, but can only be used on an error path (e.g., as part of an exception). The error condition may not ever happen due to the way to code is written, but it's unlikely the garbage collector can prove that except in the simplest possible cases. Usually, it is acceptable to do a conservative approximation of the actual lifetime, and blame space leaks on the programmer. Garbage collectors usually also make assumptions in the other direction (a non-conservative approximation) when it comes to finalizable resources (e.g., file descriptors). These uses do not involve the reference that is visible to the collector. This gives us Reference.reachabilityFence(), and again mistakes are blamed on the programmer.
- raincole 3y ago
  It's not. You're describing a static analyzer that inserts free() automatically. Not GC. GC is pretty much the opposite. Edit: Well, I didn't think it through. You're correct. A "perfect GC" is indeed undecidable, and all the real world, practical GC have "false positive" (a piece of memory is no longer used by the code, but there is no way to know it). A perfect GC without false positive is equal to halting problem. Example: var obj = new Object(); // === real code begin ... 50 lines of real code that never uses obj if (something == true) return; ... another 50 lines of real code that never uses obj // === real code end obj.doThings(); A perfect GC can release obj while the real code is running. A real world, imperfect GC can't, since whether the real code returns early or not is undecidable.
  - lisper 3y ago
    > You're correct. No, s/he's not. The original claim was: > It is in general undecidable whether an object is UNREACHABLE. [Emphasis added] Being unreachable is not the same thing as being "no longer used by the code". The latter is indeed undecidable, but the former is not.
  - chubot 3y ago
    After writing a garbage collector, I can say that I’ve seen the unreachable / “will never be used” distinction, and it’s more or less irrelevant trivia. It doesn’t help you write a garbage collector to think of it that way. It doesn’t provide insight into the problem. The problems are elsewhere. Focus on reachability, dynamic understanding of the heap, performance, etc.
    - nomel 3y ago
      > more or less irrelevant trivia What are some cases? The only I can think of is if a "remote" thing owned the memory. For example, if I sent a pointer elsewhere, then reused it later. Like, maybe with a device driver, or library.
  - monocasa 3y ago
    You normally fix that not with the GC itself, but with the compiler. If new Object() truly doesn't have any effects visible other than the valid reference, then it's creation can be moved to after the if statement.
- aatd86 3y ago
  I'll join the others in trying to bring up a nuance. The issue is not necessarily unreachability being undecidable. The issue is that reachability depends on control flow. And that implies being conservative which translates into having to deal with false positives. That static analysis in a nutshell: how to get precision and soundness. Probably a mere question of terminology.
- deleted 3y ago
  [deleted]
- 3cats-in-a-coat 3y ago
  Empirically what you say can't be the case, because if it's "undecidable" then one of these must be true: 1. The GC frees objects that could be reachable (program gets corrupted in spectacular ways). 2. The GC never frees anything (as it can't decide). The GC may not dispose of objects immediately, but when it determines they're not reachable, they're not reachable, period. There's nothing undecidable about it.
  - hashmash 3y ago
    It's undecidable when you consider the possibility that the program won't ever attempt to access an object. A tracing collector plays it safe and assumes such objects might still be accessed at some point. In GC languages you'll often see deliberate null assignments in order to allow the collector to clean up objects sooner.
    - 3cats-in-a-coat 3y ago
      Reachable/accessible and reached/accessed are different things, why are we talking about it as if it's the same thing? One is a potential eventuality, the other is an event. GC are concerned with the potential eventuality, which is 100% decidable, not with the latter, that was never under discussion. To say "reachability is undecidable" means you can't decide whether you MAY or MAY NOT reach it. Which is wrong. You can decide whether you MAY or MAY NOT reach it. And if you MAY NOT... then that's 100% unreachable and safe to collect.
- munificent 3y ago
  It's easily decidable whether a given GC object could be reached. What isn't decidable is whether a it will be used in the future. The conservative approximation that GC's make is that they keep all objects that could be accessed in the future by the program (reach-able) instead of only keeping the objects that will be used in the future. A trivial example is: void main() { var obj = new Object(); while (true) { // Do other work... if (dayOfWeek == 9) { print(obj); } } } Since there are only seven days in the week, that `print()` statement will never be reached, and an optimal GC would free obj. But the GC can't determine that. All it knows is that it could possibly be reached, so the object stays in memory.
  - cozzyd 3y ago
    https://en.wikipedia.org/wiki/French_Republican_calendar https://en.wikipedia.org/wiki/French_Republican_calendar
convolvatron 3y ago
after spending the requisite time trudging through the lifetime swamp (I couldn't couldn't imagine running my whole life on the stack), and seeing all the nice things about rust, I couldn't help but thinking at the end 'this would be a really nice language if it were garbage collected'. of course you can't say that. this is nice
- pjmlp 3y ago
  That language is called OCaml.
  - galangalalgol 3y ago
    OCaml doesn't have a borrow checker (yet). I'm sold on having a borrow checker, not just for memory, but for io of any sort. I'm not sure what adding GC to a borrow-checked language allows for other than catching self referencing but unreachable loops? I definitely think a language that has room for abstractions that aren't zero cost, while still having a borrow-checker makes sense. Using rust to make that language also makes sense. I think implementing a vm or interpreter entirely in safe rust would effectively force borrow checking on the resultant language wouldn't it? Ruby seems like a good place to start the experiment. I'd prefer it end up with something more like julia or python just for my own use cases.
    - pjmlp 3y ago
      OP was asking for a language like Rust, using a GC instead, duh! As for having both, I rather take Swift memory ownership or Linear Haskell approach, or even D/C#/Nim/Go. The productivity of automatic memory management, with the tooling to go low level C and C++ style, if and when it is really needed.
      - galangalalgol 3y ago
        I would have considered the borrow checker and zero cost abstractions to be rusts defining characteristics, so ocaml isn't anything like rust except some syntax and that they are both multi-paradigm. And then my point is that as the author points out, you don't really need a GC if you have a borrow checker. If you want a language with few costly abstractions, but with a GC, go or D come to mind I guess? But the borrow checker is such a big piece of rust I don't really consider those similar languages either. If the idea is for a safe but more ergonomic language at the cost of performance, I think you'd be focused on making clone and copy implicit when a move doesn't work, getting rid of explocit borrows/references, and perhaps figuring out mutability without needing to annotate it. The absolute type safety is probably the biggest speedbump I hit in daily usage though, not the borrow-checker. A strong but duck/dynamic type system might solve that?
bfeynman 3y ago
Having some marine background the first sentence confused me, I didn't realize people use the crab mascot for rust so much to use evolutionary terms. But there is already a term for the "opposite" of carcinization, it's just decarcinization. This analogy can come full circle if the next variant of this language uses the coconut crab or a hermit crab as its mascot.
- gabereiser 3y ago
  You hear that crab-lang? :D Decarcinization is the correct opposite of carcinization. Hermit crab would be the perfect mascot in both function and metaphor.
chc4 3y ago
Nice blog post! I also wrote a concurrent reference counted cycle collector in Rust (https://github.com/chc4/samsara https://github.com/chc4/samsara, https://redvice.org/2023/samsara-garbage-collector/ https://redvice.org/2023/samsara-garbage-collector/) though never published it to crates.io. It's neat to see the different choices that people made implementing similar goals, and dumpster works pretty differently from how I did it. I hit the same problems wrt concurrent mutation of the graph when trying to count in-degree of nodes, or adding references during a collection - I didn't even think of doing generational references and just have a RwLock...
- claytonwramsey 3y ago
  That's really cool! Thanks for the kind words. I remember peeking at it while hunting for collectors to benchmark against.
- nextaccountic 3y ago
  Why not publish to crates.io? This seems useful
  - chc4 3y ago
    Honest answer is mostly that I forgot; there was one more small TODO that I needed to fix before I wanted to publish it, and then I got busy and forgot about it.
    - nextaccountic 3y ago
      You can always publish unfinished crates as 0.0.1 version 0.0.x crates are special in that they can have breaking changes even in minor versions (so 0.0.1 isn't compatible with 0.0.2), so they convey a level of stability that is even less than a typical 0.1.x crate
      - rezonant 3y ago
        More generally, this is just semantic versioning. The first non-zero position is considered to have "major" impact, the following number is then a "minor" impact. https://docs.rs/semver/latest/semver/ https://docs.rs/semver/latest/semver/
ajani 3y ago
> If carcinization happens when languages evolve to be more like Rust, then what do you call it when Rust evolves to be more like Java? Caffeination? Surely oxidation is better than carcinization. And rust evolving to Java would be mineralization? Or maybe germination?
- jakear 3y ago
  Eh, carcinization is a better ontological fit. Many separate things evolving into the same structure, versus the process of losing electrons and/or structurally degrading.
- OJFord 3y ago
  And it's the version I've actually heard used (multiple times) before now - having looked up 'carcinisation', I assume that comes via 'rustacean' (cf. crustacean), which makes it a bit more contrived and then sort of implies the result is a Rust developer, not Rust itself? Makes more sense to me that a language/framework/etc. would 'oxidise' to Rust, and someone learning/getting hooked on Rust would 'carcinise'. But this is all silly and doesn't matter anyway, ha!
  - Tyr42 3y ago
    The rust mascot Ferris is a crab. Like how go has a gopher.
    - munificent 3y ago
      And, of course, the name "Ferris" comes from being a homophone of "ferrous".
      - andyferris 3y ago
        And not only a homophone - they have the same etymology.
    - OJFord 3y ago
      Has that existed since day 1? I don't think I've ever seen that before. The gear icon comes to mind, not a crab.
loeg 3y ago
> box_ref.tag.store(COLLECTING_TAG.load(Ordering::Release)) Is it just me or do release semantics not make sense for a load? Release is for stores (I'm coming from the C/C++ atomics model). Hm, the docs[1] say a Release load will panic: > Panics if order is Release or AcqRel. Maybe just a blog transcription typo for tag.store(TAG.load(Relaxed), Release). [1]: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html#method.load https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize...
- claytonwramsey 3y ago
  This is correct, thank you. I'll fix it shortly.
teleforce 3y ago
Personally I think D language got it right when it makes GC as a default but still allows for no GC whenever applicable thus keeping most of the language relatively safe, easier to grok and more Pythonic compared to Rust. It will be very interesting to survey how many Rust implementations nowadays do away with memory safety [1]. Not sure if the author of the article referred to this seminal paper on Rust for GC for his GC implementation for Rust in Rust [2]. [1] What is a safe programming language? https://cs.stackexchange.com/questions/93798/what-is-a-safe-programming-language https://cs.stackexchange.com/questions/93798/what-is-a-safe-... [2] Rust as a Language for High Performance GC Implementation: https://users.cecs.anu.edu.au/~steveb/pubs/papers/rust-ismm-2016.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/rust-ismm-...
- loeg 3y ago
  You would think that if D "got it right," it would have seen a tenth the excitement / engagement Rust does. The proof is kind of in the pudding?
  - Jtsummers 3y ago
    > You would think that if D "got it right," it would have seen a tenth the excitement / engagement Rust does. Why? Excitement doesn't always follow correctness or even "goodness" (whatever that means in context), even if we'd like it to. Fashion and marketing matter more when it comes to excitement.
    - loeg 3y ago
      I think they're very correlated!
      - cozzyd 3y ago
        counterpoint, PHP?
  - crabbone 3y ago
    It's very naive to think that language popularity correlates with engineering merits... I worked very little with D, and a lot more with Rust. I cannot really speak to the qualities of D because, by and large, I dealt with a very few instances of it, and only at the interface level (mostly writing in another language). But, in terms of fame and popularity -- Rust developers and backers put a ton of effort into promoting the language. There were times when every other week there would be an article in some popular tech. media source from all kinds of "big names" about how Rust is superior to something (usually C++). There were massive efforts made to create a self-sustained community of Rust-evangelists who'd go and spread the word to the heathens... I haven't been around to witness the birth of D and don't remember if it had any kind of adoption campaign, but from what I can tell, even if it had a campaign, it didn't succeed. Now, here's another example from the same category of languages: Ada (esp. with Spark). I'm not very knowledgeable about it, but from the little I know, there are a lot of good reasons to prefer Spark over Rust. At least, on engineering merits, they should be roughly equivalent. But, in terms of popularity, Rust beats Spark by a lot.
zengid 3y ago
This is really impressive work and I applaud the author for building something that I'm sure lots of folks will find interesting and possibly very useful, but I want to say that I think there's a reason reference semantics (using and sharing heap allocations) are hard in Rust: It's because references are just plain hard to use safely. Rust tries to make the gnarly things awkward, but what is the easy path? If you look at the Hylo (formerly Val as of 3 days ago) language [0] that folks like Dave Abrahams have been working on, they're outright saying to just not use reference semantics if you can avoid it. In this talk at CppCon about Value Semantics, Dave argues that we should be decoupling object graphs from access to objects [1]. That's right folks, using `usize` indexes into collections, or adjacency lists, isn't just a hack to get around the borrow checker as people like Jonathan Blow have famously critiqued [2], it may just be the right way of doing things. [0] https://www.hylo-lang.org https://www.hylo-lang.org [1] https://youtu.be/QthAU-t3PQ4?t=2354 https://youtu.be/QthAU-t3PQ4?t=2354 [2] https://www.youtube.com/watch?v=4t1K66dMhWk https://www.youtube.com/watch?v=4t1K66dMhWk
- claytonwramsey 3y ago
  I know of a lot of people trying to do "arena" GC in Rust using integer indices. I think that's an excellent approach, but it does mean you have to pass in the arena as a resource to every single function which produces an allocation. This isn't even necessarily a bad thing - the net result is a lot like Zig's allocator API. I know there's a nontrivial overhead to using index-based references, especially since CPUs can't easily predict load operations. This gives me an idea: create a CPU architecture where pointers are actually (object, offset) tuples, enabling better on-metal performance with index-based references. I've neither the time, money, expertise, nor energy to implement such a thing, but it would be really cool if it existed - maybe CHERI is a close approximation, though I haven't looked very closely at it.
  - gpderetta 3y ago
    > it does mean you have to pass in the arena as a resource to every single function which produces an allocation Implicit arguments! I'm more and more convinced that this form of controlled dynamic scoping dynamic scoping should be embraced by more languages. > create a CPU architecture where pointers are actually (object, offset) tuples Segments might yet see a renaissance (and CHERI might be indeed be a form of it).
3cats-in-a-coat 3y ago
I think GC is a very cool set of algorithms that have their place for collecting detached elements of a graph. But in a programming language, the baseline memory model should not be a graph in the first place.
- claytonwramsey 3y ago
  That's an interesting idea. Can you clarify some more on what the baseline memory model should be, if not a graph?
  - 3cats-in-a-coat 3y ago
    I don't want to impose what it should be, as I'm asking myself this question every day. But I can list a few thoughts. The actual memory model is (seemingly) a flat address space, in which processes allocate segments, and everything else arises from there. There's some remapping behind the scenes, some segments are shared, some not, but this is beside the point. And a pattern I see often is arena allocation, where you allocate a large segment and then "virtually" allocate smaller segments inside, down to individual scalar variables. This can happen several times with a lot of memory, but tends to be shallow. For this and many other reasons, I see mutable memory is best structured as a tree, a shallow tree, almost relational, but still permitting nesting, where every item has one owner, one caller, and anything else is routed through that tree. Of course once this semantic model is established, you can reduce and optimize many calls into more direct calls. But you get clear intercept points when you need to decorate, block, remap and so on behaviors in the system. No "action from distance" surprises. Everything should be pass by copy. For larger structures, we need copy-on-write optimization. Which means underneath the mutable tree there is a Directed Acyclic Graph of immutable segments supporting copy-on-write. This is also not new, it's how forking works on Unix for example. Every modern OS utilizes copy-on-write on the file system, in memory, it's also utilized, if we think about it, in network caching systems. But to the process it looks like normal flat address space, where everyone owns their own copy of the content. For collecting unused segments in COW you'd naively need refcounting. There are other approaches that borrow from GC algorithms, in a much simpler and more performant way, because, well, there are no cycles in a DAG. The best part is that once you decide to use copy semantics, you have a plethora of algorithms at your disposal to try and switch between adaptively (including... just copying the thing if it's small enough, which turns out is the fastest approach), while maintaining the same exact semantics for the programmer who doesn't have to care how it works under the hood. Another benefit of copy semantics is that things are copied between processes, or especially between machines in a network, and now your language locally has the same semantics as when it talks to the network, which removes barriers and unifies interfaces. "Write once, run at any scale" if you will. Anyway, this is not comprehensive. And just my opinion. But the problem with graphs is that it is the data structure with least discipline, and most complications. And in most cases those complications do not pay off. Not only they require complex GC, but they result in heavily entangled code, tons of shared mutable state, that gave the whole OOP space a bad name (that it doesn't deserve). This was never a problem with objects, because objects were never supposed to share mutable state. It's a problem of graphs and handles, a system that pretends everyone "has" a mutable piece of state... which it doesn't have, as ownership must be exclusive to be reliable. Discipline of dependency management (packages etc.) often removes cycles and results in a tree or a DAG. This is not coincidental. And there's no reason we can't replicate this at the lower levels to individual objects. Of course, we still need graphs. But not everywhere, and not all the time.
nicechianti 3y ago
[dead]
MatthiasPortzel 3y ago
I’m not a Rust programmer, but I’ve heard Rust has compile-time AST macros. I wonder if it would be possible to implement a Rust GC by defining a macro to tag garbage collected sections of code. The macro expansion could then insert cycle-checks on moves as described early in the post. I have no intuition for how performance would compare to the trait-based approach that the author went with.
- claytonwramsey 3y ago
  In Rust, macros work at the tokenization level. Making a macro do that would require the macro to fully parse and analyze the syntax tree - possible, but not very efficient. Additionally, there's no guardrail to enforce that the user doesn't move a `Gc` anyway.
- chubot 3y ago
  IME a lot of people want some kind of help from the compiler when writing a GC, but there is the fundamental static vs. dynamic problem. Heap integrity / reachability is a dynamic property of a running program, and so all the static solutions basically end up as half-measures. (I imagine this would include using macros, though I don't know exactly what you mean), FWIW this is my experience - https://www.oilshell.org/blog/2023/01/garbage-collector.html https://www.oilshell.org/blog/2023/01/garbage-collector.html Take it with however many grains of salt, but I heard many static solutions proposed, and they're all "wrong" for the simple reasons in theory of computation. Also, Rust's static memory management inherently clashes a bit with dynamic memory management. That's also a fundamental thing, and you can have a bazillion mechanisms to ameloriate it for some cases (which may be valuable), but the problem will still be there no matter what.
- 1letterunixname 3y ago
  Yeap. 2 flavors: procedural and pattern matching. Even the build can be scripted in Rust. And there is constant evaluation. https://doc.rust-lang.org/reference/const_eval.html https://doc.rust-lang.org/reference/const_eval.html Rust already has precise heap allocations with Box and Rc/Arc without the need for GC. GC implies uncomputed heap allocation liveness deferring work until later.
webkike 3y ago
I’ve recently been looking at this space for using a Gc smart pointer in a language I’ve been writing. It’s extremely useful - you can integrate builtins and external functions very cleanly
tayistay 3y ago
Is this essentially the "cyclic reference counting" algorithm from the Garbage Collection Handbook [1], Chapter 5, Algorithm 5.5? [1] https://gchandbook.org https://gchandbook.org
e_y_ 3y ago
As I understand it, Rust originally had support for garbage collected objects. It was removed because the community avoided it as a general practice to ensure that libraries could work without the optional GC runtime, due to its popularity as a systems language. https://web.archive.org/web/20130607161259/http://pcwalton.github.io/blog/2013/06/02/removing-garbage-collection-from-the-rust-language/ https://web.archive.org/web/20130607161259/http://pcwalton.g...
- 1letterunixname 3y ago
  Yeap. Vec, String, Box, format!, and println! all depend on alloc for heap allocations. If an allocator is provided, alloc can be used in no_std. For format!, there are alternatives such as providing a fixed u8 buffer. It's quite amazing what can be accomplished without alloc.
celeritascelery 3y ago
This looks very cool! Thank you for sharing. I find GC's in rust particularly fascinating. So if I understand correctly, every time a Gc drops you add it a hashmap and then periodically, you run through all Gc's in that map and trace all their children to see if they are part of a cycle? I still don't understand how this would work without knowing the rootset. Just because something is part of a cycle doesn't tell you if it is inaccessible. There must be something here that I am missing.
kmeisthax 3y ago
I'm going to point out one potential footgun with your library: circularly-linked Drops. If you have values A and B, both instances of T that implement Drop and hold a Gc<T> to one another, then either A sees a dropped B or B sees a dropped A, and you get UB. Technically this isn't a problem because you already marked it as an unsafe trait, but your documentation should also mention this problem. You have a safe derive macro for Collectable, however, so it needs to reject Drop. This is possible with some weird macro magic[0]. For those wondering, while Python doesn't have UB, it used to enforce the same rules until PEP 442[1]. Circularly linked garbage that implemented __del__ would instead get stored in sys.gc.garbage and you'd have to go in there and break references on __del__ types. However, native code objects will actually still trigger this behavior[2] presumably to avoid UB. I have no clue if Java finalizers need to worry about this. [0] In Ruffle we use gc_arena as our garbage collector. It enforces no_drop in it's Collect derive macro. See: https://github.com/kyren/gc-arena/blob/master/src/gc-arena-derive/src/lib.rs https://github.com/kyren/gc-arena/blob/master/src/gc-arena-d... Actually, I lied: no_drop is one of two safe constraints you can use Collect with. The alternative is require_static, which only works because gc_arena treats the entire GC heap as a data structure that is owned and has a lifetime that all Gc pointers borrow. This doesn't work for dumpster, though, so ignore it. [1] https://peps.python.org/pep-0442/ https://peps.python.org/pep-0442/ [2] https://docs.python.org/3/library/gc.html#gc.garbage https://docs.python.org/3/library/gc.html#gc.garbage
- appplication 3y ago
  This comment would be significantly improved by fully spelling out what UB is at least once.
  - kmeisthax 3y ago
    Undefined behavior means the compiler will rewrite your program in ways that do not follow from the meaning of the source code. This means things like conditions and guards just disappearing, code being reordered in ways that don't make sense, and so on. All of the safety guarantees of Rust go out the window once UB is triggered, because everything goes out the window. Which is why Rust is designed so that safe code can't trigger UB. But unsafe code still has to worry about it.

Honestly, this is a very cool project. I would suggest you publish this as a formal paper to a pl journal.

Always remember: a garbage collector is a theorem prover that proves that objects are unreachable, over and over, so that they can be destroyed. It is in general undecidable whether an object is unreachable, but we can get good performance with heuristics.

convolvatron 3y ago
I'm not sure this is right. the classic gc approach is dynamic, not static, and it discovers the reachable set, not the unreachable one. please elaborate?
- Filligree 3y ago
  There's garbage collection algorithms that do one, the other, or a combination. It depends mostly on what constraints you have, though yes, high-performance GC mostly looks for the reachable set.
KRAKRISMOTT 3y ago
Why is it undecidable? Is it not just a graph traversal/coloring problem?
- zer8k 3y ago
  To put it simply it's very difficult to determine what objects (in the C term) are garbage. Hence why we have things like reference counting. We need extra data to hint to the collector what is, in fact, garbage.
  - bruce343434 3y ago
    Okay, so you need to set up some scaffolding/bookkeep some metadata. Still not impossible.
    - papruapap 3y ago
      No an expert, but afaik the problem is not the complexity but the performance cost.
      - robertlagrant 3y ago
        Sure, but that's not "undecidable"?
        hypertele-Xii 3y ago
        Technically the halting problem is a performance cost issue, because you can always tell whether a program stops by just running it. The performance cost is having to actually run it and wait and see, rather than find some quicker way to the answer.
        myk9001 3y ago
        I don't think it can be boiled down to a performance cost issue. If a program is going to run forever, how do you measure the forever has passed to conclude the program doesn't halt?
        hypertele-Xii 3y ago
        By waiting forever. I understand that "forever" is a nebulous term, but it works both ways. We both know that no computer program could actually run forever.
        myk9001 3y ago
        > I understand that "forever" is a nebulous term, but it works both ways. So, at what point in time the person who is observing a running program is going to declare it doesn't halt? What if they conclude the program doesn't halt, just for it to actually complete execution the very next second? In practical terms, that's why we have timeouts. And in some cases relying on a reasonable timeout is fundamentally the best we can do -- exactly because we can't deterministically answer if a program ever halts. > We both know that no computer program could actually run forever. No program can actually run forever, of course. But any program will stop eventually due to external factors -- me hitting Ctrl + C or pulling the power plug or whatever. The halting problem asks whether it's possible to tell if a program will ever stop or not according to its internal logic. Here's a (likely dumb) analogy off the top of my head regarding a program stopping due to external reasons. Imagine, I toss a coin, lightning strikes and evaporates the coin while its midair. Do I get to say it was heads or tails? Guess, it's impossible to claim either way.
- fweimer 3y ago
  The case that arises quite often in practice is when a reference is retained, but can only be used on an error path (e.g., as part of an exception). The error condition may not ever happen due to the way to code is written, but it's unlikely the garbage collector can prove that except in the simplest possible cases. Usually, it is acceptable to do a conservative approximation of the actual lifetime, and blame space leaks on the programmer. Garbage collectors usually also make assumptions in the other direction (a non-conservative approximation) when it comes to finalizable resources (e.g., file descriptors). These uses do not involve the reference that is visible to the collector. This gives us Reference.reachabilityFence(), and again mistakes are blamed on the programmer.
raincole 3y ago
It's not. You're describing a static analyzer that inserts free() automatically. Not GC. GC is pretty much the opposite. Edit: Well, I didn't think it through. You're correct. A "perfect GC" is indeed undecidable, and all the real world, practical GC have "false positive" (a piece of memory is no longer used by the code, but there is no way to know it). A perfect GC without false positive is equal to halting problem. Example: var obj = new Object(); // === real code begin ... 50 lines of real code that never uses obj if (something == true) return; ... another 50 lines of real code that never uses obj // === real code end obj.doThings(); A perfect GC can release obj while the real code is running. A real world, imperfect GC can't, since whether the real code returns early or not is undecidable.
- lisper 3y ago
  > You're correct. No, s/he's not. The original claim was: > It is in general undecidable whether an object is UNREACHABLE. [Emphasis added] Being unreachable is not the same thing as being "no longer used by the code". The latter is indeed undecidable, but the former is not.
- chubot 3y ago
  After writing a garbage collector, I can say that I’ve seen the unreachable / “will never be used” distinction, and it’s more or less irrelevant trivia. It doesn’t help you write a garbage collector to think of it that way. It doesn’t provide insight into the problem. The problems are elsewhere. Focus on reachability, dynamic understanding of the heap, performance, etc.
  - nomel 3y ago
    > more or less irrelevant trivia What are some cases? The only I can think of is if a "remote" thing owned the memory. For example, if I sent a pointer elsewhere, then reused it later. Like, maybe with a device driver, or library.
- monocasa 3y ago
  You normally fix that not with the GC itself, but with the compiler. If new Object() truly doesn't have any effects visible other than the valid reference, then it's creation can be moved to after the if statement.
aatd86 3y ago
I'll join the others in trying to bring up a nuance. The issue is not necessarily unreachability being undecidable. The issue is that reachability depends on control flow. And that implies being conservative which translates into having to deal with false positives. That static analysis in a nutshell: how to get precision and soundness. Probably a mere question of terminology.
deleted 3y ago
[deleted]
3cats-in-a-coat 3y ago
Empirically what you say can't be the case, because if it's "undecidable" then one of these must be true: 1. The GC frees objects that could be reachable (program gets corrupted in spectacular ways). 2. The GC never frees anything (as it can't decide). The GC may not dispose of objects immediately, but when it determines they're not reachable, they're not reachable, period. There's nothing undecidable about it.
- hashmash 3y ago
  It's undecidable when you consider the possibility that the program won't ever attempt to access an object. A tracing collector plays it safe and assumes such objects might still be accessed at some point. In GC languages you'll often see deliberate null assignments in order to allow the collector to clean up objects sooner.
  - 3cats-in-a-coat 3y ago
    Reachable/accessible and reached/accessed are different things, why are we talking about it as if it's the same thing? One is a potential eventuality, the other is an event. GC are concerned with the potential eventuality, which is 100% decidable, not with the latter, that was never under discussion. To say "reachability is undecidable" means you can't decide whether you MAY or MAY NOT reach it. Which is wrong. You can decide whether you MAY or MAY NOT reach it. And if you MAY NOT... then that's 100% unreachable and safe to collect.
munificent 3y ago
It's easily decidable whether a given GC object could be reached. What isn't decidable is whether a it will be used in the future. The conservative approximation that GC's make is that they keep all objects that could be accessed in the future by the program (reach-able) instead of only keeping the objects that will be used in the future. A trivial example is: void main() { var obj = new Object(); while (true) { // Do other work... if (dayOfWeek == 9) { print(obj); } } } Since there are only seven days in the week, that `print()` statement will never be reached, and an optimal GC would free obj. But the GC can't determine that. All it knows is that it could possibly be reached, so the object stays in memory.
- cozzyd 3y ago
  https://en.wikipedia.org/wiki/French_Republican_calendar https://en.wikipedia.org/wiki/French_Republican_calendar

convolvatron 3y ago

after spending the requisite time trudging through the lifetime swamp (I couldn't couldn't imagine running my whole life on the stack), and seeing all the nice things about rust, I couldn't help but thinking at the end 'this would be a really nice language if it were garbage collected'. of course you can't say that. this is nice

pjmlp 3y ago
That language is called OCaml.
- galangalalgol 3y ago
  OCaml doesn't have a borrow checker (yet). I'm sold on having a borrow checker, not just for memory, but for io of any sort. I'm not sure what adding GC to a borrow-checked language allows for other than catching self referencing but unreachable loops? I definitely think a language that has room for abstractions that aren't zero cost, while still having a borrow-checker makes sense. Using rust to make that language also makes sense. I think implementing a vm or interpreter entirely in safe rust would effectively force borrow checking on the resultant language wouldn't it? Ruby seems like a good place to start the experiment. I'd prefer it end up with something more like julia or python just for my own use cases.
  - pjmlp 3y ago
    OP was asking for a language like Rust, using a GC instead, duh! As for having both, I rather take Swift memory ownership or Linear Haskell approach, or even D/C#/Nim/Go. The productivity of automatic memory management, with the tooling to go low level C and C++ style, if and when it is really needed.
    - galangalalgol 3y ago
      I would have considered the borrow checker and zero cost abstractions to be rusts defining characteristics, so ocaml isn't anything like rust except some syntax and that they are both multi-paradigm. And then my point is that as the author points out, you don't really need a GC if you have a borrow checker. If you want a language with few costly abstractions, but with a GC, go or D come to mind I guess? But the borrow checker is such a big piece of rust I don't really consider those similar languages either. If the idea is for a safe but more ergonomic language at the cost of performance, I think you'd be focused on making clone and copy implicit when a move doesn't work, getting rid of explocit borrows/references, and perhaps figuring out mutability without needing to annotate it. The absolute type safety is probably the biggest speedbump I hit in daily usage though, not the borrow-checker. A strong but duck/dynamic type system might solve that?

bfeynman 3y ago

Having some marine background the first sentence confused me, I didn't realize people use the crab mascot for rust so much to use evolutionary terms. But there is already a term for the "opposite" of carcinization, it's just decarcinization. This analogy can come full circle if the next variant of this language uses the coconut crab or a hermit crab as its mascot.

gabereiser 3y ago
You hear that crab-lang? :D Decarcinization is the correct opposite of carcinization. Hermit crab would be the perfect mascot in both function and metaphor.

chc4 3y ago

Nice blog post! I also wrote a concurrent reference counted cycle collector in Rust (https://github.com/chc4/samsara https://github.com/chc4/samsara, https://redvice.org/2023/samsara-garbage-collector/ https://redvice.org/2023/samsara-garbage-collector/) though never published it to crates.io. It's neat to see the different choices that people made implementing similar goals, and dumpster works pretty differently from how I did it. I hit the same problems wrt concurrent mutation of the graph when trying to count in-degree of nodes, or adding references during a collection - I didn't even think of doing generational references and just have a RwLock...

claytonwramsey 3y ago
That's really cool! Thanks for the kind words. I remember peeking at it while hunting for collectors to benchmark against.
nextaccountic 3y ago
Why not publish to crates.io? This seems useful
- chc4 3y ago
  Honest answer is mostly that I forgot; there was one more small TODO that I needed to fix before I wanted to publish it, and then I got busy and forgot about it.
  - nextaccountic 3y ago
    You can always publish unfinished crates as 0.0.1 version 0.0.x crates are special in that they can have breaking changes even in minor versions (so 0.0.1 isn't compatible with 0.0.2), so they convey a level of stability that is even less than a typical 0.1.x crate
    - rezonant 3y ago
      More generally, this is just semantic versioning. The first non-zero position is considered to have "major" impact, the following number is then a "minor" impact. https://docs.rs/semver/latest/semver/ https://docs.rs/semver/latest/semver/

ajani 3y ago

> If carcinization happens when languages evolve to be more like Rust, then what do you call it when Rust evolves to be more like Java? Caffeination? Surely oxidation is better than carcinization. And rust evolving to Java would be mineralization? Or maybe germination?

jakear 3y ago
Eh, carcinization is a better ontological fit. Many separate things evolving into the same structure, versus the process of losing electrons and/or structurally degrading.
OJFord 3y ago
And it's the version I've actually heard used (multiple times) before now - having looked up 'carcinisation', I assume that comes via 'rustacean' (cf. crustacean), which makes it a bit more contrived and then sort of implies the result is a Rust developer, not Rust itself? Makes more sense to me that a language/framework/etc. would 'oxidise' to Rust, and someone learning/getting hooked on Rust would 'carcinise'. But this is all silly and doesn't matter anyway, ha!
- Tyr42 3y ago
  The rust mascot Ferris is a crab. Like how go has a gopher.
  - munificent 3y ago
    And, of course, the name "Ferris" comes from being a homophone of "ferrous".
    - andyferris 3y ago
      And not only a homophone - they have the same etymology.
  - OJFord 3y ago
    Has that existed since day 1? I don't think I've ever seen that before. The gear icon comes to mind, not a crab.

loeg 3y ago

> box_ref.tag.store(COLLECTING_TAG.load(Ordering::Release)) Is it just me or do release semantics not make sense for a load? Release is for stores (I'm coming from the C/C++ atomics model). Hm, the docs[1] say a Release load will panic: > Panics if order is Release or AcqRel. Maybe just a blog transcription typo for tag.store(TAG.load(Relaxed), Release). [1]: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html#method.load https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize...

claytonwramsey 3y ago
This is correct, thank you. I'll fix it shortly.

teleforce 3y ago

Personally I think D language got it right when it makes GC as a default but still allows for no GC whenever applicable thus keeping most of the language relatively safe, easier to grok and more Pythonic compared to Rust. It will be very interesting to survey how many Rust implementations nowadays do away with memory safety [1]. Not sure if the author of the article referred to this seminal paper on Rust for GC for his GC implementation for Rust in Rust [2]. [1] What is a safe programming language? https://cs.stackexchange.com/questions/93798/what-is-a-safe-programming-language https://cs.stackexchange.com/questions/93798/what-is-a-safe-... [2] Rust as a Language for High Performance GC Implementation: https://users.cecs.anu.edu.au/~steveb/pubs/papers/rust-ismm-2016.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/rust-ismm-...

loeg 3y ago
You would think that if D "got it right," it would have seen a tenth the excitement / engagement Rust does. The proof is kind of in the pudding?
- Jtsummers 3y ago
  > You would think that if D "got it right," it would have seen a tenth the excitement / engagement Rust does. Why? Excitement doesn't always follow correctness or even "goodness" (whatever that means in context), even if we'd like it to. Fashion and marketing matter more when it comes to excitement.
  - loeg 3y ago
    I think they're very correlated!
    - cozzyd 3y ago
      counterpoint, PHP?
- crabbone 3y ago
  It's very naive to think that language popularity correlates with engineering merits... I worked very little with D, and a lot more with Rust. I cannot really speak to the qualities of D because, by and large, I dealt with a very few instances of it, and only at the interface level (mostly writing in another language). But, in terms of fame and popularity -- Rust developers and backers put a ton of effort into promoting the language. There were times when every other week there would be an article in some popular tech. media source from all kinds of "big names" about how Rust is superior to something (usually C++). There were massive efforts made to create a self-sustained community of Rust-evangelists who'd go and spread the word to the heathens... I haven't been around to witness the birth of D and don't remember if it had any kind of adoption campaign, but from what I can tell, even if it had a campaign, it didn't succeed. Now, here's another example from the same category of languages: Ada (esp. with Spark). I'm not very knowledgeable about it, but from the little I know, there are a lot of good reasons to prefer Spark over Rust. At least, on engineering merits, they should be roughly equivalent. But, in terms of popularity, Rust beats Spark by a lot.

zengid 3y ago

This is really impressive work and I applaud the author for building something that I'm sure lots of folks will find interesting and possibly very useful, but I want to say that I think there's a reason reference semantics (using and sharing heap allocations) are hard in Rust: It's because references are just plain hard to use safely. Rust tries to make the gnarly things awkward, but what is the easy path? If you look at the Hylo (formerly Val as of 3 days ago) language [0] that folks like Dave Abrahams have been working on, they're outright saying to just not use reference semantics if you can avoid it. In this talk at CppCon about Value Semantics, Dave argues that we should be decoupling object graphs from access to objects [1]. That's right folks, using `usize` indexes into collections, or adjacency lists, isn't just a hack to get around the borrow checker as people like Jonathan Blow have famously critiqued [2], it may just be the right way of doing things. [0] https://www.hylo-lang.org https://www.hylo-lang.org [1] https://youtu.be/QthAU-t3PQ4?t=2354 https://youtu.be/QthAU-t3PQ4?t=2354 [2] https://www.youtube.com/watch?v=4t1K66dMhWk https://www.youtube.com/watch?v=4t1K66dMhWk

claytonwramsey 3y ago
I know of a lot of people trying to do "arena" GC in Rust using integer indices. I think that's an excellent approach, but it does mean you have to pass in the arena as a resource to every single function which produces an allocation. This isn't even necessarily a bad thing - the net result is a lot like Zig's allocator API. I know there's a nontrivial overhead to using index-based references, especially since CPUs can't easily predict load operations. This gives me an idea: create a CPU architecture where pointers are actually (object, offset) tuples, enabling better on-metal performance with index-based references. I've neither the time, money, expertise, nor energy to implement such a thing, but it would be really cool if it existed - maybe CHERI is a close approximation, though I haven't looked very closely at it.
- gpderetta 3y ago
  > it does mean you have to pass in the arena as a resource to every single function which produces an allocation Implicit arguments! I'm more and more convinced that this form of controlled dynamic scoping dynamic scoping should be embraced by more languages. > create a CPU architecture where pointers are actually (object, offset) tuples Segments might yet see a renaissance (and CHERI might be indeed be a form of it).

3cats-in-a-coat 3y ago

I think GC is a very cool set of algorithms that have their place for collecting detached elements of a graph. But in a programming language, the baseline memory model should not be a graph in the first place.

claytonwramsey 3y ago
That's an interesting idea. Can you clarify some more on what the baseline memory model should be, if not a graph?
- 3cats-in-a-coat 3y ago
  I don't want to impose what it should be, as I'm asking myself this question every day. But I can list a few thoughts. The actual memory model is (seemingly) a flat address space, in which processes allocate segments, and everything else arises from there. There's some remapping behind the scenes, some segments are shared, some not, but this is beside the point. And a pattern I see often is arena allocation, where you allocate a large segment and then "virtually" allocate smaller segments inside, down to individual scalar variables. This can happen several times with a lot of memory, but tends to be shallow. For this and many other reasons, I see mutable memory is best structured as a tree, a shallow tree, almost relational, but still permitting nesting, where every item has one owner, one caller, and anything else is routed through that tree. Of course once this semantic model is established, you can reduce and optimize many calls into more direct calls. But you get clear intercept points when you need to decorate, block, remap and so on behaviors in the system. No "action from distance" surprises. Everything should be pass by copy. For larger structures, we need copy-on-write optimization. Which means underneath the mutable tree there is a Directed Acyclic Graph of immutable segments supporting copy-on-write. This is also not new, it's how forking works on Unix for example. Every modern OS utilizes copy-on-write on the file system, in memory, it's also utilized, if we think about it, in network caching systems. But to the process it looks like normal flat address space, where everyone owns their own copy of the content. For collecting unused segments in COW you'd naively need refcounting. There are other approaches that borrow from GC algorithms, in a much simpler and more performant way, because, well, there are no cycles in a DAG. The best part is that once you decide to use copy semantics, you have a plethora of algorithms at your disposal to try and switch between adaptively (including... just copying the thing if it's small enough, which turns out is the fastest approach), while maintaining the same exact semantics for the programmer who doesn't have to care how it works under the hood. Another benefit of copy semantics is that things are copied between processes, or especially between machines in a network, and now your language locally has the same semantics as when it talks to the network, which removes barriers and unifies interfaces. "Write once, run at any scale" if you will. Anyway, this is not comprehensive. And just my opinion. But the problem with graphs is that it is the data structure with least discipline, and most complications. And in most cases those complications do not pay off. Not only they require complex GC, but they result in heavily entangled code, tons of shared mutable state, that gave the whole OOP space a bad name (that it doesn't deserve). This was never a problem with objects, because objects were never supposed to share mutable state. It's a problem of graphs and handles, a system that pretends everyone "has" a mutable piece of state... which it doesn't have, as ownership must be exclusive to be reliable. Discipline of dependency management (packages etc.) often removes cycles and results in a tree or a DAG. This is not coincidental. And there's no reason we can't replicate this at the lower levels to individual objects. Of course, we still need graphs. But not everywhere, and not all the time.

nicechianti 3y ago

[dead]

MatthiasPortzel 3y ago

I’m not a Rust programmer, but I’ve heard Rust has compile-time AST macros. I wonder if it would be possible to implement a Rust GC by defining a macro to tag garbage collected sections of code. The macro expansion could then insert cycle-checks on moves as described early in the post. I have no intuition for how performance would compare to the trait-based approach that the author went with.

claytonwramsey 3y ago
In Rust, macros work at the tokenization level. Making a macro do that would require the macro to fully parse and analyze the syntax tree - possible, but not very efficient. Additionally, there's no guardrail to enforce that the user doesn't move a `Gc` anyway.
chubot 3y ago
IME a lot of people want some kind of help from the compiler when writing a GC, but there is the fundamental static vs. dynamic problem. Heap integrity / reachability is a dynamic property of a running program, and so all the static solutions basically end up as half-measures. (I imagine this would include using macros, though I don't know exactly what you mean), FWIW this is my experience - https://www.oilshell.org/blog/2023/01/garbage-collector.html https://www.oilshell.org/blog/2023/01/garbage-collector.html Take it with however many grains of salt, but I heard many static solutions proposed, and they're all "wrong" for the simple reasons in theory of computation. Also, Rust's static memory management inherently clashes a bit with dynamic memory management. That's also a fundamental thing, and you can have a bazillion mechanisms to ameloriate it for some cases (which may be valuable), but the problem will still be there no matter what.
1letterunixname 3y ago
Yeap. 2 flavors: procedural and pattern matching. Even the build can be scripted in Rust. And there is constant evaluation. https://doc.rust-lang.org/reference/const_eval.html https://doc.rust-lang.org/reference/const_eval.html Rust already has precise heap allocations with Box and Rc/Arc without the need for GC. GC implies uncomputed heap allocation liveness deferring work until later.

webkike 3y ago

I’ve recently been looking at this space for using a Gc smart pointer in a language I’ve been writing. It’s extremely useful - you can integrate builtins and external functions very cleanly

tayistay 3y ago

Is this essentially the "cyclic reference counting" algorithm from the Garbage Collection Handbook [1], Chapter 5, Algorithm 5.5? [1] https://gchandbook.org https://gchandbook.org

e_y_ 3y ago

As I understand it, Rust originally had support for garbage collected objects. It was removed because the community avoided it as a general practice to ensure that libraries could work without the optional GC runtime, due to its popularity as a systems language. https://web.archive.org/web/20130607161259/http://pcwalton.github.io/blog/2013/06/02/removing-garbage-collection-from-the-rust-language/ https://web.archive.org/web/20130607161259/http://pcwalton.g...

1letterunixname 3y ago
Yeap. Vec, String, Box, format!, and println! all depend on alloc for heap allocations. If an allocator is provided, alloc can be used in no_std. For format!, there are alternatives such as providing a fixed u8 buffer. It's quite amazing what can be accomplished without alloc.

celeritascelery 3y ago

This looks very cool! Thank you for sharing. I find GC's in rust particularly fascinating. So if I understand correctly, every time a Gc drops you add it a hashmap and then periodically, you run through all Gc's in that map and trace all their children to see if they are part of a cycle? I still don't understand how this would work without knowing the rootset. Just because something is part of a cycle doesn't tell you if it is inaccessible. There must be something here that I am missing.

kmeisthax 3y ago

I'm going to point out one potential footgun with your library: circularly-linked Drops. If you have values A and B, both instances of T that implement Drop and hold a Gc<T> to one another, then either A sees a dropped B or B sees a dropped A, and you get UB. Technically this isn't a problem because you already marked it as an unsafe trait, but your documentation should also mention this problem. You have a safe derive macro for Collectable, however, so it needs to reject Drop. This is possible with some weird macro magic[0]. For those wondering, while Python doesn't have UB, it used to enforce the same rules until PEP 442[1]. Circularly linked garbage that implemented __del__ would instead get stored in sys.gc.garbage and you'd have to go in there and break references on __del__ types. However, native code objects will actually still trigger this behavior[2] presumably to avoid UB. I have no clue if Java finalizers need to worry about this. [0] In Ruffle we use gc_arena as our garbage collector. It enforces no_drop in it's Collect derive macro. See: https://github.com/kyren/gc-arena/blob/master/src/gc-arena-derive/src/lib.rs https://github.com/kyren/gc-arena/blob/master/src/gc-arena-d... Actually, I lied: no_drop is one of two safe constraints you can use Collect with. The alternative is require_static, which only works because gc_arena treats the entire GC heap as a data structure that is owned and has a lifetime that all Gc pointers borrow. This doesn't work for dumpster, though, so ignore it. [1] https://peps.python.org/pep-0442/ https://peps.python.org/pep-0442/ [2] https://docs.python.org/3/library/gc.html#gc.garbage https://docs.python.org/3/library/gc.html#gc.garbage

appplication 3y ago
This comment would be significantly improved by fully spelling out what UB is at least once.
- kmeisthax 3y ago
  Undefined behavior means the compiler will rewrite your program in ways that do not follow from the meaning of the source code. This means things like conditions and guards just disappearing, code being reordered in ways that don't make sense, and so on. All of the safety guarantees of Rust go out the window once UB is triggered, because everything goes out the window. Which is why Rust is designed so that safe code can't trigger UB. But unsafe code still has to worry about it.