130. Vec and HashMap

A column that grows

In chapter 105 you taught Viscosity to grow a Float64Array column by hand: keep a length and a capacity, and when they meet, allocate a bigger array and copy. In Rust that bookkeeping comes built in:

let mut xs: Vec<f64> = Vec::new();
xs.push(1.5);
xs.push(2.5);
println!("{} {}", xs.len(), xs[0]);
// 2 1.5

Vec<f64> reads “a vector of f64”. Unlike a JavaScript array, every element has the same type, so the elements sit side by side in memory with no boxes: a Vec<f64> is laid out like a Float64Array that can grow. vec![1.5, 2.5] is shorthand for building one with those elements.

Length, capacity, buffer

The standard library documents the picture exactly: a Vec value is a pointer to a heap buffer, a length and a capacity, and the buffer is one contiguous block^[2]. Step through some pushes:

let mut v: Vec<f64> = Vec::new();

The capacities in that diagram are real. On this machine, with Rust 1.97, pushing nine f64s one at a time printed capacities 4, 4, 4, 4, 8, 8, 8, 8, 16. Don’t build on those numbers: the docs say Vec guarantees no particular growth strategy, only that push is amortized O(1), which is the doubling argument from chapter 105. What it does guarantee is that Vec::with_capacity(n) allocates room for exactly n, and that a Vec never shrinks by itself^[2].

Indexing, safely or not

xs[5] on a two-element Vec doesn’t return undefined. It panics: index out of bounds: the len is 2 but the index is 5. If an index might be out of range, ask with get, which returns the Option from the last chapter: xs.get(5) is None, xs.get(0) is Some(&1.5).

Now the rule that surprises everyone once. This doesn’t compile:

let mut v = vec![1.0, 2.0];
let first = &v[0];
v.push(3.0);
println!("{}", first);

Rust 1.97 says (trimmed):

error[E0502]: cannot borrow `v` as
  mutable because it is also borrowed
  as immutable
3 |     let first = &v[0];
  |                  - immutable borrow
4 |     v.push(3.0);
  |     ^^^^^^^^^^^ mutable borrow
5 |     println!("{}", first);
  |              immutable borrow later

It is the shared-or-mutable rule from chapter 125, and the diagram shows why it matters here. If this push hit the capacity, the elements would move to a new buffer and first would point into freed memory. JavaScript never hands you a pointer into an array’s storage, so it can’t have this bug. Rust can hand you one, so it checks.

Looping uses borrows too. for x in &v lends you each element; for x in &mut v lends each one mutably, so *x += 1.0 changes it in place; for x in v moves the elements out and uses the Vec up. A function that only reads should take a slice, &[f64]: a &Vec<f64> turns into one automatically.

fn sum(xs: &[f64]) -> f64 {
    let mut s = 0.0;
    for x in xs {
        s += x;
    }
    s
}

fn main() {
    let mut v: Vec<f64> = Vec::new();
    for i in 0..6 {
        v.push(i as f64);
        println!("len {} cap {}",
            v.len(), v.capacity());
    }
    for x in &mut v {
        *x *= 10.0;
    }
    println!("{:?}", v);
    println!("{:?}", v.get(9));
    println!("{}", sum(&v));
}

HashMap: counting with keys

HashMap<K, V> maps keys of type K to values of type V. It isn’t imported automatically, so you start with use std::collections::HashMap;. Here is a count of which fields a loop touches, the kind of fact Viscosity’s analysis collects:

let used = ["x", "vx", "x", "y", "x"];
let mut n: HashMap<&str, i32> =
    HashMap::new();
for f in used {
    *n.entry(f).or_insert(0) += 1;
}
println!("{:?}", n.get("x"));
// Some(3)

get returns Option<&V>, since the key may be missing. insert(k, v) adds or replaces. The entry line is the counting idiom: entry(f) finds the slot for f, or_insert(0) fills it with 0 if it’s empty, and either way hands back a mutable reference to the value, which *... += 1 increments. And ownership applies: inserting a String key moves it into the map, which owns it from then on.

use std::collections::HashMap;

fn main() {
    let fs = ["x", "vx", "x", "y", "x"];
    let mut n: HashMap<&str, i32> =
        HashMap::new();
    for f in fs {
        *n.entry(f).or_insert(0) += 1;
    }
    println!("{:?}", n.get("x"));
    println!("{:?}", n.get("mass"));
    n.insert("mass", 0);
    println!("{}", n.len());
    // Run it twice: the order changes.
    println!("{:?}", n);
}

That last sentence is not a technicality. Running the example four times in a row and printing the whole map gave three different orders, among them {"vx": 1, "y": 1, "x": 3} and {"y": 1, "vx": 1, "x": 3}. A JavaScript Map iterates in insertion order^[4]. The Rust port of Viscosity must make the same decisions as the TypeScript one, message for message, so where order matters it uses IndexMap from the indexmap crate, a hash map that remembers insertion order. One comment in engine/rust/crates/core/src/builder.rs explains why: the incomplete phis of SSA construction are filled in insertion order, which “decides value numbering and the order of instructions, exactly as in the TS reference”.

Your turn

use std::collections::HashMap;

fn count_fields(used: &[&str])
    -> HashMap<String, usize> {
    todo!()
}

use std::collections::HashMap;

fn hot_fields(
    n: &HashMap<String, usize>,
    min: usize,
) -> Vec<String> {
    todo!()
}

What you learned

• A Vec<T> owns a contiguous heap buffer of Ts, with a length and a capacity. push grows it; only amortized O(1) growth is promised.
• v[i] panics when out of range; v.get(i) returns an Option.
• You can’t push while a reference into the Vec is alive, because the buffer might move.
• A HashMap<K, V> owns its keys and values; get returns Option<&V>, and entry(k).or_insert(v) is the counting idiom.
• Its iteration order is arbitrary. The Rust Viscosity uses IndexMap where order reaches the output; drip-rs keeps its own SoA hash table.