K&R malloc的优点
- 简单
- 代码大小很小(malloc仍然内置等)
- 除非有大量碎片空间，否则malloc是O(1) 复杂度
- 适用于小程序，整个程序中只使用几十次malloc
K&R malloc的缺点
- 当小型malloc频繁出现时，会出现大量碎片空间
- free是O(n)复杂度
- 在调用brk时，需要遍历freelist一次(如果有数万个列表，缓存、刷新、代码状态将是很恐怖的)
- 当碎片空间增加，内存效率也急速恶化
时代变了
现在的编程语言
- GUI
- 脚本语言或者Java
- C++程序语言
- 等等
只重复一个小型的malloc
最大的问题是什么
- 在这里，首先假定碎片是最大的问题
- 如果能够解决碎片问题
- 内存使用效率UP
- 内存使用量较少，缓存效率UP
- 看起来很酷
现在需要best fit 分配器，根据just Idea来实现它
停止使用地址顺序，尝试使用size顺序进行排序
free的时候，不可能和相邻节点合并
就会产生额外的碎片空间
毕竟我们需要将新增成员增加到malloc header里
地址空间的prev，next不是用指针保持的，而是用size
发生了什么变化
- 哪里变好了
- free从典型的O(n) 变成了O(1)
- 碎片造成的空间浪费减少了
- 哪里变得更糟糕
- malloc从O(1)变成了O(n)
- header size增加，空间效率降低
