1. 28

  2. 7

    Welcome to Rust! If you’re interested and want to dig deeper on the topic, search for “monomorphic dispatch” which is what you’re describing in the post. Monomorphic dispatch can happen in either the return position (as in the post) or the arguments. Monomorphic dispatch is a form of “generics” (and sometimes simply referred to as such) where the compiler looks at the type placeholder in the function signature and all (possible) uses of the function, then generates individual functions with the correct signature. So fn foo<T>() -> T with two possible types (for simplicity, lets say the concrete types are Bar and Baz), the compiler generates two functions; fn foo_Bar() -> Bar and fn foo_Baz() -> Baz. Hence the mono in monomorphic (i.e. one function per concrete type in the actual program). This is in contrast with “dynamic dispatch” where the concrete type isn’t used at compile time, and instead uses indirection (via pointers) to have just one version of the function, and at runtime follows the indirection to arrive at the concrete types actual implementation. Rust uses “Trait Objects” (i.e. dyn Trait) for dynamic dispatch.

    To recap, monomorphic dispatch is where the compiler generates individual functions for each concrete type, whereas dynamic dispatch is where the compiler uses indirection with a single function that then dynamically (at runtime) finds/utilizes the correct implementation.

    Most often, monomorphic dispatch is preferred for performance, but can suffer in readability and code bloat (i.e. binary size). While dynamic dispatch takes a runtime hit for the indirection, but makes reading the code easier and a smaller binary footprint. This isn’t always the case, but generally speaking I’d say its a decent rule to start with.

    1. 13

      I’m going to quibble on the terminology here a bit. The type of polymorphism you’re describing is parametric polymorphism, and monomorphization is one strategy for dispatching parametrically polymorphic functions statically. You could call the strategy “monomorphic dispatch” as you do here; the distinction I’m drawing is between the kind of polymorphism (parametric polymorphism) and the implementation strategy (static dispatch with monomorphization / monomorphic dispatch).

      Other common kinds of polymorphism, since I’m getting into it:

      • Subtype polymorphism: polymorphism based on the substitutability of one type for another. Different languages determine the substitution relation in different ways. Languages with subclasses and superclasses establish a subtype relationship that way (subclasses may be used wherever the superclass is expected); Rust uses subtype polymorphism for lifetime bounds, treating any lifetime longer than the required bound as substitutable for it.
      • Ad hoc polymorphism: polymorphism based on the number and types of the inputs to a function. This is not part of the type system, but is instead about the selection of functions for dispatch; it is sometimes called “operator overloading,” “specialization,” or “multiple dispatch” (all different flavors of the same thing).
      1. 1

        The article is about parametric polymorphism is general. Your comment is about something different which is how to compile this using either monomorphization (like Rust or C++) or some kind of dynamic dispatch (like Java or OCaml I think).

      2. 4

        FWIW, Swift has this too. It’s not limited to generics; in Swift you can define multiple normal functions with the same parameters (if any) but different return types, and the compiler will do it’s best to choose the right one.

        On the downside, it must get complicated for the compiler to solve these puzzles, so I’m sure this feature contributes to both Rust’s and Swift’s infamously slow compile times.

        1. 5

          Rust’s compile times aren’t due to issues like selecting the right return type, but rather for things like code generation. Monomorphization as a strategy for implementing statically-dispatched parametric polymorphism requires the generation of distinct copies of each generic type or function based on the concrete types it’s actually used with. The time to perform this code generation and update call sites can be long. Monomorphization can also lead to code bloat, though there are techniques to manage that bloat.

          I don’t know as much about Swift, but I doubt that type resolution is a major cause of slow compilation.

          1. 3

            I remember at least one case where the type resolution was a major compilation time slowdown, it was checking 11k+ alternatives for a common function before it was fixed.

            1. 2

              Your link about using an inner function to limit the code generated by monomorphization is super interesting.

              1. 2

                Glad you like it! I wrote that post.