Try   HackMD

Malloc 對於多執行緒程式的效能影響

contributed by <ierosodin>, <refleex>, <stanleytazi >

好讀版本

開發的同學可以移至好讀版本來做筆記，這邊可以留存，如果想要報告時用投影片模式，可以使用

github

預期要做的事情

  • 讀 SuperMalloc 論文
  • 讀上學期關於 針對多執行緒環境設計的 Memory allocator 的共筆
  • SuperMalloc 的使用
  • 決定要採用何種評估效能的程式(方式)
  • rpmalloc
  • Begun/lockfree-malloc
  • Daniel Micay 的 allocator
  • Openstack
  • 在 cloud 上跑 malloc
  • opic

比較 Daniel Micay 的 allocator [2] 和下方兩個 allocator 實作的效能:

背景知識

Multicore Storage Allocation (Dr.Dobb's)

此篇文章提到在 multicore(or multi-thread) 環境下做 memory allocation/deallocation 有幾個要考慮的議題:

  • Thread safty
  • Overhead and Contention
  • Memory drift
  • False sharing

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

False sharing (count.)

這問題是指說如果兩個 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 ( 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 的課程講義提供的資料，可以看到使用 HTM 在 Balanced Tree 下不管多少個 processors 都可
    以有很好的效能

#論文筆記

SuperMalloc: A Super Fast Multithreaded Malloc for 64-bit Machines

Different malloc

  • C/C++ 中動態記憶體配置相關的函式： malloc() free()
  • 衡量一個 allocator cost 的主要因素： speed 、 footprint 、 complexity

  • 配置記憶體主要分成兩個步驟：
    • 呼叫 mmap() 來取得一段連續的虛擬記憶體
    • 當程式實際使用到這個虛擬記憶體時，會發生 page fault( page table 中找不到)，於是配置一段實體記憶體，有實體記憶體對應的 page 稱為 committed page ，反之，則稱為 uncommitted page

  • 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

不懂這句是如何實現，是說一定會保證同一種 size 一定會在同一個 cache line 裡面嘛？stanleytazi

  • 對於 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

  • 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.

實驗

環境

$ 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
在 phonebook_concurrent 中，將程式改成在 append() 時直接對 DICT_FILE 做 memory map，然後每個 thread 盡量平均分配處理 map 後的 names，所以每個 thread 會各自的使用 malloc() 建立 entry node


























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

      • thread num = 16

可以明顯發現，使用 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






















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）

實驗二：去年共筆 提供的malloc_benchmark

參考：https://github.com/jffrosen/fragbench
更改後 TempoJiJi 的版本：https://github.com/TempoJiJi/malloc_benchmark

  • 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
    • 4 threads
    • 8 threads
    • 16 threads
    • 32 threads
    • 64 threads
  • 1000 objects allocated, avg. elapsed time (100 runs)
    • 這次我們每個 thread 還有每個 size 都分配 1000 個 objects

image alt
image alt
image alt
image alt
image alt
image alt

實驗三：延續實驗二，但加入 free()

對比實驗二一直只有做 malloc() 的動作，因為有看到 SuperMalloc 會將 free 掉的 memory 有 caching 的機制，另外也看到 paper 中有一個 benchmark 是producer 一直在做 malloc() ， 而 consumer 會一直 free() ，所以我們也想加入 free() 的行為來觀察執行時間。可以看到我們連續做了兩次的 do_malloc()，每一次做完後都會把所有分配的 memory free 掉，然後我們針對第二次的 do_malloc() 去統計時間



















































































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

  • thread_num = 4
    image alt

  • thread_num = 8
    image alt

  • thread_num = 16
    image alt

  • thread_num = 32
    image alt

  • thread_num = 64
    image alt

  • 以上可以觀察出幾個點

    • 這邊我們可以看到 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 跟目前大家會拿來比較的 memory allocator，比如說 tcmalloc, hoard, ptmalloc3 jemalloc, scalloc 等，甚至在最近把 supermalloc 也一併加入比較，我們接著把他們所提供的 benchmark 試著重現一遍。

  • 雖然看到 README 上有提示 build 的步驟，但是下意識還是會找 make or MAKEFILE，結果原來是採用另外一種 build code 的流程 Ninja
  • 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

* 過程遇到 jemallocMADV_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

OpenStack

Usage

ptmalloc

問題區

  • 讀論文突然有個疑問，看論文中的作法和在去年同學的共筆中都有提到 malloc() 是用 memory pool 的作法來減少對 system call brk() mmap() 的使用，但是課堂中也有幾次作業是想利用先分配 memory pool 的方式，來減少實際在程式執行中因為呼叫 malloc() 所帶來的成本，這樣我的疑問是既然本來 malloc() 就有 memory pool 的管理機制，那我們自己做 memory pool 所想要減少的成本是指什麼呢？

malloc() 只是事前分配好哪個區段的 memory 是給甚麼樣的 size 來配置，而作業中的 memory pool 則是預先將要使用的記憶體一次配置完畢，減少這之中的 overheadierosodin

我重新看過 glibc 的 ptmalloc 的運作方式後
減少成本應該是 malloc 時，他需要去判斷當前的 memory pool(也是 ptmalloc 本身管理的 heap) 的 空閒空間 是否足夠拿來分配，如果不夠的話就需要將 memory pool(heap) 變大
而如果 ptmalloc 每次變大的 size 比我們自己設計的 memory pool 變大的 size 還要小
那麼使用 ptmalloc 的成本就會來的比我們自己設計還要多
而這個差距也是我們減少的成本
李東霖

  • 論文中提到 per-thread cache 是怎做到的呢？
  • 使用 SuperMalloc 之後，記憶體配置的速度反而變慢了

參考資料

Last changed by 
Guest
0
3735
Published on HackMD