我主要使用 O(1) 小块内存管理器 (SBMM)。基本上它是这样工作的:
1) 它从操作系统分配更大的超级块,并将开始+结束地址作为一个范围进行跟踪。SuperBlock 的大小是可调的,但 1MB 是一个相当不错的大小。
2) 超级块被分成块(大小也可调节……4K-64K 好,具体取决于您的应用程序)。这些块中的每一个都处理特定大小的分配,并将块中的所有项目存储为单链表。当你分配一个 SuperBlock 时,你会创建一个 Free Blocks 的链表。
3) 分配一个项目意味着 A) 检查是否有一个带有空闲项目的块处理该大小 - 如果没有,则从超级块分配一个新块。B) 从块的空闲列表中删除该项目。
4) 通过地址释放项目意味着 A) 找到包含地址的超级块 (*) B) 在超级块中找到块(减去超级块的起始地址并除以块大小) C) 将项目推回到块的空闲项目列表中。
正如我所说,这个 SBMM 非常快,因为它以 O(1) 的性能 (*) 运行。在我实现的版本中,我使用了一个 AtomicSList(类似于 Windows 中的 SLIST),因此它不仅是 O(1) 性能,而且在实现中还有 ThreadSafe 和 LockFree。如果您愿意,您实际上可以使用 Win32 SLIST 来实现该算法。
有趣的是,从 SuperBlocks 分配 Blocks 或从 Blocks 分配项目的算法导致几乎相同的代码(它们都是 O(1) 的空闲列表分配)。
(*) SuperBlocks 排列在一个范围图中,平均性能为 O(1)(但在 N 是 SuperBlocks 数量的最坏情况下可能存在 O(Lg N))。范围图的宽度取决于大致了解您需要多少内存才能获得 O(1) 性能。如果你过冲,你会浪费一点内存,但仍然可以获得 O(1) 性能。如果您低于目标,您将接近 O(Lg N) 性能,但 N 用于 SuperBlock 计数 - 而不是项目计数。由于 SuperBlock 计数与 Item 计数相比非常低(在我的代码中大约是 20 个二进制数量级),因此它不像分配器的其余部分那么重要。