我有一个非常大的(在运行时固定,大约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 回答
Boost.Interprocess似乎有一个整洁的managed memory-mapped files实现,其条款类似于malloc / free但是对于映射文件(即你有一个适当大的内存映射文件的句柄,你可以要求库子分配一个未使用的部分某事物的文件,如数组) . 从文档:
你能负担多少个mmap的区域?如果128可以,那么我创建了128个区域,这些区域对应于阵列的所有可能大小 . 理想情况下,每个区域的免费条目链表 . 在这种情况下,您将获得每个区域的固定记录大小 . 并且将数组从N增加到N 1是将数据从区域[N]移动到区域[N 1]的操作(如果N 1的空条目的链表是空的)或者在空插槽中移动不 . 对于区域[N],删除的插槽将添加到其空闲条目列表中
更新:链表可以嵌入主结构中 . 因此,不需要额外的分配,每个可能的记录(从大小1到128)内的第一个字段(int)可以是下一个空闲条目的索引 . 对于已分配的条目,它始终为void(0xffffffff),但如果条目是空闲的,则此索引将成为相应链接链的成员 .
我设计并最终采用了一种内存分配算法,该算法符合我的要求,O(1)分摊,非常少的碎片和非常小的开销 . 随意评论,我会在有机会时详细说明 .