I liked the article! But I don't think that Rust has static gc because it would imply that C has it too. It would make the term gc meaningless. I'm a fan of having words mean what people think they mean, even if it is not technically correct. And when people think of gc they think of an explicit method of disposing objects that is executed during program runtime.
Also, it is not Go has so great escape analysis that lets it elide so many allocations. It is that it passes objects by value which, for example Java doesn't:
person := Person { ... }
doPerson(person)
...
Go knows that doPerson can't modify person so it is free to allocate the variable on the stack. In the equivalent Java code, Java can't make that assumption (unless it introspects doPerson) because it passes references.
The escape analysis algorithm is detailed in an old article from 1999, https://dl.acm.org/citation.cfm?id=320386, and afaik both Java and Go uses the same idea. But Java's escape analysis is much less precise due to the described differences.
The weak generational hypothesis I believe is related to problem complexity because all algorithms are in a way reductions. You have something big and you make it smaller. A larger fractions of the variables used in an O(n^3) algorithm goes out of scope than in an O(n) algorithm.
Edit: Downvoters either explain yourself or go fuck off.
The author explicitly defines his notion of static garbage collection in opposition to what it's like programming in C:
> This also opens up two more things about why I don’t feel that “Rust is too hard and so you should use a GC’d language when you can afford it.” First of all, Rust’s strong, static checking of memory provides me a similar peace of mind to a runtime GC. To make an analogy to types and tests, when I program in a language like C, I have to think a lot about the details of memory management, because I don’t really have anything at all checking my work. Its memory management is completely unchecked, similar to (compile time) types in a Ruby program. But with automatic memory management, I don’t have to worry about this, as the memory management system has my back. I won’t get a use after free, I won’t get dangling pointers.
> I liked the article! But I don't think that Rust has static gc because it would imply that C has it too. I
Could you clarify how C would count?
From my understanding of the article's premise, a key part is whether the memory management is automatic or not. In C, everything on the heap is manual, you have to explicitly free and ensure it lives long enough for all owners and borrowers
C++ adds RAII. Going by the article, you might be able to refer to this as gradual automatic memory management except it only helps with the owners and not borrowers.
Rust has owner and borrow tracking, it just verifies it all at compile time and not runtime like traditional GCs (unless you opt-in to Rc). This puts it in a weird middle ground where I can see it being referred to as either automatic or manual, depending on how you look at it.
> From my understanding of the article's premise, a key part is whether the memory management is automatic or not. In C, everything on the heap is manual, you have to explicitly free and ensure it lives long enough for all owners and borrowers
But everything on the stack is automatic, so by this definition any type of automatic memory management being a "GC", then C has a GC (stack), paired with an unsafe mode (heap).
> Go knows that doPerson can't modify person so it is free to allocate the variable on the stack
Escape analysis does not care about modification. It only cares about whether the scope of the variable may end up expanded past the end of the function. Whether that scope is read or write is not relevant.
Causes of escape would be returning the value from the function, referencing the value in a closure, or using a reference to the value in a context with a different lifetime (channels, structs outliving the function). Calling a function with an argument as reference is not a cause of escape.
Escape analysis is tricky and fragile. Go often has to bail out to the heap.
Also, you don't really pass around structs by value much in real code, so the point that this is a benefit to GC performance is kind of moot.
True! What matters is that doPerson() doesn't get hold of a reference to the object which could cause escape. Since it doesn't get hold of a reference, it of course can't modify the object either. Had the call been doPerson(&person) it would have gotten a reference and Go would be forced to heap-allocate person. I agree that escape analysis is tricky because it is easier than one might think for objects to escape. That Go is better than Java at imprisoning objects I think is mostly because of different usage patterns between programmers of the two languages.
> [1]: Garbage collection is simulating a computer with an infinite amount of memory.
Chen even provides the "memory reclamation" definition in his post, but points out that it is incomplete. The article could be made much shorter (although the full read is still very interesting): as Rust has no free() call, Rust simulates infinite memory and is hence garbage collected.
A compiler can determine that a local variable x has no "next use", and insert the x = [] at that point to help garbage collection (or else provide some map of what is live).
Well as the person I was replying to points out, this is uncomputeable in general (`someUnknownCondition` might be brute-forcing all possible mathematical proofs to see whether the Reimann hypothesis is true), and I would expect optimizing compilers to already handle this in the cases where it is feasibly computable. Is that not the case?
In this case, you cannot free the memory manually either without making your program potentially invalid. It is unreasonable to expect a GC to do runtime control flow analysis, which is also more than you would do in a normal case of manual memory management.
If you have tricky situations where you know that program flow dictates that an expensive but reachable variable is no longer needed, you would insert a "x = nil" or similar in the position where you would otherwise have made a free.
However, this is solely a case of fine-tuned optimization, rather than a case of correctness.
You'd only need the GC to disconnect that local from the stack frame, as anything that escapes would be rooted elsewhere. This can be done by having the compiler/JIT emit a liveness map: instruction pointer ranges indicating which variables uninitialized, live or dead.
Otherwise, exactly.
Rust could do this with zero runtime overhead (as the map would be used by borrowck). This is pretty simple to do but generally isn't, precisely because of this: "this is solely a case of fine-tuned optimization."
If you are part of the 0.1% of the people who is actually solving one the of 0.001% problems where this level of control is _genuinely_ important, then use a language that supports this. Assuming that the method is executing for a very long time (>μs), because this the only time you'd probably care about memory management at this level, any FFI is virtually free.
However, even if you are part of the 0.1% of people who have a legitimate concern for this, and you are working on a 0.001% problem, why on earth are you doing so many allocations and frees? Against your own better judgement? If you care enough to worry about when memory is freed, you should know enough that you should re-use memory as much as possible without involving the allocator.
The article I linked deals with this. GCs typically guarantee cleanup in a scope. With managed languages, this is whenever the runtime decides to run the GC (probably when memory is needed and isn't available). With Rust RAII this is when the ref count reaches zero which is, at the very soonest, at the end of the current scope (you can force the collection with a naked scope if you need[1]).
> [1]: Garbage collection is simulating a computer with an infinite amount of memory.
But that definition also applies to virtual memory. On any modern OS, you can simulate a computer with an infinite amount of memory in C and C++ by just never calling free(). It'll even work pretty well for programs with small working sets, as the kernel will start paging out unused memory to swap.
I think any definition of garbage collection needs to specify that it is a form of memory management: it can automatically determine what memory will be used later so that it can recycle memory that will not.
> I don’t generally find writing Rust to be significantly harder than using a GC’d language. I’ve been trying to figure out why that is.
That's quite surprising! Here's some examples of where things would be easier to write if Rust had a GC:
1. Any sort of lock free algorithm. This is a big one - hazard pointers and the like are much harder than letting the GC clean up.
2. Data structures which may contain "back" pointers (e.g. parent pointers in a tree).
3. Data structures which may be cyclic. For example the classic LRU cache is best implemented with a cyclic linked list which is hard to express in Rust.
4. Any sort of refactoring that may adjust ownership. E.g. going from T to Rc<T>. GC requires fewer choices so these refactorings are easier.
Surely this pain is real, even if Rustaceans think it's worth tolerating?
In fairness precious resource cleanup (file descriptors, etc) is easier without a GC.
2. I agree on this one. The basic solution is "well instead of a pointer use a index into a vector" which has some correctness advantages (but less than "normal" rust does), but generally a bit of extra programmer pain.
3. See 2.
4. The compiler takes good enough care of you during things like this that it's basically painless.
#4 highly depends on a project size. On big projects, some of these decisions might become effectively one way doors.
I've been struggling a bit with these issues on the project of ~70k lines. I cannot even imagine what the refactoring would look like if we had, let's say, 1 million LOC.
To be fair, though, we use Rust the way it wasn't specifically designed for (large "enterprise" software, think Java-like enterprise).
I think, potentially, Rust could offer a much better story for this kind of software (assuming we are not mad and the issues we are facing are not because we doing something completely wrong :) ). In my opinion, the key thing would be to allow building "bridges" between pieces of the system which are "ownership-incompatible", so your decisions around ownership are not "one way doors" anymore (at the cost of translation / adapter layer).
Some random things which I think would be helpful:
1. Better self-referential structs, to allow going from "owned A + borrowed B" into "fully owned A+B" (rental crate helps here, though). Basically, hiding lifetimes in scenarios where you cannot easily change the original data structure to "own".
2. GATs. Honestly, this one is my speculation, but it seems like certain patterns which are hard to express now (abstraction of a "mutable reference", for example) would be possible with GATs. In our case, this would allow to bridge the gap between "trait object" world and "parametric over trait" world. The issue I was having is it is hard to express "mutably borrow from self" with traits (this is something similar to the issue "streaming iterator" crates solves). I was able to hack something using arbitrary self types, but it's quite... hacky.
3. Trait objects stable(r) ABI. Again, purely my speculation, but would allow to go back from "trait reference" world into "trait object" world. I won't go into details here, but trait objects want to "borrow" from something and it is not always easily possible (think that favorite vector+indices data structure) -- being able to "fake" those borrows would be nice (maybe).
Issues #2 and #3 specifically happens around deciding on data structure: regular structs have one set of tradeoffs, vectors with indexes -- another. In a big enterprise software, I would like to have an option to use whatever works in a particular spot and still have it API-compatible to the rest of the system.
Crossbeam makes lock-free data structures easier to write than in any other mainstream language I know of.
Regarding graphs, just use indices and vectors. It's often better to use indices for graph nodes anyway, for example in games, where an ECS design using IDs is generally preferable to direct references to objects.
For a while, I was kind of obsessed with showing that Rust could do doubly linked trees and graphs just as well as C++ could. I now realize that this was a mistake, and I made a big mess of a lot of code in the process. Having a single owner and using IDs for "secondary" references is often preferable even in languages that easily allow multiple strong references to objects. In the small, direct references and an OO style can be convenient, but in the large, you often want to break up your graph code into components and systems anyway, and it's kind of nice to have the language push you to front loading that kind of design.
The other posters have sorta said this, but the key is Cargo, and strong generics. I don’t write these things, I use a package where someone else has written them. The difficulty of writing this stuff does not impact my day-to-day getting stuff done. I don’t write Hashes in Ruby, I don’t write HashMaps in Rust.
I'd just like to add, most engineers aren't writing data structures all day. There are certainly some sharp corners, some of these Rust will help you with though: re: multithreaded algorithms. Robust libraries are helpful also.
30 comments
[ 3.5 ms ] story [ 83.4 ms ] threadAlso, it is not Go has so great escape analysis that lets it elide so many allocations. It is that it passes objects by value which, for example Java doesn't:
Go knows that doPerson can't modify person so it is free to allocate the variable on the stack. In the equivalent Java code, Java can't make that assumption (unless it introspects doPerson) because it passes references.The escape analysis algorithm is detailed in an old article from 1999, https://dl.acm.org/citation.cfm?id=320386, and afaik both Java and Go uses the same idea. But Java's escape analysis is much less precise due to the described differences.
The weak generational hypothesis I believe is related to problem complexity because all algorithms are in a way reductions. You have something big and you make it smaller. A larger fractions of the variables used in an O(n^3) algorithm goes out of scope than in an O(n) algorithm.
Edit: Downvoters either explain yourself or go fuck off.
> This also opens up two more things about why I don’t feel that “Rust is too hard and so you should use a GC’d language when you can afford it.” First of all, Rust’s strong, static checking of memory provides me a similar peace of mind to a runtime GC. To make an analogy to types and tests, when I program in a language like C, I have to think a lot about the details of memory management, because I don’t really have anything at all checking my work. Its memory management is completely unchecked, similar to (compile time) types in a Ruby program. But with automatic memory management, I don’t have to worry about this, as the memory management system has my back. I won’t get a use after free, I won’t get dangling pointers.
Could you clarify how C would count?
From my understanding of the article's premise, a key part is whether the memory management is automatic or not. In C, everything on the heap is manual, you have to explicitly free and ensure it lives long enough for all owners and borrowers
C++ adds RAII. Going by the article, you might be able to refer to this as gradual automatic memory management except it only helps with the owners and not borrowers.
Rust has owner and borrow tracking, it just verifies it all at compile time and not runtime like traditional GCs (unless you opt-in to Rc). This puts it in a weird middle ground where I can see it being referred to as either automatic or manual, depending on how you look at it.
But everything on the stack is automatic, so by this definition any type of automatic memory management being a "GC", then C has a GC (stack), paired with an unsafe mode (heap).
Escape analysis does not care about modification. It only cares about whether the scope of the variable may end up expanded past the end of the function. Whether that scope is read or write is not relevant.
Causes of escape would be returning the value from the function, referencing the value in a closure, or using a reference to the value in a context with a different lifetime (channels, structs outliving the function). Calling a function with an argument as reference is not a cause of escape.
Escape analysis is tricky and fragile. Go often has to bail out to the heap.
Also, you don't really pass around structs by value much in real code, so the point that this is a benefit to GC performance is kind of moot.
Oh, please let's not do this.
https://news.ycombinator.com/newsguidelines.html
> [1]: Garbage collection is simulating a computer with an infinite amount of memory.
Chen even provides the "memory reclamation" definition in his post, but points out that it is incomplete. The article could be made much shorter (although the full read is still very interesting): as Rust has no free() call, Rust simulates infinite memory and is hence garbage collected.
[1]: https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=...
https://en.wikipedia.org/wiki/Live_variable_analysis
However, it's just not worth the effort of a significant increase in GC complexity.
It could still be reachable, just never read from. Static code analysis can detect some forms of this, but not all e.g.
if (someUnknownCondition) { // access x }
If you have tricky situations where you know that program flow dictates that an expensive but reachable variable is no longer needed, you would insert a "x = nil" or similar in the position where you would otherwise have made a free.
However, this is solely a case of fine-tuned optimization, rather than a case of correctness.
You'd only need the GC to disconnect that local from the stack frame, as anything that escapes would be rooted elsewhere. This can be done by having the compiler/JIT emit a liveness map: instruction pointer ranges indicating which variables uninitialized, live or dead.
Otherwise, exactly.
Rust could do this with zero runtime overhead (as the map would be used by borrowck). This is pretty simple to do but generally isn't, precisely because of this: "this is solely a case of fine-tuned optimization."
If you are part of the 0.1% of the people who is actually solving one the of 0.001% problems where this level of control is _genuinely_ important, then use a language that supports this. Assuming that the method is executing for a very long time (>μs), because this the only time you'd probably care about memory management at this level, any FFI is virtually free.
However, even if you are part of the 0.1% of people who have a legitimate concern for this, and you are working on a 0.001% problem, why on earth are you doing so many allocations and frees? Against your own better judgement? If you care enough to worry about when memory is freed, you should know enough that you should re-use memory as much as possible without involving the allocator.
[1]: https://play.rust-lang.org/?gist=66740557884b17683b868483e52...
This is not a correct definition.
But that definition also applies to virtual memory. On any modern OS, you can simulate a computer with an infinite amount of memory in C and C++ by just never calling free(). It'll even work pretty well for programs with small working sets, as the kernel will start paging out unused memory to swap.
I think any definition of garbage collection needs to specify that it is a form of memory management: it can automatically determine what memory will be used later so that it can recycle memory that will not.
So your code would look a lot like it was running under a garbage collector? The OS memory manager is the garbage collector in this case.
That's quite surprising! Here's some examples of where things would be easier to write if Rust had a GC:
1. Any sort of lock free algorithm. This is a big one - hazard pointers and the like are much harder than letting the GC clean up.
2. Data structures which may contain "back" pointers (e.g. parent pointers in a tree).
3. Data structures which may be cyclic. For example the classic LRU cache is best implemented with a cyclic linked list which is hard to express in Rust.
4. Any sort of refactoring that may adjust ownership. E.g. going from T to Rc<T>. GC requires fewer choices so these refactorings are easier.
Surely this pain is real, even if Rustaceans think it's worth tolerating?
In fairness precious resource cleanup (file descriptors, etc) is easier without a GC.
2. I agree on this one. The basic solution is "well instead of a pointer use a index into a vector" which has some correctness advantages (but less than "normal" rust does), but generally a bit of extra programmer pain.
3. See 2.
4. The compiler takes good enough care of you during things like this that it's basically painless.
I've been struggling a bit with these issues on the project of ~70k lines. I cannot even imagine what the refactoring would look like if we had, let's say, 1 million LOC.
To be fair, though, we use Rust the way it wasn't specifically designed for (large "enterprise" software, think Java-like enterprise).
I think, potentially, Rust could offer a much better story for this kind of software (assuming we are not mad and the issues we are facing are not because we doing something completely wrong :) ). In my opinion, the key thing would be to allow building "bridges" between pieces of the system which are "ownership-incompatible", so your decisions around ownership are not "one way doors" anymore (at the cost of translation / adapter layer).
Some random things which I think would be helpful:
1. Better self-referential structs, to allow going from "owned A + borrowed B" into "fully owned A+B" (rental crate helps here, though). Basically, hiding lifetimes in scenarios where you cannot easily change the original data structure to "own".
2. GATs. Honestly, this one is my speculation, but it seems like certain patterns which are hard to express now (abstraction of a "mutable reference", for example) would be possible with GATs. In our case, this would allow to bridge the gap between "trait object" world and "parametric over trait" world. The issue I was having is it is hard to express "mutably borrow from self" with traits (this is something similar to the issue "streaming iterator" crates solves). I was able to hack something using arbitrary self types, but it's quite... hacky.
3. Trait objects stable(r) ABI. Again, purely my speculation, but would allow to go back from "trait reference" world into "trait object" world. I won't go into details here, but trait objects want to "borrow" from something and it is not always easily possible (think that favorite vector+indices data structure) -- being able to "fake" those borrows would be nice (maybe).
Issues #2 and #3 specifically happens around deciding on data structure: regular structs have one set of tradeoffs, vectors with indexes -- another. In a big enterprise software, I would like to have an option to use whatever works in a particular spot and still have it API-compatible to the rest of the system.
2. Make the front-pointers be Rc's or Arc's, then use the downgrade() method to construct the back-pointers.
3. Array-based ring buffer instead, perhaps?
4. Like any refactoring, the compiler errors guide you to the places that you haven't yet changed.
Regarding graphs, just use indices and vectors. It's often better to use indices for graph nodes anyway, for example in games, where an ECS design using IDs is generally preferable to direct references to objects.
For a while, I was kind of obsessed with showing that Rust could do doubly linked trees and graphs just as well as C++ could. I now realize that this was a mistake, and I made a big mess of a lot of code in the process. Having a single owner and using IDs for "secondary" references is often preferable even in languages that easily allow multiple strong references to objects. In the small, direct references and an OO style can be convenient, but in the large, you often want to break up your graph code into components and systems anyway, and it's kind of nice to have the language push you to front loading that kind of design.