如果我来设计 C++ 的 内存堆 ， 我会这样设计 ：
进程 首先会跟 操作系统 要 一块大内存区域 ， 我称之为 Division ， 简称 div 。
然后 ， 将这块 div 作为 堆 ， 就可以开始 从堆里分配 内存 了 。
堆里 未分配 可使用 的 内存区域 称之为 Free Space ， 一开始的时候 ， div 里 只有一个 Free Space ， 就是 整个 div 。
如果 只分配 不回收 的话 ， div 里 永远都只有一个 Free Space 。 随着 分配 和 回收 ， div 里会产生多个 Free Space 。
我们需要建立一张 堆表 来 记录 Free Space ， 这样才能知道 每一次分配 应该 到 哪个 Free Space 里 分配 。
堆表 应该是一个 链表 ， 便于 插入 和 删除 表项 。 表项 就是 Free Space ， 或者说 表项 描述 Free Space 。 所以 表项 会包含 2 个 字段 ， 一个是 Free Space 的 起始地址 ， 另一个是 Free Space 的 结束地址 。
同时 还应该有一个 指针 ， 指向 当前在用的 表项 ， 一次分配 就是 在 当前表项 指向的 Free Space 里分配 ， 如果 当前 Free Space 的 大小 不足以分配本次申请的 内存块大小 ， 则 将指针 指向 当前 Free Space 的 下一个 Free Space 。 如果 下一个 Free Space 的 大小也不够 ， 那么 就继续指向 下一个 Free Space 。 如此循环 。
那如果 最后一个 Free Space 的大小也不够的话 ， 就需要向 操作系统 要 一个 新的 div 。 注意 ， Free Space 只能属于一个 div ， 不能跨 div 。
如果 堆里的 Free Space 比较多 ， 那么 如果 Free Space 大小不够 ， 有可能会连续找多个 Free Space 才找到 足够大小的 Free Space ， 这里就产生了一个 性能问题 。
最坏的情况 ， “从头找到尾” ， 到最后一个 Free Space 才足够大小 。 但 ， 这还不是最坏的 ^^ ， 如果最后一个 Free Space 的大小也不够的话 ， 就要跟操作系统要一个 新的 div ， 这好像要 “更坏” 一点 。 ^^
还有一个重要的问题需要考虑 ， 就是 如果 跟操作系统要了 1 个以上的 div ， 如果长期占用 ， 这是一个不小的空间 。 那么 ， 要怎样在 div 中的内存全部都已经回收 （整个 div 是一个 Free Space） 的时候 ， 将 div 归还操作系统呢 ？
可以通过一个 计数器 。 可以为每个 div 设置一个 计数器 ， 同时在 堆表项 里增加一个 字段 ： Free Space 所在的 div 。
这样 ， 每次 分配 的时候 就在 计数器 里 加 1 ， 每次 回收 就让 计数器 减 1 ， 如果 减 1 以后 计数器 的 值 是 0 ， 那么就说明 div 已经全部回收 ， 可以将 div 归还 操作系统 。
最后 ， 我很好奇 ， C++ 是怎么解决 内存碎片 的问题的 。 哈哈哈哈
突然发现 堆 的 管理算法 有点 小复杂 ， 如果 堆表 本身占用的内存空间是 固定 的 ， 那么如果 Free Space 的数量超出了 对表 的空间所能存储的数量 ， 这就有问题 ， 如果舍弃一些 比较小的 Free Space ， 会造成 内存泄露 。
如果 堆表 的存储空间也是通过 堆 的方式来分配 ， 那么 ， 当应用程序申请了一块内存 ， 此时产生了一个 新的 Free Space ， 为了记录这个 Free Space ， 需要为描述这个 Free Space 的 堆表项 也 申请一块内存 ， 这样 Free Space 又会发生变化 ， 可能产生 1 个新的 Free Space， 或者 要记录的这个 Free Space 发生变化 ， 需要把这些情况也考虑进去 。
还有一种情况是 归还 内存块 的时候 ， 这个内存块刚好在 2 个 Free Space 中间 ， 那么归还这个内存块就不是简单的在 堆表 里添加一个 堆表项 ， 而是要和 前后 2 个 FreeSpace “合并” 起来 。 这 3 个 Free Space 会 合并成 1 个 Free Space ， 在 堆表 里 会 删除 原来的 2 个 Free Space 表项 ， 同时在 这 2 个 表项 的位置 添加入 合并后的 新表项 。
问题是 ， 要怎么知道 归还的内存块 在 某 2 个 Free Space 中间 ？ 好像只能 遍历 。 但这意味着 每次 归还的时候都要 遍历 。
然后 。
实际上 ， 不仅仅 内存块 在 2 个 Free Space 之间会存在这个问题 ， 只要 归还的内存块 的 任一边（前 或 后） 和 1 个 Free Space 相连 ， 都需要 “合并” 。
如果要快速的找到 和 自己邻近的 Free Space ， 可能需要建立 索引 。 可以建立 不止一个 的 索引 。
比如 可以 按 起始位置 建立索引 ， 同时还可以按 Free Space 的大小 建立索引 。 前者可以快速的寻找 和当前 归还的内存块 相邻的 Free Space 。 后者可以快速的寻找接近指定大小的 Free Space ， 这可以用在 分配 的 时候 ， 寻找接近 申请内存块大小 的 Free Space 进行分配 有利于提高 内存利用率 ， 减少碎片 。
索引 也可以排序 ， 如果要 优先从 小的 Free Space 或者 大的 Free Space 来 分配 的话 ， 索引的 排序作用 也可以派上用场 。
关于索引 ， 我在 《我发起了一个 .Net 开源数据库项目 SqlNet》 https://www.cnblogs.com/KSongKing/p/9501739.html 中有一些论述 。 实际上 ， 我正是考虑 数据库 中 Data Block 的 Free Space 如何管理 ， 所以才继续思考 内存堆 的 管理问题 ， 然后就产生了上面的一些思考结果 。
可以设想一下具体的做法 ：
如果不考虑 堆 的 无限增长 的话 ， 设计起来并不太难 ：） 所谓 无限增长 ， 主要是指 堆表 的无限增长 。 堆表 为什么会无限增长呢 ？ 堆表 是保存 Free Space 的 ， 如果 Free Space 无限增长 ， 那么 堆表 就会无限增长 。 Free Space 的数量是不确定的 ， 但理论上 ， 似乎不能给出一个限制 。 如果我们给定 堆表 的长度是 1万 ， 那么就只能记录 1万 个 Free Space ， 超出 1万 个的 Free Space 会因为不能记录而处于 “遗弃” 的状态 ， 既不能 分配 也不能回收 。 这就造成了 内存泄漏 。
如果在 堆表 达到上限的时候 抛出 异常 “堆表超出最大范围” ， 就像 StackOverflow 或者 OutOfMemory ， 但这可能会限制了应用程序的能力 。
如果按照上文的说法 ， 堆表 的 存储 本身也完全通过 堆分配 进行 ， 这样可以很灵活 ， 看起来只要内存空间足够 ， 那么 ， 堆表 可以无限增长 。
但这种做法 是 “自己描述自己” 的一个 循环 ， 会导致算法复杂 ， 循环 ， 或者 无解 。 所以我们放弃了这种方式 。
问题出在哪里呢 ？ 堆表项 自身对于 内存空间的 占用不能 计算到 堆 的分配里 。 堆表应该是单独占用一块空间 ， 堆表项 及 索引项 的 添加删除 在这个空间也会造成 空闲空间 （Free Space） ， 但这些 Free Space 不能 计算到 堆 里 ， 而应该是 独立 于 堆 的 存在 。 否则就会陷入上述的 “自己描述自己” 的 循环 。 总之情况很复杂 ， 可能无解 。 当然也许有解 ， 但我不想继续思考下去了 ：）
所以 ， 回到开始 ， 如果不考虑 堆 的 无限增长 的话 ， 就是说 给定一个 堆表 的 固定大小 ， 我们这样来设计 堆 试试看 。 经过上面的论述 ， 实际上 ， 如果要设计 无限增长的 堆表 ， 那么 ， 在 固定大小 的 堆表 基础上 ， 增加一点 ： 当 当前堆表 空间不够时 ， 再申请一块 堆表空间 用于 继续存放 堆表 ， 这样 堆表 就能继续增长了 。
我们提供一块 连续的 内存空间 来 存储 堆表 ， 这块 内存空间 我们 称之为 堆表空间 。 按照上面说的 ， 我们先尝试实现 一个固定大小 的 堆表空间 的 堆 。
堆表 的内容 包括 Free Space 项 和 索引 。 索引 由 索引项 组成 ， 索引项 最终会指向 堆表项 ， Free Space 项 之间通过 链表 的方式 相连 。 Free Space 项 和 索引项 都 存储在 堆表空间 里 。
堆表 还 包括一个 指针 ， 指向 堆表 的最后一个元素的结束地址的下一个地址 ， 我们将这个指针 称为 “Append 指针” 。
所有 新建 的 堆表项（Free Space 项 和 索引项） 都 添加至 Append 指针 指示的 地址 ， 每添加完一个 堆表项 ， Append 指针 会指向这个 堆表项 的 结束地址 的 下一个地址 。 当 Append 指针指向的 地址 到 堆表 的结束地址 之间的空间 不够 存放新的 堆表项 时 ， 会检查 “堆表空闲空间计数器” ， —— 等 —— 什么是 “堆表空闲空间计数器” ？ 在 堆表 的使用过程中 ， 随着 Free Space 项 和 索引项 的 添加 删除 ， 当然也会出现 “空闲空间” ， 我们会用一个 整数变量 ， 来记录空闲空间有多少（以 Byte 为单位） ， 每次删除 堆表项 （Free Space 项 和 索引项） 的时候 ， 会 将 回收 的 空闲空间 累计 到 这个 整数变量 里 。 这个变量 就是 “堆表空闲空间计数器” 。 注意 ， “堆表空闲空间计数器” 记录的是 Append 指针指向的地址之前 “已使用的空间” 中 因 堆表项 的 删除 而 “空出来” 的 空闲空间 。 这些 空闲空间 平时不会去动它 ， 只有上面说的 “当 Append 指针指向的 地址 到 堆表 的结束地址 之间的空间 不够 存放新的 堆表项 时” ， 才会去关心 它 。 怎么关心呢 ？ 这个时候 ， 会做一次 “垃圾回收” ， 就是把 这些 空闲空间 后面 的数据 向前移动 ， 填补这些 空闲空间 ， 就可以了 。 当然 ， 会先检查 “堆表空闲空间计数器” ， 如果 计数器 值为 0 ， 表明没有空闲空间 ， 不需要 垃圾回收 ， 大于 0 表示 有空闲空间 ， 需要 垃圾回收 。 如果没有要 回收的 空闲空间 ， 或者 回收了 空闲空间 以后 Append 指针指向的 地址 到 堆表 的结束地址 之间的空间 仍然不够 存放新的 堆表项 ， 怎么办呢 ？ 对于 固定大小的 堆表 ， 则 抛出异常 “堆表超出最大范围” ， 就像 StackOverflow 或者 OutOfMemory 。 对于 可以无限增长的 堆表 ， 则 新申请一块 堆表 空间 ， 继续工作 。 新的 堆表空间 和 原来的 堆表 空间之间 通过 链表 的 方式 相连 。
一个 堆表空间 包括 3 个部分 组成 ：
1 一块连续的内存空间
2 Append 指针
3 堆表空闲空间计数器
要 申请新的 堆表空间 ， 需要提前进行 ， 不要等到 空间不够用 的时候再进行 。 这是因为 新的 堆表空间 的申请 同样也是 通过 堆 的方式进行 ， 同样需要在 堆表 里 记录 堆表项 （Free Space 项 和 索引项）。 当某一次 申请 或 回收 需要记录 堆表项（Free Space 项 和 索引项） 而 空间不够时 再去 申请 新的堆表空间 ， 则 本次应用程序的申请或者回收 所产生 的 堆表项 （Free Space 项 和 索引项） 和 申请 新的 堆表空间 所产生 的 堆表项 （Free Space 项 和 索引项） 要放在一起计算 和 存储 ， 这样情况很复杂 。
所以 ， 应用程序的申请和回收 内存块 ， 和 申请 新的 堆表空间 ， 应该是 2 次 独立操作 。 所以需要 提前进行 “未雨绸缪” 。 提前到什么程度呢 ？ 在 原来的 堆表空间 的剩余空间 还 足够 存储 一次 申请内存块 产生的 可能的 最大数量的 堆表项 （Free Space 项 和 索引项） 的时候 。
申请一次 内存块 可能产生多少 堆表项 （Free Space 项 和 索引项） ？ Free Space 项容易理解 ， 上文也分析过 。 那么会产生多少 索引项 ？
上文中提到可以 创建 2 个索引 ： 1 Free Space 起始地址 作为检索条件 的索引 ， 2 Free Space Size（空间大小） 作为检索条件 的 索引 。
索引 1 可以用做 回收时 查询 和 回收的内存块 相邻的 Free Space ， 如果 2 者是 相接 的 ， 则会进行 合并 。
索引 2 可以用做 分配时 查找 Size（空间大小） 最接近 申请内存块大小 的 Free Space 。
但实际上 ， 索引 的 创建 也是 比较消耗时间的 ， 分配 可以采用前文最早提出的 先在 当前 Free Space 中分配 ， 若当前 Free Space 的空间大小不足以分配 ， 则 查找下一个 Free Space 分配 ， 以此递推 。 在 内存空间 充裕的条件下 ， 这种方式比查找 索引 快 ， 同时避免了 创建索引 消耗的时间 。
我们接下来就来 分析 索引的 创建 和 查询 ：
根据上述 ， 我们只会建立和使用 索引 1 ， 用于 回收 时 合并 相接 的 Free Space 。
索引 1 在 分配时 创建（更新） ， 在 回收时 查询 并 更新 。
索引 1 的 索引项 是 这样 ： 最高位字节 用来保存 索引项的值 ， 只会用到 低位 的 2 位 ，表示 4 种情况 ： 00 , 01 , 10 , 11 。 后面再跟 4 个字节 或 8 个字节 表示 指向的 子索引项 或者 Free Space 项 的 地址 。 如果是 32 位 或 “Any CPU” 应用程序 ， 则是 4 个字节 ， 如果是 64 位 应用程序 ， 则是 8 个字节 。
在 分配 时 ， 用于 分配的 Free Space 的 大小（Size） 和 起始地址 会发生变化 。 对于 索引 1 ， 只需根据 起始地址 来 更新索引 即可 。
Free Space 的 起始地址 字段 表示 空闲空间 的 起始地址 。 同上 ， 如果是 32 位 或 “Any CPU” 应用程序 ， 则是 4 个字节 ， 如果是 64 位 应用程序 ， 则是 8 个字节 。 根据 《我发起了一个 .Net 开源数据库项目 SqlNet》 https://www.cnblogs.com/KSongKing/p/9501739.html 文中对于 索引 的 论述 ， 对于 32 位的数据 ， 会建立 32 / 2 = 16 个索引项 -_- ， 对于 64 位的数据 ， 会建立 64 / 2 = 32 个索引项 -_- 。
所以 ， 对于 32 位 或 “Any CPU” 应用程序 ， 分配时 Free Space 起始地址 发生变化 需要修改 索引 最多需要 约 16 个索引项 ， 或者说 时间花费是 O(16) 。 因为 检索 1 个 索引项 需要 判断 4 种情况 ： 00 , 01 , 10 , 11 。 所以我们可以假设 1 次操作的时间是 4ns （4 纳秒） ， 那么 O(16) 的时间就是 16 * 4 = 64 ns （64 纳秒） 。 而 回收 需要查找索引找到 和 回收的内存块 相邻的 Free Space ， 同时 回收后 可能更新相邻 Free Space 的 起始地址（合并） ， 或者 产生一个 新的 Free Space ， 对于前者 ， 需要修改索引 ， 对于后者 ， 需要创建索引 ， 但不管是哪种 ， 最多需要检索（修改）的 索引项 约 16 个 ， 可以认为 时间花费 是 O(16) ， 而 回收 时查找索引寻找相邻 Free Space 的 时间花费 也可以认为是 O(16) ， 所以 加起来就是 回收 的 时间花费 是 O(16) + O(16) = O(32) ， 同上 ， 假设 1 次操纵的时间是 4ns ， 则 回收 的时间花费是 32 * 4 = 128 ns （128 纳秒） 。 当然 分配 和 回收 具体花费的时间还会 包括 修改 Free Space 起始地址 ， Next 指针 ， 合并时 删除 多余的 Free Space 项 等 ， 这些先忽略不计 ， 在下面估算的时候会酌情估算进去 。
一次 分配 的时间是 64ns ， 再加上 分配 时 可能发生的一些遍历 （在 当前 Free Space 的大小不够时 ， 访问下一个 Free Space 尝试分配 ， 以此递推） ， 就按 80ns 算 ， 1 秒钟 大概可以进行 1200万次 分配 。 如何 ？ 还行吧 ， 呵呵 。 不过比起我想象中的 new ， 还是 慢了一点 ， 我想象中的 new 应该是 1ns new 一个嘛 ！ P： new 就是 分配 。
一次 回收 的时间是 128ns ， 就按 150ns 算 ， 1 秒钟 大概可以进行 600万次 回收 。 能不能再快一点 ？ ^^
对于 64 位 应用程序 ， 时间花费 是 32 位 的 2 倍 ， 所以 1 秒钟 可以分配 600万次 ， 回收 300万次 。 如何 ？ 哎 ？ 为什么 64 位 反而慢了 ？
上面的 分配 和 回收 的 执行速度 是 针对 1 个 CPU 核 分析的 ， 但对于多核 ， 分配 和 回收 的 执行速度 也是 如此 。 因为 堆 是进程内所有 线程 共享的 ， 堆表 也是共享的 ， 在进行 分配 和 回收 时要修改 堆表 ， 此时需要对 堆表 进行 同步/互斥 （Lock） ， 所以 ， 对于多核 ， 分配 和 回收 的 执行速度 也是 如此 。
从这里可以看出 ， 堆 的这一特性会成为 瓶颈 。 在 高频 高密度 计算的 场合 。 比如 高并发 实时 响应式 系统 。 说的直接一点 ， 就是跟现在的 互联网 大规模 计算 有关 。
这一类型的 瓶颈 也表现在 其它方面 。 比如 套接字（Socket） ， Socket 对于每个网卡只会有一个 线程 负责从 网卡 读写数据 。 这是我的 推测 。 一个 端口（Port） 的 Socket 由一组线程组成 ： 1 负责从网卡读写数据的线程（1 个网卡 对应 1 个线程） ， 2 处理和分发数据给应用程序的线程们（有若干个线程 ， 线程数 和 CPU 的 核数对应 ， 可以包括 虚拟线程(超线程) 数） 。 在 线程 1 和 线程 2 们 协作 的时候 ， 会有一个共享数据区 ， 线程 1 会把从 网卡 读取到的 数据 放到 共享数据区 ， 线程 2 们 会从 共享数据区 取出数据处理分发 。 显然 ， 线程 1 和 线程 2 们 的协作需要 同步/互斥（Lock） ，
我们可以看一下这篇文章《面向对象编程的弊端是什么？》 https://www.zhihu.com/question/20275578/answer/136886316?utm_source=com.tencent.tim&utm_medium=social&utm_oi=697587017629851648
文中有一幅图 ：
如图 红线 所示 ， Mutex（同步 / 互斥 Lock） 的时间是 17ns （17 纳秒） 。 这个时间是一个 不太能忽视 的 时间 。
所以 ， 这会成为 利用 并行计算 大幅提升计算能力的 瓶颈 。 而 利用 并行计算 大幅提升计算能力 正是 当下和未来 的 主题 。
另外就是 ， 一个网卡只有一个 IO 线程 ， 这也可能成为 瓶颈 。 当网络技术发展到 5G 或 6G 的时候 ， 会不会有 NPU（Net Process Unit）出现 ？ 就像 GPU 一样 。 ^^
实际上 ， 对于 堆表 的无限增长 ， 有一个 “终极” 的解决办法 ， 或者说 更好的办法 。 就是 GC （垃圾回收器） 。
在 现代 ， 或者说 “当代” 的 语言 ， 如 C# , Java 里都有 GC 。 GC 可以将 Free Space 的 数量 控制在 有限 和 很少 的 范围 。 这样就不存在 堆表 的 无限增长 了。
然后 。
当然 ， GC 要登记 所有变量 ， 并定期遍历 ， 移动数据 ， 这些也要花费时间的 。
堆表 的 无限增长 ， 这是一个问题 。 堆表 增长 ， 表示 Free Space 增多 ， 碎片 也增多 ， 这样 在 分配 时可能会遍历 比较多的 Free Space 。
对于 64 位 应用程序 ， 64 位 理论上的 寻址空间 可以达到 16eb ， 如果 应用程序 对于 存储空间 的使用是没有限制的 ， 那么 ， 一段时间之后 ， 堆表 ， 或者说 Free Space （包括碎片） 的 数量 可能会达到 很大的 数量 。
假想一下 ， 如果 Free Space 很多 ， 碎片也很多 ， 那么可能要遍历 很多次 才能找到 大小足够的 Free Space 进行分配 。 这个时候 ， 我们可以考虑加入这样的算法 ， 最多遍历 10 个 Free Space ， 遍历了 10 个 Free Space 还找不到大小足够的 Free Space ， 则 向操作系统 申请 1 个 新的 div ， 并将 div 作为 新的 Free Space 插入到当前位置 ， 并从这个 div（新的 Free Space） 中分配 。 分配以后 ， 下一次分配当然也会从这个 div 开始 ， 如果这个 div 的 剩余空间 不够 ， 则 访问下一个 Free Space 。 如果访问了 10 个 Free Space 也找不到足够大小的 Free Space ， 则 重复上述流程 ， 向操作系统 申请 1 个 新的 div ， 并将 div 作为 新的 Free Space 插入到当前位置 ， 并从这个 div（新的 Free Space） 中分配 。 以此递推 。
这种方式 ， 可能会浪费一些空间 ， 或者说 ， 会向 操作系统 申请多一些的 空间（div） ， 但是在 时间 上提高了效率 。 这也算是 “空间换时间” 吧 。 在 现在来讲 ， 硬件容易扩充 ， 提升计算速度 是一个主要目标 。
根据以上 ， 我们再来整理一下 具体的 做法 。
我们 以 64位 应用程序 的 标准 来实现 ：
当进程启动时 ， 会分配一块 固定大小 的 连续空间 ，作为 堆 的 基础元数据区 ， 基础元数据区 包括 5 部分 ：
1 Append 指针 ， 指向 堆表 可插入 堆表项 的 地址 （当前 最后一个 堆表项 之后） ， 插入 堆表项 后 ， Append 指针 会 指向 堆表项 结束地址 的 下一个地址 。 Append 指针 的 初始值 应指向 第 5 个 堆表项 的 起始位置 。 因为会在 堆表 中 预先建立 4 个 1 级 索引项 ， 见 下面 第 4 部分 。
2 堆表 的 Free Space 项 链表 头指针 ， 指向 Free Space 项 链表 的 头 。 （Free Space 项 之间通过 链表 的方式连接起来）
3 当前 Free Space 项 指针 ， 指向上一次用于 分配 的 Free Space 项 。 下一次 分配 会先尝试在 上一次 分配 的 Free Space 中进行 ， 若 Free Space 的 大小不够 ， 会 访问 下一个 Free Space 尝试分配 。 分配 成功后 ， 当前 Free Space 项 指针 会指向 分配 成功的 Free Space 项 。 当然这里面还有些具体的逻辑 ， 比如 访问 超过 10 个 Free Space 项 仍然找不到 大小足够 的 Free Space ， 则 会向操作系统 申请 新的 div ， 作为 Free Space 加入进来 ， 然后在这个新的 div 中 分配 。
4 堆表 的 初始空间 。 堆表 的 初始空间 可以是 1 MB 。 进程启动 时 ， 会初始化 基础元数据区 ， 此时应在 堆表 的 第 1 ~ 4 个 堆表项 位置 预先建立 1 级 索引项 （00 , 01 , 01 , 11） 。 所谓 初始空间 是指这部分是 固定不变 的 ， 之后 堆表空间 不够用时 ， 会在 堆 中申请新的 堆表 空间 。 这些新申请的 堆表空间 空出来的时候会 归还 堆 ， 但 初始空间 是 不变的 ， 不变是指 一直存在 ， 大小不变 。 且 初始空间 不属于 堆 。
5 Next 指针 ， 指向 下一个 堆表 空间 。 随着 堆 的规模的增长 ， 堆表 大小不够时 ， 会从 堆 里 申请 新的 堆表 空间 ， 新的 堆表空间 会和 初始空间 用 链表 的方式连接起来 ， 可以 申请 多个 堆表空间 ， 如 ： 初始空间 -> 第 1 个新申请空间 -> 第 2 个新申请空间 -> 第 3 个新申请空间 -> …… 第 n 个新申请空间 -> ……
当 堆 的规模缩小时 ， 会释放 空闲 的 堆表空间 （归还 堆） 。
初始空间 不属于 堆 ， 当然永远不会释放 。
接下来 ， 我们这样来定义堆表项 ：
堆表项 分为 2 种 ：
1 索引项
2 Free Space 项
具体规则是 ：
1) 索引项 和 Free Space 项 都占用 34 个字节 。 第 1 个字节 是 标识字节 ， 为 1 表示 索引项 ， 为 2 表示 Free Space 项 ， 为 0 表示 已删除 。
2) 对于 索引项 ， 第 2 个 字节表示 索引值 ， 就是 00 , 01 , 10 , 11 这 4 种值中的一种 ， 实际上这 4 种值只用到了 2 位 ， 不过我们还是用一个字节来存储 。 如果是 十进制 表示这 4 个值 ， 就是 0 , 1 , 2 , 3 。 我们设计的是 4 阶索引 ， 第 3 ~ 10 个字节存储 第 1 个 子索引项 或 Free Space 项 的 地址 （64 位地址 用 8 个字节存储）， 第 11 ~ 18 个字节存储 第 2 个 子索引项 的 地址 ， 第 19 ~ 26 个字节存储 第 3 个 子索引项 的 地址 ， 第 27 ~ 34 个 字节存储 第 4 个 子索引项 的 地址 。 若 8 个字节表示的 64 位地址 （ulong 无符号长整型 uInt64） 为 0 ， 表示 子项 不存在 。 有关 索引 和 4 阶索引 ， 我在 《我发起了一个 .Net 开源数据库项目 SqlNet》 https://www.cnblogs.com/KSongKing/p/9501739.html 一文中有论述 。
所以 ， 可以看出 ， 索引项 长度 是 1 + 1 + 8 + 8 + 8 + 8 = 34 个字节 。
3) 对于 Free Space 项 ， 第 2 ~ 9 个字节 表示 起始地址 ， 第 10 ~ 17 个字节 表示 结束地址 。 第 18 ~ 25 个字节 表示 所在的 div 的起始地址 。 第 26 ~ 33 个字节 表示 Next 指针 指向 下一项 Free Space 项 （Free Space 项 之间会通过 Next 指针来用 链表 的方式连接起来） 。 Free Space 项 的 长度 是 1 + 8 + 8 + 8 + 8 = 33 个字节 。
为了便于管理 ， Free Space 项的长度也定义为 34 个字节 ， 和 索引项 一样 。 多出来的 1 个字节 不会用到 。
将 索引项 和 Free Space 项都定义为 34 位 是 便于管理 ， 或者说 便于算法处理 。 堆表 进行垃圾回收的时候 ， 只需要每隔 34 个字节检查一次 标识字节 ， 就可以知道 堆表项 是否已删除 ， 若 已删除 则将后面的 堆表项 移动上来 ， 填补 已删除 的 空闲空间 。 这就是 堆表 的 垃圾回收 。
div ， 接下来说明 div 的定义规则 。 div 是 进程向 操作系统 申请 的一块 大的 内存区域 ， 用于作为 堆空间 。
第 1 次 分配 内存块 时 会申请 第 1 块 div 。 如果从来没有 申请 过 内存块 ， 则不会申请 div 。
div 分为 3 个部分 ：
1 结束地址 ， div 的 结束地址 ， 用 8 个字节表示 （ulong 无符号长整型 uInt64）
2 分配计数器 useCount ， 用于记录 分配 的内存块 数量 ， 若 计数器 的值为 0 ， 表示 div 完全空闲 ， 即没有 分配 任何空间 ， 可以 归还 操作系统 。 当然 刚申请到 div 的时候 ， 计数器 的值也是 0 ， 不过那时会接着用于 分配 。 计数器 也用 8 个字节表示 （ulong 无符号长整型 uInt64）
3 剩余的空间 用于 分配 。
接下来说明 运行逻辑 ：
我们先 估算一下 ， 1 MB 的 堆表 空间 够存放多少个 Free Space 项 （包含 索引项） ？
Free Space 项 的 地址是 64 位地址 ， 要为 64 位地址 建立 索引 ， 需要 64 / 2 = 32 个 索引项 。 每个 索引项 占据的空间是 34 个字节 ， 再加上 Free Space 项 占据 的 34 个 字节 ， 1 个 Free Space 需要的 存储空间 是 (32 + 1) * 34 = 1122 个字节 。 实际中会比 1122 小 ， 因为 索引 的 父节点 存在共用的现象 。 我们可以按 1024 来算 ， 存储一个 Free Space 需要 1024 个字节（包含 索引项） ， 那么 1 MB 可以 存储 1024 个 Free Space（包含 索引项） 。
所以 ， 1 MB 的 堆表 可以记录 1024 个 Free Space ， 如果 应用程序 申请 和 归还 内存块 产生的 Free Space 不超过 1024 个的话 ， 1 MB 的 堆表就够了 。 如果超过 ， 则需要 申请 新的 堆表 空间 。 新的 堆表 空间 在 堆 中申请 。 可以仍然申请 1 MB 。 如果 新申请 的 1 MB 堆表空间 用完了 ， 可以继续申请 1 MB ， 以此递推 。 当然 ， 实际中 不会等到 堆表空间 不够用时才去申请新的 堆表空间 ， 上文分析过 ， 如果这样的话 ， 会陷入 “自己描述自己” 的 循环中 ， 所以 ， 应该在 快用完（至少还足够保存一次申请产生的 最大的 Free Space 变化 ( 包含 索引项 ) ） 的 堆表 空间 时 就申请 新的 堆表空间 。
当 应用程序 第 1 次 申请 内存块 时 ， 堆管理程序 会 检查 基础元数据区 的 第 1 个 div 的 起始地址 ， 若 为 0 （div 不存在） ， 就向 操纵系统 申请 div ， 申请到后将 div 的 起始地址 记录到 基础元数据区 的 “第 1 个 div 的 起始地址” 。
然后 ， 将 div 的 第 3 部分 （用于 分配 的空间） 作为 1 个 Free Space 记录入 堆表 （这是 第 1 个 Free Space） 。 当然 ， 记录的操作 包括 了 建立 索引 。 注意 ， 1 级索引项 （00 , 01 , 10 , 11） 固定存储在 堆表 的 第 1 ~ 4 个 堆表项 位置 。 应用程序启动 ， 初始化 基础元数据区 时应预先建好这 4 个 索引项 。
接下来 ， 就开始在 堆表 中访问 Free Space 进行分配 ， 当然 现在只有 1 个 Free Space ， 就是上面刚添加进去的 Free Space 。 分配的话 ， 就从 Free Space 的 起始地址 开始分配 。 比如 ， 要 申请 1 KB 的 内存块 ， 那么就把 Free Space 起始地址 ~ Free Space 起始地址 + 1 K - 1 这块内存 分配 给 应用程序 。 如果 申请的 内存块大小 比 这个 第 1 个 Free Space 都大 ， 那么应该抛出异常 “只允许申请大小在 xx 范围内的内存块” 。
分配 的 具体工作 ： 修改当前 Free Space 的 起始地址 ， 修改为 Free Space 起始地址 + 1 K ， 同时 修改索引 ， 根据 Free Space 原来的 起始地址 遍历 索引项 ， 遍历到 和 新的 起始地址 不同 的 索引项 就修改 索引项 。 这么说好像不知道在说什么 。好吧 ， 我们举个具体的例子 ：
我们的设计是 64 位地址 ， 举例的话 就 简单一点 ， 我们 以 8 位地址 为例 ， 假设 Free Sapce 的 起始地址 是 0 （0000 0000）， 申请 4 个字节大小的内存块 。
申请前 Free Space 的 索引是这样的 ： 00 -> 00 -> 00 -> 00 ， 申请后 Free Sapce 的 起始地址 会变成 4 （0000 0100） ， 相应的 ， 索引会变成 ： 00 -> 00 -> 01 -> 00 ， 可以看到 ， 从 第 3 个索引项 开始 ， 新的索引 和 旧的索引 变得不同 ， 所以 我们 从 第 3 个 索引项 开始修改 为 新的索引项 就可以了 。
整个修改索引的过程 会 遍历 全部的索引项 （包含了 修改） ， 64 位地址 是 32 个 索引项 ， 所以 分配 的 时间复杂度 约大于 O(32) （还要考虑其它的操作 ， 所以是 约大于） ， 我们上文中就是这样估算的 。
其它还有什么操作呢 ， 好像没有了 。 ^^
分配就 2 步操作 ： 1 修改 Free Space 起始地址 ， 2 修改索引 。
接下来是 归还 ， 归还 分为 4 种情况 ：
1 归还 的 内存块 的 前后 不和 已有的 Free Space 相接 ， 这样 归还 会产生 一个 新的 Free Space 。
2 归还 的 内存块 和 前面 或者 后面 已有的 Free Space 相接 ， 这样 需要 和 相接的 Free Space 合并 。
3 归还 的 内存块 和 前面 和 后面 已有的 Free Space 相接 ， 这样 需要 和 前后 2 个 Free Space 合并 。
4 归还 的 内存块 没有 相邻 的 Free Space ， 这种情况比较特殊 ， 这种情况就是 整个 div 的 内存 完全被 分配 出去的 情况 。
具体 流程 是这样 ：
应用程序 将 内存块 的 起始地址 提供给 堆 来 归还 这块内存块 。 堆 根据 内存块 的 起始地址 查找索引 ， 查找 和 内存块 前相邻 的 Free Space 。 前相邻 ， 是指 相邻 且 在 前面 。 什么是 前面 ？ Free Space 的 起始地址 小于 内存块 的 起始地址 叫 前面 ， 大于 叫 后面 。
根据 索引 查找到 前相邻 的 Free Space ， 还不一定是 真正 的 前相邻 的 Free Space ， 还要加一个 判断条件 ： Free Space 所在的 div 和 内存块 所在的 div 是 同一个 div ， 这样才是 前相邻 的 Free Space 。
我们这样来 定义 前相邻 后相邻 ：
前相邻 ： 起始地址 小于 内存块 的 起始地址 ， 且 和 内存块 属于同一个 div ， 则为 前相邻 。
后相邻 ： 起始地址 大于 内存块 的 起始地址 ， 且 和 内存块 属于同一个 div ， 则为 前相邻 。
如果 查找不到 前相邻 ， 那么就根据 基础元数据区 里的 Free Space 链表 头指针 找到 头指针 指向 的 Free Space 项 ， 这个 Free Space 项 就是 内存块 的 后相邻 。
如果 Free Space 链表 头指针 为 空 （0） ， 也表示 没有 相邻 （既没有 前相邻 ， 也没有 后相邻） 。
什么情况下 Free Space 链表 头指针 为 空 （0） 呢 ？ 在 应用程序 初始化 后 ， 还没有 分配 的时候 。 以及 分配 以后 ， 整个 div 都被分配出去 。 如果有多个 div ， 所有 div 都被完全的分配出去 ， 头指针 也为 空 （0） 。
头指针 不空 ， 可以找到 起始地址 大于 或 小于 内存块 起始地址 的 Free Space ， 但 Free Space 和 内存块 不在同一个 div 的话 ， 也不是 相邻 。
怎么判断 Free Space 和 内存块 在不在 同一个 div ？ Free Space 项 有一个字段 是 所在 div 的 起始地址 ， div 的 第 1 个 部分 是 div 的 结束地址（见上文对 div 的定义） ， 根据 div 的 起始地址 可以找到 div 的 结束地址 ， 根据 div 的 起始地址 和 结束地址 可以判断 内存块 在不在 div 里 。
找到 前相邻 后 ， 判断 前相邻 的 结束地址 + 1 和 内存块 的 起始地址 是否相等 ， 若相等 ， 则 两者应合并 。 但这里还要进一步的判断 ， 是 情况 2 还是 情况 3 ， 所以 还需要 根据 前相邻 的 Next 指针 找到 下一个 Free Space 项 ， 这就是 后相邻 。 判断 后相邻 的 起始地址 和 内存块 的 结束地址 + 1 是否相等 ， 若相等 ， 表示是 情况 3 ， 若不等 ， 表示是 情况 2 。
如果 没有 相邻的 Free Space ， 就是 情况 4 。 如果有 相邻的 Free Space ， 但既不是 情况 2 ， 也不是 情况 3 ， 就是 情况 1 。
对于 情况 1 ， 需要 新建一个 Free Space 项 ， 插入到 Free Space 项 链表 里 ， 插入位置是 内存块 的 前相邻 之后 ， 或者说 ， 后相邻 之前 。 当然 ， 新建 Free Space 项 需要建立 相应 的 索引 。 索引 有 32 个 索引项 ， 所以 新建 Free Space 的时间复杂度 约大于 O(32) 。再加上 查找 前相邻 的时间复杂度 O(32) ， 所以 情况 1 的 时间复杂度 约大于 O(32) + O(32) = O(64) ， 约大于 O(64) 。 上文就是这样估算的 。
对于 情况 2 ， 如果和 前相邻 相接 ， 就 修改 前相邻 的 结束地址 和 索引 就可以 ， 如果和 后相邻 相接 ， 修改 后相邻 的 起始地址 和 索引 就可以 ， 这个和 分配 的 操作方法 一样 ， 参考上文 分配 的部分 就可以 。
对于 情况 3 ， 可以 修改 前相邻 的 结束地址 和 索引 ， 同时 删除 后相邻 ， 相应的 ， 后相邻 的 索引 也要删除 。 删除索引 的 步骤是 ： 根据 后相邻 的 起始地址 遍历 索引项 ， 对于只有 1 个子索引项 的 索引项 删除 即可 。 只有一个 子索引项 表示 从 当前索引项 开始的 索引路径 仅仅指向 要删除的这个 后相邻 。
对于 情况 4 ， 直接按照 内存块 的 起始地址 结束地址 新建一个 Free Space 项 ， 添加到 Free Space 堆表 ， 当然会建立相应的 索引 。 同时 ， 还要将 Free Space 项 插入 Free Space 项 链表 里 。 插入位置 在 —— 根据 索引 查找出 起始地址 小于 自己 的 Free Space 项 ， 插入到这一项之后就行 。 注 ： 因为不在同一个 div ， 所以 不能叫 前相邻 或者 后相邻 。 如果 查找不到 起始地址 小于自己的 ， 就插入到 头 ， 即 基础元数据区 里的 Free Space 链表 头指针 指向 自己 ， 自己 的 Next 指针 指向 原来 头指针 指向 的 那一项 。 如果 头指针 原来是 空 （0） ， 那就 让 头指针 指向 自己 就可以了 。
Free Space 项 链表 不是一个 独立 的 东西 ， 而是 堆表 里的 Free Space 项 之间会通过 Next 指针来用 链表 的 方式 连接起来 。 因为只有 Next 指针 ， 所以是 单向链表 。 现在看起来 ， 单向链表 够用了 。 -_- '
每次 申请 和 归还 后会检查是否进行 垃圾回收 ， 当满足以下 2 个条件时进行 垃圾回收 ：
1 Append 指针 到 堆表 结束地址 的 内存空间 小于 1500 个字节时 ，
2 堆表 的 空闲空间 超过 堆表空间 的 2/3 的时候
每次 垃圾回收 后会检查是否需要 扩充 堆表， 当满足以下条件时 扩充 堆表 ：
Append 指针 到 堆表 结束地址 的 内存空间 小于 1500 个字节时 ，
扩充 堆表 就是 申请新的 堆表空间 和 初始空间 用 链表 的方式 连接起来 ， 当然 ， 随着 堆 的规模的扩大 ， 可以 申请 第 2 个 、 第 3 个 、第 n 个 …… 堆表空间 ， 用 链表 的方式连起来就是 ： 初始空间 -> 第 1 个新申请空间 -> 第 2 个新申请空间 -> 第 3 个新申请空间 -> …… 第 n 个新申请空间 -> ……
这一点的意义上面已经多次分析过 ， 为了避免陷入 “自己描述自己” 的 陷阱 ， 所以需要在 堆表 空间 快用完时 ， 扩充 堆表 空间 。 堆表 空间最少要能够存储一次 分配 （包含 可能 申请 div 的 情况） 所产生的 Free Space 项 （包含 索引项） 。 一般的 分配 只需 修改 Free Space 项 的 起始地址 和 索引 ， 当有 申请 div 的 情形 时 ， 会新建 Free Space 项 及 完整的 索引 （32 个 索引项） ， 这应该是 分配 时 占用空间 最大的情况 ， 我们按这种情况来计算 。 上面说过 ， 1 个 Free Space （包含 索引项） 会占用 1122 个 字节 ， 我们放宽松一点 ， 在 堆表 剩余空间 只有 1500 个字节 时 就 扩充 堆表 。
那什么时候 “压缩” 或者说 释放 空闲出来的 堆表 空间 呢 ？
在 垃圾整理 后 ， 检查 最后一个 “不空” 的 堆表空间 ， 即 最后一个 存储了至少 1 个 堆表项 的 堆表空间 ， 如果 这个 堆表空间 的 空闲空间 超过 堆表空间 的 2/3 ， 那么将 释放 这个 堆表空间 之后 所有的 堆表空间 。 释放 就是 将 堆表空间 归还 堆 。 上文说了 ， 初始空间 以外 的 堆表空间 都是 从 堆 里申请的 。
初始空间 不属于 堆 ， 显然 ， 永远不会释放 。
说到这里 ， 显然 ， “堆表” 是一个 可扩充的 ， 由若干个 线性表 通过 链表 的 方式 连接起来的 数据结构 。
Append 指针 指向的是 最后一个 堆表项 ， 这个 堆表项 可能在 初始空间 ， 也可能在 新申请 的 第 n 个 堆表空间 。
在 分配 时 ， 会从当前 Free Space 项 指针 指向的 Free Space 项 开始 尝试分配 ， 如果 当前项 大小不够 ， 会 访问 下一个 Free Space 项 ， 如果 访问超过 10 个 Free Space 项 还找不到大小足够的 Free Space ， 则 会向操作系统 申请 新的 div ， 作为 Free Space 加入进来 ， 然后在这个新的 div （新的 Free Space） 中 分配 。
这主要是从 执行速度 的角度考虑 。 这也算是 “空间换时间” 。
这逻辑真的 乱 ， 烦 。
我们可以用 文件 的方式来模拟实现这个 堆管理 算法 。
就是用 一个文件 模拟 一块内存区域 ， 来实现这个 堆算法 。
我们会先实现一个 EnLargableList 的数据结构 ， EnLargableList 是一个 线性表 通过 链表 的方式连接起来的 可扩充的 数据结构 ， 用来实现 堆表 。
堆 的 复杂来自于 堆表 的 动态增长（无限增长） ， 如果 堆表 是 固定大小 的 ， 那么 堆 并不太难 。
上面有一个地方的逻辑有漏洞 ， 向操作系统申请了一个 div 之后 ， 除了 将 div 可分配的空间作为一个 Free Space 项 加入 Free Space 项 链表 外 ， 还应该新建一个 “空的” Free Space 项 加入 。 这个 “空的” Free Space 项 的 起始地址 和 结束地址 都是 div 的 可分配空间 的 起始地址 。 因为 起始地址 和 结束地址 相等 ， 所以是 “空的” 。 因为 大小 是 0 ， 总是 小于 申请的内存块的大小 ， 所以 ， 在 分配 的时候不会分配这个 Free Space 。
这个 空的 Free Space 有什么用呢 ？ 这是为了解决 整个 div 都被完全的分配出去的情况 ， 上文分析过了 ， 整个 div 都被完全的分配出去的话 ， Free Space 链表 里就没有这个 div 的 Free Space ， 这样 当 这个 div 里的 内存块 归还时 ， 会找不到 前相邻 和 后相邻 ， 从而不知道这个 内存块 是 哪个 div 的 ， 这样 归还 的逻辑就有问题 ， 就算不管是哪个 div 而直接将内存块作为 Free Space 归还 ， 最终也会导致即使这个 div 已经全部空闲（所有 分配 出去的 内存块 都 归还 了） ， 但是无法将 这个 div 归还 操作系统 。 相当于这个 div 处于 “半遗弃” 的状态 。因为 它的 Free Space 仍然可以继续 分配 和 归还 ， 但 这个 div 已经不在 正式名单 上了 ， 无法在 全部空闲 时 归还 操作系统 。 当然 ， 实际中 这样的操作是 不允许的 ， 因为 Free Space 项最后一个字段就是 指向 自己所在 div 的 起始地址 ， 就是说 Free Space 项 应该 知道 自己所在的 div ， 如果不知道 ， 程序不能运行下去 。
所以 ， 每个 div 一定会有一个 空的 Free Space ， 不管 div 的空间如何分配 ， 这个 空的 Free Space 会一直存在下去 ， 直到 div 归还操作系统 ， 这个 空的 Free Space 才会被删除 。
因为我们没有专门的表 来记录 div ， 所以这个 空的 Free Space 相当于 div 的代表 ， 或者 占位 。
上面的做法还是有一点问题 。 用一个 “空的” Free Space 来表示 div 会有一些问题 。 实际上 “空的” Free Space 不是空的 ， 是大小为 1 个字节 的 空间 。 起始地址 和 结束地址 相等 ， Free Space 的大小 = 结束地址 - 起始地址 + 1 = 1 。 所以 ， 在 归还 Free Space 时 ， 如果 归还的 Free Space 和 这个 “空的” Free Space 相接 ， 会和 “空的” Free Space 合并 ， 这又会引出合并后下次分配时 第 1 个字节 不能分配（作为 “空的” Free Space） 之类的判断 ， 会把算法逻辑变复杂 。
所以 ， 我们放弃了这种方式 。 正统的做法应该还是把 div 记录到 堆表 里 ， 也会为 div 建立索引 。 也就是说 ， 增加一种 堆表项 ： div 项 。 标识字节（第 1 个字节） 为 3 表示 div 项 。 div 项的第 2 ~ 9 个字节存储 div 的起始地址 。 当然 div 项的长度也是 34 （和 索引项 Free Space 项 相同） ， 多余的字节不会用到 。
这样 ， 在 归还 内存块 时 ， 如果找不到 前相邻 ， 也找不到 后相邻 ， 说明 div 被完全分配出去了 ， 此时就会根据索引查找 div ， 找到 起始地址 小于 内存块的起始地址 且相邻 的 div ， 这就是 内存块 所在的 div 。
归还 内存块 后 ， div 的 分配计数器 会 减 1 ， 减 1 后检查 计数器值 是否为 0 ， 若为 0 则 div 的空间已完全空闲 ， 于是将 div 归还操作系统 。
但这样的做法还是有问题 ， 要为 div 建立索引 ， 这有一点额外的麻烦 ， 比如 现在的 堆表项 开始的 4 个项位置 存储的是 4 个 1 级索引项 ， 如果要为 div 建立索引 ， 需要专门再为 div 建立 4 个 1 级索引项 ， 这些会增加算法内容 ， 会变得复杂或者麻烦 。
所以 ， 我们还是回到用 一个 “空的” Free Space 来表示 div ， 或者 占位 的做法 。 在 申请一个新的 div 的时候 ， 会创建 2 个 Free Space ， 一个是 “空的” Free Space ， 另一个是 可用的 Free Space 。 div 的开头会用 8 + 8 = 16 个字节分别表示 结束地址 和 分配计数器 use Count ， “空的” Free Space 就是 第 17 个字节 ， 起始地址 和 结束地址 都是 第 17 个字节 ， 从第 18 个字节开始就是 可用空间 了 ， 可用的 Free Space 就是 第 18 个字节 开始到 div 的 结束地址 。
我们可以给 Free Space 项 增加一个 字节 来表示 Free Space 的 “Type” ， 在 标识字节 之后 。 第 1 个字节是 标识字节 ， 我们用 第 2 个字节来表示 Free Space Type ， 0 表示 “空的” Free Space ， 1 表示 普通的 Free Space 。 这样的话 ， Free Space 项 和 索引项 一样 ， 都是 34 个字节了 。
在 分配 和 回收 时 需要判断 Free Space 时 “空的” Free Space 还是 普通的 Free Space 。 上文中定义过 ， 标识字节 为 2 表示 普通的 Free Space 。
在 分配 时 判断 ， 如果 是 “空的” Free Space ， 就不进行分配 ， 而是 访问下一个 Free Space 尝试分配 。
在 回收 时会寻找 前相邻 ， 如果 前相邻 是 “空的” Free Space ， 则不进行 判断是否相接若相接则合并的逻辑 。
EnLargableList （用于 堆表） 会设定这样一些参数：
1 whenRecycleFragment ， 这是一个 整数 ， 表示 碎片数量 超过多少 应开始 碎片回收 ， 可以设置为 1万 ， 碎片数量 是 以 对表项 为 单位 。 假设 堆表空间 是 1MB ， 每个 堆表项 占用 34 个字节 ， 可以存约 3 万个 堆表项 ， 约表示 1024 个 Free Space （每个 Free Space 最多由 33 个 堆表项 表示 ， 包含 32 个 索引项 + 1 个 Free Space 项） 。
如果 设置 whenRecycleFragment 为 1 万 ， 相当于是 一个 堆表空间 中有 1/3 的 空闲空间 ， 此时回收 。 效果怎么样 ？ 不知道 。
或者说 相当于 一个 堆表 空间中 记录了 600 个 Free Space 项 ， 还有 300 个 Free Space 的位置可以记录 ， 此时回收 。 效果怎么样 ？ 不知道 。
上文中提到 当 Append 指针 到 堆表空间 的 结束位置 的 空间 小于 1500 时 回收 ， 但现在放弃了这种做法 。
因为 这种做法 好像不太科学 ， 在应对 规模很大 的 堆 时候 ， 好像不太适用 。 堆 的 规模很大 ， 是指可以无限制的 使用 地址空间 ， 内存块 数量 和 Free Space 数量（包含 碎片） 可能 持续增长 。 大小 1MB 的 堆表 可以存约 3 万个 堆表项 ， 以 堆表项 为 单位 遍历 一遍 需要 遍历 3 万个 堆表项 。 3 万 是一个不小的数量 ， 所以我们想 当 碎片（空闲出来的 项位置） 达到 1 万 的时候回收 可能会比较好 。
2 whenEnLarge ， 这是一个整数 ， 表示 append 指针 到 堆表 末尾 的 空间还有多少时 扩充 堆表 容量 ， 扩充 堆表 容量 就是 申请新的 堆表空间 ， 新申请的 堆表 空间 以 链表 的方式连接到 当前 堆表空间 。
3 heapTableSpace ： 就是每一个 堆表 空间的 大小 ， 可以设为 1MB ， 每次申请 新的 堆表空间 就是 申请 heapTableSpace 大小的 一个 内存块 。
EnLargableList 还会 保存这样一些 字段 ：
1 appendPtr ， append 指针 ， 存储一个 64位地址 ， EnLargableList 写入数据时从 append指针 指向的数据开始写 ， 每写入一段数据 ， append 指针会移动到这段数据之后的位置 。
2 currentHeapTableSpace ， 当前 堆表空间 ， 即 append 指针 指向的 位置 所在的 堆表空间 。 这个字段用来 归还 堆表空间 。 归还 是指 ， 当 末尾一个 堆表空间 ， 即 当前 堆表空间 的 空间 全部 空闲出来时候 ， 会将 堆表空间 归还 堆 。 仅仅凭 append 指针 不能知道 append 指针 所在的 堆表空间 ， 所以还需要这个字段来记录 append 指针 所在的 堆表空间 ， 即 当前 堆表空间 。
3 recycleFreeItem ， 碎片回收 时 指向 空闲的项位置 ， 即 “碎片” ， 或者说 “已删除”的项 。
4 recycleScanItem ， 碎片回收 时 会先扫描 “碎片” ， 扫描到一个 “碎片” 之后 ， 会将 recycleFreeItem 指向这个 “碎片” 的位置 。 然后会扫描 堆表项 ， 每扫描一个 堆表项 ， 会检查 堆表项 的 子项 （子索引项 Free Space项） ， 若 子项 的 位置 大于 recycleFreeItem 指向的位置 ， 则将 子项 移动到 recycleFreeItem 指向的位置 ， “填补”这个碎片 ， 同时修改 当前扫描的 堆表项 中保存的 该 子项 的位置 。 这样就完成一个 “碎片” 的 回收 （“填补”） 。
然后就继续 扫描下一个 “碎片” ， 扫描到 “碎片” 后 ， 又接着扫描 上一次 扫描的 堆表项 。 怎么知道 上一次扫描的 堆表项 ？ 就是 recycleScanItem 指向的堆表项 。 不过这样看起来 ， 还要加一个 字段 ， 来表示 扫描到了 堆表项 里的 哪个子项 ， 如下 ：
5 recycleScanSubItem ， 表示 扫描到的 堆表项 的 子项 。 这个字段只要 8 位整数 就可以了 。
6 fragmentCount ， 表示 “碎片” 数量 ， 每次 删除 堆表项 时 加 1 ， 在 碎片回收 “填补” 碎片 的时候 减 1 ， 这个字段用于上文中 如果 fragmentCount 的数量达到 whenRecycleFragment 的值 的 时候 ， 就开始 碎片回收 。
7 堆表空间 的 useCount ， 这个 字段 是 每个 堆表空间 保存 1 个 ， 就是 堆表空间 的 useCount ， 就是 堆表空间 使用的计数（以 堆表项 为单位） 。 每写入 1 个堆表项 ， 就在 堆表空间 的 useCount 加 1 ， 每删除 1 个 堆表项 ， useCount 就 减 1 。 useCount 为 0 表示 堆表空间
每次 分配 和 回收 之后会 检查 fragmentCount ， 当 fragmentCount 超过 whenRecycleFragment 时 会开始回收 。 由于不希望回收占用太多时间 ， 可以设定 一个参数比如 recycleItemCount ， 比如 300 ， 表示 不管有没有回收完 ， 只 扫描 300 个堆表项 。
但这样会有一个问题 ， 本身要 fragmentCount 超过 whenRecycleFragment 时才开始回收 ， 而且每次又不回收完 ， 空闲出来的 碎片空间 得不到重复利用 ， append 指针 只能 一直向后移动 ， 所以可能导致 永远回收 不完 ， 堆表 持续 增长 。
所以 ……
我们这里有了一个 突破 ， 即对于 堆表 的 碎片回收 ， 我们采用了一个 新的算法 ， 就是在 堆表项 里 增加 1 个字段 ： fragmentNext 。
就是把 已删除的堆表项（碎片） 用链表的方式 连接 起来 ， 这样每次写入 堆表项 的时候从 这个 链表 的 头 取出 一个 碎片 ， 作为 新的堆表项 的 写入位置 。 fragmentNext 表示 下一个 碎片 的 位置 ， 或者说 ， fragmentNext 是一个指针 ， 指向下一个 碎片 。
实际上 是一个用 链表 实现 的 队列 。
所以 ， 需要在 基础元数据区 里增加 2 个字段 fragmentListHead , fragmentListTail ， 用于保存 碎片链表（队列） 的 头指针 和 尾指针。
每次 删除 堆表项 时 ， 将 被删除的 堆表项 的 标识字节 更新为 0 ， 表示 已删除 ， 同时将 堆表项 添加到 碎片队列 的 尾部 。
如果是 第一次 删除 ， 那么 碎片队列 里 还没有 元素 ， 则 将 头指针 和 尾指针 都指向 堆表项 。
每次写入 堆表项 的时候 ， 会先从 碎片队列 里 取得碎片 ， 作为写入位置 ， 如果 碎片队列 为空 ， 才会将 append 指针 作为写入位置 。
fragmentNext 指针也是一个 64位无符号整数 ( uInt64 ) ， 所以也占用 8 个字节 。 这样的话 ， 索引项 和 Free Space 项 的 大小 都是 34 + 8 = 42 个字节了 。
好的 ， 现在我们再来看看在这种算法下 ， 如何 回收 碎片 。 （这里的 “碎片” 是指 堆表 里的 碎片 ， 不是 堆 里的 碎片）
实际上 ， 在这个算法下 ， 碎片可以得到充分的利用 （每次 写入 都优先 从 碎片队列 中取得 碎片 作为写入位置 ， 碎片队列 为空才会用 append 指针 的方式） ， 所以 看起来 堆表 不会无理增长 。 但又一些特殊的情况 ， 比如 应用程序 先申请了 大量的 小块内存 ， 造成了 大量 的 Free Space ， 为了存储这些 Free Space ， 堆表 会变得很大 ， 之后 应用程序 又归还了 所有 或者 大部分 内存块 ， 也是 Free Space 会变得 很少 ， 此时 堆表 中就会产生大量 空闲空间（碎片） ， 这些 空闲空间 如果 长时间不用又不归还 堆 ， 也是一种浪费 。
我们可以这样来设计 堆表 的 碎片回收 算法 ：
首先 ， 只有 碎片数量 大于 某个值 的时候 ， 才会开始回收 。 比如 大于 1000 个碎片（约 1 MB） 。
从 初始空间 开始 ， 向后遍历每一个 堆表空间 ， 如果 堆表空间 的 useCount 为 0 ， 则可以考虑 释放 这个 堆表空间（归还 堆） 。
注意 ， 这里是 考虑 ， 不是一定要归还 。 还要判断一个条件 ， 就是 堆表 的 可用空间 usableSpace 是否足够 ， 若 足够 则 释放（归还）堆表空间 ， 否则不释放 。 注意 usableSpace 是 整个堆表 的 可用空间 （包括 所有的 堆表空间） 。
堆表 的 初始空间 不属于 堆 ， 属于 基础元数据区 ， 永远不会释放。
所以在 基础元数据区 中要增加一个字段 usableSpace ， 上文的一些算法逻辑也要做一些修改 。
usableSpace 初始值 等于 初始空间 的 大小 。 之后 每申请一个 新的 堆表 空间 ， 则 加上 新的 堆表空间 的大小 ， 若 归还 堆表空间 ， 则 减去 归还的 堆表空间 的 大小 。
每次 向 堆表 写入数据 ， usableSpace 加上写入数据的长度 ， 比如 1 个 堆表项 长度是 34 个字节 ， 那么 写入一个 堆表项 的话 ， usableSpace += 34; 。
每次 从 堆表 中 删除数据 ， usableSpace 减去删除数据的长度 ， 比如 删除 1 个 堆表项 ， 则 usableSpace -= 34; 。
上文中的 append 指针 到 堆表 末尾 的 空间 小于 1500 时 应 扩充 堆表 （申请 新的 堆表空间） 这一段 需要改成 ：
usableSpace 小于 1500 时 ， 应 扩充 堆表 （申请 新的 堆表空间） 。 上文中也提到 如果一个 堆表空间 的 useCount 为 0 ， 则 可以考虑 释放 这个 堆表空间 ， 但要判断一个条件 ， 即 堆表 的 可用空间 usableSpace 是否足够 。 我们可以设定比如 当 usableSpace - 当前考虑释放的堆表空间的大小 > 50 万个字节（可以存储约 500 个 Free Space 项 (包含 索引项)） 时 ， 可以 释放 这个 堆表空间 。
我们上文 设定的 1 个 堆表空间 的 大小是 1MB ， 所以 50万个字节 约等于 0.5 MB ， 上面的条件相当于是 释放了 这个 堆表空间 后 ， 堆表 的 可用空间 还有 0.5 MB ， 也就是 相当于 还有 半个 堆表空间 。
这些参数 可以 根据需要 进行设定 ， 上面给出的是 参考数值， 也是 举例 。
归纳一下 ， 就是 usableSpace 小于 1500 时 应扩充 堆表 ， usableSpace - 考虑释放的堆表空间大小 大于 50万 时 可以释放 堆表空间 。
是不是 更清晰 了 ？
碎片回收 应放在一个 另外的 线程 里 进行 。 （是不是 想起了 GC -_- ' ） ， 每隔一段时间运行一次（比如 每秒运行一次） ， 如果 堆表空间 的数量很大 ， 可以每次只遍历 几个 堆表空间 （比如 10 个） ， 后面的 下次 继续遍历 。 这样可以不影响 分配 和 回收 内存块 的 执行速度 。
（这里的 “碎片” 是指 堆表 里的 碎片 ， 不是 堆 里的 碎片）
为了能在 更新索引 时 只上溯到 索引项值 不同的 索引项 ， 需要再在 索引项 和 Free Space 项 里再增加 一个 字段 ， parentItem ， 保存 上一级 索引项 的 地址 ， 是一个 ulong 无符号长整型 ， 占 8 个 字节 ， 这样 ， 索引项 和 Free Space 项 的 长度 就是 42 + 8 = 50 了 。
更新索引 时 只上溯到 索引项值 不同的 索引项 ， 可以避免 为了 更新一个 Free Space 项 的 索引项 而 删除 这个 Free Space 项 的 全部索引项 并 重建全部索引项 。 删除全部索引项 再重建 可能会比较省事一些 ， 但效率上可能会低一点 。
上溯 的 逻辑 是 检查 上一级 索引项 的 索引值 和 新索引 在 这一层级 的 索引项 的 索引值 是否相等 ， 如果 相等， 则 在 这一级 索引项 上 开始 向下建立 新索引 的 索引项 ， 如果不等 ， 则 检查 这个 “上一级” 索引项 除了 当前 索引项 以外 还有没有 其它 子项 ， 如果没有 ， 则 删除 这个 “上一级” 索引项 之后 继续 上溯 ， 如果有 ， 则 直接继续 上溯 。 删除 “上一级” 索引项 当然 包括了 删除 当前 索引项 ， 实际上 ， 上溯 是从 Free Space 项 开始， Free Space 项 是 索引树 的 最底层 ， 也可以说是 叶子节点 ， 也可以说是 索引 最终指向 的 数据 ， 或者说 数据项 。
实际上 “上溯” 这个逻辑好像 行不通 ， 因为 上溯 到 索引值 和 新索引 在 这一层级 的 索引值 相同 这并不能说明 更上层 的 索引值 和 新索引 的 对应相同 。要知道 更上层 （或者 说 每一层） 的 索引值 是否 和 新索引 的 对应相同 ， 需要 一直 上溯 到 顶层（一级索引）， 但这和 从 一级索引 自顶而下 好像没什么区别 。 啊哈哈
为了简单起见， 我们采用 删除旧索引， 建立新索引 的方式 。 即 更新索引 采用 删除旧索引 建立新索引 的方式 。
我们来看一下这样的做法的 时间花费 ：
对于 申请 内存块（new）， 需要更新用于分配内存块的 Free Space 的 索引， 按照上述的做法， 更新包括了 删除旧索引 和 建立新索引， 删除旧索引 和 建立新索引 的 时间复杂度 都可以认为是 O(32) ， 加起来就是 O(32) + O(32) = O(32 + 32) = O(64) 。 按照我们在上面的 估算方法， O(1) 的时间按 4ns （4纳秒） 算 ， 那么 申请内存块（new） 的 时间花费 就是 64 * 4 = 256 ns 。 256 ns 我们按 300ns 算的话， 1 微秒 就可以 执行 3.3 次 new 操作， 1 秒就可以执行 330 万次 new 操作 。 因为我们将 256 ns 近似为 300 ns 计算， 所以可以认为 1 秒可以执行 330 万次 以上 的 new 操作 。
对于 归还 内存块（delete）， 分为 4 种 情况：
情况 1 ： 归还的 内存块 前面 和 后面 都 不和 已有的 Free Space 相接， 所以 不需要 “合并”， 这样只需要 新建 索引 就行， 时间复杂度是 O(32) ， 时间花费 是 32 * 4 = 128 ns ， 可以估算为 1 微秒 可以执行 7 次， 那么 1 秒可以执行 700 万次 。
情况 2 ： 归还的 内存块 前面 和 已有的 Free Space 相接， 需要 “合并”。 合并 只需 更新 相接 的 Free Space 的 结束地址 就行 。 因为 索引 是 按 Free Space 的 起始地址 建立的， 所以 更新 结束地址 不需要 更新索引， 所以 情况 2 的 时间复杂度 是 O(1) ， 由于只是更新结束地址， 可以认为 O(1) 的 时间花费 是 1 * 1ns = 1ns ， 1 秒 可以执行 10 亿次 。 我也有点怀疑， 真的这么简单吗 ？
情况 3 ： 归还的 内存块 后面 和 已有的 Free Space 相接， 需要 “合并”。 合并 只需 更新 后面相接的 Free Space 的 起始地址， 由于 索引 是 按 起始地址 建立的， 所以需要更新索引， 和 申请内存块 一样， 更新索引 包含 删除旧索引 和 建立新索引， 时间复杂度 是 O(64) ， 时间花费是 64 * 4 = 256ns ， 1 秒可以执行 330 万次 以上 。
情况 4 ： 归还的 内存块 前面 和 后面 都和 已有的 Free Space 相接， 需要将 前面 后面 的 Free Space “合并” 为一个 。 合并 需要 修改 前面的 Free Space 的 结束地址， 删除后面的 Free Space 。 修改 结束地址 不需要 更新索引， 所以 只需要 删除 后面的 Free Space 的索引就行 。 所以 时间复杂度 是 O(32) ， 和 情况 1 一样， 时间花费 是 32 * 4 = 128 ns ， 1 秒可以执行 700 万次 。
哎 ？ 我刚又想到一个 好主意， 申请内存块 的 时候为什么不从 Free Space 的 结束地址 分配呢？ 如果 从 Free Space 的 结束地址 分配的话， 就不用 更新索引， 只要修改 Free Space 的 结束地址 就可以了。 这样 就和 归还 的 情况 2 一样， 时间复杂度 是 O(1) ， 时间花费 是 1 * 1ns = 1ns ， 1 秒 可以执行 10 亿次 。 （1 秒 可以 new 10 亿次）
上面的 讨论 是 从 起始地址 开始 分配 内存块 的， 所以 每次 new 的时候 会 更新 起始地址， 也就会 更新索引 。
如果 换成 从 结束地址 一端 来 分配内存块 的话， 就不需要 更新 起始地址， 也就 不需要 更新索引， 可以大大提高效率 。
当然 这是在 Free Space 的大小足够分配的情况下， 如果 Free Space 的大小不够， 会向后寻找 Free Space， 若寻找了 10 个 Free Space 还未找到 大小足够 的 Free Space， 则会向 操作系统 申请 div 。 在这些情况下， 还需要考虑这些 时间花费 。
因为 不需要 上溯， 所以 索引项 和 Free Space 项 不需要 保存 上一级索引项 的 位置（地址）， 也就是不需要 parentItem 这个字段， 这样的话， 索引项 和 Free Space 项 的 长度 就 从 50 个字节 变回 50 - 8 = 42 个字节了。
实际上， 我们在 索引项 里 设计了一个字段 用来保存 索引值， 但后来发现， 由上一级索引保存的 4 个 子索引项 的 指针字段 可以 直接指向 子索引项， 子索引项 好像不需要 保存 索引值 。
我 这个 设计 是 不会 回收 堆里 的 碎片 的 。 这 跟 C# Java 之类 有 GC 的 不同 。 我想 C++ 也不会 回收 堆 里的 碎片 。 上文提到的 “碎片回收” 是 回收 堆表 里的 碎片 ， 不是 回收 堆 的 碎片 。 所以 不存在 “全盘整理” 。 每次 归还内存块 的时候 会检查 div 的 useCount ， 每次 分配 内存块 的时候， 这个 内存块 所在 的 div 会 useCount ++ ， 每次 归还内存块 ， 这个 内存块 所在的 div 会 useCount -- 。 如果 useCount == 0 ， 则将 div 归还 操作系统 。 但 这种情况 概率 可能 不大 ， 因为 一旦 div 投入使用后， 分配出去 的 内存块 必须 全部 释放， div 才会空（useCount == 0） ， 才能 归还 操作系统 。 但 在 实际使用中， div 投入使用后， 有 申请 有归还， 全部清空 的 概率 可能不大， 很长时间后， 可能 还有一些 “零碎” 的 内存块 占据着， 即使 是 少量的 内存块， 也 导致 div 不能归还 。 这就是 C++ 这一类 静态 做法 的 局限 。 可能导致 大块 内存 区域（div） 被 进程占据， 无法 回归到 操作系统 层面， 造成 资源的 浪费 。
所以， 要解决 这种 静态做法 的 局限， 就需要 引入 GC 这样的 动态特性 。 我想， 当初 GC 的 出现 （以 Java 为 代表） ， 不仅仅 是 为了解决 “内存泄漏” 的问题 ， 其实 也 隐藏了 上述 静态做法 的 种种 局限 的 原因 吧 ！
当然， GC 的做法 会增加 工作量， 会 花费 时间， 但是， GC 确实 可以有效 的 控制 堆碎片 数量 和 堆表大小 。 就是说， GC 可以 使 堆碎片 控制在一个 有限的 范围内， 使 堆表大小 控制在 一个 有限的 范围内 ， 这 本身 就 简化了问题， 减少了 管理 开销 和 复杂度 。 从 这个 角度来讲， GC 又是 减小了 时间花费， 提升了 效率 的 。
所以， 从 技术 进步 或者 进化 的 角度 来看， GC 是一次 进化， 使得 可以用 更现代 更高级 的 方法 来 管理 存储资源 。
相较之下， C++ 的 静态做法， 是 早期 和 朴素 的 。
在 现代 存储资源 可以 大幅 甚至 无限扩展 的 情形下， 或许 确实 需要 GC 这样 “动态” 的 方式 来 管理 存储资源 。 静态的 方式 面对 大幅 存储资源 可能 会 有 局限 。
当然， 在本文中设计的这种 “静态”做法， 实际上 也是 利用了 现代 存储资源 大幅提升 的 特点， 比较多 的 应用了 “空间换时间” 。
但确实 存在一个 问题， 就是 静态的 做法 无法 控制 碎片 的 增长， 包括 堆碎片， 甚至 堆表碎片， 或者说 不能有效控制 堆表大小 的 增长 。 本文的做法 可以回收 堆表 碎片， 但是 效果如何， 不知道 。 只要 堆表空间 里还有一个 堆表项， 就不能 释放 堆表空间（归还堆）， 这是一个 概率问题 。
所以， 要 准确 有效 的 管理 存储资源， 还是 需要 GC 这样的 “动态” 做法 。
所谓 “动态”， 套用一个术语， GC 建立了一个 “抽象层” 。
因为 有 这个 “抽象层”， GC 可以 移动 进程中 的 变量位置， 而 对于 程序来讲， 没有感觉到 变化 。
也正因为这样， GC 可以 有效的 控制 堆碎片 的 数量 和 堆表大小 在一个 有限 的 范围 。
在 C++ 里， 由于 C++ 比较 直接 的 面向 “底层”（操作系统）， 所以， C++ 不能提供 GC 这样的 “抽象层”， 对于 堆管理， 也就只能使用 “静态”的做法， 如上所述 。
但 到 目前为止， 上面说的 设计 解决了 基本 的 分配 和 回收 （包括 索引机制， 索引机制 确保了 检索操作的 时间花费 在一个 已知的范围内）， 但还存在一个重要的问题， 就是 “碎片占据 div” 的问题 。 就是说， div 里只要还有一个 内存块 没有 归还， div 就会被 进程 一直占用， 不能 归还 操作系统 。 这就导致 大块内存空间 的 浪费 。 这是一个 大问题 。
有 网友 查了 资料， 说 Linux 有一块 3G 的 用户空间， 进程可以使用， 使用这个 用户空间 不需要 系统调用（不需要切换到系统进程， 即不需要跨进程） 。 我的理解是 这是 操作系统 提供的 系统级 的 一个 “公共堆”， 可供所有进程使用 。 这样在 3G 的范围内， 进程可以共用 这个 公共堆， 这样可以解决 “碎片 占据 div” 的 问题 。
所以， 我说 这是个 重大发现 。
但 后来一想 ， 这样 又有一个 问题， 就是 地址访问 的 时候 不能 或者 难于 作 安全检测 了， 所谓 安全检测， 是指 检查 访问 的 地址 是否 越界 。 越界 指 访问了 其它进程 的 内存 。
资料显示， 现在的 安全检测 是 在 存储管理部件 中 完成的 。 这是一个 硬件， 是 CPU 的 一部分 。
操作系统 为 存储管理部件 设置 页表， 然后 存储管理部件 就可以工作了 。
看起来， 公共堆 没有 “段” 的 概念， 大概 很难 实施 判断 是否越界 的 安全检查 。
呀， 这可怎么办 ？
碎片， 分为 2 个 层面 ，
1 物理内存， 页文件
2 虚拟内存， 虚拟地址
对于 1 ， 操作系统 可以进行整理， 可以将 多个页 上的 零碎 的 数据 整理 到 一个 页， 再把 虚拟地址 映射到 新的页 就行 。 这样可以避免 频繁的 载入 载出 页 。
对于 2 ， 需要 程序 自己管理 。 比如 GC ， 内存池 。
但 上面的说法 也有一点问题， 操作系统（虚拟内存） 也不能 整理 数据层面 的 碎片， 因为 虚拟内存 管理的是 虚拟页 和 物理页 之间的 对应关系， 并没有细化到 虚拟地址 和 物理页 之间的 对应关系， 所以 虚拟内存 也不能 整理 数据层面 的 碎片， 上面说的 “将 多个页 上的 零碎 的 数据 整理 到 一个 页” 这是 不能 做到的 。
操作系统（虚拟内存） 只能 删除 空页（没有数据在用 的 页） 。
而 只要 页上还有 数据 在用， 那么， 即使 数据 占用的空间 很小， 这个页也不能被删除 。
所以， 从这个角度来看， 如果 程序 产生了 很多的 碎片， 那么可能导致 操作系统（虚拟内存） 频繁 的 载入载出 页 。
堆 在 计算机系统结构 里的 地位 等同于 虚拟内存 和 文件系统 。