algorithm - 计算尺寸等级

Question

高性能 malloc 实现通常会实现分离的空闲列表，也就是说，每个更常见（较小）的大小都有自己单独的空闲列表。

对此的第一次尝试可以说，低于某个阈值，大小等级只是大小除以 8，四舍五入。但是实际的实现有更多的细微差别，将识别的大小类排列在指数曲线上（但比每一步简单地加倍更温和），例如http://jemalloc.net/jemalloc.3.html

我试图弄清楚如何在一些这样的曲线上将尺寸转换为尺寸等级。现在，原则上这并不难；有几种方法可以做到这一点。但是要达到加速普通案例的预期目标，它确实需要快速，最好只有几条指令。

进行这种转换的最快方法是什么？

标签： algorithmperformancemalloclanguage-agnosticimplementation

Answer 1

在黑暗时代，当我曾经担心这些事情时，我只是从最小的开始迭代所有可能的尺寸。

这实际上很有意义，因为分配内存强烈意味着实际分配之外的工作——比如初始化和使用该内存——这与分配大小成正比。除了最小的分配之外，在所有分配中，这种开销将淹没您选择大小等级所花费的任何费用。

只有小的真正需要快速。