Idea: Would Rust benefit from explicitly polymorphic generics?

If the compiler optimizations are good enough, you can get them automatically for most cases, and for cases you want to ensure polymorphizm use the current trick of inner non-generic function.

If we can ensure polymorphizm, we should be able to use the generic function in an object safe trait. You see the problem, of course. You absolutely cannot use the current trick of inner non-generic function to create an object-safe trait.

More to the point, if I create a trait, how can I be sure all the implementations fall under a compiler optimization? Without some way to stop bad implementations, I really can't. I would need a way to tell the compiler to enforce some acceptable subset of the surface syntax. I would need a way to differentiate polymorphic generics from monomorphized generics.

1 Like

Note that very often we want to have a polymorphic inner function (which gives us compile time benefits) inside a monomorphized shell (which gives us a nicer API). The momo proc macro gives us exactly that for the price of a small annotation and a modicum of compile time.

While I'm always happy to concede that having more optimizations is better than having fewer optimizations, the idea of explicit polymorphism addresses an orthogonal concern. The issue at hand isn't optimization, it's type-level expressiveness.

As the community has gained experience writing Rust, we have found that there is some nonzero cost to pure monomorphization. And to be fair, the other way ("polymorphic inner function inside a monomorphized shell") also has a nonzero cost. So what we're really looking at is a tradeoff problem.

Two ways to approach this are:

  1. Give the code author the tools to manually opt-in to the polymorphic-in-monomorphic form.
  2. Make the compiler switch to this form automatically as an optimization.

The momo crate seems like a good tool to address 1, since it's available today, it's minimal, it works, and it matches Rust's "let libraries experiment first" approach.

Separately, it could still be valuable to pursue 2 in parallel, to implicitly optimize to the polymorphic-in-monomorphic form if we can find a good heuristic indicator that applying the optimization is likely to be a net benefit. Who knows, maybe it could even be a good strategy to do this for every applicable function just to reduce the volume of code in intermediate representations even if the compiler decides to re-duplicate the object code at the end.

Related discussions:

1 Like

It seems like neither of these two ways lets us pass type information through a polymorphic function. As far as I understand them, neither could be leveraged as low-hanging fruit to expand object safe traits into a specific reliable subset of generic functions.

The issue isn't just about code optimization, it's about passing type information through polymorphic functions in such a way that we can leverage our knowledge that it is both polymorphic and generic, the example that most comes to mind is object safety.

In languages that auto-box most values, a very generous portion of code that gets written ends up being pointer juggling underneath. It happens less is Rust, but you currently can't leverage this style (in the type system, not just from an optimization angle) at all even if you want to.

The polymorphic-in-monomorphic form doesn't quite match the description of what I'm discussing here either. That describes the situation where a very short computation turns a generic function into a non-generic function. If you make the generic and non-generic code explicit, Rust can leverage that. This is something which we couldn't as easily leverage to extend object safety as you have the same trouble putting the generic section of code in a virtual table.

Instead, I'm describing the situation where generic code is already polymorphic and if it were to get monomorphized, it would generate identical code for large predictable classes of input (perhaps depending on pointer-sized, but not depending on type info). This feels similar to what the momo-crate is doing because they look similar from an optimization standpoint, but as potential low-hanging fruit to expand object safety they're still leagues apart.

Does the difference make sense as I describe it?
Am I misunderstanding you?

2 Likes

It sounds like you want to expand what can be "polymorphized" (in contrast to monomorphized) by exposing some very limited type information to otherwise fully polymorphic code.

For example, say your generic code takes a slice of objects and invokes some dyn trait "Sub()" on adjacent pairs. Maybe it could be formulated to be a single polymorphic copy if only your function just knew the array stride. Alas the function being generic over different slice types means that it can't do that, and the impls for i32 and f64 are regrettably duplicated even though your code doesn't really care what types they are, and both impls could have been collapsed into one if we somehow provided the stride to the code at runtime.

Is this the kind of issue that you're taking aim at?

1 Like

Yeah.

Think about the way Rust currently does generic lifetimes, they're always polymorphic. The same code is generated regardless of the lifetime, but the lifetime is remembered in the type system and used later in the analysis of the program. For generic lifetimes it's easy because they are always (and without exception) polymorphic, but there are many cases where references to some type act exactly the same way.

Right now, generic lifetimes are the only types of generics that are object safe in a trait. This works because they're explicitly polymorphic, not just as an optimization, but in a way that both the compiler and programmer can both understand easily and maintain.

Is it possible to do the same trick with references to types? It would have to somehow have an emphasis on it being clear to a developer when the polymorphic rules are being upheld, so such code can be consistently written, updated, and maintained. If so, this would greatly expand the power of trait objects.

That's my thesis, I suppose.

4 Likes

The difference between lifetimes generics and type generics is that lifetime generics can't affect the memory layout of types while type generics can. If you want to polymorphize all type generics, you will have to store the type definition for all generic types and pass around type definitions for types used as generic parameters at runtime in addition to copying all the layout logic of rustc into libcore I think. For specialization you did also have to store all specializing implementations somewhere. While all this should be doable, it did likely come at a non-trivial runtime and complexity cost. Maybe it could be done for debug mode, but I don't think it will work for release mode.

