# hmalloc

**Repository Path**: huangxyee/hmalloc

## Basic Information

- **Project Name**: hmalloc
- **Description**: hmalloc 高并发内存池
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-06-06
- **Last Updated**: 2024-09-04

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# hmalloc 高并发内存池

## 项目描述

原型是谷歌开源项目ThreadCachemalloc（Thread-Caching Malloc），是Google性能工具套件（gperftools）的一部分，主要用于优化C++程序的内存分配性能。它通过以下几个核心机制来提高内存分配和释放的效率，尤其在多线程环境下：

1. **线程缓存**：ThreadCachemalloc为每个线程提供了一个小对象的缓存，这可以大大减少对中央内存堆的访问次数，从而减少了锁的竞争。
2. **大小类**：将内存分配请求分为多个大小类，每个大小类对应一定范围的内存大小。这样可以减少内存碎片，提高内存使用效率。
3. **中央缓存**：用于存储各个线程不常用的内存块，可以在线程之间共享。
4. **页级分配**：对于大对象的分配，ThreadCachemalloc直接从操作系统申请内存页。

相较于标准的malloc/free，ThreadCachemalloc通过这些机制减少了内存碎片，降低了锁的竞争，从而在多线程高并发的场景下，提高了内存分配和释放的效率。

本项目是一个简化的ThreadCachemalloc，实现了ThreadCachemalloc最核心部分，也就是三层缓存池结构：ThreadCache，CentralCache，和PageCache。

我画了一个简图，可以更清晰地了解这三个缓存池，暂时看不懂可以先pass。

![iamge](./learn_hmalloc.png)

## 一个例子搞懂hmalloc

### 申请过程

假设线程要申请一个7字节的内存，调用hmalloc函数，会有以下几个步骤:

1. **数据对齐**：先把7字节对齐为8字节，这样做是为了提高内存访问效率、减少内存碎片和简化内存管理
2. **线程向ThreadCache申请内存**：对齐后，线程通过线程TLS（线程本地存储，如果不使用，线程之间数据是共享的）获得自己专属的ThreadCache，向它申请内存，对齐的字节数是8，找到ThreadCache的0号哈希桶去获取一个8字节的内存块
   1. 如果哈希桶有内存块，返回地址，【结束】
   2. 如果没有，进行步骤3.
3. **ThreadCache向CentralCache申请内存**：由于ThreadCache的0号哈希桶是空的，所以向CentralCache的0号哈希桶去获取一个非空的span
   1. 如果哈希桶中有Span，取出k个大小为8字节的Span，1个返回，其余k-1个给ThreadCache，【结束】
   2. 如果没有，进行步骤4.
4. **CentralCache向PageCache申请内存**：CentralCache申请k个8B的Span，假设大小是p页（向上取整，不满1页给1页），PageCache就去自己的p号哈希桶取
   1. 如果有，取出1个，返回地址，【结束】
   2. 如果没有，那么往后找
      1. 如果找到更大的下标不为空，设下标是q，那么将q拆分成p大小、q-p大小的2块，前者返回给CentralCache，后一个放在PageCache对应哈希桶上，【结束】
      2. 如果找到最后还是没有，就向系统申请一个128页的内存块，把128页拆成p大小、128-p大小的2块，前者返回给CentralCache，后一个放在PageCache对应哈希桶上，【结束】
 
至此，整个申请内存流程大致完成。

### 释放过程

假设线程要释放一块内存，调用hfree，会有以下几个步骤:

1. **空间放入ThreadCache**：根据空间的大小，计算这块空间应该存放在该线程ThreadCache的哪个哈希桶，把空间放入这里
   1. 放入空间后，数量没有超过设定的max值，【结束】
   2. 放入空间后，数量超过了设定的max值，进行步骤2.
2. **空间放入CentralCache**：取出ThreadCache这个哈希桶的前max块空间，放入CentralCache对应哈希桶的Span中（哈希映射可以找到，页号相同的空间，会放入同一个Span）
   1. 放入空间后，CentralCache哈希桶的Span没到一页大小，【结束】
   2. 放入空间后，CentralCache哈希桶的Span满足一页大小，进行步骤3.
3. **空间放入PageCache，合成更大的页**：取出这一页，放在PageCache对应的哈希桶后面，检查页号，尝试向前合并页，向后合并页
   1. 如果前后都没有空闲的页，【结束】
   2. 如果有，不断检查，直至遇到空桶，将合并的页，放入PageCache更大的哈希桶

至此，整个释放内存流程大致完成。

## 项目结构
```bash
.
├── benchmark_visualize.py  # *.csv数据可视化python代码
├── CentralCache.cpp
├── CentralCache.h
├── FreeList.h              # 自由链表类
├── helper.h                # 工具函数
├── hmalloc.h               # 封装函数
├── macros.h                # 宏
├── ObjectPool.h            # 定长内存池
├── PageCache.cpp
├── PageCache.h
├── PageMap.h               # 基数树类
├── SizeClass.h             # 字节对齐、哈希桶映射相关
├── SpanList.h              # Span结构体，SpanList类
├── test.cpp                # 测试代码
├── ThreadCache.cpp
└── ThreadCache.h
```

## 测试结果

![iamge](./benchmark_size.png)

这是4个线程，100轮，单轮申请/释放10000次，size作为自变量的结果对比图。这里每次申请/释放的size大小是不变的，只会频繁使用某几个哈希桶。

结果：当size小于2KB时，hmalloc性能领先malloc，但当size超过2KB时，性能优势不大。

![iamge](./benchmark_times.png)

这是4个线程，100轮，每次申请/释放的size大小随机，每轮的申请/释放次数times作为自变量的结果对比图。

结果：当times小于100时，由于时间短，误差相对较大，但是hmalloc的性能还是领先malloc。

![iamge](./benchmark_works.png)

这是100轮，单轮申请/释放10000次，每次申请/释放的size大小随机，线程数works作为自变量的结果对比图。

结果：该条件下，hmalloc的性能均领先于malloc。