Abstraction without overhead: traits in Rust

http://blog.rust-lang.org/2015/05/11/traits.html

by steveklabnik • 11 years ago

212 137 11 years ago

bkeroack• 11 years ago

There is always overhead when adding abstractions--the only question is whether you pay at runtime or at compile time. C++ (and presumably Rust) choose the latter, Python and Go choose the former.

steveklabnik8• 11 years ago

Yes, in these discussions, the overhead being referred to is runtime overhead.

There's also overhead in the sense of complexity for the programmer, which isn't really either of those two.

humanrebar4• 11 years ago

There's also overhead in the sense of complexity for the programmer

Well, from the programmers' perspectives there are both read-time and write-time overheads. In C++-land, the discussion about the new (to C++) 'auto' keyword is about the trade-offs between the two.

SamReidHughes• 11 years ago

C++ chooses both kinds, with templates and virtual functions. Rust does too.

Dewie33• 11 years ago

If you want to be really pedantic, there is also the choice between "runtime overhead" and "code overhead" (code specialization).

And why not mention the overhead of the programmer foregoing these "short cuts" and hand-coding it herself.

comex5• 11 years ago

That first one ain't pedantic; C++ code on the whole tends to generate a lot of assembly bloat with inlined methods and template instantiations, and while executable size probably isn't that important for most use cases, it is for quite a few.

halayli• 11 years ago

C++ traits, templates, and non-virtual classes have no overhead.

Manishearth6• 11 years ago

Technically Rust (and C++, IIRC) choose both, but the mindsets of most Rust(/C++) programmers/libraries is to use lower cost abstractions wherever possible. Rust provides features and libraries that provide a dynamic alternative to many different statically checked things; eg trait objects, cell types (internal mutability), shared pointers, etc.

The difference is in the mindset: Most Rust programmers will hem and haw at having to use Box<Trait> until we don't have any other viable alternative (with Rust and its enums, there usually are many better ways to do it with lower cost). Java/Go libraries are completely okay with using dynamic dispatch everywhere. While writing Java code I won't be concerned about using an interface type or `Object` or whatever because zero-cost abstractions are not Java's thing. Of course, if there is a static alternative I will still prefer it, but I won't be too bothered if I just stick with `Object`.

haberman4• 11 years 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.

pcwalton6• 11 years ago

It 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

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.

fmstephe2• 11 years ago

I 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/

Thanks

kalmar• 11 years ago

What 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?

skybrian• 11 years ago

This is also how Go does it. It looks like Rust traits can do everything Go interfaces can do, and more?

pcwalton6• 11 years ago

More 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• 11 years ago

There are some key differences, like Rust traits using generics, and Go interfaces using an empty interface for generic code.

Manishearth6• 11 years ago

Go'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• 11 years ago

This is also how interfaces are implemented in Go.

nostrademons• 11 years ago

And typeclasses in Haskell as well.

detrino2• 11 years 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...

humanrebar4• 11 years ago

C++ 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.

comex5• 11 years ago

This only works for callables, though; if you want a virtual dispatch wrapper for some other set of methods, you have to write it yourself (right?). On the other hand, if you do have a relevant base class and you know the exact type, you can avoid virtual calls in C++ just by declaring the relevant methods final, although the vtable pointer will still bloat the struct a bit.

However, I'd say Rust traits are more elegant in unifying what are two separate worlds in C++:

(1) calling virtual methods on a base class pointer, which can be (usually is) dispatched at runtime, but thus can't support methods with generic parameters or having a 'virtual type' (instead of a method), and

(2) accessing members of template parameter classes, including (possibly generic) methods, constants, typedefs, etc. - much more flexible, but doesn't work at runtime. Also dynamically typed, for better or worse; Rust thinks worse.

In Rust, (1) is a trait object, and (2) can be done with a generic parameter specified to implement a certain trait with methods, associated types, and constants. Rust's compiler doesn't try to be magic (unlike, say, Haskell), and so traits with generic methods and such can't be made into trait objects, but they're still traits - they feel like the same basic kind of thing.

MichaelGG2• 11 years ago

Does 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• 11 years ago

I 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.

kzrdude2• 11 years ago

The compiler could even choose the say 256 most popular vtables and use this optimization for those. Not sure how sane that would be.

asdasfsdfsdf• 11 years ago

The 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.

haberman4• 11 years ago

Extra 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.

coolsunglasses6• 11 years ago

Typeclasses benefit from the same "zero runtime overhead" in Haskell (but not Scala). This is particularly important in non-strict languages where inlining is a more prominent aspect of making code performant. Fortunately, GHC is a lot easier to understand WRT optimizations than gcc.

You revert to the OOP-style vtables if existential quantification is introduced because you have to pack code with the data, rather than being able to inline the data from a statically known index of methods into the concrete call-sites.

As it stands, I'm more likely to want Clean-style uniqueness typing in Haskell for a non-GC'd life-cycle for memory than I am to use Rust, but it's nice to see what we can accomplish with linear types baked into the compiler. Wish regions hadn't been abandoned, but it seems like somebody wanted Rust pushed into becoming a product quickly.

cwzwarich• 11 years ago

Haskell type classes can not be implemented with zero runtime overhead in all cases, because it is possible to have an unbounded number of instances at runtime for a single type class. The Rust equivalent will just fail at compile time (of the trait implementation, not the trait definition) due to a recursion error.

gue5t• 11 years ago

Could you describe some of the upsides of regions as compared to Rust-style lifetimes and borrowck?

kibwen5• 11 years ago

  > Wish regions hadn't been abandoned, but it seems like 
  > somebody wanted Rust pushed into becoming a product quickly.

No idea what you're referring to here. Lifetimes are entirely based on the regions literature, and four frigging years of design iteration is hardly "pushed into becoming a product quickly". :P