1 Like

I'm not sure I understand how temporarily forgetting type information can possibly have a runtime cost. Is there any chance you can explain using the canonical example given above?

Even if you need to deal with different pointers (by, say, compiling multiple versions), can't you still temporarily forget about the generic T and more or less use the function polymorphically? Certainly there shouldn't be any runtime costs above monomorphization in such cases?

Complexity is another issue though! It's proving tough to even agree whether we're talking about the right thing. That's a red flag to be sure.

You need the type information to compute the memory layout of values. Either at compile time when doing monomorphization or at runtime when doing full polymorphization (a subset of the cases doesn't need it at runtime, but it is necessary in the general case). The former option has a compile time cost, while the later option has a runtime cost.

Why would you be computing the memory layout of values in this case? The type you have a reference to is already somewhere in memory and you aren't dereferencing, so you're not interacting with the layout locally in such functions.

What am I missing?

The type parameter is always used behind a reference and never there are no field projections involving it and no methods called on it, keeping the type info at runtime isn't necessary, but as soon as any of these conditions doesn't hold (like I expect to be the case most of the time), it will be necessary to keep the type info at runtime.

This is what a lot of the discussion in this thread has been about. How useful is it to operate under such restrictions? (And also, how hard is it to explain such restrictions to both developers and compilers... ignoring the second, the first seems a hard sell already)

My feeling is that if there is a benefit (Restricted generics in object safe traits for example), a lot can be done if a type parameter is always used behind a reference and there are no field projections involving it and no methods called on it.

When trying to write libraries for web, I'm often finding myself in this scenario. The library could be small and take a slight performance hit on dynamic dispatch, but trait objects are a bit too restrictive so I need to use a bunch of work-arounds that make it hard to colocate code cohesively while maintaining a nice API and keeping generated code size small.

I think the messaging so far as been that my use-case isn't that common and such support is still a long ways out (if it happens at all). That's okay, it has been an interesting discussion none-the-less.

5 Likes

I think we cover a lot of the cases where it is possible with -Zpolymorphize already. I think it would be possible to improve it to allow it to work on fn pointer_identity<T>(&T) -> &T (but not pointer_compose), but I'm not sure by how much effect that would have. I also believe -Zpolymorphize still has some bugs, so enabling it by default isn't possible yet.

Oh! Neat. I can't find anything on Zpolymorphize, do you have a link?


I do think pointer_compose demonstrates a serious complication.

Consider the following (I've not included lifetime annotations to keep it looking simple)

struct Holder<T> {
    value: &T
}

impl<T> Holder<T> {
    fn print_size(&self) {
        println!("{}", size_of_val(self.value));
    }
}

fn make_holder<T>(value: &T) -> Holder<T> {
    Holder { value }
}

I think that at first blush, it looks make_holder should be pretty close in spirit to pointer_identity. I'm not sure that it really is. In this case, Holder is pretty simple and very likely to look identical for most references, but I'm not sure this generalizes.

In general, Rust doesn't guarantee that Holder<i32> and Holder<i64> will have the same layout in memory. I do think that passing references into containers like this would be useful, but it pushes this problem into struct layout as well. Holder's size/layout is not affected by the generic in its definition, so it's theoretically "safe" to return from a polymorphic function.

But that comes with all the same concerns that have already been shown for polymorphic generics in functions/methods.

In order for it to work, shouldn’t Holder be #[repr(transparent)]?

I mean, holder is a stand-in here for generic structs that only reference their generic parameters. Here's another example of the same thing where #[repr(transparent)] wouldn't help.

struct Example<T,R> {
    p1: &T,
    p2: &R,
    count: u8 
}

Since v1 and v2 hold references and not T & R directly, Example really only needs a single layout. It's the same issue again where we want to type info to pass through but we want to thing itself to have a single implementation.

Well, specifically thin references.

Change it to

struct Example<T: ?Sized,R: ?Sized> {
    p1: &T,
    p2: &R,
    count: u8 
}

and it has at least 4 layouts.

Not to mention that, even without ?Sized, if we ever do https://github.com/rust-lang/rfcs/pull/3204 -- as I hope we will -- then Option<Option<Option<Example<_, _>>> will have different layouts depending on the alignments of the generic arguments.

Yeah, this is a hiccup to be sure. At 4 layouts, they could still be used with a trait object, but I take your point. Functions may me polymorphic over some generic T, but not over the a generic reference to T. Each type of reference may need it's own treatment. This does become a problem as the number of properties/parameters grow.

Forcing polymorphic functions to stick with thin references (for example) makes this tractable, but feels like it violates the principle of least astonishment.


I don't think I fully understand this RFC, though it does look like it could become more or less a hard-stop for this idea. Seems like the low-hanging fruit for expanding the power of trait objects might not be so low after all.