高效流失的高效堆管理器，微小的分配？

6 回答

• 6

  可以构建一个对于大小相同的对象非常有效的堆管理器 . 您可以为所需的每个对象大小创建其中一个堆，或者如果您不介意使用一些空间，则为16字节对象创建一个，为32创建一个，为64创建一个 . 最大开销将是33字节分配31个字节（将在64个块大小的堆上） .

  回复于 2024-04-28T17:22:05+08:00
• 0

  为了扩展Greg Hewgill所说的，实现超高效固定大小堆的一种方法是：

  • 将大缓冲区拆分为节点 . 节点大小必须至少为sizeof（void *） .

  • 将它们组合成一个单链表（"free list"），使用每个空闲节点的第一个sizeof（void *）字节作为链接指针 . 分配的节点不需要链接指针，因此每节点开销为0 .

  • 通过删除列表的头部并返回它来分配（2个加载，1个存储） .

  • 通过插入列表的头部免费（1个加载，2个商店） .

  显然，第3步还必须检查列表是否为空，如果是，那么做一堆新的大缓冲区（或失败） .

  正如Greg D和hazzen所说，更高效的是通过递增或递减指针（1个加载，1个存储）进行分配，而不提供释放单个节点的方法 .

  编辑：在这两种情况下，free都可以处理复杂的“我在常规堆管理器上传递的任何更大的东西”，这是因为你在免费调用中获得了大小 . 否则，您将查看一个标志（每个节点的开销可能为4个字节），或者在您使用的缓冲区的某种记录中查找 .

  回复于 2024-04-28T17:22:05+08:00
• 0

  答案可能取决于这些对象的生命周期模式 . 如果对象都是在你继续进行实例化，然后一次性全部删除的话，那么创建一个非常简单的堆管理器可能是有意义的，它通过简单地递增指针来分配内存 . 然后，当你完成后，吹掉整个堆 .

  Raymond Chen做了一个可能有助于激励你的interesting post . :)

  回复于 2024-04-28T17:22:05+08:00
• 3

  我喜欢onebyones的回答 .

  对于固定大小的堆集，您可能还会考虑buddy system .

  回复于 2024-04-28T17:22:05+08:00
• 1

  如果在进行下一轮分配之前分配，使用和释放了一堆内存，我建议使用最简单的分配器：

  typedef struct _allocator {
      void* buffer;
      int start;
      int max;
  } allocator;
  
  void init_allocator(size_t size, allocator* alloc) {
      alloc->buffer = malloc(size);
      alloc->start = 0;
      alloc->max = size;
  }
  
  void* allocator_malloc(allocator* alloc, size_t amount) {
      if (alloc->max - alloc->start < 0) return NULL;
      void* mem = alloc->buffer + alloc->start;
      alloc->start += bytes;
      return mem;
  }
  
  void allocator_free(allocator* alloc) {
      alloc->start = 0;
  }
  

  回复于 2024-04-28T17:22:05+08:00
• 6

  我主要使用O（1）小块内存管理器（SBMM） . 基本上它以这种方式工作：

  1）它从OS分配更大的SuperBlock并跟踪Start End Addresses作为范围 . SuperBlock的大小可调，但1MB的尺寸相当不错 .

  2）SuperBlocks被分成块（也可以调整大小...... 4K-64K很好，具体取决于你的应用程序） . 这些块中的每一个都处理特定大小的分配，并将块中的所有项目存储为单个链接列表 . 分配超级块时，可以创建自由块的链接列表 .

  3）分配项目意味着A）检查是否存在具有处理该大小的免费项目的块 - 如果没有，则从超级块分配新块 . B）从块的空闲列表中删除项目 .

  4）通过地址释放项目意味着A）查找包含地址的超级块（*）B）在超级块中查找块（减去超级块开始地址并除以块大小）C）将块推回块的空闲项目列表 .

  正如我所说，这个SBMM非常快，因为它以O（1）性能（*）运行 . 在我实现的版本中，我使用了AtomicSList（类似于Windows中的SLIST），因此在实现中不仅有O（1）性能，还有ThreadSafe和LockFree . 如果需要，您可以使用Win32 SLIST实际实现该算法至 .

  有趣的是，用于从超级块分配块或从块中分配块的算法导致几乎相同的代码（它们都是自由列表中的O（1）分配） .

  （*）超级块被安排在具有O（1）平均性能的范围映射中（但是对于最坏情况，潜在的O（Lg N），其中N是超级块的数量） . 范围映射的宽度取决于大致了解您需要多少内存才能获得O（1）性能 . 如果你超调，你会浪费一些内存，但仍然可以获得O（1）性能 . 如果你下冲，你将接近O（Lg N）表现，但N是超级块数 - 而不是项目数 . 由于SuperBlock计数与项目计数相比非常低（在我的代码中大约20个二进制数量级），因此它不像分配器的其余部分那样重要 .

  回复于 2024-04-28T17:22:05+08:00