We have seen that Rust does a lot to keep us safe
in how we manage/access memory/types.
These things are baked into the language design, and enforced by the compiler.
Option type to avoid the need for null pointers.At the same time, Rust almost always gives zero-cost abstractions. Almost none of these safety assurancecs cost us run-time performance. They are generally ensured at compile-time, and therefore there's no extra work to do at run-time.
Compare garbage collection, which inherently happens while the program runs.
Of that list, the only thing I can see that has any runtime cost is Option: it has to store one extra value as a flag indicating I'm a
vs Some()I'm a
.None
use core::mem::size_of;
type Point3D = (f64, f64, f64);
println!("{}", size_of::<Point3D>());
println!("{}", size_of::<Option<Point3D>>());
24 32
Since we're talking about things that should be zero-cost, what about generic functions?
fn is_larger<T: Ord>(a: T, b: T) -> bool {
a > b
}
Is there dynamic dispatch happening here, since the actual type of T isn't known? (i.e. can the compiler statically-bind an implementation of >?)
Rust does statically bind this code because it does monomorphization while compiling.
What that means: a version of this function is compiled for each T that you use it with.
When we did this:
fn is_larger<T: Ord>(a: T, b: T) -> bool {
a > b
}
println!("{}", is_larger(2, 3));
println!("{}", is_larger("two", "one"));
The compiler actually created single-type versions is_larger<i32> and is_larger<&str>.
So, we might expect a small increase in the size of our compiled output (since there are two implementation of the same
function compiled), but all of the code can be statically-bound.
It is possible to have dynamically-bound code in Rust. We can create a
, but there's more to say before we can.Vec of things that implement the Ord trait
In particular, the dyn keyword will be there wherever dynamic binding is happening: it won't be a secret.
Let's make a binary tree in Rust.
We will have nodes
with left and right children. Either child could be either another node, or missing. In Rust, that would be:
struct Node<T> {
value: T,
left: Option<Node<T>>,
right: Option<Node<T>>,
}
This fails to compile:
recursive type `tree::Node` has infinite size… insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `tree::Node` representable
All of the values we have been using in Rust have a size known at compile time. Rust demands this so it can know how large a function's stack frame is, etc.
One of the compiler's suggestions was & (since the size of a reference is known). Let's try:
struct Node<T> {
value: T,
left: Option<&Node<T>>,
right: Option<&Node<T>>,
}
Nope.
missing lifetime specifier… consider adding an explicit lifetime bound… so that the reference type … does not outlive the data it points at
The problem now is the Rust rule for references: references must always be valid.
Any reference we hand to this data structure might be stored for a long time. Nothing guarantees that the value behind the reference will live that long.
All of the values we have worked with so far in Rust have been on the stack: local variables to a function that disappear when the function exits. The Rust ownership rules were easy to apply in that case, but what if we actually need a long-lived reference?
How can we put things on the heap?
BoxRust has a collection of smart pointer types that can be used to contain other value, and safely manage them on the heap.
The first one we'll need: Box<T>. A Box can hold another value, takes ownership of that value, and makes sure the value lives as long as the Box exists.
BoxA Box is effectively a unique reference: it's not Copy, and is Clone but clones the entire contents of the box.
When a Box gets dropped, its contents will be dropped as well (because it owns the contents).
BoxWe can make a Box with Box::new: it creates a new box and moves ownership of the value into the box (or copies).
let f1 = 1.234; let b1 = Box::new(f1); let b2 = Box::new(1.234);
These are f1: f64 and b1,b2: Box<f64>.
BoxBoxes are auto-dereferenced, so we can usually use them like their contained value.
println!("{:?} {:?}", b1, b2); // 1.234 1.234
println!("{:?}", b1 == b2); // true
Or we can explicitly dereference with * (same as references):
let f2: f64 = *b2;
BoxWe can return to the tree data structure now: the left and right children will either be None or another Node in a Box (and thus on the heap):
#[derive(Debug, Clone)]
struct Node<T> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
BoxLet's implement some methods:
impl<T> Node<T> {
fn new(value: T) -> Node<T> {
Node {
value,
left: None,
right: None,
}
}
fn set_left(&mut self, value: T) {
self.left = Some(Box::new(Node::new(value)));
}
fn set_right(&mut self, value: T) {
self.right = Some(Box::new(Node::new(value)));
}
}
BoxAnd we have a memory safe data structure we can use.
let mut n = Node::new(10);
n.set_left(5);
n.set_right(15);
println!("{:?}", n);
Node { value: 10, left: Some(Node { value: 5, left: None, right: None }), right: Some(Node { value: 15, left: None, right: None }) }
The Box is doing two things for us: letting us put values on the heap, and giving us a safe reference that owns it, like the C++ unique_ptr.
There are other smart pointer
-like things we might need to do, and other Rust data structures that let us.
Because Box is unique, it can hold a mutable value and let you mutate it. But what about multiple immutable references?
The Rc<T> type is a reference-counted container for immutable values.
An Rc can be safely cloned and is guaranteed to live as long as the contents are accessible. It owns its contents, and drops them when zero references remain.
use std::rc::Rc;
let mut v = Vec::from([1, 2]);
v.push(3); // can get "&mut v" here
let r1 = Rc::new(v);
let r2 = r1.clone();
//v.push(4); // fails: borrow of moved value
//r1.push(4); // fails: cannot borrow as mutable
println!("{:?}", r1);
println!("{:?}", r2);
Using Rc is probably most useful when creating/using a data structure and want to work with it in multiple places.
The value can be created (with mut if needed) and then moved into an Rc. The Rc can be cloned and shared in as many places as you need it.
But Rc is not thread-safe: it does not implement Send or Sync.
For that, there's a separate Arc<T>: atomic reference counted. It does the locking necessary to safely be used across multiple threads. i.e. it is Clone, Send, and Sync
let vec = Arc::new(Vec::from([1, 2, 3, 4, 5, 6]));
let vec1 = vec.clone();
let vec2 = vec.clone();
let jh1 = thread::spawn(move || {
let sum = vec1.iter().fold(0, |a, b| a + b);
println!("I added and got {}", sum);
});
let jh2 = thread::spawn(move || {
let sum = vec2.iter().fold(1, |a, b| a * b);
println!("I multiplied and got {}", sum);
});
println!("I'm just hanging out with {:?}", vec);
jh1.join().unwrap();
jh2.join().unwrap();
There's only one copy of this vector in memory.
The output will be (with lines permuted arbitrarily):
I'm just hanging out with [1, 2, 3, 4, 5, 6] I added and got 21 I multiplied and got 720
Both Rc and Arc ensure immutable contents because there's no way to get a mutable reference to the contents. i.e. they do not implement AsMut.
But we can get immutable references to the contents (because they implement AsRef).
The Box does implement AsMut and whenever we did mutable things inside a Box, there was an implicit dereference using .as_mut().
What if we need shared mutability? We can't have multiple mutable references, but there are cases where it's necessary.
It would be nice to be able to have a shared mutable data structure, but keep Rust's safety.
We have RefCell: a sharable Box-like thing where you can get a mutable reference, but safe borrowing is checked at runtime. And Mutex that is like RefCell but thread-safe.
A lot of things kind of mean reference
in Rust…
| Type | Sharable? | Mutable? | Thread Safe? |
|---|---|---|---|
& | yes * | no | no |
&mut | no * | yes | no |
Box | no | yes | no |
Rc | yes | no | no |
Arc | yes | no | yes |
RefCell | yes ** | yes | no |
Mutex | yes, in Arc | yes | yes |
I keep saying it: concurrency is easy if you don't have shared mutable state. How hard is it in Rust if you do want/need shared mutable data structures?
Let's try it. tl;dr there's some accounting to convince the compiler you're doing it right. Then it's easy.
My goal: a shared Vec that's going to collect values generated by calculations in several threads.
I'm going to generate random numbers, we I started with:
cargo init references cd references cargo add rand
Then, the shared data structure needs to be in a Mutex (to protect it from concurrent access). The Mutex isn't Copy or Clone: there's only one, and it owns its contents. So it must be in an Arc so we can share it between threads.
And we'll need to keep track of the JoinHandles of each thread as they're created.
let values = Vec::new(); let values_shared = Arc::new(Mutex::new(values)); let mut handles = Vec::new();
Each thread needs its own reference to the Arc contents: .clone it to create the reference and give ownership to the thread.
for i in 1..6 {
let my_values_shared = values_shared.clone();
let h = thread::spawn(move || {
add_some_values(my_values_shared, i);
});
handles.push(h);
}
The add_some_values function that is run for each thread is going to get one of these:
Arc<Mutex<Vec<i64>>>
So to do any work with the vector, we have some layers to peel.
The Arc implements Deref, so auto-dereferencing will get us into it.
Arc<Mutex<Vec<i64>>>
To get into the Mutex, we .lock() it:
Note: .lock takes &self, a non-mutable reference. It returns a Result<MutexGuard>. MutexGuard implements DerefMut which lets us get a mutable reference to the contents.
That's the whole trick: the mutex takes ownership of its contents, and is capable of giving out a way to get mutable references to it safely.
As long as the MutexGuard exists, no other thread can .lock the mutex (i.e. their calls to .lock() will block until it's available).
So we want the MutexGuard to exist for as short a time as possible so other threads can get the mutex:
fn add_some_values(values: Arc<Mutex<Vec<i64>>>, thread_id: i64) {
let mut rng = rand::thread_rng();
for _ in 0..3 {
let v = rng.gen_range(0..100);
{
let mut vals = values.lock().unwrap();
vals.push(v + thread_id * 1000);
}
let delay = rng.gen_range(100..200);
thread::sleep(Duration::from_millis(delay));
}
In the main thread, wait for everybody to finish:
for h in handles {
h.join().unwrap();
}
Then we know that there's only one clone of the Arc left: ours.
We can consume the Arc to get ownership of its contents back. Same for the Mutex.
let mutex = Arc::into_inner(values_shared).unwrap();
let final_values = mutex.into_inner().unwrap();
println!("{:?}", final_values)
[1070, 3038, 2057, 4061, 5047, 3037, 2007, 1040, 5070, 4099, 1002, 2061, 3006, 4022, 5017]
So is shared mutable state hard in Rust?
Harder than shared immutable state. Easier than it would be in most other languages.
With Box, we can revisit dynamic values in Rust. We can use trait objects that are a value of any type that implements a specific trait.
Trait objects (always?) need to be wrapped in Box or similar: values must have a size known at compile time, and arbitrary thing implementing
doesn't.trait
Let's create a trait and implementation of it:
trait CanSpeak {
fn speak(&self) -> ();
}
struct Speaker {}
impl CanSpeak for Speaker {
fn speak(&self) -> () {
println!("hello");
}
}
Remember: we can use it in a static/monomorphization way:
fn speak_twice_static<S: CanSpeak>(s: &S) {
s.speak();
s.speak();
}
let s = Speaker {};
s.speak();
speak_twice_static(&s);
But we can also create variables and function arguments that take a dynamically-typed trait object:
fn speak_twice(s: &Box<dyn CanSpeak>) {
s.speak();
s.speak();
}
let s: Box<dyn CanSpeak> = Box::new(Speaker {});
s.speak();
speak_twice(&s);
The dyn keyword indicates anything that implements this trait
. These operations are then dynamically-bound.
Dynamic types are more useful to create a collection of values:
use std::fmt::Display;
let mut displayable: Vec<Box<dyn Display>> = Vec::new();
displayable.push(Box::new(5));
displayable.push(Box::new("hello"));
displayable.push(Box::new(GeoPoint::default()));
Again: the Box wrapper is needed so the size of each element is known by the compiler.
We can then use these values, knowing that they implement Display, and usages of it will be dynamically-bound.
for value in displayable {
println!("{}", value);
}
5 hello 0°N 0°E @ 0m
We can do a lot (all?) of the dynamically-typed things from other languges, but only when we need them.
And we always see the dyn keyword, so we know it's happening.