# Brief History of Free List Sharding

每個系統的 memory 都是有限的。一個程式的動態性越強，對於 memory 的管理就越重要。因此，隨著技術與需求的演進，發展了各式各樣的 memory allocator 。

大家都用過由 glibc 提供的 malloc ，他背後上其實是 `ptmalloc2 `。而` ptmalloc ` 系列是由 Doug Lea 實現的 `dlmalloc` 改進而成的。

## dlmalloc
內部只有一個 ` main arena ` 來對所有 thread 給予空閒記憶體。每次分配的時候，將 ` main arena ` 上鎖，分配完之後釋放鎖。
:::info
可以選擇使用 spin-lock 或是 mutex!
:::
* 單一分配區 + 鎖 = 名符其實的 [Arena](https://www.google.com/search?q=arena+%E4%B8%AD%E6%96%87&oq=arena&aqs=chrome.1.69i57j69i59j0l4.4314j0j7&sourceid=chrome&ie=UTF-8)。

因此，在 multi-thread 的競爭下，催生了 `ptmalloc` = ` per thread malloc ` 。

## ptmalloc
> 來一人一個，不要搶！
> [color=green]

在 dlmalloc 的基礎上，對每個 thread 再各別動態分配一個的 ` dynamic arena `，從這個時候開始 Free list 存在於 ` main arena ` 以及 ` dynamic arena ` 。
但是，當空間被分配到 thread A 之後，就無法重新分配給其他的 thread B C D。
* 隨著程式運行越來越長，記憶體也會被撕成碎片。
* [fragment of memory](https://en.wikipedia.org/wiki/Fragmentation_of_memory)

為了減少多 thread 的空間浪費，在一定數量 thread 下，會有 ` dynamic arena `共用的情況，導致 ` main arena ` 、 ` dynamic arena `都不是 lock-free 的設計。

因此， google 推出了空間回收機制較佳的 `tcmalloc` ` thread cache malloc `。

## tcmalloc
> tcmalloc 的命名相當有意思，"` thread cache `"。 相較於 "` per thread `" ，這份分配給 thread 的記憶體只是讓它 cache 而已。
>
> 在 High concurrency 的 mysql 下有很好的[表現](https://github.blog/2013-02-21-tcmalloc-and-mysql)。
> [color=green]

tcmalloc 的設計基於` ptmalloc `上的分割，將分配區分為` Central Cache`跟` Thread Cache ` ，各別也都有 Free list 存在。

tcmalloc 的改進在於回收機制、細緻度以及減少額外空間等等，這邊介紹回收機制。
* 回收機制
* tcmalloc 會定期的進行垃圾回收，將 ` Thread Cache Free List` 中過多的內存回收到` Central Cache Free List`。

在 tcmalloc 之後，facebook 推出了 jemalloc 優化了對於碎片問題的處理，相較於 tcmalloc 對於大型的 multi-thread 程式更加友善。

## mimalloc
microsoft 推出了 mimalloc 專案。其中，運用分割 free list 以及
thread local heap 的方式應對了提升效能，
* 較好的 spatial locality
* 不需要考慮 concurrency 的 allocation 以及 thread 內的 local free
* 釋放的情況，只需要在 thread 間的 free 考慮 concurrency。減少不必要的效能損耗。
以往的 memory allocator ， 大多使用一個 Central heap 來做主要記憶體來源，導致在 multi-thread 的情況，對於 heap 的操作要非常小心。 在 mimalloc 中，則用 Thread Local Heap (TLH)取代，Heap 屬於各個 thread ，讓 thread 在分配的時候可以不用考慮 concurrency，

而 mimalloc 的 free list，則有3個。

### Allocation Free List
以往的實現裡，對於每類 size 的空間都有一個 Free list，就 tcmalloc 而言，位於 ` Thread Cache ` 跟 ` Central Cache `裡。隨著程式的使用，同樣 size 的空間地址可能會分散在整個儲存空間的各處，導致長期下來會有很糟的` spatial locality `。
::: info
以下是一個 8 bytes 的 free list 在程式執行一段時間後的情況。
此時，allocate 一個 8bytes 的 linked list，就會變成一個 spatial locality 很差的 linked list。
:::
因此，在 mimalloc 中將主記憶體依序分頁，每頁只有特定 size-class的空間，因此獲得較好的 spatial locality。
::: info
這是一個 8 bytes 的 mimalloc free list。
:::

### The Thread and Local Free list
接下來，釋放的情況，則考慮以下兩者的不同，使用不同的 Free list。
* 單一 Thread 內的釋放
* 兩個 Thread 之間的釋放
::: info
Thread t1 釋放了一個物件 p1 ，釋放後將物件 p1 的空間放入 Thread t1 Local Free List 內對應大小的 page 中。而如果是 Thread t2 釋放了 t1 中的 p1 則將其放入 t1 中的 thread Free list。
:::
這樣的策略有以下的好處:
* 對於 Local Free List 不用考慮 concurrency 的問題，
* 對於 Thread Free List 則使用無鎖的 exchange & swap 來實作。