bustub-private 性能优化

寒假的时候做了 15445 几个 projects 基础的功能，最近比较闲，优化一下性能玩玩...

Project #1 - Buffer Pool Manager

异步读写磁盘

因为最开始的做法是给在每个函数前面加上 std::scoped_lock lock(*bpm_latch_); 来支持并发。因为缺页或者写回脏页的时候涉及读写磁盘，显然是一个瓶颈，所以读写之前先拿到单个 frame 的锁，然后释放 bpm_latch_ 再到 disk_scheduler 推送读写任务。

但是我发现这样做在 latency=0 的时候，也就是非连续读没有惩罚的时候，确实提升很大。但是 latency=1 时还不如之前，暂时还没搞清楚原因，看了半天火焰图也没看出什么门道。 折磨了一天，才发现 DiskScheduler 还是单线程获取任务，一开始这么写是因为 DiskManager 读写的时候直接上了一把大锁，而我又不能改那部分代码。实际上 DiskScheduler 之间获取，释放锁的开销还是很大的，之前并发率低刚好减少了拿锁的竞争，所以写了一个多队列的线程池就解决了这个问题...

LRU-K

~~ 看火焰图的时候发现 lru-k 的效率其实挺低的，因为我的 lru 是 set 实现的不是双向链表...
之所以这样做是因为 pin 住的 frame 无论如何都不能删除，unpin 的时候如果用链表就只能从头遍历去找合适的位置插入。
不过实际上 lru-k 的 size 也就 16，bpm size 是 64, 所以遍历一遍的开销应该还好，因为理论上，驱逐的情况应该也不多。~~

实际上因为 lru-k 是根据最近的前 k 次使用时间，所以每次记录都可能要移动到非队首的地方，应该还是用 set 排序更好。

并且用 set 按权值排序还很容易实现按照 AccessType 来调整优先级，比如说 AccessType::Scan 应该被容易被驱逐，因为大概率不会回头再用到，加上这个优化 QPS 就从 10000 多变成了 35177.18399，减少了缓存污染。

Project #2 - B+Tree

这里我先把之前搞的幽默读锁来实现螃蟹锁删了。如果能实现读锁原地转换成写锁，应该是很有用的优化。但是我现在的实现是要保证祖先上一定有一个节点是写锁，这个 “优化” 除了增加锁的竞争和开销没什么用... 删除之后 QPS 大幅提升

奇怪的是我正确实现了螃蟹锁，contention ration 的测试比率 (多线程运行时间 / 单线程运行时间) 还是 1 左右，官网说大多正常是 [2.5, 3.5] 也就是说我的锁竞争并不激烈，不知道是好还是坏...

b+ tree 还有墓碑机制之类的优化，之后写了再更新吧,,,