# Malloc 對於多執行緒程式的效能影響 contributed by <`ierosodin`>, <`refleex`>, <`stanleytazi `> [簡報版本](https://hackmd.io/s/S1X1it3Tl) ## github ## 預期要做的事情 - [ ] 讀 SuperMalloc 論文 - [x] 讀上學期關於 [針對多執行緒環境設計的 Memory allocator](https://hackmd.io/s/HkICAjeJg#) 的共筆 - [x] SuperMalloc 的使用 - [x] 決定要採用何種評估效能的程式(方式) - [ ] rpmalloc - [ ] Begun/lockfree-malloc - [ ] Daniel Micay 的 allocator - [x] Openstack - [ ] 在 cloud 上跑 malloc - [ ] opic :::info 比較 Daniel Micay 的 allocator [2] 和下方兩個 allocator 實作的效能: * https://github.com/Begun/lockfree-malloc * https://github.com/rampantpixels/rpmalloc ::: 6/6 jserv 給予的建議 - [ ] Daniel Micay 的 allocator 是個非常進階的設計，可對比 rpmalloc，請提出比較和效能解讀; - [ ] benchmark suite 可參照 scalloc-bench 和 rpmalloc-bench，提出可行的折衷方案 - [ ] 如何確保 benchmark 符合真實應用情境？ - [ ] 個別實作如何考慮到 fragment 跟 memory leak 呢？ ## 背景知識 ### [Multicore Storage Allocation](http://www.drdobbs.com/multicore-storage-allocation/221600440?queryText=False%2BSharing) (Dr.Dobb's) 此篇文章提到在 multicore(or multi-thread) 環境下做 memory allocation/deallocation 有幾個要考慮的議題: #### **Thread safty** 主要是在多個 threads 如果都要做 malloc() / free()，是否能保證這些 threads 不會同時對 internal data structure 做操作，而產生不預期的結果( stomping on each others' toes ) #### **Overhead and Contention** 要解決上述 thread safty 的問題可以使用 mutex lock，但是又會產生效能問題，就是會有使用 lock 的 overhead，另外就是所有的 thread 都在嘗試取得同一塊 storage 的 lock 在 thread 數量越多會有越多的 contention，這個也是在論文中 **Caching** 章節中提到的 per-thread cache 做法，是可以解決這問題，概念就是分配不同的 memory pool 給各個 thread 做使用，這樣分配 per-thread cache 大小內就不用 lock 以及 不會有 contention 的發生 **[解法]** 使用 local storage pool per thread #### **Memory drift** 這個問題是如果在有 thread local 的 storage 的狀況下，如果 threadA 所 allocated 的 memory (也就是從 threadA 的 storage 取得的) 都是被 threadB 給 free 掉，並且是 return 給 threadB 的 free-list 則 threadB 的 storage 就會一直長大，變成是 unbound 的，這種情況就有點像是 memory leak。 **[解法]** 1. local storage 一旦超過某個 threshold ，則 return 一些給 global storage 2. 限制一律由 allocator 來做 deallocation #### **False sharing** ![](http://i.msdn.microsoft.com/cc872851.figo2(en-us).gif) 這問題是指說如果兩個 thread(tA, tB)分別在不同 cores 針對不同的 data(tA->dA, tN->dB) 做 R/W ， 從 code 來看可能不覺得有什麼問題，但是萬一這些 data 都是存在於同一條 cache line(dA+dB)， 此時兩個 thread 所各自 R/W 的 cache line 都含有 dA+dB ，則會造成一旦 tA 對 dA 做改動(new dA + old dB)，則對於 tB 的 cache line 就會變成是 invalidate (old dA **invalid**, old dB)，而產生 cache-misses，如果整個程式充斥這種問題，則越多的thread(cores) 只會造成越來越多的 cache misses，而不會如預期的得到 multi-core 的好處 **[解法]** 可以把 dA 和 dB 各自 align cache line ### Hardware Transactional Memory (HTM) #### + [Transactional memory](https://en.wikipedia.org/wiki/Transactional_memory) ( TM ) provides optimistic concurrency control by allowing threads to run in parallel with minimal interference **[中文]** TM 最主要就是希望可以讓 multithreads 的程式可以有最佳的 concurrency，最主要就是想把因為要平行跑threads所造成的成本降到最低 + TM 的最終目的就是希望標示 transcation 的程式區段可以達到 **atomicity**, **consistency** and **isolation** + 在 TM 中如果有 conflict 被偵測到(同時有不同 threads 更改同一個值)，則會回到改變前的狀態; 而在成功的 commit 前，任何值都只是 transcations 中的暫態值 + HTM 就是從 processor, cache, bus 都要可以support "transcations" + HTM 希望可以提供比一般用 fine-grain lock 更高的 abstraction，讓 programmers 不用處理資料同步問題 (因為有時候會有些風險，比如造成 deadlock)，只需要在 critical section 標上關鍵字，比如說 transcation, atomic + 以下就是在 [cmu](http://www.cs.cmu.edu/afs/cs/academic/class/15418-s12/www/lectures/20_transactionalmem.pdf) 的課程講義提供的資料，可以看到使用 HTM 在 Balanced Tree 下不管多少個 processors 都可 以有很好的效能 ![](https://i.imgur.com/I7IO6e9.png) ## 論文筆記 論文: [SuperMalloc: A Super Fast Multithreaded Malloc for 64-bit Machines](http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf) + C/C++ 中動態記憶體配置相關的函式： `malloc()` `free()` + 衡量一個 allocator cost 的主要因素： speed 、 footprint 、 complexity + 配置記憶體主要分成兩個步驟： * 呼叫 `mmap()` 來取得一段連續的虛擬記憶體 * 當程式實際使用到這個虛擬記憶體時，會發生 page fault( page table 中找不到)，於是配置一段實體記憶體，有實體記憶體對應的 page 稱為 committed page ，反之，則稱為 uncommitted page ### Comparison among Different malloc + DLmalloc * 利用 boundary tags( 8 bytes )來記錄每一個 object 的大小，用這個資訊來找到下一個 chunk 的位置 * 當配置的空間小於 8 bytes 時，會造成超過50%的 overhead + Hoard * 將記憶體分成許多不同的 chunks ，來控管記憶體的分配 * 每個 chunk 擁有相同大小的 object ，因此不需要有 boundary tags * 利用 allocate-fullest heuristic 來檢查放入的 object 是否超過 chunk( superblock ) * 支援 multithread( no locking was required ) + JEmalloc * 將 memory 分成三部分： small class 、 large class 、 huge class * 將 chunk 分割成 run ，每個 chunk 記錄 metadata ，並利用紅黑樹來維護 untouched and uncommitted 的記憶體 * 在 long-running processes 中縮小了 memory footprint * 使用 first-fit strategy 來取得適合的記憶體 * 使用 thread-local cache ，使用後再將 object return 回 global ### SuperMalloc + Small Object + size 從 8 bytes 到 256 bytes + 以 25% 的增幅來增加支援 object size + 關於 **false sharing**，SuperMalloc 並不負責來解決這件事情，作者假設使用者如果會是有這方面的考量，是可以自己用 memalign() 的方式來解決這問題 + Caching * 在 SuperMalloc 中，將 cache 分成三層： per-thread cache 、per-CPU cache 以及 global cache * 每一個 bin 維護一種 size 的 memory ，並各自擁有自己的 cache * 對於 locking & accessing the shared data 的成本會是在於要達到 cache coherence * 作者對於三種不同 scope 的 cache 做了實驗如下圖，可以看到使用 Global cache 的所花的時間跟 per-CPU 和 per-thread 有很大的差距，而 per-CPU 和 per-thread 的差距就小很多，**由此實驗我們可以知道說對於 cache coherence 的成本是遠比 locking & increment instruction 還要大很多的，所以在設計上應該要盡量減少 global share data 的使用** > 不過作者這邊也描述了兩個現象，現在不確定是否是正確結論 > + per-CPU data structure mostly resides in the right cache > + the lock instruction is mostly uncontended [color=#CCFF80] + schd_getcpu() 是 per-CPU cache 最大的成本來源，所以可以藉由把 call 這個 function 的次數降成原來的 1/16，同樣地作者有提到使用 malloc() 時，絕大多數都會是在正確的 CPU 上使用 + 底下原文不太了解，一開始提到要償還 per-CPU 中因為使用了 uncontended locking 所帶來的代價，所以每個 per-thread cache 都是10個 objects，但是下一句又提到他決定要把在 thread cache 裡的每個 bin 都要存兩條 linked list，然後每一條會存有總共 8KB 大小的 objects > The SuperMalloc per-thread cache needs to be just big enough to amortize the 34 ns uncontended locking overhead compared to the 3.1 ns unlocked overhead, so we want about 10 objects in the per-thread cache. I decided to store two linked lists each containing up to 8 KiB worth of objects for each bin in the thread cache. ![](https://i.imgur.com/fLTgqoO.png) ## 實驗 ### 環境 ```shell $ lscpu Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 每核心執行緒數：2 每通訊端核心數：2 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 69 Model name: Intel(R) Core(TM) i5-4260U CPU @ 1.40GHz 製程： 1 CPU MHz： 1638.281 CPU max MHz: 2700.0000 CPU min MHz: 800.0000 BogoMIPS: 4000.14 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 3072K NUMA node0 CPU(s): 0-3 ``` ``` $ uname -a Linux my-mac 4.4.0-64-generic #85-Ubuntu SMP Mon Feb 20 11:50:30 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux ``` ### benchmark 的選擇 在實驗之前必須要選擇一個可以觀察出 **SuperMalloc 對 multithread 影響** 的 benchmark ，原始 phonebook-concurrent 程式有三個地方有使用到 `malloc()`，分別是 + 在一開始給了一大塊足夠給後來所有的 entry 使用的 memory，大小就是 total_name_num * sizeof(entry) + 分別建立每個 thread 的 arguement + 在 `finName()` 中找到目標後，將電話簿其他資訊所需的 memory 分配出來 所以其實可以看到這些使用 `malloc()` 的地方對於我們的想要觀察的事情是比較顯現不出來的。接著我們選了一些可以觀察的程式 #### 實驗一：hw4 時的作業 [phonebook_concurrent hw4](https://github.com/stanleytazi/phonebook-concurrent.git) 在 phonebook_concurrent 中，將程式改成在 append() 時直接對 `DICT_FILE` 做 memory map，然後每個 thread 盡量平均分配處理 map 後的 names，所以每個 thread 會各自的使用 `malloc()` 建立 entry node ```clike= void append(void *arg) { thread_arg *t_arg = (thread_arg *) arg; char *data = t_arg->data_start; int w = 0; int count = 0; entry **ne = &(t_arg->entry_list_head); while (data < t_arg->data_end) { if (*(data+w) == '\n') { count++; *ne = (entry *)malloc(sizeof(entry)); (*ne)->lastName = data; (*ne)->dtl = NULL; (*ne)->pNext = NULL; *(data+w) = '\0'; data+=(w+1); w = -1; t_arg->entry_list_tail = *ne; ne = &(*ne)->pNext; } w++; } t_arg->count = count; pthread_exit(NULL); } ``` + 執行時間比較 * 這裡的 optimized version 是把 entry size 縮短為 24 bytes（在supermalloc中屬於 small object） + thread num = 32 ![](http://imgur.com/ah2LDHa.png) + thread num = 16 ![](https://i.imgur.com/EmlbpHY.png) 可以明顯發現，使用 SuperMalloc 在我們這個測試程式中效能降低，接下來就要觀察最主要的原因是什麼呢？ + 利用 perf 分析程式 + 可以看到在 pthread_mutex_lock 中花了很多時間，但是我們在 phonebook_opt 的程式裡並未使用 pthread_mutex_lock & unlock，所以先猜測是在 SuperMalloc 使用的 + 按照論文中 caching 一節所說，它對於每個 bin 去分配空間是按照 per-thread cache, per-CPU cache , global cache 所以想要確認一下是不是 per-thread cache 使用完了 ``` $ perf record -e cycle -F 25000 ./test-SuperMalloc phonebook_opt $ perf report ``` ```shell= Samples: 3K of event 'cycles', Event count (approx.): 549275135 Overhead Command Shared Object Symbol ▒ 11.44% phonebook_opt libpthread-2.23.so [.] pthread_mutex_lock ▒ 7.45% phonebook_opt libpthread-2.23.so [.] pthread_mutex_unlock ▒ 5.95% phonebook_opt libsupermalloc_pthread.so [.] small_malloc ▒ 5.10% phonebook_opt [kernel.kallsyms] [k] native_queued_spin_lock_slowpath ◆ 5.02% phonebook_opt phonebook_opt [.] append ▒ 2.78% phonebook_opt [kernel.kallsyms] [k] clear_page_c_e ▒ 2.70% phonebook_opt [kernel.kallsyms] [k] futex_wait_setup ▒ 2.69% phonebook_opt [kernel.kallsyms] [k] _raw_spin_lock ▒ 2.67% phonebook_opt libpthread-2.23.so [.] __lll_lock_wait ▒ 2.56% phonebook_opt phonebook_opt [.] main ▒ 2.45% phonebook_opt [kernel.kallsyms] [k] futex_wake ▒ 2.04% phonebook_opt [kernel.kallsyms] [k] get_futex_key ▒ 1.96% phonebook_opt [kernel.kallsyms] [k] copy_page ▒ 1.91% phonebook_opt libsupermalloc_pthread.so [.] cached_malloc ▒ 1.80% phonebook_opt [kernel.kallsyms] [k] entry_SYSCALL_64 ▒ 1.79% phonebook_opt ld-2.23.so [.] __tls_get_addr ▒ 1.72% phonebook_opt [kernel.kallsyms] [k] hash_futex ▒ 1.69% phonebook_opt [kernel.kallsyms] [k] futex_wait ▒ 1.56% phonebook_opt libsupermalloc_pthread.so [.] malloc ``` **（使用 DICT_FILE = words.txt, THREAD_NUM = 16）** #### 實驗二：去年[共筆](https://hackmd.io/s/HkICAjeJg#) 提供的malloc_benchmark 參考：https://github.com/jffrosen/fragbench 更改後 TempoJiJi 的版本：https://github.com/TempoJiJi/malloc_benchmark 以下實驗用版本： https://github.com/stanleytazi/malloc_benchmark.git ![](http://imgur.com/8caObBY.png) - **100 objects allocated, avg. elapsed time (100 runs)** 雖然我們從上面的圖可以看到 **Supermalloc** 對於一次從 2^2, 2^4, 一直分配到 2^22 所累積的時間都是比較多的，但是因為每個 size 都只分配一個 object，然後 size 越大其實是會 dominate 所累加出來的值，所以改用下方實驗方式，每一個 size 都會分配 100 objects，然後每個 size 所耗費的時間分別作累加。以下可以觀察到幾個現象： 1. 在分配小於 512 bytes 的時候 **SuperMalloc** 都是表現比較差的 2. 但在 512 bytes 之後，隨著 threads 的個數增加，**SuperMalloc** 有機會跟 **Ptmalloc** 一樣或是更好 3. 在 32 bytes 時，**SuperMalloc** 與 **Ptmalloc** 都有著很微小的時間差距，也可以看到 16, 32, 64, 256 bytes 會呈現一個 W 型的結果 + 2 threads ![](https://i.imgur.com/1HIbHXy.png) + 4 threads ![](https://i.imgur.com/En1hyCM.png) + 8 threads ![](https://i.imgur.com/y4UHpf2.png) + 16 threads ![](https://i.imgur.com/8NTtBfy.png) + 32 threads ![](https://i.imgur.com/Z2qKDRE.png) + 64 threads ![](https://i.imgur.com/Dbm2oOH.png) - **==1000== objects allocated, avg. elapsed time (100 runs)** + 這次我們每個 thread 還有每個 size 都分配 1000 個 objects ![image alt](http://imgur.com/uT526Q4.png) ![image alt](http://imgur.com/FtJgpsK.png) ![image alt](http://imgur.com/ACEfEOH.png) ![image alt](http://imgur.com/6g6szSd.png) ![image alt](http://imgur.com/h1EqKbU.png) ![image alt](http://imgur.com/n9pR3lP.png) #### 實驗三：延續實驗二，但加入 `free()` 對比實驗二一直只有做 `malloc()` 的動作，因為有看到 **SuperMalloc** 會將 free 掉的 memory 有 caching 的機制，另外也看到 paper 中有一個 benchmark 是producer 一直在做 `malloc()` ， 而 consumer 會一直 `free()` ，所以我們也想加入 `free()` 的行為來觀察執行時間。可以看到我們連續做了兩次的 `do_malloc()`，每一次做完後都會把所有分配的 memory free 掉，然後我們針對第二次的 `do_malloc()` 去統計時間 ``` clike= static void *do_malloc (void *arg) { vector<char*> ptrs; int id = *((int*)arg); Timer t(clock_speed_ghz); for (int i = 0; i < N_ALLOCS; i++) { char *a = NULL; t.tick(); vptr_array[id][i] = malloc(SIZE); memset(vptr_array[id][i], rand(), SIZE); // make sure we actually have pages allocated t.tock(); assert(!(reinterpret_cast<unsigned long long>(a) & 0xFFFFF)); #if defined(__GNUC__) __builtin___clear_cache((void *) vptr_array[id][i], (void *) vptr_array[id][i] + (SIZE)); #endif times[id][i] = t.get_time(); ptrs.push_back(a); } for (int i = 0; i < N_ALLOCS; i++) { free(vptr_array[id][i]); vptr_array[id][i] = NULL; } pthread_exit(NULL); } static void testAllocation_output() { FILE *fp; int id[THREAD_NUM]; pthread_t threads[THREAD_NUM]; /* Different thread_num different file */ char s[10]; sprintf(s, "output_%d", THREAD_NUM); fp = fopen(s,"a+"); /* Separate size to each thread */ SIZE = pow(2,power_size); for (int i = 0; i < THREAD_NUM; i++){ id[i] = i; pthread_create(&threads[i], NULL, do_malloc, (void*)&id[i]); } for (int i = 0; i < THREAD_NUM; i++) pthread_join(threads[i], NULL); double sum = 0.0; for (int i = 0; i < THREAD_NUM; i++) sum += count_sum(i); fprintf(fp, "%zubytes %.10lf\n", SIZE, sum); fclose(fp); } static void testAllocation() { FILE *fp; int id[THREAD_NUM]; pthread_t threads[THREAD_NUM]; /* Separate size to each thread */ SIZE = pow(2,power_size); for (int i = 0; i < THREAD_NUM; i++){ id[i] = i; pthread_create(&threads[i], NULL, do_malloc, (void*)&id[i]); } for (int i = 0; i < THREAD_NUM; i++) pthread_join(threads[i], NULL); } int main(int argc, char **argv) { clock_speed_ghz = 1.6; THREAD_NUM = atoi(argv[1]); power_size = atoi(argv[2]); testAllocation(); testAllocation_output(); return 0; } ``` + thread_num = 2 ![image alt](http://imgur.com/XsQNnEF.png) + thread_num = 4 ![image alt](http://imgur.com/OEq6u8P.png) + thread_num = 8 ![image alt](http://imgur.com/LRrMxRf.png) + thread_num = 16 ![image alt](http://imgur.com/4hfqfmf.png) + thread_num = 32 ![image alt](http://imgur.com/ALWmtXu.png) + thread_num = 64 ![image alt](http://imgur.com/Vc13qJs.png) + 以上可以觀察出幾個點 + 這邊我們可以看到 **caching** 所帶來的好處，執行時間都比實驗二還要短 + 另外也可以看到對於 **SuperMalloc** 做 caching 所提昇的效能是很明顯的，在 8 個以上的 threads 在分配 32 bytes 以上的 objects 都比 **Ptmalloc** 還要好 ## 觀察 mutex_lock 的效能瓶頸 ### mutrace 想起之前作業曾經看到 **mutrace** 可以查看 mutex_lock 的 contention 狀況，結果一定要用 glibc 的 memory allocator ... 或是要重新自己改 **mutrace** 了 ``` stanle@stanle-mac:~/course/ncku/sysprog21/project1/malloc_benchmark$ LD_PRELOAD=../../project1/SuperMalloc/release/lib/libsupermalloc_pthread.so mutrace ./sizebenchmark 4 7 mutrace: Detected non-glibc memory allocator. Your program uses some mutrace: alternative memory allocator (jemalloc?) which is not compatible with mutrace: mutrace. Please rebuild your program with the standard memory mutrace: allocator or fix mutrace to handle yours correctly. ``` ## rpmalloc 作者也提供了 [benchmark](https://github.com/rampantpixels/rpmalloc-benchmark) 跟目前大家會拿來比較的 memory allocator，比如說 tcmalloc, hoard, ptmalloc3 jemalloc, scalloc 等，甚至在最近把 supermalloc 也一併加入比較，我們接著把他們所提供的 benchmark 試著重現一遍。 + 雖然看到 README 上有提示 build 的步驟，但是下意識還是會找 `make` or MAKEFILE，結果原來是採用另外一種 build code 的流程 [Ninja](https://ninja-build.org/) + configure before code building ``` $ python confiure.py -h ``` 可以看到以下可以設定的選項： ``` usage: configure.py [-h] [-t {windows,linux,macosx,bsd,ios,android,raspberrypi,pnacl,tizen}] [--host {windows,linux,macosx,bsd,ios,android,raspberrypi,pnacl,tizen}] [--toolchain {msvc,gcc,clang,intel}] [-c {debug,release}] [-a {x86,x86-64,ppc,ppc64,arm6,arm7,arm64,mips,mips64,generic}] [-i INCLUDEPATH] [--monolithic] [--coverage] ``` 所以我們照以下設定來跑這次的效能測試 ``` $ python configure.py -t linux --toolchain gcc -a x86-64 ``` 跑完後會產生 **build.ninja** 這個檔案，下面即是此檔案開頭部份內容 : ``` ninja_required_version = 1.3 # configure.py arguments configure_args = -t linux --toolchain gcc -a x86-64 # configure options configure_target = linux configure_host = linux configure_toolchain = gcc configure_archs = x86-64 configure_configs = buildpath = build/ninja/linux target = linux config = toolchain = cc = gcc cxx = g++ ar = ar link = gcc includepaths = moreincludepaths = ... ... ``` + build ``` $ ninja ``` \* 過程遇到 **jemalloc**`MADV_FREE` 沒有被宣告的 error，查了手冊 `MADV_FREE` 是在 linux kernel 4.5 之後才有的，我的環境目前是 4.4，目前我先跳過 jemalloc 的 驗證，先繼續跑下去 + run ``` $ sh runall.sh ``` 就會針對所有的 malloc 跑 benchmark + benchmark 先來解釋 benchmark 的驗證方式： + 指標一：每秒可以做幾次 malloc operation + 指標二：memory overhead (會用到實際使用的 virtual memory size 與 requested allocated memory 做計算) + 使用參數： `benchmark <num threads> <mode> <distribution> <cross-thread rate> <loop count> <block count> <op count> <min size> <max size>` + <num threads> 可以設定幾個 threads 來跑 + <mode> 可以選擇是 random or fixed 來決定所分配到的 size 的分佈 + 如果是 mode 選 random，那是要何種 distribution + 前一點 size 選擇的範圍會是 [<min size>,<max size>] + 會跑 <loop count> 次的迴圈做 allocate 動作 + 每跑 <cross-thread rate> 次的迴圈會做一次 cross-thread deallocation (舉例來說就是從 threadA 做 allocation，會把這些 allocated memory 丟給 threadB 做 deallocation) + 目標分配 <block count> 個 blocks + 每次 loop iteration 會選其中的 <op count> 個 blocks 做 deallocation 再 allocation ### rpmalloc 機制 * 每個 thread 有獨自的 heap and memory block，不超過 2 MiB * 對於大的空間需求，直接 map 與 unmap * 每個 Spans 只會對應到一種 size class * Spans 所包含的 pages 是可以流動的，與 ptmalloc 較為不同的是，一次必須整個 page 流動，不可只流動一個 block * 基於 64 KiB 對齊 * block 以 size 主要分為三種種類，大 [16, 2032]、中 (2032, 32720]、小 (32720, 2097120]，單位為 bytes * Small block: 16 bytes, 127 buckets * Medium block: 512 bytes, 60 buckets * Large blocks: 64KiB granularity, 32 buckets * 所有的空間需求都會對齊到 size class，例如：an allocation of 34 bytes will allocate a block of 48 bytes * 每種 block size 都有個 associated span configuration 用來描述 allocate 時需要多少 pages * 有四層機制來減少 map/unmap * 在各種 size class 下，各 thread 的都有 single active span * 在各種 size class 下，thread 都有個 list 紀錄空閒的 span * 在每個 span 配置中，thread 都有個 list 紀錄空閒的 span * 在每個 span 配置中，Global 有個 list 紀錄空閒的 span * 每個中小 size class 都會持續追蹤有多少 blocks allocated 或 free，用一條 list 紀錄哪些 blocks 是可以被分配的 * 每個 span 完全屬於分配自己的那個 thread，跨 threads 的 deallocations 都會被推遲到 span 主人 thread 那邊去做 * 對於 Large blocks 有兩層 cached 的機制，在 allocations 會先檢查 thread 的 free list，再來會往 global 的 free list 尋找，當 free list 中找不到可用空間時，才會再跟記憶體要空間 ### 效能分析 #### THREAD_NUM=4 ![](https://i.imgur.com/3zeQckI.png) #### THREAD_NUM=128 ![](https://i.imgur.com/anYjkoM.png) #### THREAD_NUM=16384 ![](https://i.imgur.com/JK71zSh.png) ### 程式碼分析 為了改善效能，先來理解一下程式碼寫了什麼 ```clike= void* rpmalloc(size_t size) { #if ENABLE_VALIDATE_ARGS if (size >= MAX_ALLOC_SIZE) { errno = EINVAL; return 0; } #endif return _memory_allocate(size); } ``` 當第三行的 ENABLE_VALIDATE_ARGS 設成 1 時，就會檢查 malloc 的 size，並且保證 global entry 的 size 不會導致 overflow ```clike= static void* _memory_allocate(size_t size) { if (size <= MEDIUM_SIZE_LIMIT) return _memory_allocate_from_heap(_memory_thread_heap, size); else if (size <= LARGE_SIZE_LIMIT) return _memory_allocate_large_from_heap(_memory_thread_heap, size); //Oversized, allocate pages directly size += SPAN_HEADER_SIZE; size_t num_pages = size / PAGE_SIZE; if (size % PAGE_SIZE) ++num_pages; span_t* span = _memory_map(num_pages); atomic_store32(&span->heap_id, 0); //Store page count in next_span span->next_span = (span_t*)((uintptr_t)num_pages); return pointer_offset(span, SPAN_HEADER_SIZE); } ``` 若 malloc 的 size 是屬於中、小型的種類，從中、小 heap 中取空間 若 malloc 的 size 是屬於大型的種類，則有一個獨立出來的 large size 的 heap，會從這個 heap 取空間 若 malloc 的 size 比大的種類還大的話，則計算需要多少 pages，直接跟記憶體直接要空間，並將 span 中有多少 pages 紀錄在 next_span 這個 member data 裡 最後回傳 span 的起點指標: 前 SPAN_HEADER_SIZE 位置是用來紀錄一些要維持 rpmalloc 所需的空間，span 真正的起點須為 malloc 後的位置 + SPAN_HEADER_SIZE > 將 pages 的個數除存在 next_span 裡的用意不太清楚 > 猜測是紀錄 num_pages 之後就可以計算這個 span 的大小，在這個大小之後即可得到下個 span > [name=Cayonliow][color=#4bed91] ```clike= static int _memory_deallocate_deferred(heap_t* heap, size_t size_class) { //Grab the current list of deferred deallocations atomic_thread_fence_acquire(); void* p = atomic_load_ptr(&heap->defer_deallocate); if (!p) return 0; if (!atomic_cas_ptr(&heap->defer_deallocate, 0, p)) return 0; //Keep track if we deallocate in the given size class int got_class = 0; do { void* next = *(void**)p; //Get span and check which type of block span_t* span = (void*)((uintptr_t)p & SPAN_MASK); if (span->size_class < SIZE_CLASS_COUNT) { //Small/medium block got_class |= (span->size_class == size_class); _memory_deallocate_to_heap(heap, span, p); } else { //Large block got_class |= ((span->size_class >= size_class) && (span->size_class <= (size_class + 2))); _memory_deallocate_large_to_heap(heap, span); } //Loop until all pending operations in list are processed p = next; } while (p); return got_class; } ``` 這個函式是用來處理使用者先前 deallocate 的空間，會推遲到這個函式呼叫時才 deallocate 先檢查如果沒有需要 deallocate 的空間就會直接 return 一次處理一個 deallocate，並回傳釋放了哪種 size class(大中小)，即可知道經過這次釋放空間後有哪些 size class 有可用空間 * _memory_allocate_from_heap * 先試著從當前可以使用的 span 中找合適可用的 block，因為他們儲存在 heap 中，可以最快存取使用 * 將還沒處理的 deallocations 先處理完，再尋找是否有合適空間 * 尋找別人正在使用但還有空間的 span，試著共用 * 從 thread cache 拿看看有沒有可用 span * 從 global cache 抓一串 span 到 thread cache 使用 * 若連 global cache 都找不到可用空間，跟記憶體 mapping 一些新的 pages 來使用 * _memory_allocate_large_from_heap * 從合適大小的 thread cache 中檢查是否有可用的 span * 將還沒處理的 deallocations 先處理完，再次檢查 thread cache 中是否有可用 span * 從 global cache 中試著拿一串 spans 來 thread cache 中 * 若連 global cache 都沒有可用空間，則跟記憶體 mapping 新的 pages 來使用 新見型態 uintptr_t、ptrdiff_t ## Begun/lockfree-malloc [Begun/lockfree-malloc github](https://github.com/Begun/lockfree-malloc) 這個 malloc 實作是使用 C++ 撰寫 因此如果要建立 靜態/動態函式庫 必須使用 g++ 而執行 lockfree-malloc 的要求則是有支援 mmap/munmap 並且要在 x86_64 CPU 上 從這邊可以看出這個 malloc 是基於 64 位元去開發的 至於 lockfree 是使用 C++ 的 std::atomic 去實現 在處理分配的指標跟儲存 free 的指標都是用 std::atomic 避免多個執行緒同時呼叫導致錯誤 這邊先來解釋一下它的一些名詞，方便理解其設計理念 ( ) 內為程式碼使用的名稱 - SUPERBLOCK (Sb) - 是 lockfree-malloc 的最基礎單位 - 像是 chunk 的存在 - SUPERBLOCK_CACHE (Sb_cache) - 負責利用 mmap/munmap 管理 SUPERBLOCK - 如 CACHE 之名，free 的時候會把小於 LITE_MALLOC_SUPERBLOCK_CACHE_SIZE 保存起來 - Pool (Pool) - 在分配較小 size 時，會從這邊分配 - 每個 Pool 都只有一個分配的 size (elem_size) - 第一次分配時，會使用 Sb_cache 要一塊 Sb 來使用 - 當這邊分配出去的 空間 被 free 掉，會回到 Pool 裡等待再次被分配 - Engine (Engine) - 是核心的分配器 - EnginePool (EnginePool) - 為了多執行緒而設計 - 預設設定會為每個 thread 配置一個特定的 engine - 加快分配的速度 從原始碼可以觀察到，不像 ptmalloc 會使用到 brk() sbrk() lockfree-malloc 只有使用 mmap() / munmap() 來向系統取得記憶體 並且秉持著 64 位元有很多記憶體可以使用，因此浪費是沒關係的 但是並不會造成 fragment 跟 memory leak ### 效能分析 利用前面學長們所設計的 benchmark - 2^2^ - 2^22^ bytes allocation in very threads number ![](https://i.imgur.com/WtyBjo4.png) 發現到在 16 條以前都很接近，之後 lockfree-malloc 輸給 ptmalloc - **100 objects allocated, avg. elapsed time (100 runs)** - 1 thread ![](https://i.imgur.com/oGjWoX4.png) - 2 threads ![](https://i.imgur.com/wB0bwWn.png) - 4 threads ![](https://i.imgur.com/HxxBJ9i.png) - 8 threads ![](https://i.imgur.com/jiuqDoL.png) - 16 threads ![](https://i.imgur.com/8wUyk3L.png) - 32 threads ![](https://i.imgur.com/kwG3YNt.png) - 64 threads ![](https://i.imgur.com/zV02ZxU.png) ### 論文 後來有發現一份論文，但不是屬於前面 Begun/lockfree-malloc 是一份研究如何用 lockfree 來改善 alloc [Scalable Lock-Free Dynamic Memory Allocation](https://pdfs.semanticscholar.org/068d/0b393db03678ea1d346ee01871e91e88c560.pdf) ## OpenStack ### [Usage](https://hackmd.io/s/HyS7SLdyb) ## ptmalloc ## Daniel Micay allocator [Daniel Micay allocator](https://github.com/thestinger/allocator) ## 問題區 + 讀論文突然有個疑問，看論文中的作法和在去年同學的共筆中都有提到 `malloc()` 是用 memory pool 的作法來減少對 system call `brk()` `mmap()` 的使用，但是課堂中也有幾次作業是想利用先分配 memory pool 的方式，來減少實際在程式執行中因為呼叫 `malloc()` 所帶來的成本，這樣我的疑問是既然本來 `malloc()` 就有 memory pool 的管理機制，那我們自己做 memory pool 所想要減少的成本是指什麼呢？ > malloc() 只是事前分配好哪個區段的 memory 是給甚麼樣的 size 來配置，而作業中的 memory pool 則是預先將要使用的記憶體一次配置完畢，減少這之中的 overhead[name=ierosodin][color=#55AA55] > 我重新看過 glibc 的 ptmalloc 的運作方式後 > 減少成本應該是 malloc 時，他需要去判斷當前的 memory pool(也是 ptmalloc 本身管理的 heap) 的 空閒空間 是否足夠拿來分配，如果不夠的話就需要將 memory pool(heap) 變大 > 而如果 ptmalloc 每次變大的 size 比我們自己設計的 memory pool 變大的 size 還要小 > 那麼使用 ptmalloc 的成本就會來的比我們自己設計還要多 > 而這個差距也是我們減少的成本 > [name=李東霖][color=#d3ea5d] + 論文中提到 per-thread cache 是怎做到的呢？ + 使用 SuperMalloc 之後，記憶體配置的速度反而變慢了 ## 參考資料 * [github source](https://github.com/kuszmaul/SuperMalloc) * [wiki-HTM](https://en.wikipedia.org/wiki/Transactional_memory) * [What is transactional memory?](http://stackoverflow.com/questions/11255640/what-is-transactional-memory) * [transactional memory](http://www.cs.cmu.edu/afs/cs/academic/class/15418-s12/www/lectures/20_transactionalmem.pdf) (cmu) * [infoQ](https://www.slideshare.net/InfoQ/understanding-hardware-transactional-memory) * [TCMalloc小记](http://blog.csdn.net/chosen0ne/article/details/9338591) (講解 TCMalloc 運作方式與安裝方式) * [中譯 How tcmalloc Works](http://blog.chinaunix.net/uid-24990614-id-3911071.html) * [Malloc 介紹](http://blog.csdn.net/efren_yang/article/details/46722997) * [Memory Allocation](https://hackmd.io/s/B1SRlfeee) * [tcmalloc](https://github.com/google/proto-quic) * [Linaro's malloc improvements](https://wiki.linaro.org/WorkingGroups/ToolChain/LibraryPerformance/GlibcPerformance/GlibcMalloc) * [Malloc Microbenchmark](http://www.lmdb.tech/bench/inmem/malloc/)
Last changed by  
 
蔡玉倫 (team_alun)
2845
Published on HackMD