rust-collections

How Rust Can Make Your Code Safe and Fast

(And How You Can Make it Usable)

Alexis Beingessner

Why Rust?

• High-performance applications like C/C++
• C/C++ are really awesome (for control)!
• C/C++ are really awful (for reasoning)!

Firefox is basically an operating system that accepts and executes arbitrary data from the internet.

• Gotta be fast/effecient (so people use it)
• Gotta be safe (because people use it)
• Gotta be maintainable (so people build it)

Solution: Rust!

Rust bridges the gap between low-level control and high-level safety/convenience.

Let's see what Rust's about in practice:

http://play.rust-lang.org/

In Summary, in (safe) Rust code:

• No unitialized memory can be accessed
• No null pointers
• No dangling pointers
• No data races
• No buffer overflows

Collections in Rust are hard

• Academic texts assume C-style "full access" to memory
  • Raw pointers everywhere!
• Persistent/functional structures are overkill
  • BRB writing a lazy persistent memoization framework

Success Stories: Array-based structures

Really straightforward ownership and traversal: They're just a single block of memory!

Nightmare Stories: Tree-based Structures

• Stacks of raw pointers!
• Macros as far as the eye can see!

Common Realities

• Collections have to be fast and lean
• They're going to have to use computational primitives
• They're going to use unsafe code, somewhere

Goals (Internal)

• Make the unsafe code minimal
• Make the unsafe code centralized
• Keep it DRY
• Avoid macros

Goals (External)

• Never require unsafe code to use a collection "right"
• Make the safe interface the fastest
• Make the safe interface actually usable
• Make the safe interface composable

Problem: Iterating over a Vec

  for i in range(0, vec.len()) {
      let elem = &vec[i];
      ...
  }
    

• Wordy/Repetitive (and therefore error-prone)
• Slow! We're doing bounds checks on every index

  for i in range(0, vec.len()){
      unsafe {
          let elem = vec[].unsafe_get(i);
          ...
      }
  }
    

• Even more error-prone boiler-plate
• Unsafe!!!

  vec.for_each(|x| {
      ...
      return false;
  });
    

• Safe! (Assuming Vec is written correctly)
• Fast?
  • Vec can use unsafe internally to yield elements
  • LLVM can sometimes inline closures away
• Still some boiler-plate.
• Internally: written "naturally"

  vec.for_each(
      map(|x| x * 2,
      filter(|x| x < 10,
      |x| {
          ...
          return false;
      })
      })
      })
  });
    

Adaptors...?

Zip? How do you iterate two things simultaneously?

  for elem in vec.iter() {
      ...
  }
    

• Super Fast!
  • Compiles down to ASM of equivalent C
  • Easier for LLVM to work with
• Safe! (Assuming Vec is written correctly)
• Short! No boiler-plate or closures!
• Internally: a bit harder to write.

  for elem in vec.iter()
      .map(|x| x * 2)
      .filter(|x| x < 10) {

      ...
  }
    

  for (a, b) in vec.iter().zip(vec2.iter()) {
      ...
  }
    

  let mut it = vec.iter_mut();
  let a = it.next().unwrap();
  let b = it.next().unwrap();
  let c = it.next().unwrap();
  // !!! Multiple aliasing? Safety???
    

It's safe and allowed because:

• Collection is inaccessible while iterator exists
• Returned references have no connection to the iterator
• Each yielded element is disjoint from all others
• Iterators can't "go back"

Wizard Magic does have its costs:

• Can't soundly be mutably bi-directional (no prev)
• Inserting/Deleting in the stream is very constrained

Help!

Rust's standard libraries are an inconsistent and buggy mess.

We're super friendly, just submit a PR on Github!

Don't know Rust yet? No worries, it's a great way to learn!

http://rust-lang.org/