Generics and Compile-Time in Rust

https://pingcap.com/blog/generics-and-compile-time-in-rust/

by Bella-Xiang • 6 years ago

268 86 6 years ago

the_duke• 6 years ago

There are plenty of Rust features I'd love to see finalized, like GAT ( HKT, sort of), generators, async trait methods, custom test frameworks, ...

But there is an area that could have a big impact on certain (mostly higher level) domains, yet doesn't seem to get much attention: better trait objects.

They are severely limited in a few aspects:

* only a single trait/vtable

* casting is only available with Any and you can't cast between different traits, requiring really awkward super-traits with manual conversion methods or hacks like mopa [1]

* object safety rules are cumbersome and prevent certain important traits like Clone to be available, leading to clone_boxed, clone_arc everywhere, or proc macro solutions like dyn-clone [2]

* ...

Doing anything more fancy with them usually feels annoying. Therefore the standard library and entire ecosystem strongly favor generics and monomorphization.

This is generally fine and has worked out well for the language, but there are plenty of use cases where more advanced trait objects could reduce code size and compile times with very small impact on performance, while also enabling some interesting new patterns.

I realize there are plenty of implementation challenges that make work in this area far from trivial in the current language, but it's frustrating to miss out on part of a toolbox.

I think Swift is an interesting comparsion. The languages are similar in quite a few aspects, but Swift often prioritizes small code size and dynamic dispatch over monomorphization. Compile times aren't that great either, though...

ps: it is briefly mentioned in the post, but switching to LLD has provided noticeable build time improvements on most of the binary crates I am working on.

[1] https://github.com/chris-morgan/mopa [2] https://github.com/dtolnay/dyn-clone

whb07• 6 years ago

Hypothetically couldn’t you implement this as a macro extension of sorts?

m-hilgendorf• 6 years ago

You can, it's how com-rs [0] works and we're co-opting it in vst3-sys [1] for non-Windows targets. It's painful, unsurprisingly. There are some people working on better abstractions, but I hand-coded a VST3 plugin using those macros just for the FFI-safe COM bindings and it is verbose and particularly unsafe [2]

I'm in disagreement with the parent, dynamic dispatch through vtables is only a zero-cost abstraction across FFI boundaries. Personally I'd ballpark about 33% of the value-add of traits are shared interfaces on different types.

The real money is in associated types and trait bounds. The latter is still a serious type-checking requirement at compile time, and the former requires RTTI to support dynamically in some form - both of which have costs at compile and runtime.

All that said, there may be an argument that the features GP is talking about are covered currently by enum variants (many of the use cases one would have for base classes with associated member variables are done that way, for example), and if you could show how performance and ergonomics improved by increasing the semantic complexity of dyn trait objects - you'd have a strong argument to add it to the language. Just my two cents.

[0] https://github.com/microsoft/com-rs/

[1] https://github.com/RustAudio/vst3-sys

[2] https://github.com/RustAudio/vst3-sys/blob/master/examples/p...

saghm3• 6 years ago

This is generally fine and has worked out well for the language, but there are plenty of use cases where more advanced trait objects could reduce code size and compile times with very small impact on performance, while also enabling some interesting new patterns

To elaborate a bit on the part about new patterns, I've encountered issues where trait objects allow me to define APIs that otherwise wouldn't be possible. One example is when developing something like a database driver, you might define a trait EventHandler with the methods `handle_start_event` and `handle_completion_event`, where users can pass in values of types that implement EventHandler, and you call their handling methods whenever you start or complete an operation. The most straightforward way to specify this would be to have your client type have an internal vector of EventHandlers that you can iterate over and call the corresponding event handling methods whenever needed. If you use generics for this, then your client type will need to be generic over the type of EventHandler it can contain, which means you can't specify EventHandlers with different concrete types. The best way to get around this is to use something like `Vec<Box<dyn EventHandler>>`.

I understand the sentiment behind favoring generics over trait objects in the Rust ecosystem, as strongly preferring compile time costs to runtime costs when there's a choice between them is one of the more fundamental guiding principles to the Rust ecosystem (and is one of the things I really like about Rust), but there are patterns that trait objects allow that just can't be expressed with generics, and when you need to use one of them, it can be frustrated to hit some of those sharp edges you mentioned.

