计算尺寸等级-解网

问：

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

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

我正在尝试弄清楚如何在一些这样的曲线上将尺寸转换为尺寸类。现在，原则上这并不困难;有几种方法可以做到这一点。但要达到加快常见情况的预期目标，确实需要快速，最好只有几条指令。

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

算法性能 malloc 语言无关的实现

评论

答：

4赞 Matt Timmermans 10/30/2021 #1

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

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

只有小的才真正需要快速。

1赞 Surt 10/31/2021 #2

假设您想使用两种尺寸和一半尺寸的所有幂，即 8、12、16、24、32、48、64 等。4096.

检查该值是否小于或等于 4096，我任意选择该值作为此示例的最高可分配值。

取结构的大小，然后使用最高设置位乘以 2，如果还设置了下一个位，则添加 1，并且您将索引放入大小列表中，如果该值高于两个位给出的值，则再添加 1。应该是 5-6 ASM 指令

所以 26 是 16+8+2 位是 4,3,1 4*2 + 1 + 1，所以为 10 字节列表选择第 32 个索引。

您的系统可能需要一些最小分配大小。

此外，如果您要进行大量分配，请考虑使用一些程序专用的池分配器，并从系统分配器进行备份。

上一个：将小数组排序为大型排序数组

下一个：快速饱和整数转换？