static-vs-dynamic-dispatch.md

Static vs Dynamic dispatch

AKA: Why is consuming an Iterator from glutin so damn hard?

In Rust, like many other languages, there are two different ways to call a function: static and dynamic dispatch. They're used in different scenarios and each have their own pros and cons, which are summarised thusly:

Static calls tend to be faster because they do not require the use of a lookup table, which incurs overhead as the compiler has to 'find' the function it is calling at runtime.
Dynamic calls tend to be more conservative of space as they can be re-used. This isn't so much an issue with functions like strcpy, but with functions that have multiple types of arguments (generics, for example), the code for the function must be duplicated.

How does this relate to consuming an Iterator from glutin? Well, in my naivety as I was learning both Rust and OpenGL at the same time, I wrote something like this:

fn main() {
  let display = ...

  loop {
    for event in display.poll_events() {
      ...
    }
  }
}

This works fine, but having that loop in that place and not being extracted to a function is an eyesore. It would look much nicer if it were written something like this:

fn main() {
  let display = ...

  loop {
    let events = display.poll_events()
    handle_input(events)
  }
}

fn handle_input(iter: Iterator<Item = Event>) {
  ...
}

However, therein lies the problem. The above code - provided you added in the elided code - would throw a compiler error unpon reaching handle_input. If we look at the Glium docs, we can see that poll_events returns a PollEventsIter, which in turn implements Iterator, like so:

struct PollEventsIter<'a> {}
impl <'a> Iterator for PollEventsIter {}

So, what gives? These are type compatible - why does the compiler complain? The answer lies in how trait objects relate to parameters; when you ask for a trait in a parameter in such a way, you're asking for a Trait Object.

In case you don't know already, a Trait Object is an object that implements a trait. Such an object has an unknown definite type at compile time; all that is known is that the type definitely has an implemention of a given trait (in this instance, Iterator). As a result of this, the ultimate type of the object can only be determined at runtime; that also means the memory layout of iter, how many bytes to allocate on the stack for an object of its type, is unknown at compile time and only known at runtime.

This means two things:

Rust must use dynamic dispatch for the Iterator's methods (because Rust does not know where, at compile time, the memory location of the methods are).
Rust cannot accept ownership of an object that implements the Iterator trait in this manner (because passing it in parameters like this would require Rust to know the size of the object so it could be allocated on the stack).

Using dynamic dispatch is not necessarily a bad thing, but the second point is definitely a problem. So, how do we get this code to compile? As it turns out, there are two² ways: One way preserves dynamic dispatch, and the other takes advantage of a feature of Rust called monomorphisation. We'll start with the second approach and I'll illustrate both examples in the conclusion.

Monomorphism

Monomorphism is a technique used in Rust (and other languages, like C++). The name comes from the opposite of Polymorphism and is used to illustrate that instead of having a single function that can accept many types, Rust will create multiple functions for each type you pass into the same function. This relates to our Iterator example, because it means that if we specify the Iterator trait as a generic bound instead of a parameter type, Rust's type system is intelligent enough to monomorphise each invocation of that function at compile time. In other words, if we use a generic bound, Rust will know - ahead of time - the size of the objects being passed to each invocation of the generic function and their memory layout, which enables the use of static dispatch (which, as mentioned before, tends to be faster¹).

In visible terms, that means something like this:

fn foo<T>(item: T) { }

fn main() {
  foo(5);
  foo(true);
}

Will be compiled into the following code at compile time (note that if you put this exact code into a Rust compiler it would not work because Rust does not support method overloading, but this is good enough for illustrative purposes).

fn foo(item: bool) {}
fn foo(item: i32) {}

fn main() {
  foo(5);
  foo(true);
}

This ultimately means that if we were to use a generic bound to accept our Iterator, rather than trying to retrieve it directly from parameters, that the method would be monomorphised and Rust would know the size of the Iterator (due to it's seriously cool type system) at compile time, and thus have no issues.

Putting it together

So, here are the two ways we could potentially solve our handle_input compiler issue code²:

fn handle_input<I>(iter: I) where I: Iterator<Item = Event> {

}

// or

fn handle_input(iter: &Iterator<Item = Event>) {

}

The first approach also has the benefit of not requiring any change on behalf of the caller in our original code; we can just call handle_input(display.poll_events()); the second example however would require us to pass a reference of &(display.poll_events()) to handle_input.

Footnotes

This tends to be a micro-optimisation, however, in this specific instance I'm opting to prefer static dispatch because this iteration tends to be done many times - indeed, this is in the game loop - and so is performance sensitive.
Note that we could also have encapsulated Iterator into a Box instead of doing an immutable borrow. This may be useful if we need the iterator to outlive its parent scope, but that isn't the case here.

punmechanic/article.md