Rust入门失败之Collections

Rust►入门失败 , , , , , , , , , , Comments

Rust容器和其它语言不同之处:

  • 到处都是move和borrow, Rust用move来避免深拷贝. 也就是说对不能实现Copy的类型(管理堆或其它额外资源的类型)Rust插入到容器里是非常快的.
  • Rust容器里不存在无效值错误(invalidation error).
  • Rust没有null类型

Vec<T>

  • 包含长度(length), 容量(capacity)和一个指向堆上分配的内存的指针(buffer). 例如下面代码:

    1
    2
    3
    4
    5
    6
    // Create an empty vector
    let mut numbers: Vec<i32> = vec![];

    // Create a vector with given contents
    let words = vec!["step", "on", "no", "pets"];
    let mut buffer = vec![0u8; 1024];  // 1024 zeroed-out bytes

    上面的三个Vec在内存里布局如下:

    Vec<T>

  • 大部分操作都返回的是reference, 因为如果返回类似是T意味着move所有权. 但是, 有一个例外: 就是如果所有元素都可以Copy的话, 那么这些函数返回的是一份栈上的拷贝, 比如整型. 而to_vec()这个方法也只能作用在T可以Copy的数组上.

    1
    2
    3
    4
    5
    let v = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    assert_eq!(v.to_vec(),
               vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    assert_eq!(v[0..6].to_vec(),
               vec![1, 2, 3, 4, 5, 6]);

Vec<T>的详细方法以及其它容器的使用说明这里就不过多介绍, 可以参考官网. 这里再说说一些容器的性能方面选择.

Performance of Collections

  • 如果遍历Vec容器, 从C++尤其是C语言转过来的开发者会偏向使用下标的形式访问元素内容:

    1
    2
    3
    4
    5
    let arr = ['a', 'b', 'c', 'd', 'e', 'f'];

    for i in 0..arr.len() {
      println!("{}", arr[i]);
    }

    这么干有两点问题:

    • 这样在热点代码中很伤害性能, 因为Rust对Vec的下标访问都要做有效性判断.
    • 如果这个手写下标i超出范围, 那么Rust程序就直接panic崩了.

    推荐的做法是用之前将的Iterator. 这样Rust会调用next方法一直跑下去, 直到返回None. 并且Rust会将这个代码转换成和手写C/C++同样性能的代码, 没有额外成本.

    1
    2
    3
    4
    5
    let arr = ['a', 'b', 'c', 'd', 'e', 'f'];

    for c in &arr {
      println!("{}", c);
    }

  • 和C/C++一样, 遍历上Vec<T>性能最快, 充分利用Cache-line.

  • LinkedList<T>是双端列表, 头尾插入、删除快, 但是访问慢, 如果只关心头尾访问速度应该选择VecDeque<T>, 和Vec<T>一样的实现的双端队列. 相比之下, LinkedList<T>唯一的优势就是合并两个List的时候速度很快.

  • Map方面有HashMap<K, V>和BTreeMap<K, V>.

    • 前者采用SipHash 1-3散列算法(我当前版本Rust1.38), 主要预防*HashDoS attacks*, 但哈希表的实现采用的是Google的SwissTable, 速度刁刁的, 查找复杂度O(1).
    • 后者元素有序, 采用B-Tree, 相比平衡二叉树有更好的局部性(locality), Cache友好, 速度快. 查找复杂度O(lgN).

  • Set方面也有对应的HashSet<T>和BTreeSet<T>.

  • 用Vec, HashMap和HashSet足以cover绝大部分场景性能.

All images are copyrighted by original authors Jim Blandy & Jason Orendorff who wrote in the book Programming Rust.