一、面试让你手写内存池到底要写什么如果面试官突然问手写一个简单的内存池。一般并不是让我们重新实现一套完整的malloc free jemalloc tcmalloc而是希望看到是否理解内存池最基本的思想。普通内存申请需要内存 ↓ malloc ↓ 使用 ↓ free如果大量小对象频繁创建和销毁就会不断进行malloc → free → malloc → free ...内存池的思路则是先申请一大块内存 ↓ 切成很多小块 ↓ 使用链表管理空闲块 ↓ 申请时取出一块 ↓ 释放时重新放回来因此面试中一个简化内存池至少需要解决三个问题1. 怎么把大块内存切成小块 2. 怎么知道哪些块现在是空闲的 3. 申请和释放时怎么快速找到这些块最常见的答案就是固定大小内存块 空闲链表 Free List例如一次申请128字节然后按照16字节切分┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐ │Block1│Block2│Block3│Block4│Block5│Block6│Block7│Block8│ └──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘然后使用链表连接这些空闲块Block1 ↓ Block2 ↓ Block3 ↓ Block4 ↓ ...申请的时候从链表头取一个释放的时候重新插回链表头这样申请和释放都可以做到非常简单。二、先设计一个最简单的内存池为了突出面试核心我们先实现固定大小内存块而不是一开始就处理8字节 16字节 32字节 64字节多个档位。先定义class MemoryPool { private: struct FreeNode { FreeNode *next; }; void *pool_; // 整块内存起始地址 FreeNode *free_list_; // 空闲链表头 size_t block_size_; // 每个内存块大小 size_t block_count_; // 内存块数量 public: MemoryPool(size_t blockSize, size_t blockCount); ~MemoryPool(); void *allocate(); void deallocate(void *ptr); };这里真正关键的是struct FreeNode { FreeNode *next; };为什么每个空闲块只需要保存next因为当一块内存正在被用户使用时里面应该全部交给用户。但当它处于空闲状态时这块内存暂时没人使用。所以完全可以拿这块内存最前面的几个字节保存下一个空闲块地址也就是空闲状态 ┌───────────────┐ │ next │ │ │ │ 空闲空间 │ │ │ └───────────────┘而分配出去以后使用状态 ┌───────────────┐ │ 用户数据 │ │ 用户数据 │ │ 用户数据 │ │ 用户数据 │ └───────────────┘这也是很多内存池代码中会看到FreeNode *甚至void **这种写法的原因。本质都是利用空闲内存块本身保存链表指针。三、构造函数申请内存并建立空闲链表接下来真正初始化内存池。MemoryPool::MemoryPool(size_t blockSize, size_t blockCount) : pool_(nullptr), free_list_(nullptr), block_size_(blockSize), block_count_(blockCount) { // 内存块至少要能保存一个指针 if (block_size_ sizeof(FreeNode)) block_size_ sizeof(FreeNode); // 一次申请整块内存 pool_ std::malloc(block_size_ * block_count_); if (!pool_) throw std::bad_alloc(); char *start static_castchar *(pool_); // 将所有内存块连接成空闲链表 for (size_t i 0; i block_count_; i) { FreeNode *node reinterpret_castFreeNode *(start i * block_size_); node-next free_list_; free_list_ node; } }这里最重要的一步是start i * block_size_假设block_size 16那么每个块的地址就是第0块start 0 第1块start 16 第2块start 32 第3块start 48于是原来的一整块pool_被逻辑切成┌────────┬────────┬────────┬────────┐ │ Block0 │ Block1 │ Block2 │ Block3 │ └────────┴────────┴────────┴────────┘然后node-next free_list_; free_list_ node;使用头插法建立链表。最终得到free_list_ ↓ Block3 ↓ Block2 ↓ Block1 ↓ Block0 ↓ nullptr这里并没有真的为每个节点重新new FreeNode因为每一个Block本身就是一个FreeNode。例如FreeNode *node reinterpret_castFreeNode *(start i * block_size_);实际上就是告诉编译器从这个地址开始我现在暂时把这块空闲内存当成一个 FreeNode 使用。这是手写内存池中非常关键的一个思想。四、allocate和deallocate怎么实现链表建立完成以后申请内存就非常简单了。1. allocatevoid *MemoryPool::allocate() { // 内存池已经没有空闲块 if (!free_list_) return nullptr; // 取出链表头 FreeNode *node free_list_; // free_list指向下一个空闲块 free_list_ free_list_-next; // 返回当前块 return node; }假设原来的链表free_list_ ↓ Block3 ↓ Block2 ↓ Block1 ↓ Block0执行void *p pool.allocate();实际上就是取出Block3然后free_list_ ↓ Block2 ↓ Block1 ↓ Block0所以申请一个内存块实际上只进行了读取链表头 修改链表头时间复杂度O(1)2. deallocate释放同样非常简单void MemoryPool::deallocate(void *ptr) { if (!ptr) return; FreeNode *node static_castFreeNode *(ptr); // 重新插回空闲链表头 node-next free_list_; free_list_ node; }假设现在free_list_ ↓ Block2 ↓ Block1 ↓ Block0然后释放Block3执行node-next free_list_;得到Block3 ↓ Block2然后free_list_ node;最终free_list_ ↓ Block3 ↓ Block2 ↓ Block1 ↓ Block0所以释放操作同样是O(1)最后析构时统一释放整块内存MemoryPool::~MemoryPool() { std::free(pool_); }完整代码整理如下#include cstdlib #include iostream #include new class MemoryPool { private: struct FreeNode { FreeNode *next; }; void *pool_; FreeNode *free_list_; size_t block_size_; size_t block_count_; public: MemoryPool(size_t blockSize, size_t blockCount) : pool_(nullptr), free_list_(nullptr), block_size_(blockSize), block_count_(blockCount) { // 每个空闲块至少要能够保存一个指针 if (block_size_ sizeof(FreeNode)) block_size_ sizeof(FreeNode); // 一次申请整块内存 pool_ std::malloc(block_size_ * block_count_); if (!pool_) throw std::bad_alloc(); char *start static_castchar *(pool_); // 将每一个块加入空闲链表 for (size_t i 0; i block_count_; i) { FreeNode *node reinterpret_castFreeNode *(start i * block_size_); node-next free_list_; free_list_ node; } } ~MemoryPool() { std::free(pool_); } void *allocate() { if (!free_list_) return nullptr; FreeNode *node free_list_; free_list_ free_list_-next; return node; } void deallocate(void *ptr) { if (!ptr) return; FreeNode *node static_castFreeNode *(ptr); node-next free_list_; free_list_ node; } }; int main() { // 创建10个32字节内存块 MemoryPool pool(32, 10); void *p1 pool.allocate(); void *p2 pool.allocate(); std::cout p1 p1 std::endl; std::cout p2 p2 std::endl; // 使用完成以后归还内存池 pool.deallocate(p1); pool.deallocate(p2); return 0; }整个过程可以总结为构造MemoryPool ↓ malloc一大块内存 ↓ 按照block_size切分 ↓ 建立free_list ↓ allocate ↓ 从free_list头部取块 ↓ 用户使用 ↓ deallocate ↓ 重新插回free_list五、面试最容易继续追问什么如果能把上面的简版内存池写出来面试官一般还会继续追问几个问题。1. 为什么不用malloc/free不能回答因为malloc很慢这种说法太绝对。更合适的表达是在大量固定大小或者小对象频繁申请和释放的场景下内存池可以提前批量申请内存通过空闲链表进行复用减少频繁进行通用动态内存分配的管理开销同时提高内存局部性。2. 为什么allocate和deallocate是O(1)因为两个操作本质都是修改链表头申请node free_list_; free_list_ free_list_-next;释放node-next free_list_; free_list_ node;都没有遍历链表。所以平均可以做到O(1)3. 为什么block_size至少要大于一个指针因为空闲状态下需要在块里面保存FreeNode *next;因此block_size_至少必须满足block_size_ sizeof(void *);否则连下一个空闲块地址都放不进去。4. 这个内存池有什么问题这个简化版本并不是工业级实现还有很多问题只支持固定大小内存块 没有处理线程安全 没有检测重复释放 没有检测非法指针 没有自动扩容 没有处理更复杂的内存对齐 内存池耗尽后只能返回nullptr如果需要支持不同大小可以进一步设计8字节 FreeList 16字节 FreeList 32字节 FreeList 64字节 FreeList 128字节 FreeList例如申请13字节 ↓ 进入16字节档位申请27字节 ↓ 进入32字节档位这就是size class大小分类。5. 多线程情况下怎么办现在allocate(); deallocate();都会修改free_list_如果多个线程同时操作线程A ─┐ ├→ free_list_ 线程B ─┘就可能产生数据竞争。最简单的解决方法就是std::mutex在申请和释放时加锁。更加复杂的实现还可以考虑线程本地缓存 无锁FreeList CAS 分级内存池不过一般面试让手写简版内存池时先把大块内存 固定大小Block Free List O(1)申请释放这几个核心点写出来就已经足够。如果让我在面试中用几句话总结这个实现我会这样说我实现的是一个固定大小块的简化内存池。构造时一次性申请一块连续内存再按照固定 block size 划分成多个小块并利用空闲块自身保存 next 指针组成 Free List。申请内存时直接从空闲链表头取出一个块释放时再通过头插法放回因此申请和释放都可以做到 O(1)。当前实现主要用于说明内存池核心原理如果继续完善还可以增加多级 size class、内存对齐、线程安全以及自动扩容。这段也是面试时比较适合直接表达的一套回答。0voice · GitHub