首页 文章

链接列表 . 在哪里分配以及如何应对碎片？

提问于
浏览 次
2

  • 位置
    堆中的

  • ，碎片化（每个节点的malloc） - 以几种不同的方式有效（缓慢分配，慢访问，内存碎片）

  • 在堆中，在一个大块中 - 当需要重新分配时，数据结构获得的所有灵活性都会丢失
    堆栈中的

    • 堆栈的大小往往相当有限，因此根本不建议在其上分配大型结构

它们的巨大优势，即插入O（1），在碎片化内存的环境中看起来相当无用，并且数千次调用内存分配器给我们另外10个字节 .

编辑澄清：
在接受采访时询问了这个问题 . 这不是一个工作场所的问题，所以通常的启发式方法是希望盲目地从一小组标准算法中找出正确的决策，这是不适用的 .

现有的答案和评论提到“malloc不是那么慢”，“malloc部分地与碎片作斗争” . 好的，如果我们使用另一个数据结构，例如C向量的C端口（即 - 分配足够大小的顺序内存，如果数据扩展，重新分配到两倍大的块），所有问题都解决了，但我们松开了快速插入/删除 . 链接列表（分配在哪里？）的任何场景都具有对向量的巨大优势？

c memory-management

5 回答

  • 4

    理想情况下，您的链接列表实现不应使用上述任何一种 . 应该由调用者来分配和销毁内存 . 想想像 sprintf ， fgets 等函数......他们分配任何内存吗？不，这是有原因的：简单 . 想象一下，如果你必须 fgets 从 fgets （或更糟糕的是， fscanf ）得到的一切 . 难道不痛苦吗？尝试开发您的功能以与标准库保持一致 .

    声明 listnode_alloc 函数可能会有所帮助，但这只会包装 malloc 和 listnode_init 函数 . 考虑 realloc 如何处理 NULL 输入...

    回复于
  • 0

    这听起来像是过早的优化 . 我认为正确的方法是：

    • 使用最简单的实现;

    • 简介整个计划 .

    • 如果分析显示列表存在性能问题，请考虑替代实现（包括备用分配器） .

    回复于
  • 0

    如果您担心标准分配器无法有效处理专用的10字节分配，请编写一个自定义分配器，从标准（ malloc() ）分配器中获取大块内存，并有效地发送小项 . 当你在最初的大块中耗尽内存时，你不应该重新分配;你应该分配一个新的（额外的）大块并从中分配 . 您可以决定如何处理释放的内存 . 您可以简单地忽略版本，直到您在使用列表处理结束时释放所有大块 . 或者你可以通过跟踪大块的释放内存来使生活复杂化 . 这样可以减少整体内存使用量，但最初编写起来会更复杂 .

    另一方面，您应该意识到过早优化的风险 . 你有没有测量过性能？鉴于我在你最近的问题中所看到的，你应该坚持使用 malloc() 而不是尝试编写你自己的分配器（还） .

    回复于
  • 0

    这可能不是确切的解决方案，而是另一种方法

    • 自己处理碎片 .

    • 分配大量内存

    • 为每个新节点提供此节点的内存，直到有空闲内存 .

    • 如果使用了池，则分配另一个池并使用它来分配新块

    然而，这说起来容易做起来难 . 你可能会遇到很多问题 .

    所以，会建议让这种优化到 malloc 及相关功能 .

    堆栈分配不是一个可行的选择 . 你不能从堆栈中 malloc . 您将不得不在某些功能中预先分配大块缓冲区 . 在这种情况下，数组比链表更好 .

    回复于
  • 7

    好吧，内存分配策略可能因内存碎片，成千上万的系统调用等而有所不同，这就是使用O的原因！ ;-)

    回复于

相关问题