Rayn Miller
  • 2022年 03月27日
  • 0 阅读

Rust编程·高级概念(1)

 

智能指针概念 Box/Cow/MutexGuard 集合容器 切片[T]/&[T]/&mut[T]/Box<[T]> 迭代器Iterator HashMap 内存布局、查找原理、自定义HashMap Rust的错误处理

  • 智能指针概念
    • Box/Cow/MutexGuard
  • 集合容器
    • 切片[T]/&[T]/&mut[T]/Box<[T]>
    • 迭代器Iterator
  • HashMap
    • 内存布局、查找原理、自定义HashMap
  • Rust的错误处理

智能指针

  • Rust 的基本概念包括
    • 所有权与生命周期
    • 内存管理
    • 类型系统
    • 数据结构
      • 数据结构里最容易让人困惑的就是智能指针
  • 指针
    • 指针保存着内存地址
    • 通过寻址(解引用)读写内存
    • 可以解引用到任意类型
  • 引用
    • 特殊的指针
    • 只能解引用到它引用数据的类型
  • 胖指针
    • 智能指针有所有权
    • 胖指针没有所有权

    • 区别

      diff

  • 普通结构体
    • 没有实现Deref和DerefMut
  • 智能指针
    • 行为很像指针的数据结构
    • 除了指针外，它还有元数据以提供额外的处理能力
    • 凡是需要做资源回收的数据结构
    • 且实现了 Deref/DerefMut/Drop，都是智能指针

Box

  • Box相当于C语言的malloc，相当于C++的unique_ptr

  • 类型签名

      pub struct Box<T: ?Sized, A: Allocator=Global>(Unique<T>, A)
    • 这里的泛型参数A必须满足内存分配Trait，这个Trait有很多方法
      • allocate：malloc/calloc
      • deallocate: free
      • grow/shrink: realloc

    • 替换默认的内存分配器

        use jemallocator::Jemalloc;

  #[global_allocator]
  static GLOBAL: Jemalloc = Jemalloc;

  fn main() {}

