This is a simple idea that I’m sure a lot of ya’ll have had that I wanted to present here just to have it out in the open.
Return impl Trait can be optimized to improve spatial locality (i.e. remove the cache miss associated with dynamic dispatch) while being able to return multiple disparate types. This works by always returning an object of the largest size of the disparate return types. If the disparate types are similarly sized, then this is zero overhead. Otherwise memory can be wasted.
I will motivate this with an example. Say we have a trait with methods that only take a reference to self as a receiver (that is to say, none of them take ownership of self. Otherwise they may take any number of arguments):
trait Simple {
fn method1(&self) -> u32;
fn method2(&self, arg1: u32) -> u32;
fn method3(&self, arg1: u32, arg2: u32) -> u32;
}
Assume that we have three types, T1, T2, and T3 that all implement Simple. Consider the following function that we would like to return T1, T2, or T3 from while removing dynamic dispatch cache miss:
fn retSimple(v: u32) -> impl Simple {
match v {
1 => T1{ ... },
2 => T2{ ... },
3 => T3{ ... },
}
}
If is possible to implement this with no overhead thanks to unions. To do this, we make an anonymous return type for retSimple as follows:
union DataUnion {
t1: T1,
t2: T2,
t3: T3,
}
struct retSimpleRetType {
data: DataUnion,
simpleMethod1: fn (&DataUnion) -> u32,
simpleMethod2: fn (&DataUnion) -> u32,
simpleMethod3: fn (&DataUnion) -> u32,
}
retSimple would then be implemented as follows:
fn retSimple(v: u32) -> retSimpleRetType {
match v {
1 => retSimpleRetType {
data: DataUnion {
t1: T1{ ... },
},
simpleMethod1: <T1 as Simple>::method1, // (with necessary transmutes/casts)
// etc ...
},
2 => retSimpleRetType{ ... },
3 => retSimpleRetType{ ... },
}
}
If (and this is a big if) the number of methods in Simple is few, and the sizes of the different return types are relatively equal, this method removes the cache miss required by dynamic dispatch for multiple disparate return types in impl Trait with little overhead.
In fact, if the disparate traits all have size equal to that of a pointer, and the trait in question only contains one method, this method is entirely equal to returning a boxed trait object.
Just a thought