我认为这是一个非常普遍的问题。让我举个例子。
我有一个文件,其中包含很多行(例如一百万行),每一行都是以下形式:首先是一个数字 X
,然后是一个长度为 X
。
现在我想读取文件并存储所有字符串(无论出于何种原因)。通常,我会做的是:对于每一行,我读取长度 X
,并使用 malloc
(在 C 中)或 new
(在 C++ 中) 分配X
个字节,然后读取字符串。
我不喜欢这种方法的原因是:大多数字符串可能都很短,比如不到 8 个字节。那样的话,按照我的理解,无论是时间上还是空间上,分配都会非常浪费。
(这里的第一个问题:我的理解是否正确,分配小块内存是一种浪费?)
我考虑过以下优化:每次我分配一个大块,比如 1024 字节,每当需要一小块时,就从大块上切下来。这种方法的问题是,释放几乎不可能......
这听起来像是我想自己做内存管理......但是,我还是想知道是否有更好的方法?如果需要,我不介意使用一些数据结构来进行管理。
如果您有一些只在有条件的情况下有效的好主意(例如,知道大多数作品都很小),我也很乐意知道。
最佳答案
进行内存分配的“自然”方式是确保每个内存块至少足够大以包含一个指针和一个大小,或某种足以维护空闲节点结构的类似簿记。细节各不相同,但您可以通过查看在进行小额分配时从分配器返回的实际地址来实验性地观察开销。
这就是小分配“浪费”的意义。实际上,对于大多数 C 或 C++ 实现,所有 block 都四舍五入为 2 的某个幂的倍数(幂取决于分配器,有时取决于分配的数量级大小)。所以所有分配都是浪费,但按比例来说,如果将大量 1 字节和 2 字节分配填充到 16 字节,比将大量 113 字节和 114 字节分配填充到 128 字节,浪费更多。
如果您愿意取消释放和重用单个分配的能力(这很好,例如,如果您计划在担心此文件的内容后一起释放所有分配) 那么当然,您可以以更紧凑的方式分配许多小字符串。例如,将它们全部首尾相连地放在一个或几个大分配中,每个字符串都以 nul 结尾,并处理指向每个字符串第一个字节的指针。每个字符串的开销是 1 个或 0 个字节,具体取决于您如何看待 nul。如果您只是用 nul 字节覆盖换行符,这在将文件拆分为多行的情况下可以特别巧妙地工作。显然,您无需介意每行的换行符已被删除!
如果您需要释放和重新使用,并且您知道所有 分配的大小相同,那么您可以从簿记中删除大小,并编写您自己的分配器 (或者,在实践中,找到一个您满意的现有池分配器)。最小分配大小可以是一个指针。但是,如果所有字符串都小于指针的大小,那么这只是一个轻松的胜利,“大多数”并不是那么简单。
关于c++ - 动态分配许多小块内存,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31639593/