Avoiding monomorphisations for structurally-equivalent types


#1

(This is a toy example only to illustrate a single point.)

Consider the following C++ code. It defines two types Foo and Bar that are mutually-incompatible in the sense that neither can be replaced with the other. Both have two common methods large_foo() and complex_bar that are large/complex enough to not be inlined. The code as written communicates (by use of a common base class) that these types are structurally equivalent, and I only one copy of each method is needed in the binary. (Now, keep in mind that there may be many more structurally-equivalent types and I am paying attention to how much code would need to be added for each type.)

#include <iostream>
using namespace std;

struct Base {
  Base(int val): val_(val) { }
  int val() const { return val_; }

  void large_foo() const {
    cout << "I am large! " << this->val() << endl;
  }

  void complex_bar() {
    cout << "I am complex and self-modifying! " << this->val() << endl;
  }

private:
  int val_;
};

struct Foo: public Base {
  Foo(int val): Base(val) {}
};

struct Bar: public Base {
  Bar(int val): Base(val) {}
};

int main() {
  Foo f(1);
  Bar b(2);
  f.large_foo();
  f.complex_bar();
  b.large_foo();
  b.complex_bar();
}

Below my attempt to do something similar in rust (playground link). I find my attempt quite a bit more repetitive, though some – though not all – of it can be handled with macros. And, as far as I can see, the compiler would have to be quite a bit smarter to generate only one version of large_foo() and complex_bar() for both. I don’t really read LLVM IR, so it wasn’t entirely obvious whether the IR contained only one version or two.

pub trait Base {
  fn new(val: i32) -> Self;
  fn val(&self) -> i32;
}

pub struct Foo { val: i32 }

impl Base for Foo {
  fn new(val: i32) -> Self { Foo { val: val } }
  fn val(&self) -> i32 { self.val }
}

pub struct Bar { val: i32 }

impl Base for Bar {
  fn new(val: i32) -> Self { Bar { val: val } }
  fn val(&self) -> i32 { self.val }
}

pub trait TraitWithLargeComplexMethods {
  fn large_foo(&self);
  fn complex_bar(&mut self);
}

impl<T: Base> TraitWithLargeComplexMethods for T {
  fn large_foo(&self) {
    println!("I am large! {}", self.val());
  }
  fn complex_bar(&mut self) {
    println!("I am complex and self-modifying! {}", self.val());
  }
}

fn main() {
  let mut i1 = Foo::new(1);
  let mut i2 = Bar::new(2);
  i1.large_foo();
  i1.complex_bar();
  i2.large_foo();
  i2.complex_bar();
}

So my question is: Can I ensure a single implementation of large_foo() and complex_bar() without a tremendous amount of verbosity? I can imagine a more compositional approach with a tuple struct struct Foo(BaseStruct) where BaseStruct implements all the methods, but then we which would then have to implement (inlineable) forwarding methods to large_foo() and complex_bar() to implement TraitWithLargeComplexMethods. But that seems a lot of machinery for each implemented trait (which, admittedly, could be automated with macros per trait).

Actually, that reminds me: D supports forwarding methods to a field with alias this, if that’s any inspiration. Rust equivalent of this could be some sort of Trait delegation to a member that implements the trait. Aaand…a little search brought me to https://github.com/rust-lang/rfcs/issues/292 which seems to have been closed for some reason. Is this feature already supported somehow?


#2

It does indeed generate two copies of each function.

Look again - the issue you linked to is not closed.

However, as a general observation, the structure you desire seems a little arbitrary. Without seeing the real code that inspired this, I can only guess at your motivation, but still - Why are you implementing what sounds like quite a lot of traits and methods on a family of objects, which all just forward to this common subobject? Why not just have the clients call methods directly on the subobject? Why do you have all these types which are ‘the same but different’ in the first place?


#3

Oof! Silly me! I just scrolled to the bottom and saw “closed”, but that was referring to the other issue that was linked.

Thanks for the feedback. Indeed, I failed to provide the motivation. The question was inspired by C++ code structured similarly to what I pointed out above which also had generic code that acted on all subclasses of struct Base. I was trying to think of a similar effect in rust. Having a common sub-object that implements all the methods as you suggested solves all problems except for having a common trait bound on Foo and Bar suggesting the availability of the functionality for generic code, thus my attempts at implementing the traits on Foo and Bar directly. I would, of course, want to write the trait implementation only once. Unfortunately, I cannot do that for the constructor/getters/setters (represented by the Base trait), but I can write common code for the rest of the methods (represented by the TraitWithLargeComplexMethods trait) which may rely on the constructor/getters/setters. Thus the two traits instead of one.

The feature request I linked about supporting trait delegation addresses this precise case correctly.

An alternative workaround currently is to implement everything in a common sub-object of Foo and Bar (as you suggested), and use a ProviderOfTraitWithLargeComplexMethods trait on Foo and Bar with a single getter for the sub-object, and bound generic code with that trait instead. I might do this for now for porting the C++ code, at least until the above linked feature request is implemented.


#4

Here is some work I did on this earlier this year. I tried a few routes, and couldn’t find any obvious, consistent wins. It was easy to collapse monomorphizations for many simple functions, but such functions have little impact on compilation time (they get immediately inlined by LLVM presumably).

I still think there’s lots of opportunity here, and maybe with a MIR-based compiler the logic of analyzing functions for candidates won’t be so terrifying.


DRYing nearly identical implementations for &T and &mut T
#5

Interesting! And I agree, the only improvement will come from generic functions that are not obvious targets for inlining. This would be common, for example, in graph algorithms, although, depending on the types, it would make it less likely that monomorphisation can be avoided.

And of course, as a complementary point, abstractions that make it clearly obvious to the programmer that no separate monomorphisations are needed (like the C++ example and a variation of the rust example that uses composition instead of a trait abstraction (Base) of the constructor/getters) reduce this burden from the compiler altogether and any uncertainty for the programmer. (So, really hinting at trait delegation to facilitate porting this type of implementation inheritance pattern in C++ to compositions more ergonomically. ;))