coolsunglasses6• 11 years ago

Lifetimes aren't regions.

4 years when it is a recapitulation of existing technology and hasn't had time to push anything forward and we already have PLs with similar facilities? That's a product-oriented rather than research-oriented direction whether you think it's too fast or not. For comparison, Haskell dates to the early 90s, based on non-strict FP languages from the 80s. ML itself started in the 70s. Much of what makes Haskell nice today happened because it had a decade to gestate without the demands of industry coming first. Applicative wasn't discovered until 2008. Those discoveries are a big part of why I happily use Haskell for work today.

This is emphatically not a value judgment, I will likely not use Rust in anger so I'm not your customer anyway at least WRT the programming language. Representations of linear types embeddable in dependently typed languages (such as Brady is figuring out in Idris) will probably be the next step.

In my ideal universe, there's a language for people to experiment with theoretical models and practical applications of linear typing such as Idris provides for DTPLs. This is particularly appealing as it could enable programmers to define their own linearly typed models for the compiler to enforce.

megaman821• 11 years ago

For being a lower level language, Rust's abstractions really make feel closer to a higher level language than to C. It will be even more so if HKT's land.

ajanuary• 11 years ago

HKT = Higher-Kinded Polymorphism [1]

[1] http://www.hydrocodedesign.com/2014/04/02/higher-kinded-type...

EugeneOZ3• 11 years ago

Traits are interfaces

So why not use "interface" keyword?

masklinn2• 11 years ago

Because trait is a much better word for it: https://en.wikipedia.org/wiki/Trait_(computer_programming)

EugeneOZ3• 11 years ago

So in Rust traits can include full methods bodies, not only signatures?

GolDDranks2• 11 years ago

Traits are somewhat between an interface and a mixin: an interface is made only of method signatures, while a trait includes also the full method definitions, on the other side mixins include method definitions, but they can also carry state through attributes while traits usually don't.

Rust's traits may specify just a method signature and force the implementor of the trait to implement the method, but they may specify full definitions of methods too.

MichaelGG2• 11 years ago

Java's interfaces are getting default implementations now, aren't they?

ajross6• 11 years ago

Probably for the same reason that they call their unions "enums" or their heap blocks "boxes". Standardization of jargon has never been a thing with rust, just roll with it.

steveklabnik8• 11 years ago

Well, enums aren't unions, they're tagged unions. And other languages call boxed values by that name too.

Dewie33• 11 years ago

And I guess by "standardization" you mean use a C-like name, even though it is inaccurate and misleading and the data type declaration is taken from another language family (ML)?

(I agree that "enum" is a wrong name to use, but apparently for different reasons.)

dragonwriter• 11 years ago

So why not use "interface" keyword?

They aren't really interfaces. They can be like interfaces (just method signatures) or like classes without data (including definitions for some or all methods). Using a name distinct from either "class" or "interface" limits the degree to which incorrect expectations from similar-but-critically-different constructs in other language interfere with understanding of the Rust construct.

seanmcdirmid2• 11 years ago

Traits as defined in scala can actually have state and data.

agumonkey• 11 years ago

It sits between interface and implementation. They're... more an `intermediate`.

pron3• 11 years ago

What you do use, you couldn’t hand code any better.

... given you have no information about runtime behavior other than the static code.

How to achieve "zero-cost abstractions" is, as usual, a design tradeoff.

Rust -- like C++ -- lets you choose in your code whether you'd like to pay for an abstraction or not. This does produce good machine code, but has two costs: 1/ the language gets more complicated and the programmer needs to be aware of what she's paying for, and 2/ you might end up paying for stuff you end up not using (for example, all button listeners might end up being the same type, and a vtable adds unnecessary cost), so that the generated code is only optimal if you have no other information about runtime behavior.

There's another way to add zero-cost abstractions: have a single simple abstraction and a JIT to figure out at runtime -- based on observed behavior -- what the optimal machine code is. This is what the JVM does. All method calls are virtual from the programmer's perspective, and no choice needs to be made ahead of time. At runtime, the JIT views the class hierarchy and usage, and decides whether a specialized, inlined version of a function is produced or whether a vtable is actually necessary (HotSpot even makes a special case when there are exactly two implementations, replacing the vtable with an `if`). If runtime behavior changes (a new type of listener is added or even new code is loaded at runtime that adds another implementation), the JIT will notice, reconsider and recompile. So in Java, virtual or even interface method calls are also zero-cost, even though you have no choice about using them; the decision on how to implement the abstraction is done by the (JIT) compiler at runtime. This, too, is a tradeoff -- a simpler language and truly optimal code taking into consideration not only static consideration but actual runtime behavior -- at the cost of a possibly significant warmup time and possible non-optimal "mistakes" by the JIT.

Narishma• 11 years ago

I wouldn't call that zero-cost. It's more like variable-cost, which could be even worse than always doing virtual calls in some application types.

pron3• 11 years ago

The average case is always as expensive or less than a virtual call. But yes, the JIT most certainly introduces unpredictability, which may be unsuitable for hard realtime applications (hard realtime Java programs employ AOT compilation for those classes that require absolute predictability).

nathan_long3• 11 years ago

"new traits can be implemented for existing types (as with Hash above). That means abstractions can be created after-the-fact, and applied to existing libraries."

Sounds a bit like a Ruby monkey patch. What happens in case of conflict - my trait adds a .hash method, but there already was one?

phaylon2• 11 years ago

Trait methods are only visible when the trait is in scope. So a conflict would only appear when both traits are imported and the method is called, in which case you'll have to disambiguate.

nathan_long3• 11 years ago

Cool, thanks for explaining. :) Would it be a compile-time or runtime error?

Abstraction without overhead: traits in Rust

Related Stories