Rust has a static “garbage collector”
words.steveklabnik.com
words.steveklabnik.com
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.
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.
This isn't to say that futzing with integers is the best imaginable solution for these tasks. Language-level support (or at least stdlib support) for generational indices would be an interesting subject to pursue.
Granted, you could `Option`-up all your operations, but the dynamic GC languages (or even C++) will let you operate on stuff "correctly", so long as your implementation is right.
You can go `unsafe` and implement correct stuff and still be better than C++. I really feel like reference IDs aren't a great way to solve something like a doubly-linked list. Reference IDs make you lose almost all guarantees of correctness, unsafe + a good API will at least give you a fighting chance.
There are problems (like entity system stuff) where reference IDs are just the way to go, though
But I don't think anyone should be juggling integers themselves; they should be using a library (just like a library-defined smart pointer) that handles that (the presentation at https://www.youtube.com/watch?v=P9u8x13W7UE may be of interest).
> There are problems (like entity system stuff) where reference IDs are just the way to go, though
Sure, and there isn't anything stopping anyone from both using them where they're practical and not using them where they're not. Some of the comments in this thread seem to be suggesting that you must choose one or the other, but that's simply not the case; using references in one part of one's program and indices in another is totally fine, as is using references and indices together in the same part of the program. They're not exclusive.
In particular, nobody is saying that one should be reaching for indices regularly; I've written Rust for years and have never, ever needed them. References work just fine for plenty of applications. But we have other smart pointers for good reasons, and sometimes an application will call for the use one of those smart pointers, and that's totally cool; again, references may be thoroughly useful, but they are not the end-all be-all of pointer-like abstractions.
I'd phrase it the other way - pointers are just a tool to express certain reference patters. The solution you proposed - integers - are another. Conceptually, the way both are used, both are references - a way to indirectly access another object.
But if you do it with indices into another data structure, then you do, in fact, just work around the borrow checker, and escape to the land of freedom where you do whatever you want - and pay the price. Now you can pass them with impunity, sure... but now you also have to deal with indices that reference non-existent elements, or (depending on your usage patterns) indices that were not properly updated when an element was deleted from the middle etc.
I explicitly said that I don't think integers are the solution; it's simply that for tasks like e.g. managing the thoroughly interconnected world state of a video game, where you have a web of dynamic entities, references aren't the right solution, and so people start to concoct other solutions using the primitives they have available. I mention that I think generational indices are the solution (or at least a solution).
> But if you do it with indices into another data structure, then you do, in fact, just work around the borrow checker
Why is it "working around the borrow checker" when it happens in Rust, but "employing an ECS architecture" when it happens in C++? The fundamental insight is that pointers and references as we know them kinda sorta suck at managing arbitrarily-interconnected webs of entities with dynamic lifetime; a garbage collector neatly solves this use case (dynamic lifetimes are their entire jam), but if you're using Rust or C++ then we're assuming that you have stricter performance requirements than a typical garbage collector provides (and if you don't, then you should consider using a GC'd language). An ECS-like approach using indices (which, if you squint and turn your head, resembles a very specialized form of garbage collection) is a way to keep entity management tractable without going all-in on GC.
> now you also have to deal with indices that reference non-existent elements, or (depending on your usage patterns) indices that were not properly updated when an element was deleted from the middle etc.
Generational indices address these problems. Again, I don't think anyone should use integers directly, you should seek to leverage abstractions that other people have already sat down and thought about.
Anyway, the point still stands: this is bypassing the borrow checker, because something cannot be adequately handled by it. And by doing that, you're back to square one with all the problems that the borrow checker was supposed to solve.
https://www.gamedev.net/blogs/entry/2265481-oop-is-dead-long...
In this particular case, currently Rust's borrow checker isn't of much help either, hence the workaround with generations.
I find this argument deeply frustrating. C++ doesn't even try to make graph memory management safe. Rust has several different strategies for graphs, all of which have some drawbacks, but which are all nonetheless safe. But because they aren't quite as ergonomic as C++, C++ somehow wins. No. C++ graph management is unsafe, regardless of whether you're using the lifetime profile.
One reason why Pascal, Ada and Modula-2 lost against C, was because they weren't ergonomic enough to the eyes of many developers.
The typical magazine articles why using them felt like ceremony and straitjackets by those whose security wasn't on their top concerns.
So I get to have a bit of experience being on the losing side, arguing how using array indexes with bounds checking (which could be disabled if really needed) was a better option than just incrementing away bare bones pointers. Or why explicit type casts were a better option.
Ideally, I would be using C# or Java for everything I do, so it isn't about C++ vs Rust as such, rather making the point that it is not only about grammar and semantics when comparing programming languages.
Given Biscuit's paper, I would say Go is on the good path if their Go 2.0 plans actually play as promise. Which remains to be seen, nonetheless.
In the end it is a matter of ergonomics and perceptions.
So if you can't prove your ownership graph is safe at compile time, you have to do it at runtime. For some ownership graphs, reference counting with Rc<T> is the right choice, but in the general case indexes and vectors are the least-verbose way to represent a runtime ownership graph.
And to clarify something that's probably obvious. A direct pointer to a vector element could easily end up becoming invalid when the vector has to be copied somewhere else for it to grow or if the element gets deleted in another thread, so you can't just easily use pointers to vector (or array) elements in Rust.
Reductio ad absurdum: Implement the entire heap as a single array with typed views and you have the asm.js model. Memory safety is ultimately just another class of bug and it's worth keeping the end goal in mind. (And the asm.js approach is resistant against smashing the return address even if the hosted application has buffer overflows out of every orifice, and of course it provides isolation from the rest of the host process, so segregating the heap into a separate memory space has real security value.) I use indices and tagged handles instead of pointers in low-level C code all the time for sound engineering reasons as it's often the superior solution (and the move to 64-bit pointers created further incentives), but I think skepticism is warranted towards the growing Rust prescription of indexed arrays whenever you're dealing with non-tree-structured data.
Probably the greatest thing about pointers is that they enable generic code without any abstraction cost. It's painful enough to work in a language like Java with object references but without interior pointers to array elements or structure fields. You may feel tempted to introduce a case-specific 'fat pointer' pairing of an array reference with an index, which is not only awkward to work with but puts you in the absurd situation of having an index type which will often round up to 16 effective bytes on a 64-bit platform due to packing alignment for the next value in memory, when often one of the goals of replacing pointers with indices on a 64-bit platform should be to reduce the size from 8 bytes to 4 or 2 bytes.
I think there might be a disconnect here between people who talk about Rust and people who use Rust, because the use cases that are amenable to indexing into arrays are few and far between. I have never encountered such an approach in any Rust project that I have contributed to; tracking indexes is far, far less common than e.g. something like the Rc smart pointer. It does get talked about a lot though, for some reason.
It does avoids the worst security issues (bad reads are at least contained to the same data structure, which can easily be a serious security issue but at least not arbitrary memory reads) but for a lot of purposes it has the same properties that you have with C style pointers.
It seems like a giant problem that Rust advocates are strangle quick to gloss over as a good pattern.
1. Use-after-free (C, C++). This is a logic bug and a security problem.
2. "Logically" dangling pointers (safe languages with non-generational indices). This is a logic bug, but not a security problem.
3. A memory leak (safe languages with garbage collectors). This is a bug that can be difficult to track down.
4. Panic/exception (safe languages with generational indices or weak pointers). This is a runtime failure.
I'd argue that, of these four options, (4) is generally the best. The ideal would of course be a static guarantee instead of any of these. However, static guarantees always come with restrictions of some kind. For the truly unrestricted case, in which your data references are completely irregular, I'm not sure you can really do better.
Its basically a less performant, less ergonomic version of using raw C pointers. Less ergonomic because you need to write your own allocator for your array. And its less performant because fetching the associated struct from memory requires 2 fetches rather than 1. If you're convinced dynamic memory management is the only solution to your data structure, rust's unsafe{} seems a better choice. Its in the language for a reason.
If my index 2 now contains the contents of lets say index 5, due to array rearrangement after deletion of the element at 2, whatever happens with data[idx].is_data_valid() is not what the developer would be expecting.
To me it feels a bit like a workaround for something that cannot be validated by the borrow checker, because it is something that developers have to go the extra mile to implement, or get a third party library, which someone has to validate that actually works as expected.
In a way, it isn't much different than expecting C and C++ developers to use static analysis for lifetime validations.
Meaning, using a tool outside of the core language for added safety.
Is it so hard to believe that references are not the correct abstraction for 100% of use cases? Reaching for something other than references when references are the wrong tool for the job is not working around the borrow checker; it's choosing the right abstraction for the right task. Being hung up on the borrow checker is missing the forest for the trees.
> get a third party library, which someone has to validate that actually works as expected.
How is this different from using any third-party library, ever?
> Meaning, using a tool outside of the core language for added safety.
Rust explicitly supports users defining their own smart pointer types to provide pointer-like abstractions with custom semantics; using tools outside of the core language for added safety (for whatever definition of "safety" one wants) is completely expected and encouraged.
Meaning Java/C++, .NET + (C++/CLI | C++/WinRT), Node.js + C++, Swift / Objective-C++.
So with C++ improving its safety history, usually with ideas taken from Rust, Rust ergonomics and tooling need to have a better story than C++'s to replace it on the above stacks.
As for C++ adding more static analysis, its lifetime analysis is a nice-to-have, but doesn't compare to Rust's borrow checker. You simply can't tack on a sound borrow checker to C++, because the language wasn't designed to accommodate one, and trying to impose the concomitant rules regarding mutability, aliasing, and single-ownership would break every C++ program ever written. For anyone who prioritizes sound static analysis WRT lifetime verification, C++ isn't a competitor to Rust. And there are plenty of people for whom that isn't the case, and they will continue to use C++, and that's not a problem. Rust exists to provide an alternative systems language for people who favor memory safety, and it's pretty good at that. :)
As for being an alternative systems language for people who favor memory safety, I fully agree, my point is that it still needs to improve its productivity and eco-system.
At CppCon 2018 Embedded Development panel, one theme was that only now companies are slowly willing to migrate from C to C++11(!), with a language that allows for a progressive rewrite from C while keeping the existing toolchains.
Another productivity example, with .NET I can get the safety I advocate, while C++/CLI/CX/WinRT allow for a seamless interoperability story with native code.
So even if the lifetime analysis is a subset of what Rust is capable of, mixed debugging and seamless CLR/COM/UWP integration are more attractive than rewriting that code in Rust, without having VS integration and WIP integration with Windows APIs.
I think Rust on its current state, is more indicated for GC free scenarios with either CLI or headless execution.
That's funny, because the largest deployment of Rust is in Firefox, which has a UI.
As far as I am aware, Rust is only being used for low level rendering, not widgets.
That's pretty different to static analysis tools which most likely won't always work.
Maybe we could uplift them to the nursery, but again, generational indices are nowhere near the top 10 crates on crates.io.
Many logic bugs become security issues. This specific one -- by way of TOCTOU races -- is one of the richest sources of security issues in Unix. The proposed "dormant index" solution is likely to generate a lot of these as well.
What is a dormant index? I've not seen anything like this proposed, or heard the terminology before.
I like the “dormant” name because unlike a weak pointer (say, in Java or Python), you can’t use it directly - you have to borrow the actual object to use it; so it lies “dormant” until you wake it up. It’s not (necessarily) weak because there is no automatic destruction once all other references are gone.
In other words, static safety in the face of circular references is what would provide me a major clear advantage for better-than-C++, and unfortunately that doesn't seem to be something that is even seen as an opportunity for Rust given all of the rhetoric about that being an abnormal pattern and index-into-array being safe enough under that world.
Having a compiler able to solve the halting problem would also be “a major clear advantage for better-than-C++”, but too bad it's impossible … Arbitrary circular graphs can't be statically managed, that's it. Your need a runtime support, and it will either be a garbage collector, or some kind of constructions with array an indices.
Checking for graph cycle is elementary CS - planning the entry/exit nodes is not. It is similar to link time optimization to implement.
Yeah, but that's for built graphs, not graphs that will be built at runtime? Seems really, really different.
Even with unchecked weak references, you can't get arbitrary undefined behavior. It's more like Java where you can defeat the type system due to the way generics work, but it's still memory-safe.
Also, relational databases work the same way. Sometimes people use constraints to avoid dangling references, but not always.
So if SQL can deal with it, BASIC too, what would be the issue in Rust? Even in Pascal/C/C++, especially in 64-bit platforms, encoding index maybe the better thing to do, and then in GC collected languages - the less pointers to explore the less work the GC has to do.
In BASIC, yeah, you pretty much had to use indices. And it was very much not fun! BASIC was actually the first thing I remembered in the context of this discussion, because I wrote a lot of that kind of code.
The other thing that it reminded me of is J2ME. People used indices into arrays of primitives there to avoid GC, because it was not really practical given the memory constraints of your average phone back then.
And accessing data through an index still requires you to first acquire e.g. a borrow, and the useful invariants of that borrow still hold: for the duration of that borrow, you have freedom from data races - there will be no other borrows to that instance when you're holding a &mut T, or there will be no other mutable borrows to that instance when you're holding a &T.
An index may allow you to reduce the scope and lifetimes of your borrows, but it does not allow you to eliminate your borrows.
I think it's possible to write a DormantPtr library that encapsulates this pattern with better ergonomics than vec<> + generational index.
Further, even if Rust guarantees memory safety, the approach is still less safe in the broader sense of guaranteeing program correctness. For one thing, if you just use raw integers for your indices, you basically have the equivalent of a C void pointer, a pointer to some unknown type. The compiler doesn’t know what the index is for and can’t catch you if you accidentally index into the wrong array. You can partially solve this by making a newtype wrapper for indices into each type of array, but even that can’t differentiate between multiple arrays of the same type.
Also, if you have a system for ‘freeing’ array indices and reusing those array slots for new data, you run the risk of keeping an index around too long and causing a semantic use-after-free: not as bad as a traditional memory use-after-free, usually, but certainly a source of incorrect and unpredictable behavior. And whereas tools like ASan let you ‘flip a switch’ to catch traditional use-after-frees if they happen in development builds, with arrays you have to add the extra checking manually. (On the other hand, if you do design extra checks, they might be cheap enough to run in production, where ASan is probably not. And yes, I know, when it comes to security, “if they happen in development builds” is quite meager comfort.)
But I’m not saying all this just to be negative. Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles. If so, it won’t just help with pointers, but with array-based designs as well: it’ll become a more viable approach to have the borrow checker check array indices, by adding lifetimes to those array index newtypes. That would remove all of the aforementioned safety issues, while keeping the performance benefit of arrays – indeed, increasing it, since with the right design you would be able to safely disable the bounds check when indexing.
One of the many great things described by Catherine's keynote about ECS's in Rust: generational indices. Generational indices are a dynamic fix for this problem.
> Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles.
I agree it'd be nice, and I've given it a lot of thought, as has Niko. In the limit, though, I think you're always going to have the situation in which there just aren't any static guarantees and the graph structure is truly unrestricted. In those cases, I'm not sure you can really do much better than dynamic checks of some kind, and it's hard to get much more efficient than a single bounds check.
Hmm… I'd heard of stuffing a generation ID into unused bits (which can help but is limited), but I see this proposes having the index type be a full (index: usize, generation: u64). Well, that works, but now instead of indices potentially being half the size of pointers (if you don't need more than 2^32 objects), they're double the size. Also, each object must store a generation, and you have to check that each time you use the index. (So it's not just a single bounds check, though I suppose you could turn the generation check off in release builds or something.)
If you're willing to accept that overhead, it seems to me that you may as well just store a pointer instead of an index; design the arena to ensure that the pointers remain valid as long as the arena itself lives, and use lifetimes to track that (much easier than managing lifetimes of each object). That way you don't need to keep track of the array and the index separately, and you also save on the bounds check. Well… I guess that with an array you can have unique mutable access, whereas with pointers you'd have to rely on interior mutability. But it sounds like a pain to ensure uniqueness when threading around &mut references to the arrays (especially if there's one big object with all the arrays); you could never keep references across calls even when that would be completely safe. I would rather rely on interior mutability. (Have I mentioned that I think Cell should be built into the language?)
I should note that one nice thing about the ECS style is that it's built around threading around Systems, which consist of references to the various Components. So it's a natural fit for the borrow checker.
pub struct SmartRef<'a> {
container: &'a Container,
widget: usize,
}
impl <'a> std::ops::Deref for SmartRef<'a> {
type Target = Widget; // Widget provides non-traversing functionality
fn deref(&self) -> &Widget {
&self.container.widgets[self.widget]
}
}
impl <'a> SmartRef<'a> {
fn children(&'a self) -> impl Iterator<Item = SmartRef<'a>> {
self.container
.widgets[self.widget]
.children.iter().map(move |w| SmartRef { container: self.container, widget: *w })
}
}
fn boo(container: &Container) {
let root = SmartRef { container, widget: 0 };
println!("name: {}", root.name);
for child in root.children() {
println!("child name: {}", child.name);
}
}
Mutability is also possible to some extent with these "smart" pointers. It gets a bit trickier and less ergonomic, though. See https://play.rust-lang.org/?gist=fbf1c24397e7020c95774bf0906...
Another option would be to store something like "Rc<RefCell<Container>>" instead of "&'a mut Container", in which case you will be able to achieve something that behaves like multiple mutable references (with all the concurrency issues of them).
References (i.e. pointers the compiler knows about), on the other hand, are strictly better than either. Indices can only be bounds-checked at runtime, while references can be both alias-checked and bounds-checked (if they're references into a slice of memory that is known to the compiler) at compile-time.
But, of course, you can't do math to references. Construct a pointer by through an integer cast + math, and now the compiler has no idea what that thing is, what it's inside of, or how many other pointers point to the same place it does.
I prefer my runtime validity checking to not come with CVE numbers, the corruption of instances of completely unrelated types, and other such heisenbugs.
> I feel like raw pointers and indices are about the same
On a large codebases with lots of contributors, there's several orders of magnitude of difference - between the number of bounds checked indices that could be "corrupting" your instances of type T (only those used to index arrays of T or things containing them), vs the number of pointers that could be corrupting your instances of type T (basically any pointer in the program whatsoever.)
Frequently with a similar "several orders of magnitude" difference in debug times.
Conceptually similar, practically not.
> I prefer my runtime validity checking to not come with CVE numbers, the corruption of instances of completely unrelated types, and other such heisenbugs.
I agree with your point, but DoS attacks do get you CVEs as well.
Personally, whenever I've got into writing Rust I was quite worried about the relaxed way you were told to use runtime-checked structures after many pages describing how Rust has such strong statically-checked safety guarantees.
I get that you need both because compilers and compiler research aren't close to proving many cases that programmers need to make use of, but selling both the ease of runtime-checked structures and how strong the static checking is feels a bit too much like trying to have it both ways. Sure, both are true, but then strong static checking doesn't really mean the same thing (that you're sure your program won't do certain things, which means you have to now do similar reasoning and debugging when dealing with other runtime-checked languages).
I don't quite understand this sentiment. If you try hard enough, you can verify anything at compile-time (modulo the halting problem, etc.). If you want, you can also use a language that verifies nothing at compile-time and does all verification at runtime. Where we choose to draw the line between static and dynamic verification depends on our requirements. The existence of dynamically-verified entities does not obviate the usefulness of statically-verified ones; Rust statically guarantees memory safety and data-race safety, and using e.g. Rc or indices into an array doesn't change any of that. If you're simply looking for a systems language with even stronger static guarantees than Rust, then look at ATS.
Not for off-by-constant-offset errors it won't. Even with address sanitization there's still a significant chance your overflowed offset will correspond with a valid part of some other a array--not really detectable at runtime in C.
I think the tldr; is, opinions vary.
Using indexes manually doesn't by-pass the borrow checker, its just a different, manual, memory allocation and management strategy.
It preserves memory-safety, but, it's questionable if you're better or worse off in terms of correctness of application logic when you use it.
...you're probably better off using the borrow checker (that's why it exists) or an abstraction in a crate to deal with this sort of problem, regardless of whatever implementation strategy it uses internally (unsafe, this, etc).
These savings matter a lot in some domains of computing.
Sure, objects aren't deallocated when the index is dropped, but that doesn't mean it isn't being automatically deallocated somewhere else for some other reason.
But usually programmers intend to destroy entities in one place; for example, in UI code, a programmer typically expects a widget to be destroyed once it's removed from the window. It can be beneficial to have the runtime system diagnose if a reference to an object thought to be destroyed is actually used. So I haven't seen anyone actually go to the trouble…
In scripting/gameplay parts of games maybe.
In rendering or other performance-critical components, pointers are just faster. They are single RAM reference, IDs are 2 RAM references (and in case of languages like C# or Rust, plus bounds checking).
I know how ECS work, but GP was advocating Rust's way i.e. not using pointers at all.
I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs.
And trees.
> I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs.
In games, graphs are used for pathfinding and other AI, for skeletal animation incl. IK.
Trees are everywhere: scene graph, bounding volumes, space partitioning, many others.
Because caches hierarchy, I usually want tree nodes to be located in nearby areas of RAM, i.e. a small arena allocator per tree/graph. This creates cycles, nodes are owned by arena and yet they need to have pointers between them.
I know about custom allocators in rust, but still, such data structure is much simpler to express in C++ with unsafe pointers. Games often know maximum sizes at compile time (e.g. in GTA5 there’s a hard limit of 255 skeletal bones) so that thing becomes a trivially simple wrapper around std::array.
Another problem with rust references for trees, sometimes nodes need to have pointers to parents. That again creates cycles.
2. MMUs in modern CPUs have prefetcher silicon in it. If the CPU detects you’re doing something resembling sequential access, it will prefetch more cache lines after that.
3. Modern CPUs also have TLBs https://en.wikipedia.org/wiki/Translation_lookaside_buffer Accessing data within the same page (platform-specific, on Windows often 4kb) is faster that accessing random locations because the virtual address->physical address mapping for that page will be in the cache.
4. Last but not least, with small arenas per tree/graph memory allocations and deallocations will be faster than even jemalloc, from the point of view of C runtime you’ll only call malloc/free once per graph, not once per item.
Look at the data in my repository: https://github.com/Const-me/CollectionMicrobench As you see, adding my custom allocator to these standard C++ collections improved performance substantially.
Update: also, with 1 arena per tree, it becomes orders of magnitude faster to copy the tree. You just memcpy and then sequentially walk through the arena adjusting the pointers. Or combine both in a single step.
I'm not sure where anyone could have gotten this impression, because 99.99999% of Rust code uses pointers (via references, which are statically verified and compile down to raw pointers). Even the people making graphs out of indices will be using references in some capacity.
It can be cached by very small chance. Or it can be cached if the developer did profile-guided optimization. Otherwise it’ll be evicted from these registers pretty often. There’re not that many general purpose registers, so unless the processing code is trivially simple like CRC32, the compiler will reuse these registers for something else.
thinking in comparison of something like go, where you'd just do
> type NodeIndex int
type MyInteger is integer;
declares a new integer type that needs to be explicitly converted to any other integer type. You can also declare a new range integer type as in
type MyPositive is integer range 1 .. Integer'Last;
But you can also delcare integer and float subtypes:
subtype Day_Number is integer range 1 .. 31;
or (a bit pointless)
subtype MyInt is integer;
The difference between new types and subtypes is that no operations of the base type are defined for the new type since it's an entirely new type. A subtype on the other hand allows the operations of the base type, and their range is checked at compile time if possible and runtime if necessary.
In addition to this, Ada also has modular integer types, real types, floating point types, fixed point types, and decimal types in the numeric type system and all of them can be subtyped.
Of course, you can create a new type for any other type in Ada as well, but that's not what I meant when I was talking about integer subtypes.
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.
The transformations between T, Box<T>, Rc<T>, Arc<T>, etc. are mechanical, so I expect someone will write a refactoring tool that makes a giant PR for you automatically. (Subject to certain limits, like if you're actually cloning the ref-counted pointer, it's indeed harder to go back.) Would that satisfy your need?
> To be fair, though, we use Rust the way it wasn't specifically designed for (large "enterprise" software, think Java-like enterprise).
IMHO, this is a valid use case for Rust. I'm not saying everyone should stop using Java (in some cases I think it's significantly faster to write) but Rust has some strong performance advantages and no data races in safe code.
It's not always possible to change the data structure -- different ways of modeling data have different trade-offs. So, for me it is about not having to make a choice than about tools that will help you to change your mind.
Also, it could be something like structure coming from a 3rd-party crate using borrowing and you want to stick it into "Arc" of some sort. Or put it (with the thing it borrows from) into a lifetime-less struct, so you don't have to care about these lifetimes.
>IMHO, this is a valid use case for Rust.
I very much hope so :)
I agree with "different ways of modeling data have different trade-offs", but I don't understand how that leads to "it's not always possible to change the data structure". I revisit trade-offs all the time.
Could you explain? I might need a concrete example.
> Also, it could be something like structure coming from a 3rd-party crate using borrowing and you want to stick it into "Arc" of some sort. Or put it (with the thing it borrows from) into a lifetime-less struct, so you don't have to care about these lifetimes.
Yeah, certainly the refactoring becomes harder (maybe implausible to do automatically) when you can't change both sides in one PR, and when you have to convince someone else to change their interface / bump the major version. It still can be done (partially?) by hand at least; it's just a matter of cost/benefit.
You might want different trade-offs in different places.
Like, in our case, the conflict is between three different representations:
1. Typed Rust structs 2. Vector with indexes 3. Untyped structs (HashMap of strings to values, essentially)
None of them covers 100% of the use-cases we have (though we also not sure exactly are these the use-cases we will have year from now? three years from now?), and some parts of the system needs to work with all of them.
>Yeah, certainly the refactoring becomes harder (maybe implausible to do automatically) when you can't change both sides in one PR, and when you have to convince someone else to change their interface / bump the major version. It still can be done (partially?) by hand at least; it's just a matter of cost/benefit.
One case was Transaction from postgres crate, which uses lifetime. But I want to stuff it in Arc. Would be possible, if Transaction itself used Arc instead of borrowing, but there are about zero reasons for them to change API that way.
That statement more reflects how many feel (myself included) after working with rust for a little while, and internalizing the beneficial nature of the extra pain (being more strict about how you pass around memory, etc), and getting used to being more explicit. Also, other languages have difficulties that eclipse and are more endemic than rust's so there's probably consideration of that too.
Heck, I used to say “rust will never be a good choice for web apps” but by now I’ve written several. Times change!
I read and enjoy a bunch of your articles when it gets posted here and in r/rust and you've been doing rust[0] too long to reasonably be in touch with what newcomers face IMO.
To summarize, thanks for all your contributions to rust -- I still think I'm right about it being a tiny bit hard for newcomers :)
(And, I interact with beginners all the time; I know that they struggle.)
However, this is, anecdotally, what people say after they start using rust heavily.
I've heard it from quite a lot of people.
It's like turning on all the jslint/tslint's as hard errors.
Yes, it's painful to start with... but, as you relax, and let the compiler to the hard work of checking things, you can confidently write code without worrying about a certain entire set of domain concerns, because the tooling is taking care of it.
Sure, I'd love it if there was a 'alt-enter, fix this' for rust errors in [my editor of choice for rust], and no one is saying, 'oh hey, rust is super easy to learn!'.
...but more and more (as the ecosystem matures) rust is being used to Get Stuff Done, not just to write little toys; and the people using it to Get Stuff Done aren't complaining about how hard it is, they're <3'ing it.
(Of course, I disagree on the web-apps front; I feel like that's still very painful with the 15+ frameworks out there fighting / breaking changes / being abandoned; but at the very least its starting to look like a few plausible stable options are emerging; and I admit this is survivor-bias, where the people who didn't like it gave up before they started to get productive... but, I think the idea that 'rust is hard always' isn't true at all)
[0]: https://actix.rs/
Not really, as proven by languages like Mesa/Cedar, Modula-3 or more recently D, Swift, ParaSail or Chapel.
Somehow I think many CS degrees fail at teaching a proper history of programming languages.
Just because there is a GC involved, doesn't mean that it the only language feature available for resource management.
As for the other points, that is why I would advocate the use of other ML like compiled languages like Swift, OCaml, Haskell if having making use of a GC is not an impediment for the application being deployed.
If memory management is absolute a no-go, e.g. MISRA, High Integrity, DOJ certifications, real time kernels, high performance graphics, then Rust is a very good tool.
Those languages do offer some tools and conventions that help, but they're typically opt in.
Gotta love Python's 'with' statement too, not that you'd necessarily choose Python where resources are precious, but it depends on what the resources are...
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.
This pain is real. I've been using Rust for four years now, and it hasn't gotten any easier. And unfortunately, the best strategy I have for refactoring is still "start refactoring; then see what issues come up and if I have to revert".
I write a lot of lockfree C++ that requires 100 nanosecond-magnitude latencies 100% of the time. But in doing so, my algorithms are always implemented with a cache coherent wait-free allocator pool as well.
I don’t see how you can achieve the same thing in a GC language without a lot of manual tuning or a similar memory pool design.
1 - Disabling the GC altogether during access to the data structure
2 - Ensuring that the GC wont run during the region (TryNoGCRegion() in .NET or a real-time thread in Real-Time Java)
3 - Or if the language supports it, keep part of the structure away from the GC, using RAII to keep track of the blocks
Yes you'll need a memory pool design in whatever language. But most GC'd languages only collect at allocation sites, and so if you don't allocate you won't trigger a GC.
Something else ultimately turned me away from investing more time into it, though: Chapter 17 of the book, which spends a great deal of time trying to advertise why its OOP support is so impoverished. In comparison, Donovan & Kernighan's The Go Programming Language is much more honest about the (many) misfeatures of Go.
That being said, already existing libraries and Rust's tooling are excellent, and so I'll surely return to the language. Not because it has no optional GC but despite of it.
What I found problematic was the section on "Inheritance as a Type System and as Code Sharing", especially the paragraph "Inheritance has recently fallen out of favor..." While there is some truth to the claim, you forget to mention that there are also metric tons of highly successful OOP based software libraries out there, that it is perfectly feasible to use inheritance (and multiple inheritance) in good and productive ways, and that the Rust community is still quibbling about how to implement GUI frameworks in a "Rust way" and how to interface to foreign OOP libraries in general because of Rust's OOP limitations. It is a drawback not to have full OOP with inheritance and multiple dynamic dispatch. A non-biased and informed language user may choose Rust despite this limitation, but not because of it.
Another thing I found problematic was the "newtype pattern" pp. 439-441. Whether the wrapper is optimized away or not, the newtype pattern is clearly a cumbersome solution for a language limitation. At least to a beginner who has seen many other languages, this just looks like a horrible workaround for the lack of scalar subtypes, as e.g. Ada has them. To be honest, pp. 440-441 were probably the final reason why I decided to postpone writing software in Rust. (Coincidentally, Ada also allows you to define type aliases that are discussed on the following pages, but in Ada they are normally considered bad style and only used for clearly identifiable abbreviations.)
That being said, I found your book very informative and overall good reading, and I'm planning to come back to Rust once I have the time.
Newtypes are better for Rust's purposes than subtypes because they interact better with type inference, which is deeply important, especially when trait matching is concerned. Subtyping makes type inference much more complicated, and in fact a long-term goal in rustc is to remove all subtyping from the typechecker and relegate it to the lifetime pass.
1. A language that has an optional GC and a borrow-checker is better than a language that only has a GC or borrow-checker.
2. A language that has scalar subtypes with range checking and new types is better than a language that has only new types and no range checking.
So subtyping is complicated to implement in the typechecker. And? If GNAT can do it, why can't the Rust team not do it?
3. A language that has full support for OOP including inheritance and traits (or mixins) is better than a language that has less of these features.
I'm not claiming that every language should offer everything but a general purpose language that wants to be a viable substitute for C++ should at least have its OO capabilities.
Disagree. It is worse to have two worlds that are poorly integrated with one another. Dividing the ecosystem in two would be a terrible idea.
> If GNAT can do it, why can't the Rust team not do it?
Because Ada isn't Rust?
It's not that we can't do it. It's that typechecking complexity has a cost, and Rust is already operating at near maximum feasible typechecking complexity.
> 3. A language that has full support for OOP including inheritance and traits (or mixins) is better than a language that has less of these features.
No. Not every language needs to have every feature. Every feature has a cost. Not enough people are asking for inheritance to justify its cost at this time.
> A non-biased and informed language user may choose Rust despite this limitation, but not because of it.
Yeah, I guess this comes down to a difference in perspective; many people do prefer that Rust has no inheritance, and if it did, would choose Rust despite that, not because of it :)
> the newtype pattern is clearly a cumbersome solution for a language limitation.
It depends on your view too; that is, sub-typing has a lot of other problems. Sometimes, this "cumbersome"ness is what you want, because you don't want everything automatically forwarded through. For situations where you do, there has been talk of adding delegation support in some fashion.
Anyway, thank you, this is all good to know :)
To give an example, suppose we have the following:
struct A { ... }
fn g(a: &A);
fn f() {
g(&A { ... });
}
class A { ... }
class G {
public static void g(A a);
}
class F {
public static void f() {
G.g(new A());
}
}
(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());
}
}
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 { ... });
}
However the article is well-written and very informative. Just need to skip the title :-)
"Better" here means more accurate and neutral, and preferably using representative language from the article.
Rust has a static "garbage collector"
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.
But, I also don't think this is a huge deal, given that it's no longer on the front page.
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++.
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).
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 ).
I allocate and destroy a bunch of arrays in my code (~100MB every minute), so it's not huge but definitely quite a few pages every time it happens. And so far I've got one process that's been running for 6 months. For the most part, whenever I get new data, I take a slice of an old array and append the new data to it to create a new array. It's fast enough, but more importantly it's just so much easier to do it that way and with a compacting GC I don't have to worry about anything.
Of course I don't know how good jemalloc is at avoiding fragmentation, and I don't have the time to rewrite my code (maybe enough time to simulate, not sure). But my code creates a ton of fragment-y garbage, and I would imagine that with Rust I would end up not just translating my code, but changing semantics to mutate in place, just to avoid fragmentation. I guess maybe /r/rust would be the place to ask.
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.
> [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=...
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.
Major memory leaks, but who cares it compiles hella fast.
This is not a correct definition.
x = [1, 2, 3]
...
x = []
x = [1, 2, 3]
... (x not used)
[1]: https://play.rust-lang.org/?gist=66740557884b17683b868483e52...
a = { x: [1, 2, 3], y: [1] }
... (a.y used, but a.x not used)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.
I do not see this as improving the situation. I certainly do not see it fix the case where a runtime condition mean that a variable is no longer needed, as branches touching it will no longer be hit.
A JIT could theoretically deal with this, but only if the code is retraced and recompiled after the runtime condition changed, which is not generally something you want.