C 中用于 1 字节到 8k 字节内存块的内存管理器实现 - 面试问题
Memory manager implementation in C for memory blocks of 1 byte to 8k bytes - interview question
您需要使用以下 3 个函数在 C 中实现一个内存管理器：
void init() - 初始化内存管理器。
void* get(int numOfBytes) - return 一个大小为“numOfBytes”的内存块（在堆上）。 “numOfBytes”的值可以在 [1,8k].
范围内
void free(void* ptr) - 释放“ptr”指向的内存块。
几条规则：
- 只能在"init()"函数中调用malloc函数。
- 方法“get”和“free”应该尽可能高效，但方法“init”不必如此，只要你不浪费太多内存或类似的东西。
- 您可以假设您的内存管理器总共不需要分配超过某个固定大小的字节数，比如总共不超过 1GB。
我的尝试：
我想只实现固定大小的内存池，其中每个块为 8k 字节，如 here。这将为我们提供 O(1) 运行 方法“get”和“free”的时间，这很好，但问题是如果用户只调用“get”少量字节（例如，每次 1 个字节）。
但是，如果我尝试使用可变块大小来实现它 - 我将需要处理碎片，这会使 运行 时间变得更糟。
那你有更好的主意吗？
我会避免使用固定大小的块。
一个常见的策略是以 2 的幂形成池：16,32,...1G，所有的东西最初都在最大的池中。
分配的每个块都是用户大小 n + 开销（估计为 4-8 字节），“上限”为 2 的幂。
如果池中缺少可用块，请将较大的块切成两半。
由于组中往往会出现类似的分配大小，这避免了过多的大小浪费。
在取消分配（和折叠重用）时只需要释放一对块以重新形成更大的块（这可能又会重新加入另一个块）并减少碎片。
注意：所有 *alloc() return 指针都可以对齐 max_align_t，因此这也是 get() 预期的下限 -（可能大小为 4？） .作为面试的一部分，提及对齐和可移植性问题是很好的。
有很多改进，比如很好地容纳2的幂大小的块，但是对于面试题，只需要触及这样的改进思路。
free() 是标准库。函数 - 最好不要重新定义 - 使用不同的名称。
您需要使用以下 3 个函数在 C 中实现一个内存管理器：
void init() - 初始化内存管理器。
void* get(int numOfBytes) - return 一个大小为“numOfBytes”的内存块（在堆上）。 “numOfBytes”的值可以在 [1,8k].
void free(void* ptr) - 释放“ptr”指向的内存块。
几条规则：
- 只能在"init()"函数中调用malloc函数。
- 方法“get”和“free”应该尽可能高效，但方法“init”不必如此，只要你不浪费太多内存或类似的东西。
- 您可以假设您的内存管理器总共不需要分配超过某个固定大小的字节数，比如总共不超过 1GB。
我的尝试：
我想只实现固定大小的内存池，其中每个块为 8k 字节，如 here。这将为我们提供 O(1) 运行 方法“get”和“free”的时间，这很好，但问题是如果用户只调用“get”少量字节（例如，每次 1 个字节）。
但是，如果我尝试使用可变块大小来实现它 - 我将需要处理碎片，这会使 运行 时间变得更糟。
那你有更好的主意吗？
我会避免使用固定大小的块。
一个常见的策略是以 2 的幂形成池：16,32,...1G，所有的东西最初都在最大的池中。
分配的每个块都是用户大小 n + 开销（估计为 4-8 字节），“上限”为 2 的幂。
如果池中缺少可用块，请将较大的块切成两半。
由于组中往往会出现类似的分配大小，这避免了过多的大小浪费。
在取消分配（和折叠重用）时只需要释放一对块以重新形成更大的块（这可能又会重新加入另一个块）并减少碎片。
注意：所有 *alloc() return 指针都可以对齐 max_align_t，因此这也是 get() 预期的下限 -（可能大小为 4？） .作为面试的一部分，提及对齐和可移植性问题是很好的。
有很多改进，比如很好地容纳2的幂大小的块，但是对于面试题，只需要触及这样的改进思路。
free() 是标准库。函数 - 最好不要重新定义 - 使用不同的名称。