README.md

tinydyn

Lightweight dynamic dispatch, intended for embedded use.

Ref<dyn Trait> and RefMut<dyn Trait> wrap a pointer and metadata necessary to call trait methods, and Deref into a tinydyn trait object that implements the Trait.

Traits must currently opt-in by annotating with #[tinydyn]. This defines an alternate, lighter weight vtable, and if the trait has one method, eliminates it entirely by putting the function pointer inline. This does not affect normal behavior of the trait, and can still be made into a dyn Trait. This, however, would be wasteful.

Example

use tinydyn::{tinydyn, Ref};

#[tinydyn]
trait Foo {
    fn blah(&self) -> i32;
    fn blue(&self) -> i32 { 10 }
}
impl Foo for i32 {
    fn blah(&self) -> i32 { *self + 1 }
}

// Like upcasting to `&dyn Foo`, but with a lighter weight vtable.
let x: Ref<dyn Foo> = Ref::new(&15);
assert_eq!(x.blah(), 16);
assert_eq!(x.blue(), 10);

Space Savings

TODO: numbers on a real large embedded project

For every trait and concrete type which upcasts into that trait, Rust creates a new vtable. Each vtable includes 3 extra pointer-sized values of layout and drop info. These aren't needed, so tinydyn's custom vtables do not include them.

In addition, tinydyn places the vtable inline in Ref[Mut] if it has only one method. This saves a dereference when making the virtual call as well as removing the need for a static vtable to allocate - truly as zero-cost as dynamic dispatch can get!

Design

Background

Trait objects in Rust are not fully zero-cost. In order for one set of code to handle multiple types with varying sizes, alignments, and behaviors, Rust must include extra metadata with the erased type to be able to work with it.

Say we have a trait Doggo with two methods:

trait Doggo {
    fn wag(&self);
    fn bark(&self);
}

A concrete type can implement that trait by defining the necessary methods. Each of these methods knows the concrete type at compile time.

struct Pupper {
    age: u32,
    name: &'static str,
}

impl Doggo for Pupper {
    fn wag(&self) { /* wag when self.name heard */ }
    fn bark(&self) { /* yip based on self.age */ }
}

struct Woofer {
    woof_freq: u16,
}

impl Doggo for Woofer {
    fn wag(&self) { /* big woofer wagging */ }
    fn bark(&self) { /* release a woof at self.woof_freq */ }
}

To work with multiple types that implement Doggo with the same code, generics can be used. A fn take_doggo(x: &impl Doggo) will create a copy of take_doggo for every concrete type passed in, and at compile time, this copy knows how the type is laid out in memory, how to call the needed Doggo, and how to best inline.

When you only have one copy or the code is trivial, this monomorphization is the best, as the compiler has the most information available to it.

If you need one copy of code to deal with multiple types, we can erase some of this compile-time information. A fn take_doggo(x: &dyn Doggo) works with a reference to a trait object, a dynamically-sized type that holds the needed info for Rust to work with it. This function trades some indirection and more challenging inlining with only needing one copy of take_doggo.

Say we have a bluey: Pupper (bluey is a value with type Pupper). When we upcast &bluey to a &dyn Doggo, we erase its type through an unsizing coercion. This unsizing coercion tacks on an extra pointer to a vtable, a table that defines runtime-accessible type information specific to the trait, most notably the method addresses. This creates a wide pointer, like how &[T] carries a pointer and a length.

Multiple &dyn Doggo of the same concrete type can share the same vtable.

Motivation

There's three pointer-sized values that are always included, but aren't used for dynamic dispatch, but instead for other type-erased operations:

• size, which is used by mem::size_of_val, for deallocation, and for type layout inside custom DSTs.
• align, which is used by mem::align_of_val, for deallocation, and for type layout inside custom DSTs.
• The drop glue, which is optional and is essentially drop_in_place for the concrete type. Only needed to dynamically drop a type, like Box<dyn Trait>.

However, what if your code doesn't need any of this? If all you need is dynamic dispatch through an borrow and have no need for accurate layout information, these values are an unnecessary bloat that pile up on an embedded system.

tinydyn vtables

tinydyn defines lighter-weight dynamic dispatch objects through a #[tinydyn] macro on a trait. This defines an alternative vtable format and reference wrappers to call these methods. This wrapper can't query the runtime layout information about the concrete type, nor can it drop it. However, it can call trait methods.

Inline vtable

tinydyn optimizes one step further for traits with one method: it includes the function pointer for that method alongside the erased type instead of using a static vtable. This is as cheap as this scheme of dynamic dispatch can be, and is how one might implement it in C.

Double Pointer

For safety reasons, the unsized trait object that Ref/ RefMut deref into is a pointer to the trait object, creating a double pointer to the object. So, while you can turn them into a &(impl Trait + ?Sized), that will be marginally larger code size if not optimized.

Why can't dyn Trait be made smaller as an optimization?

In theory, rustc could identify that a trait object's size, align, and drop glue are never accessed throughout the whole program and remove them from the vtable, possibly even inlining the vtable as tinydyn does. However, rustc is averse to global analysis, preferring to leave this to LLVM; and LLVM doesn't know how trait object vtables are formatted.

These are requirements tinydyn doesn't have to uphold. It doesn't have a Box.

A trait object that doesn't know its size

Since tinydyn trait objects don't know the size or alignment of what they point to, no reference to the concrete type can be made while the type is erased.

So, in order for the tinydyn trait object to implement a trait, the implementer itself has to have an erased pointer type. If that pointer type is sized, however, that comes with its own set of issues. You can swap two Sized references, and trait object-unsafe functions marked with where Self: Sized are now available to call, even though there's no possible implementation.

tinydyn trait objects do this with a specific design:

• They're primarily referenced through the [Ref] and [RefMut] types, which hold the data pointer and metadata needed to call trait methods with no overhead.
• These don't implement the trait, but Deref into a !Sized wrapper object that does, called the dyn wrapper.
• The dyn wrapper holds same pointer as the Ref[Mut], so the Deref creates a double reference to avoid creating a direct reference to the target.
• The deref wrapper object is discouraged from being used through reference like trait objects normally are. Not only does it have an inaccurate size_of_val and align_of_val, it is a double pointer and is more expensive to use directly.
• The vtable-calling functions are marked #[inline(always)] so the double pointer created when calling trait methods is detected as unnecessary and optimized away by LLVM.

This fake layout and double dereference is, in the end, a necessary design decision for soundness.

Function pointer transmute

In order to avoid the generation of duplicate functions or multiple addresses for the same method, this library performs an unsafe transmute of a function item cast to *const () into a "&self-erased" fn pointer. This is the most problematic operation it performs. It makes these assertions about unsafe Rust:

• There is no layout difference between &'a T where T: Sized and *const (). These pointers can be soundly transmuted between each other for the lifetime 'a. Similarly for &mut and *mut ().
• Lifetimes are entirely transparent to function call ABI.
• A function item cast to *const () can soundly be transmuted to a function pointer if:
  • All parameters have identical layout.
  • All pointer parameters have the same mutability.
  • Function pointers are the size of *const () on this platform (checked by transmute).

Contributing

See CONTRIBUTING.md for details.

License

Apache 2.0; see LICENSE for details.

Disclaimer

This project is not an official Google project. It is not supported by Google and Google specifically disclaims all warranties as to its quality, merchantability, or fitness for a particular purpose.