才不会告诉你我做lab的动力都是为了过check看得分呢！
这个lab要求实现一个内存管理器，通过11个样例并获得尽可能高的分数。打分包括两部分：空间利用率（已分配状态堆大小/堆的总大小 评分占60%）+吞吐量（平均每秒完成的操作数 评分占40%）。
基础知识
整理一些书上有助于做出lab的内容。
提高性能的方式
提高空间利用率：最小化碎片化。分配器通常采用启发式策略维持少量大空闲块来减少外部碎片的产生。
提高吞吐量：减少分配时间。
一个动态内存管理器的合理性能要求一个分配请求的最大运行时间与空闲块数量成线性关系，释放请求的运行时间为常数。ok这就是目标了。
几种实现
为在吞吐率和利用率之间把握好平衡，对几种实现方式的空闲块组织、放置、分割、合并进行讨论。
隐式空闲链表
遍历所有块，对已分配位检查从而间接遍历所有空闲块。（由于“间接”因而得名“隐式”）
如何标识空闲块：已分配位为0
如何得到合适空闲块：
- 首次适配：从头搜索空闲链表，选择第一个合适的空闲块
- 下一次适配：从上一次查询结束的地方开始搜索，…
- 最佳适配：检查每个空闲块，选择适合所需请求大小的最小空闲块
分割：将选中空闲块分为两个
合并：
- 立即合并：释放块时合并
- 推迟合并：稍晚再合并（快速的分配器会选择某种形式的推迟合并）
分配时间复杂度：O(堆块总数)
释放时间复杂度：O(1)
显式空闲链表
将空闲块组织为某种显式数据结构。
- 后进先出顺序+首次适配=释放时间为常数
- 按地址顺序维护链表：释放需线性时间；首次适配内存利用率>后进先出+首次适配
分离的空闲链表
一种减少分配时间的方法：分离存储。维护多个空闲链表，每个链表中的块大小相等。
简单分离存储
不分割、合并空闲块，找不到大小一样的空闲块则申请一个固定大小的额外内存片，分成大小相等的块链接起来形成新的空闲链表。
分配释放都是常数时间操作，但容易造成内外部碎片。
分离适配*
对适当的空闲链表做首次适配，找到了就分割，剩下部分插入适当空闲链表中。分离空闲链表+首次适配搜索的内存利用率近似与对整个堆进行最佳适配搜索。
伙伴系统
分离适配的特例，块大小为2的幂。适用于预先知道块大小为2的幂的特定应用。
实验
ptmalloc使用的是分离适配，我也选择了分离适配来实现。当请求大小大于某特定值时合并bin中的所有空闲chunk。这个值若过小可能导致分配时间太长，过大可能导致碎片太多，最后面向样例取了0x2000。
关于使用双向链表还是单向链表：一开始fastbin中的chunk是用单向链表组织的，但是合并的时候给我整不会了，怎么得到后向chunk进行unlink呢，没想通就统一用双向循环链表了。（这里前向后向指释放时间前后，比当前释放早的定义为prev）
关于堆块结构：尽量和ptmalloc的一样吧……一开始是按书上结构写的，头部尾部各1个字，结果查对齐查realloc内容的时候还得改测试代码，真麻烦。。
看评分代码，空间利用率貌似是用最大请求总大小除以最终堆区大小得到的，（虽然感觉不太合理）所以要求不能将堆区收缩，否则可能导致空间利用率大于1。但是realloc那俩样例如果不给堆结尾特殊处理一下会超过可用范围，就把大小被realloc不断调整的堆块放置到末尾，不断调整mem_brk的位置即可。不过给出的样例并没有用到将堆区收缩的功能所以也算满足要求（？）
总的来说样例不算刁钻，甚至有不少空子可以钻但因为遇到的错误很多还是完成得比较艰难。完结撒花✿✿ヽ(°▽°)ノ✿