Cow<’a, B>

  • Cow是写时克隆（Clone-on-Write）的一个智能指针
  • 它是一个enum
    • 一个只读借用
    • 如果要修改数据或者需要数据的所有权，则会clone借用的数据

  • 类型签名

      enum Cow<'a, B> where B: 'a+ ToOwned + ?Sized {
      Borrowd(&'a B),
      Owned(<B as ToOwned>::Owned)
  }
  • 这种根据 enum 的不同状态来进行统一分发的方法是第三种分发手段
    • 之前讲过可以使用泛型参数做静态分发和使用 trait object 做动态分发
  • 堆内存的分配和释放效率低，内部还涉及系统调用和锁

MutexGuard

  • Deref 提供良好的用户体验
  • 还通过 Drop trait 来确保，使用到的内存以外的资源在退出时进行释放
  • 当 MutexGuard 结束时，Mutex 会做 unlock

实现自己的智能指针

  • 有什么数据结构适合实现成为智能指针？
    • 我们需要实现一些自动优化的数据结构
      • 在某些情况下是一种优化的数据结构和相应的算法
      • 在其他情况下使用通用的结构和通用的算法
    • 比如当一个 HashSet 的内容比较少的时候
      • 可以用数组实现
      • 但内容逐渐增多，再转换成用哈希表实现
    • 如果我们想让使用者不用关心这些实现的细节，使用同样的接口就能享受到更好的性能，那么，就可以考虑用智能指针来统一它的行为
  • 一个智能指针
    • 当字符串小于 N 字节时，我们直接用栈上的数组
    • 否则，使用 String
    • 为了让 MyString 表现行为和 &str 一致，我们可以通过实现 Deref trait 让 MyString 可以被解引用成 &str
    • 除此之外，还可以实现 Debug/Display 和 From trait，让 MyString 使用起来更方便

容器

  • 只要把某种特定的数据封装在某个数据结构中，这个数据结构就是一个容器
    • 比如Box/Cow/Option
  • 集合容器
    • 相同类型的数据封闭在一起的数据结构

切片究竟是什么？

  • 切片[T]是一组T的集合
    • &[T]：只读切片的引用
    • &mut [T]：可写切片的引用
    • Box<[T]>：在堆上的切片
  • 切片的性质
    • &[T]之间len与内容相同就相等
    • &[T]和Vec<T>/[T; N]也看len与内容，因为它们也可以转换成&[T]
    • 因为切片实现了PartialEq，所以切片可以比较

  • 切片与数据

    slice

  • &Vec<T>和&[T]
    • &Vec<T>是栈上的ptr，因为Vec<T>就带了丰富信息，所以不用更多内存
    • &[T]是栈上的胖ptr，因为要记录长度len
  • 功能
    • 对于相同类型的数据，就可以把它们转换成切片后，使用切片的各种函数
    • 比如Vec<T>和[T; N]都能转成&[T]
      • Vec<T>实现了Deref
      • [T; N]内建了到&[T]

    • 比如函数：

      ```rust
fn print_slice<T>(s: &[T]) where T: fmt:Debug {
    println!("{:?}", s);
}

fn print_slice<T, U>(s: T) where U: fmt: Debug, T: AsRef<[U]> {
    println!("{:?}", s.as_ref());
}
```

切片与迭代器

let rst = vec![1,2,3].iter().map(|v| v*v).filter(|v| *v < 16).collect::Vec<_>();

这里的每一个操作都是一个迭代适配器Adapter, 它返回了一个带有迭代器的数据结构，到达collect之后才开始真正执行计算

itertools中包含了很多适配器

特殊切片&str

  • String是Vec<[u8]>
  • 注意理解String/&String/&str的区别，哪个是智能指针/胖指针/指针
  • String在deref解引用时会转换成&str

堆上的切片Box<[T]>

  • Box<[T]>和&[T]有区别，前者对数据具有所有权，后者是一个胖指针
  • Box<[T]>和Vec<T>有区别，后者带一个capacity
  • 产生Box<[T]>
    • 只能从Vec<T>转换
    • let b = vec![1,2,3].into_box_slice()，这时就会丢弃capacity
    • let v = b.into_vec()，又会增加cap
      • 当 Vec<T> -> Box<[T]> 时，没有使用到的容量就会被丢弃，所以整体占用的内存可能会降低
  • 当我们需要在堆上创建固定大小的集合数据，且不希望自动增长，那么，可以先创建 Vec<T>，再转换成 Box<[T]>

切片总结

  • Rust围绕着切片有很多数据结构
  • 因为切片将各种数据结构抽象成相同的访问方式
  • 实现了不同数据结构的同一抽象
    • 我们自己的数据结构
    • 如果内部也有同类型连续排列的数据
    • 就可以通过AsRef和Deref到切片

HashMap

Rust的哈希

HashMap的作用

  • 要处理随机访问的数据时，可以用列表和HashMap
  • 当输入与输出一一对应时，可以用列表
  • 当多对一时，用哈希表

如何解决冲突

  • HashMap解决冲突有链地址法和开放地址法
  • Rust的哈希表用开放地址法
    • 二次探查和SIMD查表
    • 二次探查是当地址冲突后，再搜索array[addr + i^2], (i = 1,2,3…)

HashMap的基本用法

let mut map = HashMap::new();
map.insert(1, "a");
map.insert(2, "b");

assert_eq!(map.get(&2), Some(&"b"));
assert_eq!(map.get_key_value(&2), Some((&2, &"b")));
map.remove(&1);
assert_eq!(map.contains_key(&1), false);
assert_eq!(map.get(&1), None);
map.shrink_to_fit();
println!("map len: {}, capacity: {}", map.len(), map.capacity());

Rust哈希表的原理

HashMap的数据结构

  • 数据结构

      use hashbrown::hash_map as base;

  struct HashMap<K,V, S=RandomState> {
      base: base::HashMap<K, V, S>,
  }

    • RandomState是Hash算法的状态，默认是SipHash

      ```rust #[derive(Clone)] struct RandomState { k0: i64, k1: i64, }

    • 使用hashbrown的hashmap

        struct HashMap<K, V, S=DefaultBuilder, A: Allocator + Clone = Global> {
      hash_builder: S,
      table: RawTable<(K, V), A>,
  }
      • hash_builder的类型是RandomState，默认值是DefaultBuilder

      • 成员table如下

          struct RawTable<T, A: Allocator + Clone> {
      table: RawTableInner<A>, 
      marker: PhantomData<T>, // 占位类型，表明在堆上分配内存
  }

  struct RawTableInner<A> {
      bucket_mask: usize, // 比Hash桶少1
      ctlr: NonNull<u8>,  // 用于查找
      growth_left: usize, // 在需要增长表之前可以插入的元素的数量
      items: usize,       // 表中的元素数，仅由len()使用
      alloc: A,
  }
        • marker是告知dropck拥有自己的实例T

HashMap的内存布局

  • 通过transmute查看内存布局

      let arr = unsafe { std::mem::transmute::<HashMap<i32, &str>, [usize; 6]>(map) };

    得到输出：

      added 4: bucket_mask 0x7, ctrl 0x7fa0d1405e90, growth_left: 3, items: 4
    • 哈希表分配了8个bucket
      • 每个bucket是key(i32)+value(&str)=4+16=20字节
      • 共 8x20 = 160 字节
    • 哈希表堆的起始地址：ctrl - 160

  • 通过rust-gdb查看运行状况

      » rust-gdb target/debug/mytest                                  wilson@P310
  GNU gdb (Ubuntu 9.2-0ubuntu1~20.04.1) 9.2
  (gdb) b main.rs:32
  Breakpoint 1 at 0x1055c: file src/main.rs, line 32.

  (gdb) r
  empty: bucket_mask 0x0, ctrl 0x55555559b3b0, growth_left: 0, items: 0

  (gdb) c
  added 1: bucket_mask 0x3, ctrl 0x5555555b0af0, growth_left: 2, items: 1

  (gdb) c
  added 3: bucket_mask 0x3, ctrl 0x5555555b0af0, growth_left: 0, items: 3

  (gdb) x /12x 0x5555555b0ad0
  0x5555555b0ad0: 0x00000063      0x00000003      0x00000062      0x00000002
  0x5555555b0ae0: 0x00000061      0x00000001      0x00000000      0x00000000
  0x5555555b0af0: 0x137c2aff      0xffffffff      0xffffffff      0xffffffff

  (gdb) c
  // bucket增加到了8个
  added 4: bucket_mask 0x7, ctrl 0x5555555b0b50, growth_left: 3, items: 4

  // 哈希堆重新分配，桶也重新放置，ctrl重新计算
  (gdb) x /20x 0x5555555b0b10
  0x5555555b0b10: 0x00000000      0x00000000      0x00000063      0x00000003
  0x5555555b0b20: 0x00000061      0x00000001      0x00000064      0x00000004
  0x5555555b0b30: 0x00000000      0x00000000      0x00000062      0x00000002
  0x5555555b0b40: 0x00000000      0x00000000      0x00000000      0x00000000
  0x5555555b0b50: 0xff7cffff      0xff132a6a      0xffffffff      0xffffffff
  (gdb)

ctrl 的作用

  • ctrl表分成N组
    • 每组16个字节
    • 每个字节对应一个Hash桶
    • 首位不为1说明此桶被占用
    • 为0xff说明未占用
  • hashbrown 的 hash值
    • 低几位（& bucket_mask）定位在数组的位置
    • 高 7 位存到对应位置的 ctrl 块里，类似指纹的作用
    • 一般哈希表获取时，取模定位到位置后，要完整对比 key 才能知道是找到（key相同）还是要探查（key 不同）。
    • hashbrown 可以利用 ctrl 里存起来的高 7 位快速发现冲突的情况（低几位相同但高7 位不同），直接进入下一步探查

(K, V)的查找与放置原理

  • 放置
    • 通过hash(K)计算出哈希值h
      • hash(‘a’) = h
    • h & bucket_mask 得到 (K, V) 应放置的桶编号
      • h & 0x3 = 0
      • bucket[0] = (K, V)
    • h 的头7位是ctrl值，把它放到ctrl开始的与桶统带相同的位置
      • head(h) = 0xa
      • ctrl[0] = 0xa
    • 桶与ctrl的内容
      • buckcet[0] = (K, V)
      • ctrl[0] = head(h) = 0xa
  • 查找
    • ‘C’.hash()得到hash值h
    • 找到它对应的桶
      • 找到它对应的ctrl组
        • h & bucket_mask = 139
        • 139 / 16 * 16 = 128
        • RawTableInner.ctr + 128
        • 把这组ctrl加载到CPU缓存
        • 即ctrl[128]开始的16个字节
          • head(h) & ctrl组得到桶编号
      • 二次探查
        • 第1次未找到
        • head(h) & ctrl[128] + 16*2 再得一个桶编号

HashMap的重新分配与增长

  • 分配
    • 插入第1个(K,V)时
      • 桶有4个
        • ctrl组前4个字节有效
        • ctrl[n]对应第n个桶
          • 当ctrl[n]的首bit不为1
      • 插入第5个(K, V)时
        • 桶变8个
          • Hash的堆重新分配
            • 原来的Hash堆拷贝到新堆
            • (K, V)有Copy属性就拷贝
            • String只移动(ptr, cap, len)的24个字节
              • String的负载内存不动
            • Hash的Ctrl重新计算并分配
  • 删除一个值
    • 原理
      • 找到对应的桶 bn
      • 把ctrl[bn] = 0xff即可
    • 问题
      • bucket[bn]中的(K, V)
        • 如果是String
          • 则它不会释放
          • 继续占用内存
      • 解决
        • 通过shrink_to_fit释放内存

哈希表的扩展

让自定义的结构做HashKey

  • 自己的结构要实现的trait
    • Hash
      • 计算结构的Hash值
    • Eq
      • 自己 == 自己
      • a == b, b== c => a == c
      • a == b => b == a
    • ParitalEq
      • 自己 != 自己
  • 步骤
    • #[drvie(Hash, Eq, PartialEq)]给结构

      • 自定义Hash计算函数

          let hasher = DefaultHash::new()
  let mut s = MyStruct::new()
  s.hash(hasher)
        • 装上自定义的Hash计算器

      • 把(K, V)加入Hash堆

        • let map = HashMap::new()
        • map.insert(s, “123”)

HashSet/BTreeMap/BTreeSet

  • HashSet = HashMap<K, ()>
    • 看某个值是否在集合中
      • BTreeMap
        • 内部使用BTree
        • 有序集合

Rust的错误处理

  • 错误处理发生
    • 错误捕获
      • 立即处理
    • 错误传播
      • 延迟处理
    • 错误类型
      • 转换成错误消息
      • 发送给用户

主流方法

使用返回值(错误码)

  • 如C语言，错误用ERROR或者NULL返回
  • 因为返回值的语义加入了错误语义，需要更新文档保持正常语义和错误语义得到更新
  • 返回值是错误语义，不能强制调用者处理，调用者可能忽略，导致NULL作为参数传给下面的函数
  • A调用B，A要把B返回的错误转换成自己的错误，导致每调一个函数，下面就要进行关断错误处理
  • 同时，返回的只能是最浅一层的错误，深层的错误都被上一层转换掉了
  • 也就是错误信息不能传播

使用异常

  • 异常解决了返回值不能传播错误的问题
  • 异常是把错误的产生和错误的处理分开
    • 任何地方都可以产生错误，但不用显式处理错误
    • 错误的处理可以通过异常传播的抓取来完成
  • 异常的传播
    • 因为异常是通过栈回溯(stack unwind)传播的
    • 从抓取处通过栈回溯直到遇到异常发起的地方
    • 如果到main还未遇到，则直接崩溃
  • 问题
    • 异常安全
      • 先lock(&mutex)，再调用其他函数，最后unlock(&mutex)
      • 在调用一个函数时，它抛出了异常，就会中断当前的流程，进入异常回溯
      • 这样unlock(&mutex)不会执行
    • 滥用异常
      • 异常处理开销大
      • 对于可以处理的错误也作为异常抛出，造成很多开销

使用类型系统

  • 错误仍然作为返回值
    • 返回值是一个多类型的复合类型
    • 错误包裹在必需处理的类型
    • 可以用函数式编程简化错误的处理

Rust的错误处理方法

使用类型系统构建了错误处理流程

Option和Result

enum Option<T> {
    None,
    Some(T),
}

#[must_use="this 'Result' ..."] // 编译器发现这个类型没有显式处理，会警告
enum Result<T, E> {
    Ok(T),
    Err(E),
}

这样，当我们执行read_file()时，没有处理Result类型，编译器就会报警，强制要求处理Result

?操作符

为了解决每调用一个函数，就要写判断返回值的代码，Rust使用了?操作符，把错误传播，延迟处理

?是一个语法糖，展开如下：

match result {
    Ok(v) => v,
    Err(e) => return Err(e.into()),
}

函数式编程：

fut.await?      -> Err(E)
    .process()? -> Err(E)
    .next()
    .await?     -> Err(E)
    ;           -> Ok(T)

函数式错误处理

  • Rust为Option和Result提供的函数
    • map编排结果，传播错误
      • Ok(X).map(fn) -> Ok(Y)
      • Some(X).map(fn) -> Some(Y)
      • Err(E).map(fn) -> Err(E)
    • and_then链式处理结果，传播错误
      • Ok(X).and_then(fn) -> Ok(Y)
      • Err(E).and_then(fn) -> Err(E)
    • map_err编排错误，传播结果
      • Ok(T).map_err() -> OK(T)
      • Err(E).map_err(fn) -> Err(F)
  • 区别
    • map是编排结果，而且结果肯定不会出错
      • map是fn(X) -> Y
    • and_then也是编排结果，但编排过程中可能会出错
      • and_then是fn(X) -> Result<Y, E>
  • Option<T>和Result<T, E>的互换
    • Option<X>.ok_or("err".to_owned()) -> Reuslt<Y, E>
    • Result<X, E>.ok() -> Option<X>: Some(X)/None
    • Result<X, E(e)>.err() -> Option<E>: None/Some(e)

panic!和catch_unwind

  • Rust中的异常，是必须打断执行流，不可恢复或不想恢复的错误，让程序终止运行并崩溃
    • 比如传入的参数个数不对，就应该立即panic，让错误立刻暴露
  • 有时也需要像C++的异常处理那样，能栈回溯，把环境恢复到异常发出的地方

    • 这时就有catch_unwind的捕获回溯

      let result = catch_unwind( || {
    panic!("抛个异常");
})
assert!(result.is_err());
println!("panic catch: {:?}", result);

      程序抛出异常，同时还会继续执行下面的语句

    • catch_unwind就是让一个程序的错误，不致于整个系统都崩溃

      • 可以把整个代码都放到catch_unwind()函数要传入的闭包中
      • 这样内部任何的panic都会捕获
      • 转换成一个Result，不会导致系统崩溃

Error trait和错误类型的转换

  • Result<T, E>中的E是一个错误类型，它有E: Error
    • Error是一个trait
    • 我们可以定义自己的类型，并实现Error，就可以成为一个E
  • 实现E类型的库
    • thiserror

      • 提供了派生宏，简化错误类型的定义

          use thiserror::Error;

  #[derive(Debug, Error)]
  #[non_exhaustive]
  pub enum DataStoreError {
      #[error("data store disconnected")]
      Disconnect(#[from] io::Error),

      #[error("the data of key `{0}` is not available")]
      Redaction(String),

      #[error("invalid header (expected {expectd:?}, found {found: ?})")]
      enum InvalidHeader {
          expected: String,
          found: String,
      }

      #[error("unknown data store error")]
      Unknown,
  }
    • anyhow
      • 实现了anyhow::Error和任意错误类型的转换
      • 可以直接用?
    • 推荐使用thiserror
      • 开发前，先用类似 thiserror 的库定义好你项目中主要的错误类型
      • 并随着项目的深入，不断增加新的错误类型，让系统中所有的潜在错误都无所遁形

总结

  • 相对于C返回值带错误码
    • 避免错误被忽略
    • 避免冗长的错误处理代码
    • 避免见长的错误转换代码
    • 避免深层错误变浅层错误
  • 相对于C++异常
    • 避免异常安全问题
  • 相对于Haskell
    • 可以用?简化错误传播
搜索