时间戳

首页 > 解决方案 > 使用 malloc 和 realloc 来使用 C 结构，但占用的内存空间是我计算的两倍

c - 使用 malloc 和 realloc 来使用 C 结构，但占用的内存空间是我计算的两倍

问题描述

我使用C struct 来构建前缀树，即Trie。我想用它来存储很多号码列表，以获取给定路径中的下一个可能的号码。（例如，我有 [10, 15, 17] 和 [10, 15, 18]，那么 [10,15] 的下一个可能数量是 17,18。）我遇到的问题是关于内存使用的，我的每个 struct Trie 节点只占用 12 字节（我用 sizeof() 来检查），总共有 8.3 亿个节点，应该占用 8.3 亿 * 12 字节 = 10G 内存使用，但实际上我使用了 20G 内存，我想要将内存使用减少到10G。

我使用 unsigned short 来存储每个节点的数据，unsignedn short n_child 来存储这个节点有多少孩子，一个指向他的孩子列表开始位置的指针，并为新节点重新分配 12 字节的内存空间。

#pragma  pack(2)
typedef struct trie_node{
    unsigned short data;
    unsigned short n_child;
    struct trie_node * children;
} Trie;

当我必须添加一个新孩子时，我使用：

this_node->n_child = this_node->n_child + 1;
this_node->children = (Trie *)realloc(this_node->children, this_node->n_child * sizeof(Trie));

我想知道为什么内存使用量比计算的大，我可以减少内存使用量。

标签： cmemory

解决方案

这里的问题是您分配了非常小的数据块（大小struct trie_node非常小，并且大约是malloc()库管理您所做的不同分配所需的数据大小。realloc()每次添加单个想象一下这个场景，你有一个块，比如说10节点，你添加一个，从 10 重新分配到 11，但是由于你分配了很多不同的数组，你没有空间来容纳你的洞最后一个数组，因此内存管理器必须为 10 个节点创建一个可用空间，并分配另一个空间或 11 个（其他地方）。

如果您有幸拥有另一个具有 9 个节点并增长到 10 个的块，那么您可以重用最后一个洞......但通常情况并非如此，在另一个需要从 9 增长之前，该洞被（部分）重用到 10. 这会导致动态内存区域有很多碎片。

碎片以及您使用非常小的节点结构这一事实正在产生 100% 的已用内存开销。

您可以通过多种方式缓解这种情况：

  • 不要realloc()一个。例如，只需将其加倍。这有两个优点：首先，块大小只有 2 的幂，因此碎片级别要低得多，因为如果只有 2 的幂，则具有有效的 2 幂的概率要容易得多。另一个好的价值是通过添加最后两个使用的大小来增长（如在斐波那契数列中）。

  • 添加指向同级的指针并将树组织为链表...这样您将分配相同大小的所有块（内存管理器在大小相同时最好）但是要小心，您的结构会增加一个指针。你从一侧得到的部分，在另一侧出去。

  • 如果您事先知道节点将拥有的子节点数量的平均值，那么预先分配该平均数量将会很有趣，因为它会使块接近这个固定大小，因此它会更好地管理。

最后，您无法避免一件事，那就是有一些开销，因为除了您的数据之外，内存管理器需要分配元数据来正确管理堆。但是您的分配越大，这些数据的损失就越低，因为内存管理器通常每次分配都需要一定量的数据，并且它不依赖于分配大小。

推荐阅读