dllthomas3• 6 years ago

This sounds like the Existential Antipattern, from Haskell land. I don't know to what degree it translates to this setting.

https://lukepalmer.wordpress.com/2010/01/24/haskell-antipatt...

couchand2• 6 years ago

I'm confused. In that example, what's wrong with `Vec<Box<dyn EventHandler>>`?

kccqzy2• 6 years ago

The best way to get around this is to use something like `Vec<Box<dyn EventHandler>>`.

That's exactly the right solution to your problem. It's not a workaround. It is what you need.

What you need is a heterogenous collection of objects that implement a common interface. And the exact type isn't available to you because it's provided by the client. So you need to go through virtual (or dynamic) dispatch.

Just imagine how you might write this in C++: you just define an EventHandler abstract class and ask that clients inherit from it. Then you take pointers to EventHandler and store them.

Or imagine how you might write it in Haskell: simple existential types. The type class dicts are stored by the compiler into your data type to enable dynamic dispatching.

This is object-oriented polymorphism 101. I think Rust's anti-OO pendulum has swung so far that people can't even see that what they need is basic OO.

saagarjha• 6 years ago

Can we have the title changed to "Generics and Compile Time in Rust"? The way it's written know, I thought for sure it would be about compile-time programming using generics.

marcianx• 6 years ago

first, modern CPUs have invested a lot of silicon into branch prediction, so if a function pointer has been called recently it will likely be predicted correctly the next time and called quickly

Huh, TIL. Branch prediction is normally about predicting which branch an `if` would take. But apparently this applies to indirect jumps as well: https://stackoverflow.com/a/26240197/1082652

xenadu02• 6 years ago

This also applies to predicting the return address. You can assume any form of control flow has branch prediction. A surprising amount of silicon ends up being worth the cost if it can improve prediction just a little bit because a pipeline stall is so astronomically expensive.

secondcoming• 6 years ago

There's a famous SO question: https://stackoverflow.com/questions/11227809/why-is-processi...

gpderetta9• 6 years ago

for what is worth, indirect branch prediction has been added relatively recently (as in the last 20 years) in mainstream x86 cpus.

riquito• 6 years ago

