c - 实现显式空闲列表内存分配

Question

作为分配的一部分，我们必须实现一个(基本的)malloc 函数(我们应该以某种方式模拟动态内存分配)。我已经实现了一个基于隐式空闲列表的解决方案，但问题是我得到了 50% 的利用率和 9% 的吞吐量(我必须得到 90% 的利用率+吞吐量)。隐式空闲列表的问题在于它需要花费大量时间来搜索空闲 block 。所以我想实现 explicit free list看看程序能改进多少。现在的问题是我必须跟踪空闲 block 的下一个/上一个指针。而且由于我只能使用标量变量而不能使用任何类型的数据结构，例如:链表、结构、..，我无法实现它。有人可以指出我如何跟踪 C 中的(虚拟)指针吗？

谢谢，

Answer 1

根据幻灯片中的图像(链接在评论中)，我认为您应该将链接存储为整数偏移量。

在 C 中，最好将其描述为结构。

struct alloc_cell {
    int size;
    int forward;
    int back;
    int data[];
};

现在，他还在末尾重复了大小，这很难用结构来描述。 尚不清楚它的必要性。 它用于边界合并。

---

编辑:很久以后，考虑评论。

即使您不能在代码中使用结构，您仍然可以在伪代码 中使用它们来帮助组织您的思维。结构字段，都是相同的类型，自然映射到一个数组可以通过指向第一个成员/元素的指针访问的表示。

struct alloc_cell {    // int *cell;
    int size;          // cell[0] // *cell
    int forward;       // cell[1]
    int back;          // cell[2]
    int data[];        // (cell+3)[...] // &cell[3]
};

您甚至可以为这些偏移量提供助记名称(但这可能被认为是矫枉过正和不必要的混淆)。

enum { SIZE, FORWARD, BACK, DATA };

cell[SIZE];                   // alloc_cell.size
cell[FORWARD];                // alloc_cell.forward
cell[BACK];                   // alloc_cell.back
cell+DATA; // &cell[DATA]     // alloc_cell.data