Types and Memory

Rust’s type system is powerful and gnarly. When I bump up against the compiler, it’s usually because I have lost a feel for what is happening under the hood. While types are an abstraction meant to protect our poor minds from complexity, I think it is valuable to have an intuition as to what is hidden for when things start to fall apart.

On this journey, I wind it way back and then shoot across everything, hopefully connecting some dots on the way. So to start, we are going back to C. C is great because there is little abstraction going on between it and the interface provided by a CPU. It keeps you honest.

C

Every type in C is either an object or a pointer. An object is defined in C as “a region of data storage in the execution environment, the contents of which can represent values”. So a chunk of bits which means something to someone. And that something is a type. If an object is type int, the program knows the size of the object and what its pattern of bits represents.

A pointer is a memory address. They can point at objects or functions. Pointers are what let C simulate call-by-reference instead of being call-by-value all over the place. The type of a pointer is derived from whatever it is pointing at, called its reference type.

Object pointers make a lot of sense to me, the hold a memory address which points to an object on the stack or the heap. But function pointers sounds a bit more complicated. What is a function type in C? How can we point at it? How does that influence the CPU’s program counter?

+------------------+
|      Stack       |  Local variables, function calls.
|        ↓         |
|                  |
|        ↑         |
|       Heap       |  Dynamic allocations, malloc.
|                  |
|    Data Segment  |  Global variables.
|                  |
+------------------+
|       BSS        |  "Block Started by Symbol" uninitialized global variables.
|                  |
+------------------+
|   Code Segment   |  Program machine instructions.
|                  |
+------------------+

A program’s memory.

That code segment part contains the symbols which represent the machine code. A CPU exposes an interface where it can accept symbols which map to instructions it can perform. For example, 10 might represent an ADD instruction which takes two numbers and adds them together. The fact that the program’s machine instructions are represented with symbols (usually binary) just like the data it acts on was a big revolution back in the 40s with John von Neumann’s EDVAC. But anyways, the C compiler boils instructions down to their machine codes and puts them in the code segment. “Segment” is a bit of a historical term when the memory was much more literally segmented. These days, its just a special spot for the machine instructions.

OK so back to function types and pointers in C. A C program can contain a function definition who’s machine code will be dropped somewhere in the code segment. A call to that function is compiled into a machine code CALL, a control flow instruction, which reads the function’s machine code into the program counter and holds onto the return address when the function is done. What is different about reading the machine code versus reading some data over on the heap? A function name in C “decays” to a pointer to its instructions in the read-only code segment.

This makes enough sense, but in C, you generally see a function’s signature declared separately in a header file. The C compile process needs to tie these things together in order for machine codes to be wired up. The compiler uses declarations in the first few passes to create an object file with machine code. This essentially has placeholders in it for the implementations of the declarations. The linker then takes a pass at all the require object files (or libraries) and creates an executable by filling in those blanks. So from a mental model perspective, the declaration is kinda like a pointer to the machine code.

// Header file foo.h.
// Function declaration (a.k.a. prototype).
// Establishes return type, name, and parameters. It's signature.
int add(int a, int b);

// Source file foo.c.
// Function definition.
// Creates code in code segment.
int add(int a, int b) {
    return a + b;
}

Function declaration versus definition.

A function definition which contains parameters (even void) is called a function prototype. You can technically declare a function without any parameters, but this is a deprecated feature of C and should be avoided. So let’s just assume prototype usage.

Function prototypes are definitely not objects because they cannot be modified or owned. But they are a special type of pointer since they get resolved at link time, where usually pointers can be modified at runtime. When referenced without calling the function, as in add instead of add(1, 2), the prototype is a pointer. This is what C calls “decaying” to a pointer, if you use the name in a context requiring a pointer, the compiler will decay it for you.

// Function prototype.
int add(int a, int b);

int main() {
    int (*func_ptr1)(int, int) = add;        // Direct assignment, which decays to pointer
    int (*func_ptr2)(int, int) = &add;       // Taking address explicitly

    int result1 = add(5, 3);                 // Direct call
    int result2 = (*func_ptr1)(5, 3);        // Dereference and call
    int result3 = func_ptr1(5, 3);           // Implicit dereference and call
}  

Function prototypes and pointers.

