分配器的主题经常出现在Internet上：的确，分配器是一种基石，是任何应用程序的核心。 在本系列文章中，我想详细讨论一个非常有趣且杰出的分配器
-JeMalloc ，该分配器由Facebook支持和开发，并用于
仿生[Android] lib C中。在网络上，我找不到任何可以完全揭示此分配器灵魂的细节，这最终影响了无法得出有关JeMalloc在解决特定问题中的适用性的任何结论的可能性。 大量材料问世，为了阅读不费力，我建议从以下基础知识开始：JeMalloc中使用的基本数据结构。
在猫之下，我正在谈论的是
Pairing Heap和
Bitmap Tree ，它们是JeMalloc的基础。 在这个阶段，我还没有涉及
多线程和
细粒度锁定的主题，但是，继续介绍一系列文章，我肯定会告诉您这些事情，因此，实际上会创建各种Exotics，尤其是以下所述的Exotics。
Bitmap_s是树状数据结构，可让您：
- 快速找到给定位序列中的第一个置位/未置位位。
- 在给定的位序列中，更改并获取具有索引i的位的值。
- 该树根据n位序列构建，并具有以下属性：
- 树的基本单位是节点，节点的基本单位是位。 每个节点正好由k位组成。 选择节点的位，以便在给定的计算机上尽可能快速，高效地计算所选位范围上的逻辑运算。 在JeMalloc中，节点由无符号long类型表示。
- 树的高度是按级别测量的，对于n位序列，H = 水平。
- 树的每个级别由一系列序列表示 节点，相当于一个序列 一点。
- 树的最高（根）级别由k位组成，最低的n位组成。
- 级别L的节点的每个位确定级别L-1的子节点的所有位的状态：如果某个位设置为忙，则子节点的所有位也都设置为忙，否则，子节点的位可能具有“忙”和“免费”状态。
用两个数组表示bitmap_t是合理的：第一个数组的维度等于所有树节点的数量-存储树节点，第二个数组的树高维度-存储每个级别起点在树节点数组中的偏移量。 使用这种指定树的方法，根元素可以先走，然后依次走各层的节点。 但是，JeMalloc作者将根元素存储在数组的最后，并且在其前面是基础树级别的节点。
作为说明性示例，采用92位的序列，并且K = 32。 我们假设状态为“空闲”（用一个比特表示），状态“忙”（为零）。 还假设在原始位序列中，索引为1（从零开始，在图中从右到左）的位被设置为繁忙状态。 这样的位序列的bitmap_t如下图所示：
从图中我们可以看到，生成的树只有两个级别。 根级别包含3个单位位，它指示相应位的每个子节点中是否存在空闲位和占用位。 在右下角，您可以在两个数组中看到“树”视图：所有树节点和节点数组中每个级别的偏移量。假设bitmap_t由两个数组（一个数据数组和一个数据数组中的树级偏移量数组）表示，我们描述在给定bitmap_t中查找第一最低有效位的操作：
- 从根节点开始，我们对节点的第一个最低有效位执行搜索操作：为解决此问题，现代处理器提供了可以大大减少搜索时间的特殊指令。 我们将找到的结果保存在FirstSetedBit变量中。
- 在算法的每次迭代中，我们将维护找到的位的位置之和：countOfSettedBits + = FirstSetedBit
- 使用上一步的结果，我们转到该节点的第一个最低有效位的子节点，然后重复上一步。 根据以下简单公式进行转换：
- 该过程一直持续到达到树的最低级别为止。 countOfSettedBits-输入位序列中所需位的数量。
Pairing Heap是类似于堆的树数据结构，使您可以：
- 根据实现的不同，插入时间常数为O（1）且摊销成本为O（log N）或O（1）的元素。
- 至少搜索恒定时间-O（1）
- 合并两个具有恒定时间复杂度的配对堆-O（1）和摊销成本O（log N）或O（1） -取决于实现
- 删除任意元素（尤其是最小元素），其临时复杂度估计值以O（N）为单位 ，摊销的复杂度估计值为O（log N）
更正式地讲，配对堆是具有满足堆属性的专用根的任意树（每个顶点的键不小于/不大于其父键）。
一个典型的配对堆，其中子节点的值小于父节点的值（又名最小配对堆），看起来像这样：
通常，在计算机内存中，配对堆是以完全不同的方式显示的：树的每个节点存储3个指针：
- 指向当前节点最左边的子节点的指针
- 指向节点左侧同级的指针
- 指向节点右兄弟的指针
如果缺少任何指示的节点，则将相应的节点指针无效。
对于上图中显示的堆，我们得到以下表示：
在这里，指向最左边的子节点的指针由红色虚线箭头指示，指向该节点的右兄弟的指针为蓝色，而指向左兄弟的指针为灰色。 实心箭头以树状形式显示“配对堆”表示形式，这对于人是常见的。请注意以下两个事实：
- 在堆的根部始终没有左右兄弟。
- 如果任何节点U具有指向最左侧子节点的非零指针，则该节点将成为U所有子节点的双向链接列表的“ Head”。此列表称为siblingList。
接下来，我们在
Min Pairing-Heap中列出主要运算的算法：
- 将节点插入配对堆：
让我们给出一个配对堆，其中有一个根和一个值{R，V_1}以及一个节点{U，V_2} 。 然后，将U节点插入给定的Pairing Heap中时：
- 如果满足条件V_2 <V_1：U成为堆的新根节点，则将根R“挤出”到其左子节点的位置。 同时，节点R的右兄弟成为其最旧的最左节点，并且指向节点R的最左节点的指针变为零。
- 否则：U成为R的根的最左子节点，而其最老的兄弟成为R的根的最左节点。
- 合并两个配对堆：
给出两个分别具有根和值{R_1，V_1} ， {R_2，V_2}的配对堆。 我们描述了一种将这些堆合并到结果配对堆中的算法：
- 选择根中具有最低值的堆。 让它成为一堆{R_1，V_1}。
- 从选定的堆中“分离”根R_1：为此，我们只需将其指向最左侧子节点的指针为空即可。
- 使用指向根R_1最左侧子节点的新指针，使根R_2成为根。 请注意，从现在开始，R_2失去根状态，并且是结果堆中的普通节点。
- 我们设置节点R_2的右兄弟：使用新值，使旧的指针（在归零之前）指向根R_1的最左子节点，对于R_1，分别更新指向左兄弟的指针。
考虑使用特定示例的合并算法：
在这里，根为“ 4”的堆将与根为“ 1”（1 <4）的堆连接起来，成为其最左侧的子节点。 指向节点'4'的右兄弟的指针以及指向节点'8'的左兄弟的指针被更新。- 除去根（具有最小值的节点）配对堆：
有几种用于从配对堆中删除节点的算法，可以保证对O的复杂性进行摊销估计（对数N）。 我们描述了其中一种，称为多遍算法，并在JeMalloc中使用：
- 我们删除给定堆的根，仅保留其最左侧的子节点。
- 最左边的子节点形成父节点的所有子节点的双链表，在我们的例子中是先前删除的根。 我们将始终遍历此列表，直到将节点视为独立Pairing Heap的根，然后执行将列表的当前元素与下一个元素合并的操作，并将结果放入预先准备的FIFO队列中。
- 现在，FIFO队列已初始化，我们将对其进行迭代，执行将队列的当前元素与下一个元素合并的操作。 合并的结果放在队列的末尾。
- 我们重复上一步，直到队列中剩下一个元素：生成的配对堆。
上述过程的一个很好的例子：
- 删除任意的非根节点配对堆：
将删除的节点视为原始堆的某些子树的根。 首先，按照前面描述的用于删除配对堆的根的算法，删除该子树的根，然后执行将结果树与原始树合并的过程。 - 获取最小的配对堆元素：
只需返回堆根的值即可。
但是，我们对Pairing Heap的了解并不止于此：Pairing Heap允许您不立即执行某些操作，而仅在需要时才执行。 换句话说，配对堆使您可以
“懒惰地”执行操作，从而降低其中一些操作的摊销成本。
假设我们在配对堆中进行了K次插入和K次删除。 显然，只有当我们从堆中请求最小元素时，这些操作的结果才是必需的。
让我们考虑一下先前描述的操作的动作算法在其Lazy实现期间将如何改变：
利用Kuchi根至少有两个空指针这一事实，我们将使用它们中的一个来表示插入到堆中的元素的双向链接列表（以下
称auxList ）的头部，每个元素都将被视为独立Pairing Heap的根。 然后：
- 配对堆中的惰性节点插入：
将指定的U节点插入配对堆{ R_1 ， V_1 }时，我们将其放在auxList中-列表开头之后：
- 两个配对堆的惰性合并：
延迟合并两个Pairing Heap，类似于Lazy节点插入，其中插入的节点是其中一个堆的根（双连接auxList的头）。 - 懒惰地获得最小的配对堆元素：
当要求最小值时，我们通过auxList进入独立Pairing Heap的根列表，将列表中的元素与合并操作成对组合，然后将包含最小元素的根的值返回到结果Pairing Heap之一。 - 延迟删除最小配对堆元素：
当提示您删除“配对堆”指定的最小元素时，首先我们找到包含最小元素的节点，然后将其从作为根的树中删除，然后将其子树插入主堆的auxList中。 - 延迟删除任意非根配对池节点：
删除任意非根配对配对节点时，将从堆中删除该节点，并将其子节点插入到主堆的auxList中。
实际上，使用惰性配对堆实现可以降低配对堆中插入和删除任意节点的摊销成本：从O（log N）到O（1）。
就是这样，下面您会找到有用的链接和资源的列表：
[0] JeMalloc Github页面[1]配对堆的原始文章[2]有关延迟实现配对堆的原始文章[3]有关代码优化，C ++，Asm，“低级”的电报频道，仅此而已！待续...