algorithm - 计算尺码等级

Question

高性能 malloc 实现通常实现隔离的空闲列表，即每个更常见(较小)的大小都有自己单独的空闲列表。

第一次尝试可能会说，低于某个阈值，尺寸类别只是尺寸除以 8，向上舍入。但实际的实现有更多的细微差别，将识别的尺寸类别排列在类似指数曲线的东西上(但比简单地在每一步加倍更温和)，例如http://jemalloc.net/jemalloc.3.html

我正在尝试找出如何将某个此类曲线上的尺寸转换为尺寸类别。现在，原则上这并不困难；有几种方法可以做到这一点。但为了达到加速常见情况的预期目标，它确实需要很快，最好只有几条指令。

完成此转换的最快方法是什么？

Answer 1

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

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

只有小东西才真正需要快。