64 位系统的广泛普及为简化编程提供了机会。通过利用大型虚拟地址和内存映射文件，我们将编程和文件持久化结合成一个单一的活动。当需要持久化和共享大型复杂数据结构时，这简化了编程。它还提高了数据访问和共享的效率，因为多个程序可以直接从单个实际页面副本访问数据（就地操作）。这消除了通过多层缓冲复制数据的需要。当所有程序在相同的虚拟地址共享数据时，内核有机会管理内存映射，以避免别名并在应用程序之间共享 MMU 资源。

作为概念验证，我有一个小型用户库，我称之为 SPHDE（共享持久堆/数据环境）。该库管理应用程序地址空间的一部分，以提供持久和共享存储块。该库还提供了一些锁定原语和一些“实用对象”，这些对象提供更细粒度的存储分配和索引。

作为演示，我编写了一个千兆像素 Mandelbrot (GTK2) GUI 程序。该程序计算 Mandelbrot 集合中的每个点一次，并将结果图像作为四叉树保存在 SPHDE 存储中。此四叉树表示可以由程序的多个实例共享和显示。程序实例可以合作填充下一个细节层次。

系统设计和编程模型（最初）是由管理稀缺资源的需求驱动的。在编程的早期，地址空间和物理内存都很小。IO 子系统演变为管理串行介质（如磁带和穿孔卡片）的缓冲。即使随机访问磁盘和虚拟内存的引入也没有改变基本范式。我们今天使用和教授的编程范式早已超越了导致它们的原始稀缺性。编程与持久数据的分离就是一个典型的例子。它在编程工作和运行时执行中都造成了效率低下。

随着 64 位微处理器的普及，最初的（寻址/内存）稀缺性已不复存在。我们可以利用虚拟内存直接访问和共享大型数据结构，使用“就地操作”和“隐式持久性”模式。这简化了编程，因为任何数据结构都因其分配位置而具有隐式持久性。这提高了操作效率，因为它消除了缓冲管理层，并且操作系统有更多机会共享单个物理副本。通过消除地址别名和利用硬件功能（如大页），还有更多机会提高地址转换效率。

以前有人尝试统一编程和持久性。持久性框架比比皆是，但它们只是在 IO 子系统堆栈的顶部添加了缓冲层和数据转换。为了在编程工作中获得适度的减少，操作效率会降低。

或者，单级存储已成为多年的研究主题。尽管该技术有效（简化了编程和数据效率），但对专用硬件或独特操作系统环境的要求限制了其接受度。

随着 64 位微处理器的广泛普及和标准化的 POSIX 内存管理 API，这种情况再次发生变化。小型运行时库的添加使敢于冒险的程序员可以在众多操作系统和 64 位硬件平台上使用就地操作和隐式持久性。这种混合单级存储方法允许逐步探索和采用新的编程范式。

简单的内存映射文件是不够的。我们需要一个关于如何管理地址空间和后备文件的设计。该设计应在虚拟（地址空间）和物理（实际内存和磁盘空间）资源的管理中平衡简单性和效率。

以下是我认为在设计中应包含的一些原则。运行时应该易于使用，并与 UNIX 编程和 POSIX API 兼容。它应该使用现有应用程序中通常不使用的资源（地址空间）。它应该像一个大型共享持久堆 (SPH) 一样出现在程序中。访问 SPH 中的数据应使用标准的 C 指针语义。访问 SPH 中的数据的设置应为最小。该设计演变为区域、存储、段和块的概念，所有这些都具有二次幂大小。

区域只是应用程序希望运行时代表其管理的虚拟地址范围。该区域应位于应用程序通常不使用的虚拟地址范围内。我们希望确保该区域不干扰（本地临时）堆和动态库的正常程序使用。在 Linux 上，这意味着 TASK_UNMAPPED_BASE 之上和主堆栈之下的区域。在堆栈下方和 TASK_UNMAPPED_BASE 之上留出大量空间仍然允许使用程序地址空间的一半用于 SPH。

接下来，我们需要选择段大小。段是分配后备文件并将这些文件内存映射到区域中的单位大小。这应该足够大，以便我们不会频繁进行内核调用，并且足够小，以便我们不会浪费文件空间。

存储是一个目录，其中包含一个或多个用于支持 SPH 段的文件。一个系统可以通过在不同的目录中分配后备文件来拥有多个 SPH 存储。目前（也为了保持简单），一个程序一次只能绑定到一个区域/存储。

最后，块是 SPH 区域内空间分配的单位。它的大小通常介于页面和段之间，但这不是硬性限制。唯一的硬性限制是块适合当时的剩余空间。如果将块分配给当前未分配后备文件的 SPH 区域的一部分，则 SPH 运行时将隐式地在与该区域关联的存储目录中创建文件。

为了整体简洁性，我们对块和段使用二次幂大小。这允许使用二次幂伙伴系统来跟踪 SPH 存储的各个方面。伙伴系统减少了碎片，并简化了在释放较小块时将它们重新组合成较大块的过程。

我们需要一些底层实用程序函数来帮助管理伙伴列表。首先，我们需要一个简单的堆管理器来为较小的控制块和列表子分配块。列表需要排序并且将被频繁搜索，因此我们使用简单的二叉树。堆管理器和二叉树的算法可以在 Donald E. Knuth 的 The Art of Computer Programming（参见“资源”）中找到。

最后，我们需要一个地方来存储和维护此信息。锚块是区域中的第一个块。锚块以块头开始，其中包括签名字（初始化为特殊值的醒目字）、类型信息、指向本地空闲列表（堆）开头的指针以及一组用于管理 SPH 区域中空间的各种二叉树的指针。锚块的其余部分被初始化为空闲堆空间。此内部堆用于分配二叉树所需的其他节点以及管理 SPH 区域所需的任何其他内部控制块。

在 SPH 区域初始化之后，我们主要有一个空区域，其中包含从该段分配的一个段（存储目录中的后备文件）和一个块（锚块）。各种列表已初始化以描述此状态。例如，区域空闲列表和已用列表包含区域的未分配（无后备文件）和已分配（有后备文件）部分的条目。锚块的条目被添加到“已用”列表。 “未提交”列表包含第一个段的当前未使用部分的条目。并且，空闲列表为空。现在我们准备分配更多块。

我们选择一个基于哈希表的锁管理器，使用虚拟地址作为锁 ID。SPH 中数据的地址是唯一的，并且可以在哈希表中快速找到活动锁。

锁表的存储必须是共享的但不是持久的，因此我们为此分配 IPC 共享内存。此内存使用块头和关联的堆进行初始化，用于为锁哈希表和锁列表分配存储。还分配了 IPC 信号量，并用于阻止等待争用锁的线程。

到目前为止，我们有共享持久存储块和一个基于地址的锁管理器。块对于存储大型统一数组很有用，但对于复杂结构（如链接列表和树）来说使用起来很笨拙。SPH 运行时包含实用对象，这些对象分配和管理块，用于更细粒度的分配以及复杂的列表和树。

实用对象都以块头开始，并为内部堆（使用与锚块相同的堆管理器）提供配置。使用相同的签名字，但每个实用对象都有一个唯一的类型。类型值定义了一个简单的类型系统，用于运行时检查。签名字以及块都是二次幂大小的事实简化了从块内任何地址查找任何实用对象的块头的过程。这是支持稍后讨论的 new-near 分配方案的技巧。

最简单的实用对象是 SPHSimpleStack。SimpleHeap 只是一个块头和内部堆。CompoundHeap 是一个堆管理器，用于分配 SimpleHeaps。块头将多个 CompoundHeap 块链接在一起，形成一个可扩展的 CompoundHeap。这种“堆的堆”结构与“new-near”机制相结合，对于维护大型复杂列表和树结构的引用局部性非常有用。

CompoundHeap 是 SPHStringBTree、SPHIndex 和 SPHContext 实用对象的框架（可以认为是超类）。SimpleHeap 是 SPHStringBTree 和 SPHIndex 内部 BTree 节点的框架。SPHStringBTree 将字符串（名称）映射到地址。SPHIndex 将任意二进制值映射到地址。SPHContext 定义一个或多个字符串与地址之间的双向映射。这些实用对象对于创建命名结构和内容可寻址内存非常有用。

我需要对共享持久堆运行时进行测试，并认为存储和处理大型图像会很有趣。在之前的个人项目中，我实现了一个快速 Mandelbrot 分形（参见“资源”）显示，该显示基于将图像分成象限并将图像存储在四叉树结构中。Mandelbrot 集合很有趣，因为它具有“自相似性”并且显示细节和任何缩放因子。

该程序可以在 Mandelbrot 集合的彩色渲染图上平移和缩放，其中图像的大部分是预先计算并存储在四叉树中的。该算法是增量的，因此细节是根据需要（对于当前显示）计算并添加到四叉树中的。

图 1. 轮廓化的带有四叉树的 Mandelbrot 集合

图 2. 轮廓化的带有四叉树的 8192X 缩放

当时，我没有好的方法来存储生成的四叉树以供以后使用。我确实编写了递归流代码来将四叉树的扁平化表示形式写入/读取到文件。但是，随着四叉树图像累积细节，速度明显减慢。此外，我最终得到了多个文件，其中包含 Mandelbrot 集合不同区域的预先计算的细节，但没有好的方法将它们合并为单个高分辨率图像。在这一点上，Mandelbrot 项目被搁置了。

后来，当我在 SPHDE 项目上工作并试图想出一个好的演示时，我想起了四叉树 Mandelbrot 项目。困难的部分是将原始 Mandelbrot 程序从 Borland OWL 转换为 Linux 和 GTK2。实际转换为使用 SPHDE 要容易得多。

首先，我在 main 的入口和出口处添加了 SPHJoinRegion 和 SPHCleanUp 调用。然后，我添加了代码来处理首次设置。这涉及到分配一个控制块来锚定四叉树，并创建一个扩展的 SPHCompoundHeap 来管理四叉树的存储。程序后续使用只需要获取此控制的地址。此指针可以从锚块头中的空闲槽中存储和检索。

下一步是更改四叉树算法以使用 SPHDE 存储。这只是因为希望在四叉树本身内保持良好的引用局部性而略微复杂化。SPHCompoundHeap 分配 SPHSimpleHeaps，从中分配四叉树节点。从同一个 SPHSimpleHeap 分配相邻的四叉树节点可确保内存和后备文件中的物理局部性。这最大限度地减少了显示整个 Mandelbrot 集合（四叉树的最顶层部分）或缩放到集合的任何部分所需的页面数。

简单的调用

node = (TQuadTree*) SPHSimpleHeapNearAlloc (near, sizeof (TQuadTree));

始终会尝试从包含最近现有四叉树节点的 SimpleHeap 中分配。如果此分配失败，我们需要找到另一个具有可用空间的 SimpleHeap 或调用 SPHCompoundHeapAlloc 来分配另一个 SimpleHeap

if (!node)
  {
    temp1 = SASCompoundHeapAlloc (QuadBlockPtr->compoundHeap);	
    if (temp1)
      {
       node = (TQuadTree *)
               SASSimpleHeapAlloc (temp1, sizeof (TQuadTree));
         lastAlloc = temp1;
      }
  }

最近分配的 SimpleHeaps 和最近释放节点的 SimpleHeaps 的简单缓存用于保持四叉树在 SPHCompoundHeap 管理的存储中相对密集。所有这些逻辑都包含在 100 行代码中。

最后，我们需要确保程序的多个实例可以安全地共享和更新四叉树。这需要在任何可能修改四叉树节点的代码周围添加 SPHLock/SPHUnlock 调用。当前算法中只有四个这样的位置。实用对象（SimpleHeap、CompondHeap 等）在内部使用适当的锁，以确保在共享环境中行为一致。

结果是一个可以计算和存储千兆像素或更大图像的程序。生成千兆像素 (32768x32768) Mandelbrot 图像大约需要五分钟（Apple G5 dual-2.3GHz PowerPC）。一旦生成千兆像素四叉树，退出并重新启动几乎是瞬间完成的（24 毫秒显示 512x512 像素图像）。在预先计算的四叉树周围平移和缩放也很快（12-20 毫秒）。由于需要大量计算，缩放到超出当前预先计算的集合的深度会变慢（200-500 毫秒）。一旦计算和存储了一个区域，后续显示又会很快（12-20 毫秒）。

SPHDE 运行时和 Mandelbrot 演示程序在 32 位和 64 位 Linux 上运行，包括 PowerPC、i386 和 x86_64 平台。32 位系统可以支持 1-2GB 区域，这足以存储千兆像素 Mandelbrot 四叉树（约 313MB）。更大的（万亿像素）图像将需要 64 位系统允许的大区域。使用最新的 Linux 内核，PowerPC64 可以支持 8TB 范围内的区域。X86_64 平台支持 128TB 地址空间和 64TB 区域。这对于一些有趣的项目来说绰绰有余。