That pointer type syntax is pretty gnarly, here is how to read it. A simple example is int *ip;. Or the equivalent int* ip, but the former is maybe preferred since it gets confusing with multiple variables and qualifiers. In either case, the pointer attaches to the variable not the type, so it reads “ip is a pointer to an int”, not “ip is an int pointer”. So it kinda reads left to right, which isn’t great, but even worse is it’s actually way more confusing!

Let’s lay some ground rules. A declaration includes one basic type (e.g. char, int, etc.) and zero or more derived types (pointers, arrays, functions). Array and function type operators have higher precedence than the pointer operator. Parenthesis can also be used for grouping.

• * // A pointer to…
• [] // An array of…
• () // A function returning…

Some recommend the “spiral rule”/“clockwise rule”, but it has some broken corner cases. Looks pretty though.

     +-------+
     | +-+   |
     | ^ |   |
char *str[10];
 ^   ^   |   |
 |   +---+   |
 +-----------+  

“str is an array 10 of pointers to char”.

A more sure fire way is the “go right when you can, go left when you must”, where you start at the variable name and end at the basic type. Parenthesis grouping force going left, or if you run out of things on the right.So trying out one of those gnarly ones from above, int (*func_ptr1)(int, int), “func_ptr1 is a pointer to a function which takes two ints and returns an int”. The parenthesis grouping is needed since int *func_ptr1(int, int) is “func_ptr1 is a function which returns a pointer to an int”. Cool, so we can read these gnarly types now. They aren’t super fun to write, but that is where typedef can help out.

// Without typedef - declaring multiple function pointers is messy.
int (*handler1)(int, int);
int (*handler2)(int, int);
int (*handler3)(int, int);

// With typedef - create a name for the function pointer type.
typedef int (*operation)(int, int);

// Now it's much clearer.
operation handler1;
operation handler2;
operation handler3;

typedef to the rescue.

So looping back around, functions are always pointers so are always passed-by-reference. There could be some slight performance costs to using function pointers versus a direct call, because a compiler can’t make as many optimizations with a pointer which can change at runtime.

While this is all cool there is another take-away, which is maybe not immediately obvious given my winding journey, but all function signatures in C have types with known sizes at compile time. A function has parameters with types and a return type. Each one of those can be a pointer, a fixed sized memory address, a basic type, or a set of basic types (e.g struct or union). All of these are known at compile time, the compiler does not have to make any guesses to memory requirements. Do fancy type system abstractions destroy this simplicity?

Polymorphism

Back in 1967, so actually before C came around in the 70s, some crazy Norwegians created the language Simula. It was the first to introduce ideas like classes and inheritance. Classes are the first step to adding some abstractions for the developer. They allow a developer to encapsulate data, add behavior, and introduce more type relationship structure (e.g. hierarchies). If these ideas were already being explored, why didn’t C add them in? C is designed to be a “system” language with minimal abstraction between the code and the CPU. And these are abstractions! As useful as they might be for a developer to organize their thoughts, they are implemented with a lot of code under the hood to get them to run on a CPU.

We can take a look at all the code required to implement such type systems, but first let’s look at what C offers. The most common bundling of data types is struct. A struct is just a composite of data types under a single name. The data members are stored sequentially in memory, very little abstraction. The syntax is…kinda gross.

struct <optional_tag_name> {
    type1 member1;
    type2 member2;
    /* ... */
    typeN memberN;
} <optional_comma_separated_variable_declarations>; 

Declaring a struct type.

Now you might assume that adding a tag name means you could then create a variable with just that name, but you have to keep using that struct keyword. A design decision was made to have a separate namespace for structs/unions/enums and regular identifiers (e.g. variables, functions, typedefs).

struct value {
    int x;
};
int value;  

This looks wrong, but is legal!

Like other quirks of C, this was driven to make the compiler’s job easier. Specially here, to allow for a single pass. And things like self-referencing members are easy to implement in the compiler.

typedef struct Point {
    int x, y;
} Point;  // Point now lives in regular namespace

Point p;  // Can use without struct keyword

typedef one-shot to move a struct name into the regular namespace.

So what if you wanted to write a simple class type in C?