I love when authors add how to read aloud something to help newcomers, as in

  fn print<T: ToString>(v: T) {

> We say that “print is generic over type T, where T implements Stringify”

aspaceman• 6 years ago

I also greatly appreciate this. Thanks for pointing it out for me!

seaish• 6 years ago

Does anyone actually call it "Stringify"? I would call it "to string".

smabie3• 6 years ago

Probably not. If they wanted people to call it Stringify then just name it stringify. Though personally, I like how instead of toString, Haskell calls it 'show'. Clear, to the point, and one word.

chrismorgan• 6 years ago

That’s not an instruction on how to read the code aloud, but a way of describing a certain fact about the function.

If you were actually reading it aloud, I would strongly avoid that use of the word “where”, because it’ll be confused with a where clause:

  fn print<T>(v: T) where T: ToString

The two are semantically identical, but they put the constraint in different places, so using the word “where” will confuse things, especially when it leads to you repeating the “T” in a way that where clauses do but the first form doesn’t.

For myself, I would probably read the original line of code as “function print, generic over type tee implementing to string, taking parameter vee of type tee”.

The where clause version I’d read as “function print, generic over type tee, taking parameter vee of type tee, where tee implements to string”.

platz2• 6 years ago

In general, for programming languages, there are two ways to translate a generic function:
1. translate the generic function for each set of instantiated type parameters
2. translate the generic function just once, calling each trait method through a function pointer (via a “vtable”).

The approach in haskell might be considered a variation of 2, since it involves indirection, but a little different from other languages normally using vtables, since it's not selecting different implementations at run time, but just looking up the pre-determined implementation through a new parameter.

In particular, the function is transformed into a higher-order function accepting a new parameter representing the dynamic to_string functinoality, then at the call site, the appropriate concrete implementation to_string parameter is inserted for the new transformed function, and similarly this new higher-order function 'print' only needs to be compiled once.

whateveracct• 6 years ago

One thing to note is Haskell is exceptionally good at inlining that explicit dictionary away.

Haskell isn't 0-cost-abstraction like Rust ofc, but it is definitely a minimize-the-cost-of-abstraction. And the control over said minimization is getting better with each release.

zenhack5• 6 years ago

Also worth noting that Haskell's type system is too powerful for monomorphization to work as an implementation strategy for generics in all cases. In particular, polyorphic recursion[1] means that attempting to just monomorphize anything wouldn't necessarily terminate.

Higher rank types also break this, as you can define things like:

newtype GenericThing = GenericThing (forall a. [a] -> a)

doManyGenericThings :: [GenericThing] -> [a] -> [a]

doManyGenericThings things list = map (\GenericThing f -> f list) things

Here, `doManyGenericThings` takes a list of generic functions, and applies each of them to its argument. You can't just monomorphize it, because you'd have to somehow also monomorphize every argument it is ever passed, which is a dynamic property that you can't know in advance (and again, may not be a finite set).

[1] https://en.wikipedia.org/wiki/Polymorphic_recursion

platz2• 6 years ago

It can't inline the dict in general though, and that is more the default situation than the opposite, unless the defn is in the same module

kccqzy2• 6 years ago

How is a Haskell type class dict different from a vtable?

It's in fact the same.

tome2• 6 years ago

Hmm, not sure what you mean. In the body of a function there is one class dict available. On the other hand there is one vtable per object, typically.

eeereerews• 6 years ago

One way is that it can handle functions like return : Monad m => a -> m a where m occurs only in the outputs. There's no input arg you could hang a vtable off of.

gpderetta9• 6 years ago

In c++ vtables ptrs are attached to object instances (although all instances of the same type vtable), while AFAIK in Haskell "vtables ptrs" (better known as function dictionaries) are attached to object pointers (also known as fat pointers). I believe that rust impl traits behave similarly to Haskell. I think go interfaces also use fat pointers.

The advantage is that "interfaces" can be attached to objects non intrusively (and outside of that object declaration, which is a huge win for interoperability), the disadvantage is that pointers are larger and there is no easy way to cross cast between interfaces.

In c++ "fat pointers" (also sometimes known are virtual concepts) are often implemented manually, the most well known example is std::function. We are all waiting for compile time reflection to be able to implement virtual concepts generically (you can only approximate it up to a point currently).

lalaithion• 6 years ago

If you have

    Obj f(Obj a, Obj b);

in C++, you pass in Obj's vtable twice, and the returned value includes a vtable.

If you have

    f :: Obj a => a -> a -> a

in Haskell, you pass in one dictionary. If you have

    f :: (Obj a, Obj b) => a -> b -> a

in Haskell, you pass in two dictionaries. If you have

    f :: (Obj a, Obj b, Obj c) => a -> b -> c

you pass in three dictionaries, and the caller gets to decide what the concrete type of c is, NOT the function implementation.

    data DynObj = forall c. Obj c => DynObj c
    f :: (Obj a, Obj b) => a -> b -> DynObj

In this case, you pass in two dictionaries and the returned value has a vtable. This essentially is what C++ does.

cma• 6 years ago

Sounds like static polymorphism, done in C++ with: https://en.wikipedia.org/wiki/Curiously_recurring_template_p...

amw-zero2• 6 years ago

Once all of this compile-time metaprogramming and code execution starts to happen, it always makes me ask: doesn’t this just conclude with dynamic typing? I’m currently a static typing lover. But it’s almost as if we’re just looking for the full power of a programming language. Why not just use the language itself instead of a weird, stratified compile time language?

hedora• 6 years ago

The weird stratified compile time language lets you create DSLs that generate and typecheck the program you’re trying to write. I’ve written a lot of C++ (and no Rust), but if the compile time language is turing complete, then you can push all sorts of correctness and type checks to compile time.

This is really, really powerful.

Even with unsafe C++, I’m used to writing very high level, high performance concurrent code. If it crashes after it’s passed CI testing for a week or so, it’s probably a hardware bug.

(Of course, there are exceptions, but those fall outside of the parts I have the compiler check for me.)

amw-zero2• 6 years ago

But what you can prove at compile time is rarely useful. You can use phantom types, smart constructors, and the like, but after a while you need a runtime to do anything interesting.

An example: this function is only valid on positive, odd integers in the range 3-91. With any static type system, this has to be a runtime check anyway.

I’m not an expert on dependent types, but that sounds like what those try and solve. But at that point, you just want compile time to be a full program, which has all of the same pitfalls as the runtime of a program.

_bxg1• 6 years ago

Any static type system prevents you from doing some subset of things that you could do with a dynamic type system. But there are obviously lots of things you get in exchange for that power. Type system evolution, usually, is about trying to colonize a larger and larger portion of that possibility space and put it under the domain of "statically checkable". It will never cover the whole thing, but it's still really valuable work and great strides are still being made.

josephg• 6 years ago

Not necessarily. The cleanest version of this sort of thing I’ve seen is zig’s comptime. Basically you can annotate loops, conditionals, function parameters, etc to be evaluated at compile time instead of runtime. You’re still writing zig - it’s the same language; just some of your code runs in the context of the compiler.

One really nice use of this is printf. In C, printf needs a remarkably large amount of code and it’s quite slow. In zig, printf marks the format string as comptime. Then the compiler runs the code looping over and evaluating the format string, then unrolls the result into the binary. The output ends up being a few terse calls to write / format with no extra machinery at runtime. And you get clean compile errors if the format string doesn’t match your arguments - all with no special casing in the compiler.

More detail, with code: https://ziglang.org/documentation/master/#Case-Study-printf-...

I think nim has something similar.

I’m surprised rust went with macros instead of something like comptime - though I assume there’s some trade offs I’m not aware of.

akiselev• 6 years ago

I’m surprised rust went with macros instead of something like comptime - though I assume there’s some trade offs I’m not aware of.

Rust has procedural macros which are Rust libraries built and run compile time that can transform raw tokens into valid Rust code (or more raw tokens for nested macros). Procedural macros can annotate any statement or code block - although some specific ones might still be on nightly only.

smabie3• 6 years ago

What's the difference between comptime and macros? they seem pretty much the same at first glance.

renox• 6 years ago

I agree with you that Zig comptime seems really nice.

As for the format string at comptime, it's a big improvement over C sure (no missing parameter, yes!) but I still feel that it's still much less readable than Python f-strings.

lmm3• 6 years ago

Dynamic typing would be throwing the baby out with the bathwater. Look at stage polymorphism (e.g. MetaML) for the right way to do this.

megameter• 6 years ago

If you follow through on this thought further you end up in the realm of the dynamic languages with very strong metaprogramming capability - the Lisps and Forths. With these, the reduction of the language is so complete that changing domains to the meta-mode is as easy as falling off a log. And nothing stops these languages from having a combination of useful static checks, high performance output, and fluidity of expression: they are powerful enough to be parsers at one instant, code generators at another, and optimizers at a third.

The main reason not to do it that way is the "you're on your own" nature of dynamism, in and of itself. If you don't come up with a good structure for checking things, the language isn't going to do it for you. And this is fine within the context of the quick hack or the home-grown type system, but less useful for proving broad, general properties about the code. Particularly when this is an industry where the majority of programmers are assumed to be hugely inexperienced, with less than 5 years under their belt, and trusted to build fairly complex systems.

Classical static type systems(your Pascal, Java, etc.) only really know the world in terms of combinations of primitives; they don't prove much beyond simple matching of input to output. But that's yesterday's approach - it's not what industry is looking towards.

What the newer static languages(of the Haskell and Rust ilk) have converged upon is to bolt a powerful constraint solver engine to the type-checking system, which in turn shapes the whole language around pleasing the type-checker. The resulting minimum code quality is often higher, but also semantically torturous.

Reelin• 6 years ago

What does dynamic typing have to do with the language used for CTFE? (Have I misunderstood you?)

D has fairly permissive CTFE which uses the language itself; it remains statically typed.

Haskell is statically typed while the type system can be made Turing complete by using certain language extensions.

The Terra language (embedded in Lua) is statically typed and is metaprogrammed using Lua.

Racket is certainly dynamic, but Typed Racket is ... well it's still dynamic, but type annotations are statically checked.

baby• 6 years ago

Rust compile times are just really really bad.

ed25519FUUU• 6 years ago

* Note that in these examples we have to use inline(never) to defeat the optimizer. Without this it would turn these simple examples into the exact same machine code. I'll explore this phenomenon further in a future episode of this series.*

I’m really eager to use more rust, but three optimizations really turn me off. Optimizing the compiler feels like meta programming.

prerok• 6 years ago

What do you mean? I think that these statements are there only so that the author can provide a glimpse into the difference of code generation between the two examples. You would not want to disable it when writing code for an actual project.

rob74• 6 years ago

A true gem from the "comments on the last episode":

The compile times we see for TiKV aren't so terrible, and are comparable to C++

So if you're already used to the terrible compile times of C++, the compile times of Rust won't seem that bad in comparison. And Mozilla, where Rust started, mostly relies on C++. That does explain a lot...

Ygg2• 6 years ago

That, and the more you optimize for runtime performance, the less compile-time performance you have.

Gibbon12• 6 years ago

I always keep coming back to code gets compiled a lot more than it gets modified. In C land it's typical to run analysis tools on a codebase as a separate process. Seems doing the sorts of checks Rust does on every compile seriously wastes programmers time.

Also a problem that for 95% of code written speed doesn't matter at all.

Combine those two and programmers a paying a lot for something that isn't needed. AKA 99% of the time you're compiling a module that hasn't changed. And 95% of the code in those modules speed doesn't matter at all.

blackrock• 6 years ago

Nim or Rust?

Some Rust syntax seems overly confusing. But Nim doesn’t really have strong corporate support backing it.

But, both are still new, and missing a lot of libraries.

Rust is annoying, where there aren’t standardized libraries for common functions. Just some guy’s tweet to use some random cargo crate from someone.

twoodfin2• 6 years ago

This is a good article, but rather misses the point on performance of monomorphization vs. dynamic dispatch. Yes, CPU indirect branch predictors are getting better, and compilers are getting smarter about identifying opportunities to turn dynamic into static dispatch. But inlining remains the optimizer’s silver bullet, enabling a host of dependent optimizations. It’s those further optimizations that make the primary performance difference for static calls.

AndrewBissell• 6 years ago

I did some investigation into the performance impacts of using the _Generic keyword in C11. It was a toy example so not necessarily broadly applicable to real world code, but a good 70 or 80 percent of the speedup from generics seemed to come from inlining.

https://abissell.com/2014/01/16/c11s-_generic-keyword-macro-...

twoodfin2• 6 years ago

Inlining is also what’s behind the classic “C++ is faster than C” example of “sort()”.

vlovich123• 6 years ago

I think an area ripe for improvement is compilers to think about which monomorphized variant is valuable & can benefit from that inlining vs where the dynamic dispatch is sufficient. Start with PGO & I'm sure smarter people will investigate how that can be done for 80% of the benfit at compile time without PGO.

estebank2• 6 years ago

I am convinced that `rustc` should have an "optimizer lint" phase with all the same checks other languages perform to change the behavior of the code and instead suggest changes that affect running code and compile time, like `Box`ing fields or variants that disproportionately affect the size of an `enum`[1] or to suggest changing generic params to trait objects or vice versa[2] when it makes sense.

The advantage of not doing it automatically is that the behavior of the code once compiled can be always inferred from looking at the code, no magic and sudden changes in behavior because some threshold has been passed in some optimizer.

[1] https://github.com/rust-lang/rust-clippy/pull/5466

[2] https://github.com/rust-lang/rust-clippy/issues/14

Generics and Compile-Time in Rust

Related Stories