- 智能指针概念
- Box/Cow/MutexGuard
- 集合容器
- 切片
[T]/&[T]/&mut[T]/Box<[T]>
- 迭代器Iterator
- 切片
- HashMap
- 内存布局、查找原理、自定义HashMap
- Rust的错误处理
智能指针
- Rust 的基本概念包括
- 所有权与生命周期
- 内存管理
- 类型系统
- 数据结构
- 数据结构里最容易让人困惑的就是智能指针
- 指针
- 指针保存着内存地址
- 通过寻址(解引用)读写内存
- 可以解引用到任意类型
- 引用
- 特殊的指针
- 只能解引用到它引用数据的类型
- 胖指针
- 智能指针有所有权
- 胖指针没有所有权
-
区别
- 普通结构体
- 没有实现
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() {}
- 这里的泛型参数A必须满足内存分配Trait,这个Trait有很多方法
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
,所以切片可以比较
-
切片与数据
&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()
,这时就会丢弃capacitylet 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 字节
- 每个bucket是
- 哈希表堆的起始地址:
ctrl - 160
- 哈希表分配了8个bucket
-
通过
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
- 通过hash(K)计算出哈希值h
- 查找
- ‘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 再得一个桶编号
- 找到它对应的ctrl组
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重新计算并分配
- Hash的堆重新分配
- 桶变8个
- 桶有4个
- 插入第1个(K,V)时
- 删除一个值
- 原理
- 找到对应的桶 bn
- 把ctrl[bn] = 0xff即可
- 问题
- bucket[bn]中的(K, V)
- 如果是String
- 则它不会释放
- 继续占用内存
- 如果是String
- 解决
- 通过shrink_to_fit释放内存
- bucket[bn]中的(K, V)
- 原理
哈希表的扩展
让自定义的结构做HashKey
- 自己的结构要实现的trait
- Hash
- 计算结构的Hash值
- Eq
- 自己 == 自己
- a == b, b== c => a == c
- a == b => b == a
- ParitalEq
- 自己 != 自己
- Hash
- 步骤
- #[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”)
-
- #[drvie(Hash, Eq, PartialEq)]给结构
HashSet/BTreeMap/BTreeSet
HashSet = HashMap<K, ()>
- 看某个值是否在集合中
- BTreeMap
- 内部使用BTree
- 有序集合
- BTreeMap
- 看某个值是否在集合中
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
- map是
and_then
也是编排结果,但编排过程中可能会出错- and_then是
fn(X) -> Result<Y, E>
- and_then是
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 的库定义好你项目中主要的错误类型
- 并随着项目的深入,不断增加新的错误类型,让系统中所有的潜在错误都无所遁形
- thiserror
总结
- 相对于C返回值带错误码
- 避免错误被忽略
- 避免冗长的错误处理代码
- 避免见长的错误转换代码
- 避免深层错误变浅层错误
- 相对于C++异常
- 避免异常安全问题
- 相对于Haskell
- 可以用
?
简化错误传播
- 可以用