// A Counter class using the nifty typedef shortcut to get Counter into the regular namespace.
typedef struct {
    int value;
    // Function pointer that takes a pointer to its own struct type.
    void (*increment)(struct Counter* self);
    int (*get_value)(struct Counter* self);
} Counter;

// Possible function implementations.
void counter_increment(Counter* self) {
    self->value += 1;
}

int counter_get_value(Counter* self) {
    return self->value;
}

// Initialize our "methods", like a constructor.
void init_counter(Counter* c) {
    c->value = 0;
    // Bind the functions to the function pointers
    c->increment = counter_increment;
    c->get_value = counter_get_value;
}

A simple class implemented with function pointers! Our old friends from the last section.

We could use this class, with a bunch of explicit hand holding compared to a fancy object oriented language which would implicitly hide this all away. It’s not pretty, but it is checking the boxes of data and behavior being bundled together.

// Initialize a counter instance on the stack.
Counter c;
// "Contruct" the instance.
init_counter(&c);

// Manually pass the "self" pointer to have access to the instance's data.
c.increment(&c);
int val = c.get_value(&c);   

Look, a class-like thing!

One can imagine how inheritance is implemented with pointers to base objects. A memory optimization for all the function pointers per-object is to put them all the function pointers for a class in a single table. These are often called virtual method tables (vtables). I don’t think they are strictly necessary to implement things like dynamic dispatch where a function is found at runtime, but they do make it nice and clean. An object has just one pointer to a table that can be easily maintained for all instances of the type. The trade off is a function lookup is now two hops instead of one, but that appears to be fine for most high level languages.

Another type system development in the early 70s came from some crazy Scots who created ML (Meta Language). ML brought some more type inference to the table and it made things like polymorphism look really slick. What is this polymorphism? In computer science, it’s the general strategy to expose one interface for multiple types. Us programmers like to write functions which take parameters which describe “anything that can do X” instead of “just type Y’s”. Then our logic is written down just once instead of having to copy it per type or require some translation code to get type Z to type Y before calling a function. This specific type of polymorphism is called parametric polymorphism and is usually implemented by modern languages with generics.

The inheritance feature has the more specific sub-type polymorphism, where a function can act on a parent type and not care about the specifics. But general polymorphism is usually cleaner and avoids the hierarchy mess of inheritance. But how is the implemented?

One way is through monomorphization where a compiler analyzes all the uses of a generic function, finds all the types which use it, and then stamps out a function for each type. So no runtime dispatching, this allows for regular static dispatching. Code generation can be accomplished with macros in C, so it’s technically possible. However, it would take a massive amount of hacking to match what modern compilers do with their type systems. But these are the basic ideas underpinning them.

The Rust Type System

Finally, how does this apply to a modern cutting edge programming language like Rust? The Rust design walks a bit of tightrope between it valuing zero-cost abstractions, but also supporting a rich type system. Like C, Rust does not want to add a bunch of layers between a developer and the CPU’s interface. Unlike C, Rust wants to have a type system to help programmers organize their thoughts. Other languages, like Golang, pull it in on both sides with a simpler type system and more abstractions (e.g. garbage collection). The pain point of Rust’s complex type system is that there are many ways to accomplish things, it does force you to use dynamic dispatching over static, but that means the programmer should be aware of both! Innocent looking type syntax tweaks can radically change how memory is allocated.

A benefit of Rust’s type system is that it pushes a ton of work to compile time and keeps the runtime as clean as possible. In the long run, this is the best case scenario for the programmer. But there is quite the learning curve for how to best work in the type system. For example, just look at this thing Box<dyn AsyncHandler<Future = Pin<Box<dyn Future<Output = Result<(), Error>> + Send>>>>.

pointers

As we saw with the rough C implementations of complex type system features, pointers are used heavily. In an effort to make things powerful but still performant, there are a lot of different types of pointers in Rust. And they can layer on top of each other. They differ on ownership, memory location, sharing semantics, mutability, lifetimes…a lot!

let x = 42;        // Value on stack

// Reference r does not own the data, x still does.
let r = &x;        // Reference on stack -> points to stack

// Box y owns the data which is moved to the heap.
let y = Box::new(x);  // Pointer on stack -> value on heap  

Some pointer types.

There are scenarios where you are required to use a pointer, so might assume the Rust compiler would automatically reference an object for you (decay?) cause hey, it’s required and we both know it. But the compiler won’t because it is also required for you to choose which type of pointer.

