首页 文章

C堆管理器如何跟踪分配对象的大小?

提问于
浏览
1

我想在堆中分配对象时估计C中的内存消耗 . 我可以用sizeof(object)开始计算并将其四舍五入到最接近的堆块(通常为8个字节) . 但是如果整个分配的块转到分配的对象,当我要求它删除指针时,堆管理器如何告诉对象的大小?

如果堆管理器跟踪每个对象的大小,是否意味着我应该在计算中将每个分配对象的~4个字节添加到堆管理器内部开销的总内存消耗中?或者它是否以更紧凑的形式存储此信息?堆内存分配的额外成本(内存方式)是多少?

我知道我的问题是特定于实现的,但我很欣赏有关gcc(或者可能是libc)等主要实现的堆元数据存储的任何提示 .

1 回答

  • 3

    堆分配器不是免费的 . 每个分配块的成本(无论是大小还是搜索,如果使用查找最佳算法),免费加入块的成本,以及当请求的大小小于返回的块大小时每个块的任何丢失大小 . 在内存碎片方面也存在成本 . 考虑在堆中间放置一个小的1字节分配 . 此时,您不能再返回大于堆的1/2的连续块 - 堆的一半是碎片 . 好的分配者会对上述所有内容进行斗争并尝试最大化所有好处 .

    考虑以下分配系统(在许多掌上游戏设备上用于十多年的许多实际应用 . )

    创建一个主堆,其中每个分配都有一个prev ptr,next ptr,size和可能的其他信息 . 将其舍入为每个条目16个字节 . 在返回实际内存指针之前或之后存储此信息 - 您可以选择,因为每个指针都有优势 . 是的,您在此处分配请求的大小为16个字节 .

    现在只需保留一个指向空闲列表和可能已使用列表的指针 .

    通过在空闲列表上找到足够大的块以供我们使用并将其分成所请求的大小和余数(第一次拟合),或通过搜索整个列表尽可能精确匹配(最佳拟合)来完成分配 . 很简单 .

    释放将当前项目移回自由列表,如果可能,连接彼此相邻的区域 . 你可以看到它如何进入O(n) .

    对于较小的分配,获取单个分配(来自新创建的堆,或来自全局内存),这将是您的单元分配区域 . 将此区域拆分为“块大小”块地址,并将这些地址推送到空闲堆栈 . 分配是从此列表中弹出一个地址 . Freeing只是将分配推回到列表中 - 都是O(1) .

    然后在malloc / new / etc中,检查大小是否在单元大小之内,从单元分配器分配,否则使用O(n)分配器 . 我的研究表明,您可以获得90-95%的分配以适应单位分配器的块大小,而不会出现太多问题 .

    此外,您可以为内存池分配内存块,并在反复使用它们时保留它们 . 一些更大的分配要便宜得多(Unix系统使用这个很多......)

    好处:

    • 所有单位分配都没有外部碎片 .

    • 小分配运行恒定时间 .

    • 可以根据所请求数据的确切大小量身定制更大的分配 .

    缺点:

    • 当您希望内存小于请求的块时,您需要支付内部碎片成本 .

    • 在小块大小之外的许多分配和释放最终会破坏你的记忆 . 这可能导致各种不愉快 . 这可以通过操作系统帮助或小心分配/免费订单来管理 .

    • 一旦获得1000个大额分配,就会有CPU价格 . 也可以使用平板/多个堆来解决这个问题 .

    有很多很多方案,但这个很简单,虽然已经在商业应用程序中使用了很长时间,所以我想从这里开始 .

相关问题