18 ms·
Rust has a static “garbage collector”
- bjourne 8y agoI 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 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.
- scott_s 8y agoThe 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.
- epage 8y ago> 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.
- arghwhat 8y ago> 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).
- jashmatthews 8y ago> then C has a GC (stack) IIUC the C11 standards etc actually just say "automatic storage" and stacks are never specifically mentioned.
- arghwhat 8y agoAh, yes, I forgot the term. C goes to great lengths to avoid defining/touching machine details, which is quite ironic considering how it has gained reputation in this day and age as a very low-level language.
- bjourne 8y agoBecause C has automatic variables. https://en.wikipedia.org/wiki/Automatic_variable https://en.wikipedia.org/wiki/Automatic_variable For the argument "that's a different kind of memory" see this thread from last week: https://news.ycombinator.com/item?id=18124431 https://news.ycombinator.com/item?id=18124431 It is entirely possible to write complex C programs using nothing but automatic variables.
- arghwhat 8y ago> 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.
- bjourne 8y agoTrue! 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.
- sctb 8y ago> Downvoters either explain yourself or go fuck off. Oh, please let's not do this. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- zamalek 8y agoI prefer the correct definition of a GC: > [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=13203 https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=...
- amelius 8y agoI always think that GCs are incomplete in a way. They can reclaim memory in cases such as: x = [1, 2, 3] ... x = [] But not in cases such as: x = [1, 2, 3] ... (x not used) Of course, determining if x is used might be uncomputable in general, but in practice it might be computable in a lot of cases.
- kazinator 8y agoA 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). https://en.wikipedia.org/wiki/Live_variable_analysis https://en.wikipedia.org/wiki/Live_variable_analysis
- umanwizard 8y ago
- ridiculous_fish 8y ago> 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.
- gpm 8y ago1. Rust is such a godsend for concurrent programming that any pain associated with lack of GC is worth it. We also have GC like tricks to make it not that bad: https://docs.rs/crossbeam-epoch/0.6.0/crossbeam_epoch/ https://docs.rs/crossbeam-epoch/0.6.0/crossbeam_epoch/ 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.
- idubrov 8y ago#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.
- pcwalton 8y agoOne thing to note is that borrowing in Rust is more powerful than escape analysis can ever be in other languages, because in Rust it's in the type system and therefore works well with separate compilation and higher-order functions. To give an example, suppose we have the following: struct A { ... } fn g(a: &A); fn f() { g(&A { ... }); } And let's say g() is defined in another crate and separately compiled. In Rust, we can safely allocate the instance A in f()'s stack, because we know via the type system that that instance can never escape. But compare the equivalent example in, say, pseudo-Java: class A { ... } class G { public static void g(A a); } class F { public static void f() { G.g(new A()); } } Can we promote A to the stack? Well, it depends. If the compiler can see the source of G.g and prove that A never escapes, then it can. Otherwise, it has to conservatively assume that A could escape. (Incidentally, this sort of thing is one of the main reasons why the JVM usually uses a JIT: because Java allows you to replace the bodies of classes at runtime via classloaders, you really want to be able to do these kinds of interprocedural optimizations based on the information you know at the time, but reserve the right to back them out if the class bodies change. Only a JIT is able to do this.) This gets even more difficult when you get to higher-order functions: class A { ... } interface G { void g(A a); } class F { public static void f(G g) { g.g(new A()); } } Can we allocate A on the stack? Well, it depends on whether any possible instance of G could possibly have its argument escape. Java's HotSpot compiler is quite clever here and can actually make assumptions based on the classes that are currently loaded (as a side effect of devirtualization). But Go, for example, will always allocate that A instance on the heap, as far as I'm aware. This is not a problem for Rust, because the type system ensures that A can always be allocated on the stack in the analogous code: struct A { ... } trait G { fn g(&self, a: &A); } fn f(g: Box<dyn G>) { g.g(&A { ... }); } Because the signature of the method G.g() ensures that every implementer must not let the instance of A escape, the compiler can soundly place A on the stack. In this way, lifting the escaping behavior of values into the type system is a very powerful technique that allows Rust to go beyond what typical escape analysis can do.
- ridiculous_fish 8y agoThis claim is too strong, because Rust can't reduce heap allocations to stack allocations. Java, Swift, and others can optimize apparent heap allocations into stack allocations. But (in my understanding) Box, Rc, etc. can never allocate on the stack.
- flying_sheep 8y agoIt feels like the title abuses the word "garbage collector", which implies automatic and dynamic. That sounds like "Bike is a human-powered motorcycle". However the article is well-written and very informative. Just need to skip the title :-)
- dang 8y agoOk, I took a crack at replacing the title with a representative sentence from the article. If anyone can suggest a better title, we can change it again. "Better" here means more accurate and neutral, and preferably using representative language from the article.
- kristianp 8y agoWhat about Rust has a static "garbage collector" It reflects Klabnick's thesis here, whereas the current "I don't find writing Rust to be significantly harder..." title is probably more controversial.
- dang 8y agoOk, we'll give that a try.
- steveklabnik 8y agoThis is better than the last one, for sure. Thanks.
- steveklabnik 8y agoThis title does not really reflect the entire point of the piece. The point is automatic memory management; the difficulty thing is tangential.
- dang 8y agoIf you'd like to take a crack at a title that is neither misleading nor linkbait, in accordance with the site guidelines (https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html), we'd be happy to change it again. It's hard for us to guess perfectly every time, but an imperfect guess is usually better than leaving a misleading or baity title up.
- brianpgordon 8y ago> Historically, there has been two major forms of GC: reference counting, and tracing. The argument happens because, with the rise of tracing garbage collectors in many popular programming languages, for many programmers, “garbage collection” is synonymous with “tracing garbage collection.” For this reason, I’ve been coming around to the term “automatic memory management”, as it doesn’t carry this baggage. It's fairly confusing to refer to this as automatic memory management. That term already exists to refer to stack variables getting allocated and initialized in C/C++.
- kibwen 8y agoI think the comparison is quite apt (and may be deliberate). Automatic memory management for locals in C/C++ uses the scope of a variable to determine when reclamation should occur. Likewise, ownership-based automatic memory management in Rust also simply leverages scope to determine when memory should be freed (though you can pass the memory into other scopes, but at the end of the day it's all just lexical scoping). It's RAII for memory.
- darksaints 8y agoJust out of curiosity, how many rust users have run into memory fragmentation problems with long running processes? I love the performance and low memory profile of deterministic/static memory allocation, but without a compactor, I can't see it turning out well with long running processes. Has it turned out to be a problem in practice?
- logophobia 8y agoIsn't that one of the reasons rust compiles with JEMalloc? Fragmentation avoidance is one of its main features. Otherwise, using arenas or other strategies work very well for avoiding fragmentation. I generally haven't run into issues, mainly because rust allows me to use a lot less memory which helps. Rust code also has less dynamic memory allocation in general. You allocate for dynamically sized datastructures and long-lived data, but not like c# or java where each non-value class type is allocated on the heap (unless the compiler is smart enough to use escape analysis).
- CoolGuySteve 8y agoWhat purpose does compaction serve in a 64 bit virtual address space on Intel? The processor addresses and caches by cache line and the address space is huge enough to handle most allocations. Not to say it’s impossible in C/C++, but I’ve only ever seen fragmentation issues in old versions of Java and C# where the runtime repeatedly commits large swathes of contiguous memory. The key differentiator here is the VM’s insistence on contiguous allocations, whereas malloc has no such requirements.
- kibwen 8y agoIt's a good question. As others have noted, jemalloc attempts to mitigate fragmentation, but you can't ever compact in a language where you can hand out pointers willy-nilly, so you would expect fragmentation to strictly increase as uptime approaches infinity. That said, Rust code doesn't tend to be especially allocation-heavy in the first place, and repeatedly allocating/freeing in a hot loop is already something that tends to be avoided as a core tenet of performance tuning, so allocator traffic may not be very heavy in the first place. I don't have any long-running Rust code myself, but I do know people who have had Rust servers that have been running for upwards of six months and they seem to be pleased at both how little memory it consumes and at how reliable it's been (you don't ever get tremendous uptime if your code isn't robust in the first place :P ).
- aaronblohowiak 8y agoI'd suggest that uniqueness typing is a special case of refcounting..
- heavenlyblue 8y agoHas anyone used Rust as a replacement for their Go management utilities? I'd like to find something that could be used in a set of different contexts, but using the same language.