Just remember, no matter the pointer type, ref gets a reference to an object and deref gets an object from a reference (although it could be another reference).

generics

Rust supports generics through monomorphization. There are however some confusing parts of this syntax. There are unfortunately multiple ways to describe the exact same thing. There are also keywords (e.g. impl) which mean slightly different things if used if different parts of a function the signature. But just have to keep in mind, the point of generics is to just pump out a bunch of code for you to keep things static.

You can slap generics on structs, enums, and functions and they are relatively straight forward. Things get a little more interesting when we get to struct/enum methods.

struct Point<X, Y> {
    x: X,
    y: Y,
}

impl<X1, Y1> Point<X1, Y1> {
    fn mixup<X2, Y2>(self, other: Point<X2, Y2>) -> Point<X1, Y2> {
        Point {
            x: self.x,
            y: other.y,
        }
    }
}

impl Point<f32, f32> {
    fn distance_from_origin(&self) -> f32 {
        (self.x.powi(2) + self.y.powi(2)).sqrt()
    }
}

The craziest generics possible!

The thing that looks a little off here are the impl blocks for Point. The mixup method is defined in a block where X1 and X2 are declared to be generics used in the Point. Without that <X1, X2> after the impl, they wouldn’t be in the namespace. The distance_from_orgin method on the other hand is in a block where the types are “hardcoded” to f32. The method only exists on Point instances which are <f32, f32>.

The other thing that might look weird is all the different placeholder names for the generics. How are X, X1, and X2 workin together? X is an unbounded generic for the struct definition, it helps define what types the struct can hold. But Rust has a strong separation between the data and the behavior associated with a stuct. The behavior lives over in the separate impl blocks. The impl blocks need their own generic definitions which are used to match specific versions of Point. And beyond that, X2 makes the method generic. This means there could be many combinations of types the compiler will check and stamp out for us, but it will still all be static dispatch.

with bounds

Generalizing something over a type is cool, but Rust also allows you to bound that type. This requires the type to have certain behavior in order to use the generalized code. The code can then make assumptions about what it is working with, even if it doesn’t know exactly what it is. The real beauty of polymorphism.

Thinking back to how this would be implemented, the compiler needs to do a ton of work to make sure all the given types checkout. And then it can finally pump out the code for you. This is a feature that would really stretch the capabilities of C macros.

Bounds are a powerful type feature, but again, some syntax can be a little confusing.

Bounds applied to structs, enums, and functions are pretty clear, just like their unbounded cousins. Things get a little weird when dealing with methods. With unbounded generics, you can conditionally implement a method for a specific concrete type. You can also conditionally implement based on a bounded generic. But the bound needs to be specified on the impl block.

use std::fmt::Display;

struct Pair<T> {
    x: T,
    y: T,
}

impl<T> Pair<T> {
    fn new(x: T, y: T) -> Self {
        Self { x, y }
    }
}

impl<T: Display + PartialOrd> Pair<T> {
    fn cmp_display(&self) {
        if self.x >= self.y {
            println!("The largest member is x = {}", self.x);
        } else {
            println!("The largest member is y = {}", self.y);
        }
    }
}    

Conditionally implement a method based on a bound.

Generalizing traits gets pretty cool, but also a little unwieldy at times. The syntax for implementing a trait on a type in its simplest form is impl $TRAIT for $TYPE. How many spots can be generalized?

// Generic trait.
trait Container<T> {
    fn store(&mut self, item: T);
    fn retrieve(&self) -> Option<&T>;
}

// Generic struct.
struct Storage<U>(Vec<U>);

// 1. Implement for specific types.
impl Container<i32> for Storage<i32> {
    fn store(&mut self, item: i32) {
        self.0.push(item)
    }
    fn retrieve(&self) -> Option<&i32> {
        self.0.first()
    }
}

// 2. Implement generically - stays generic! Caller determines which types get spat out by compiler.
impl<T> Container<T> for Storage<T> {
    fn store(&mut self, item: T) {
        self.0.push(item)
    }
    fn retrieve(&self) -> Option<&T> {
        self.0.first()
    }
}

