首页 文章

在mmap内存中有效分配动态数组

提问于
浏览
3

我有一个非常大的(在运行时固定,大约1000万到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)数组的分配和增长

3 回答

  • 1

    Boost.Interprocess似乎有一个整洁的managed memory-mapped files实现,其条款类似于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对象 . 这些对象可以是匿名的,也可以将名称与它们关联起来 . 搜索命名对象的功能 . 自定义许多功能:内存分配算法,索引类型或字符类型 . 原子构造和析构,以便如果在两个进程之间共享段,则无法创建与同一名称关联的两个对象,从而简化了同步 .

  • 1

    你能负担多少个mmap的区域?如果128可以,那么我创建了128个区域,这些区域对应于阵列的所有可能大小 . 理想情况下,每个区域的免费条目链表 . 在这种情况下,您将获得每个区域的固定记录大小 . 并且将数组从N增加到N 1是将数据从区域[N]移动到区域[N 1]的操作(如果N 1的空条目的链表是空的)或者在空插槽中移动不 . 对于区域[N],删除的插槽将添加到其空闲条目列表中

    更新:链表可以嵌入主结构中 . 因此,不需要额外的分配,每个可能的记录(从大小1到128)内的第一个字段(int)可以是下一个空闲条目的索引 . 对于已分配的条目,它始终为void(0xffffffff),但如果条目是空闲的,则此索引将成为相应链接链的成员 .

  • 0

    我设计并最终采用了一种内存分配算法,该算法符合我的要求,O(1)分摊,非常少的碎片和非常小的开销 . 随意评论,我会在有机会时详细说明 .

相关问题