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

  • 普通结构体
    • 没有实现DerefDerefMut
  • 智能指针
    • 行为很像指针的数据结构
    • 除了指针外,它还有元数据以提供额外的处理能力
    • 凡是需要做资源回收的数据结构
    • 且实现了 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围绕着切片有很多数据结构
  • 因为切片将各种数据结构抽象成相同的访问方式
  • 实现了不同数据结构的同一抽象
    • 我们自己的数据结构
    • 如果内部也有同类型连续排列的数据
    • 就可以通过AsRefDeref到切片

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, }

    • 使用hashbrownhashmap

        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为OptionResult提供的函数
    • 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
    • 可以用?简化错误传播