// 3. Implement for bounded generic types.
impl<T: Display> Container<T> for Storage<String> {
    fn store(&mut self, item: T) {
        self.0.push(item.to_string())
    }
    fn retrieve(&self) -> Option<&String> {
        self.0.first()
    }
}

Look at all these options!

For all the above options, the concrete type (the thing after “for”) was specified. Even if it itself took some generic. But you can actually make the whole type generic!…But what does that mean?

trait PrintDebug {
    fn print_debug(&self);
}

// Implements PrintDebug for all types that implement Debug.
impl<T: Debug> PrintDebug for T {
    fn print_debug(&self) {
        println!("{:?}", self);
    }
}    

The most standard example of a blanket implementation.

This is still all in the name of the compiler generating a bunch of code for us. A trait is still being conditionally applied to a type, but like, way more. Covering a ton of types, like a blanket. Great power, great responsibility.

return type

There is a tricky thing with a generic return type of a function. Where a function’s input parameter concrete types are determined by the caller, the return type is determined by the implementer. Different calls to a generalized parameter are easy for the compiler to stamp out. But an implementer needs to be careful not to do something that is impossible with the return type, like for instance, make it possible to return multiple types. If a function contains a conditional around two different types (e.g. IF return type1 ELSE return type2), the compiler can’t monomorphiz-ise its way outta that problem, the concrete return type can’t be determined.

This totally makes sense when you think about what the compiler is trying to produce. But was a surprising pain point for me coming from Golang. Maybe more surprising because the version of Golang I was using didn’t even have generics! Golang does have a concept of interfaces however, which allow for bounds on a parameter’s type behavior. Golang offers a nice guiding principle of “accept interfaces, return stucts” which makes it straightforward to write test-able, flexible code. Using a Golang interface on a parameter looks and acts a lot like a Rust bounded generic, which is probably why the difference are more painful.

// Golang interface.
func ProcessMessage(sender MessageSender) error {
    return sender.SendMessage("hello")
}

// Rust generic trait bound
fn process_message<T: MessageSender>(sender: T) {
    sender.send_message("hello");
}

Go interface versus Rust generic trait bound.

So what is the difference? The underlying dispatching. Golang is all about one-way-to-do-it-simplicity whereas Rust exposes all the knobs so you can hyper tune code to your use case. So while the syntax and high level goal is the same here, the Rust implementation stops short. The Rust code is more efficient, but more boilerplate-y.

Let’s say you have an app which takes some runtime configuration from the user. Maybe there is a flag that dictates if the messages are sent using an encrypted transport or not. One could imagine using some run of the mill dependnecy injection where a main function gets a Config instance from the runtime and then uses it to build an App type. The App is generic over the MessageService which has a handful of implementations, such as encrypted transport or plaintext.

struct App<S: Sender> {
    sender: S,
}

impl<S: Sender> App<S> {
    fn new(sender: S) -> Self {
        Self { sender }
    }
    
    fn send(&self, data: &str) -> Result<(), String> {
        self.sender.send(data)
    }
}

Simple dependency injection pattern with static dispatch Rust.

You might try to initialize the app with some simple matching code. And as clean as this looks, it does not compile. Over in Golang-land equivalent code would totally work because the type would just be App no matter how it is implemented. What is the Golang compiler doing for us in this case?

// App can be multiple types depending on the runtime setting...a no go.
let app = match setting {
    "encrypt" => App::new(EncryptedSender),    // Type: App<EncryptedSender>
    "plaintext" => App::new(PlaintextSender),  // Type: App<PlaintextSender>
    _ => StaticService::new(EncryptedSender),  // Type: App<EncryptedSender>
};

app.send(data);

This looks clean! And totally does not compile!

In Golang, the app variable is considered an App instance no matter which type fulfills it. Under the hood, it generates some code that does the “Is this a encrypted type? OK then go here for the function implementations, otherwise go here”. Rust does not hide this from us (but if it sounds good to you, check out the next section!). The app variable is essentially a union of two types, but that isn’t allowed in Rust. But Rust does have a neat feature, enums, which unions types! Sounds useful.

Enum dispatch pattern.

There are a few layers of boilerplate here which can get confusing, but they are all useful. Send is an enum so it can hold just one of EncryptedSender or PlaintextSender. The send method on Send holds the explicit, static dispatching of “if this type, go here for the function”. Now technically the send method doesn’t have to implement the Sender trait, but it is nice because the enum can now be passed around to spots bounding on that trait as well.

