• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

漫谈C++的内存堆实现原理

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

如果我来设计 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 , 则可以考虑 释放 这个 堆表空


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c#为字段设置默认值,以及构造函数初始化List对象。发布时间:2022-07-13
下一篇:
C#改变控制台背景颜色发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap