3

我有一个非常大（在运行时固定，大约 10 - 3000 万）的数组。每个数组包含 0 到 128 个元素，每个元素为 6 个字节。

我需要将所有数组存储在 mmap 内存中（所以我不能使用 malloc），并且数组需要能够动态增长（最多 128 个元素，并且数组永远不会缩小）。

我实现了一种简单的方法，即使用一个 int 数组来表示 mmap 内存中每个 6 字节块的状态。偏移量处的 0xffffffff 值表示 mmap 内存中的相应偏移量是空闲的，任何其他值都是数组的 id（在我当前的实现中对块进行碎片整理需要它，没有就不能移动块知道他们的数组的 id 来更新其他数据结构）。在分配时，当数组超出其分配时，它会简单地迭代，直到找到足够的空闲块，并在相应的偏移量处插入。

这就是分配数组和 mmap 内存的样子，有点：

| 0xffffffff | 0xfffffff |    1234    |    1234    | 0xffffffff | ...
-----------------------------------------------------------------
|    free    |   free    |array1234[0]|array1234[1]|    free    | ...


这种方法虽然具有offset of furthest used block in mmap'ed memory x 4（4 字节 ber int）的内存开销。

对于这种特定情况，有什么更好的方法？

我对此的理想要求是：

  • 内存开销（任何分配表 + 未使用空间）<= 每个元素 1.5 位 + 每个数组 4*6 字节
  • O(1) 数组的分配和增长
4

3 回答 3

1

Boost.Interprocess似乎有一个托管内存映射文件的简洁实现，其规定类似于 malloc/free 但用于映射文件（即您有一个适当大的内存映射文件的句柄，您可以要求库子- 为某些东西（例如数组）分配文件的未使用部分）。从文档中：

Boost.Interprocess 提供了一些基本类来创建共享内存对象和文件映射，并将这些可映射类映射到进程的地址空间。

然而，管理这些内存段对于非平凡的任务来说并不容易。映射区域是固定长度的内存缓冲区，动态创建和销毁任何类型的对象需要大量工作，因为它需要编写内存管理算法来分配该段的部分。很多时候，我们还希望将名称与在共享内存中创建的对象关联起来，以便所有进程都可以使用该名称找到对象。

Boost.Interprocess 提供 4 个托管内存段类：

  • 管理共享内存映射区域（basic_managed_shared_memory 类）。
  • 管理内存映射文件（basic_managed_mapped_file）。
  • 管理一个堆分配的（operator new）内存缓冲区（basic_managed_heap_memory 类）。
  • 管理用户提供的固定大小缓冲区（basic_managed_external_buffer 类）。

托管内存段最重要的服务是：

  • 动态分配部分内存段。
  • 在内存段中构造 C++ 对象。这些对象可以是匿名的，或者我们可以为它们关联一个名称。
  • 搜索命名对象的能力。
  • 许多特性的定制：内存分配算法、索引类型或字符类型。
  • 原子构造和破坏，因此如果段在两个进程之间共享，则不可能创建两个具有相同名称的对象，从而简化了同步。
于 2012-10-19T19:54:29.570 回答
1

你能负担得起多少个映射区域？如果 128 没问题，那么我会创建 128 个区域，这些区域对应于您的数组的所有可能大小。理想情况下，每个区域都有一个免费条目的链接列表。在这种情况下，您将获得每个区域的固定大小的记录。并且将数组从 N 增长到 N + 1 是将数据从 area[N] 移动到最后的 area[N + 1] 的操作（如果 N + 1 的空条目的链表为空）或在如果没有空槽。对于 area[N]，删除的插槽被添加到其空闲条目列表中

更新：链表可以嵌入到主要结构中。因此不需要额外的分配，每个可能的记录（从大小 1 到 128）中的第一个字段 (int) 可以是下一个空闲条目的索引。对于分配的条目，它总是无效的（0xffffffff），但如果一个条目是空闲的，那么这个索引就成为相应链接链的成员。

于 2012-10-20T05:17:44.110 回答
-1

我设计并最终采用了一种几乎符合我要求的内存分配算法，O(1) 摊销，很少的碎片和很少的开销。随时发表评论，我会在有机会时详细说明。

于 2012-10-20T23:20:11.837 回答