我希望在 C 中为内存受限的微控制器实现堆分配算法。我已将搜索范围缩小到我知道的 2 个选项，但是我非常愿意接受建议，并且我正在寻找任何有这方面经验的人的建议或意见。
我的要求：
-速度肯定很重要，但它是次要问题。
- 时序确定性并不重要——任何需要确定性最坏情况时序的代码部分都有自己的分配方法。
- 主要要求是碎片免疫。该设备正在运行一个 lua 脚本引擎，这将需要一系列分配大小（在 32 字节块上很重）。主要要求是该设备能够长时间运行而不会将其堆搅成不可用状态。
另请注意：
-作为参考，我们谈论的是 Cortex-M 和 PIC32 部件，内存范围从 128K 到 16MB 或内存（重点放在低端）。
-我不想使用编译器的堆，因为 1）我希望所有编译器的性能保持一致，以及 2）它们的实现通常非常简单，并且对于碎片来说相同或更糟。
- 由于我不想从根本上更改和重新验证庞大的 Lua 代码库，双重间接选项已被淘汰。
到目前为止我最喜欢的方法：
1）有一个二进制伙伴分配器，并牺牲内存使用效率（四舍五入到2的幂）。- 这（据我所知）需要一个二叉树为每个订单/箱存储按内存地址排序的空闲节点，以便快速查找伙伴块以进行重新链接。
2) 有两棵用于空闲块的二叉树，一棵按大小排序，一棵按内存地址排序。（所有二叉树链接都存储在块本身中） - 分配将最适合使用按大小查找表，然后按地址从另一棵树中删除该块 - 解除分配将按地址查找相邻块以进行重新链接
- 两种算法还需要在分配块开始之前存储分配大小，并让块以 2 减 4 的幂（或 8 取决于对齐方式）的形式出现。（除非他们在其他地方存储一棵二叉树来跟踪按内存地址排序的分配，我认为这不是一个好的选择）
- 两种算法都需要高度平衡的二叉树代码。
-算法 2 不要求通过四舍五入到 2 的幂来浪费内存。
-在任何一种情况下，我可能都会有一个固定的 32 字节块组，由嵌套位字段分配，以卸载这个大小或更小的块，这将不受外部碎片的影响。
我的问题：
- 有什么理由说明方法 1 比方法 2 更不受碎片的影响？
- 有没有我遗漏的可能符合要求的替代方案？