But what if you are cool with some performance overhead if the compiler could do this for you…

dynamic dispatch

Dynamic dispatch adds the pointer indirection runtime complexity, so Rust makes sure you explicitly opt-in with the dyn syntax. These are called trait objects. This gets transformed into a fat pointer (two pointers), one of which points to a vtable for the type. The Rust compiler can coerce a pointer to an object into a trait object (this special vtable fat pointer).

&dyn Animal      // Just borrowing - no allocation
Box<dyn Animal>  // Heap allocation
Arc<dyn Animal>  // Heap allocation + atomic reference counting

dyn must be a pointer, but you get (must) choose the type of pointer!

I find myself hesitant to use dynamic dispatch just cause it feels like too much abstraction. The thought of the pointer indirection makes me woozy!

// Dynamic dispatch trait object.
pub struct Screen {
    pub components: Vec<Box<dyn Draw>>,
}

impl Screen {
    pub fn run(&self) {
        for component in self.components.iter() {
            component.draw();
        }
    }
}

// Generic trait bound.
pub struct Screen<T: Draw> {
    pub components: Vec<T>,
}

impl<T> Screen<T>
where
    T: Draw,
{
    pub fn run(&self) {
        for component in self.components.iter() {
            component.draw();
        }
    }
}
    

Dynamic dispatch trait object versus generic trait bound.

The above generic trait bound strategy doesn’t stop you from making a GUI. You could have a Screen instance per-Draw implementer. Or perhaps the screen holds a vector for each type. Or event better, put all possible types in an enum and define your own static routing. Or have this library enum_dispatch do it for you. In any case, there is the potential for the boilerplate routing code to explode in size. And this is kinda what the compiler is doing for you anyways with dynamic routing.

The boilerplate really blooms if a library consumer wants to add some more types to some existing static routing. It is one thing if the library maintainer knows the set of all types they need to route, they can use one of the strategies above to make it static. It is a whole nother beast though if it is only the consumer who knows the set of types, the library’s plus their own. I have not seen a pattern here that is easy to follow, dynamic dispatch starts to look pretty good.

// Consumer code
#[derive(Debug)]
enum ExtendedComponents {
    // Include all library components
    Library(LibraryComponents),
    // Add your own
    CustomButton,
    CustomTextBox,
}

impl Draw for ExtendedComponents {
    fn draw(&self) {
        match self {
            // Delegate to library implementation
            ExtendedComponents::Library(comp) => comp.draw(),
            // Handle your additions
            ExtendedComponents::CustomButton => println!("Drawing CustomButton"),
            ExtendedComponents::CustomTextBox => println!("Drawing CustomTextBox"),
        }
    }
}

Consumer wrapping a library’s handmade static routing.

relationships

Rust doesn’t support inheritance in types, but there are still complex relationships. Associated Types allow traits to define “this trait needs some other type that’s determined by the implementer”. Why is this useful? It sounds like the trait should be generic. Well, remember where ever there is a generic it means there can be any number of implementations. Whatever concrete type the caller wants to use, assuming it passes the bounds check, is stamped out by the compiler into a new monomorphism.

The go to example is some sort of Iterator trait. It makes sense to make this generic so that it can produce whatever type is being iterated over. But imagine a vector of bytes which is a generic struct, Vec<u8>. If it wanted to produce some iterator, it makes sense to make it a u8 iterator. And that works. The downside is there is now some strange complexity placed on the caller. They need to be explicit about the u8 whenever they interact with the byte vector’s iterator. Which is kinda weird because what other iterator would make sense in this case? But the type system doesn’t know that context, it just knows there is a byte iterator, but, there could be infinite other iterators too!

Enter the associated type. It’s job is to give the type system the context of, hey, in this case a type should only implement one of these and just choose one type.

lifetimes

Generic trait bounds limit the functionality of a generic. This is a fairly common language type system feature these days. But Rust also adds a whole other dimension to bound generics on, lifetimes. These enforce how long a reference is valid. They are checked at compile time just like a trait bound, almost like a pre-check. So it changes nothing about the monomorphization output.

And that is about all I can say on that.