7 ms·
Great article. The main bit of new information for me was that while Rust supports dynamic dispatch, its implementation has a noticeable difference from C++.
by haberman 12y ago
Great article. The main bit of new information for me was that while Rust supports dynamic dispatch, its implementation has a noticeable difference from C++. In C++, the vtable pointer is in the object itself. In Rust, it's stored inside what is essentially a "fat pointer." Pointers to traits ("trait objects") are actually two pointers: the pointer to the vtable and the pointer to the actual object.
This seems to have one major downside (pointers are twice as big), but lots of upsides:
- allows traits to be implemented for existing types, as opposed
to C++ where the type's declaration has to list all base classes.
- allows a type to be used through dynamic dispatch while allowing users
who don't need this to avoid the vtable overhead.
- one less indirection in the call sequence for dynamic dispatch.
I like it a lot overall, though the idea of 16-byte pointers on 64-bit architectures does make me slightly queasy.
- pcwalton 12y agoIt also makes multiple inheritance (which Rust has, through Java-like interfaces) easy to implement, and fast at runtime. The virtual inheritance of C++ is a real mess, by contrast [1]. [1]: http://www.phpcompiler.org/articles/virtualinheritance.html http://www.phpcompiler.org/articles/virtualinheritance.html Edit: I don't mean to bash C++ here, BTW; the skinny-pointer approach has a lot of benefits when all you need is single inheritance (and there are early-stage proposals to add it to Rust too). But I don't think it works well for multiple inheritance.
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- fmstephe 12y agoI apologise in advance that this may not be most appropriate place to ask this question. I am looking for a Rust tutorial. It looks like there was one, but it was deprecated in favour of 'the book'. But 'the book' doesn't seem to have a tutorial yet. Are there any tutorial's running through how to build some small piece of working software. I found the Golang tutorial, where you build a very basic blog extremely enjoyable. Does Rust have anything similar? https://golang.org/doc/articles/wiki/ https://golang.org/doc/articles/wiki/ Thanks
- steveklabnik 12y agoThe book basically has two sets of tutorials: the "Syntax and Semantics" section is a bottom-up tutorial, and the "Learn Rust" section is a project-based, more top-down one. It's true that only one chapter of Learn Rust has landed at the moment. It's basically what I'm doing right now. Should have two or three more chapters over the next few days.
- fmstephe 12y agoGreat, thanks Steve.
- deleted 12y ago[deleted]
- kalmar 12y agoWhat is the representation for a type like Box<Reader+Writer>? Is there an extra indirection to get each of the vtables? Is there synthesized combined trait type and just one vtable pointer?
- Jweb_Guru 12y agoI am pretty sure you can't actually construct such a type (at least not at the moment) so Rust sort of sidesteps the question.
- Manishearth 12y agoIIRC you can.
- burntsushi 12y agoIt's early, so maybe I'm doing something stupid, but it looks like you can't! http://is.gd/9Y1HiS http://is.gd/9Y1HiS --- (I'm kind of surprised by the error message.)
- Rusky 12y agoI get this when I try something like `as Box<Read+Write>` error: only the builtin traits can be used as closure or object bounds [E0225]
- Manishearth 12y agoTIL; thanks :)
- drbawb 12y agoYou can sort of emulate this by having a trait which inherits from two other traits. (e.g: http://is.gd/SWZ9Ya http://is.gd/SWZ9Ya) In which case you'll have a single vtable for the "synthesized" trait object.
- skybrian 12y agoThis is also how Go does it. It looks like Rust traits can do everything Go interfaces can do, and more?
- pcwalton 12y agoMore or less, yeah. The main missing features are that downcasting isn't implemented at present (since Rust's other features remove the need for most of it), and implementation is explicit instead of implicit (a design decision which I've elaborated on in the past).
- keeperofdakeys 12y agoThere are some key differences, like Rust traits using generics, and Go interfaces using an empty interface for generic code.
- Manishearth 12y agoGo's interfaces have these additional features: - They auto-implement on types that have the appropriate methods (a feature that probably is unwanted in Rust) - They can be runtime downcasted via `.(type_name_here)` - They can be runtime type switched via `switch foo.(type)` I'm not sure of the vtable internals though.
- rwj 12y agoThis is also how interfaces are implemented in Go.
- nostrademons 12y agoAnd typeclasses in Haskell as well.
- evanpw 12y agoI don't think that's true. Dictionary-passing (or something equivalent) attaches the table of methods to the functions which take typeclass instances as arguments (with extra, hidden arguments), while Rust's Box<Trait> attaches the table of methods to the object pointer itself. So you can have a list of Box<Show> in Rust, but you can't have a list of Show in Haskell. You have to set up the extra indirection yourself using something like this: https://wiki.haskell.org/Existential_type#Dynamic_dispatch_mechanism_of_OOP https://wiki.haskell.org/Existential_type#Dynamic_dispatch_m.... I'm not an expert in Rust or Haskell, though, so I welcome corrections.
- bodhi 12y ago> but you can't have a list of Show in Haskell I'm not sure exactly what you mean, but my naive interpretation is that you can: Prelude> :t map show map show :: Show a => [a] -> [String]
- dbaupp 12y agoI'm not exactly sure what they mean, since the following works, and is pretty much a drop-in replacement for a Box<...> trait object in Rust. data Showable = forall a. Show a => Showable a This allows for [Showable 1, Showable "foo", Showable 'x'] (It requires the ExistentialQuantification language feature.)
- evanpw 12y agoRight, this is exactly what I meant by setting up the indirection yourself. The main difference seems to be that in Haskell, you have to write this code separately for each typeclass, and wrap/unwrap it manually. In Rust, you just change Show to &Show and you get dynamic dispatch with no extra code. Here's a gist of the two approaches: https://gist.github.com/evanpw/89d89aae1159c608c476 https://gist.github.com/evanpw/89d89aae1159c608c476. One other difference is that in the Haskell showStatic, static dispatch is not a guarantee, just an optimization.
- detrino 12y ago>- allows traits to be implemented for existing types, as opposed > to C++ where the type's declaration has to list all base classes. >- allows a type to be used through dynamic dispatch while allowing users > who don't need this to avoid the vtable overhead. In C++ you can have this as well. For example, std::function is able to wrap any callable type without them having to have any base classes. Sean Parent gives a great talk about this: http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil http://channel9.msdn.com/Events/GoingNative/2013/Inheritance...
- humanrebar 12y agoC++ is Turing-complete, so you can do whatever you want. What Rust offers is an hierarchy free (i.e., no inheritance) polymorphism mechanism as a core part of the language.
- detrino 12y agoThe turing-complete argument makes no sense here.
- humanrebar 12y agoSure it does. I can pass around a struct containing any bytes I want and do anything I want with it. If I want to define FatPointer that contains an opaque pointer (or some equivalent union) and a polymorphic Strategy object of some sort, I can. You can do the same in C, for that matter. Or in assembly. The reason we still come up with new languages is so that you can write code that conforms to certain patterns easily.
- jahewson 12y agoThat has nothing to do with Turing-completeness. There are Turing-complete languages which don't even have pointers.
- geofft 12y agoNo, Turing-completeness does not mean you can "do whatever you want". It means you can compute whatever you want that is computable. If the way you want to compute things is to embed a Rust compiler, yes you can do that, but there are many things that we'd colloquially refer to as "do whatever you want" that apply to the semantics of C++ itself. You cannot, for instance, create a new abstract base class and have a pre-existing class in someone else's header implement your abstract base class, such that a pointer to that pre-existing class can be dynamic_cast to your class. Because that statement refers to C++ semantics, not your ability to compute things, it's not affected by the claim of Turing-completeness.
- MichaelGG 12y agoDoes it have to be 16 bytes? I could imagine code opting in to compressed pointers (with alignment/heap restrictions). And you'd only need enough vtable bits to cover all unique types right? But imagining is easier than implementing of course. It would require recompiling all code to use the same pointer style, but whenever unwind-free Rust exists, we'll already need different compilation options for everything anyways, right? Though the added complexity could offset the 16-to-8 byte size reduction.
- adrusi 12y agoI don't try think that's feasible. The vtable is stored in the binary's data block, so that's usually a pretty compact region of memory, maybe even referenceable by 16 bits. Except that's no longer true if the type's impl for the trait is defined in a shared library. It should be possible as a compiler option if you are compiling every object that you link to and statically linking them into a single binary. Even then there's be a performance hit.
- comex 12y agoWould there be a hit? C++ has to do this: object pointer -> load vtable -> load function pointer while a compressed fat pointer would be like: fat pointer -> shift to extract vtable index -> shift to make into a global table offset -> load global table base from a global variable -> load function pointer Two loads in both cases, but in the compressed case the first one will almost always be cached; more code bloat, but not that much, and you save a bit of memory in the objects themselves.
- kzrdude 12y agoThe compiler could even choose the say 256 most popular vtables and use this optimization for those. Not sure how sane that would be.
- asdasfsdfsdf 12y agoThe other major downside being the extra level of indirection, which could potentially cause an extra cache miss per method call. A drop in the park bucket compared to most other languages, but a serious consideration for many of the areas that C and C++ dominate.
- haberman 12y agoExtra indirection? There is less indirection. With the C++ approach the data is one pointer away but the vtable is two pointers away. With the Rust approach both data and vtable are just one pointer away.
- fgsfdsfgsfds 12y agoThat's assuming that a "full pointer" (i.e. an unpredictable address to an arbitrary point in heap memory) is the only way to get a reference to an object. What about if you want to stick a bunch of objects in a vector, and iterate over them linearly? In the C++ approach, the data will have a nice linear cache access pattern. In the Rust approach (unless I'm missing something) you'd be storing a vector of (double sized) pointers, to god knows where in heap memory... suffering a cache miss on every access, on average.
- robinei 12y agoSince you are talking about a heterogeneous [edit: homogeneous] array, you would store the concrete structs continously in Rust as well. Rust would also not waste space in the vector for storing a vtable-pointer, and would instead construct fat pointers dynamically when needed (since it knows the type, it knows which vtable to inject in the fat pointer).
- fgsfdsfgsfds 12y ago> you would store the concrete structs continously in Rust as well. Rust would also not waste space in the vector for storing a vtable-pointer, and would instead construct fat pointers dynamically when needed (since it knows the type, it knows which vtable to inject in the fat pointer). Uh, what? How is the compiler just supposed to magically know which of the structures in the array are of what type, without any additional identifying information? I'm assuming that in this optimized case, there's a hidden type field in each struct, that it would use to index into a table of vtable pointers? If so, there you go, that's yet another level of indirection.