C++性能優化（十） —— JeMalloc

一、JeMalloc簡介

1、JeMalloc簡介

JeMalloc 是一款記憶體配置設定器，最大的優點在于多線程情況下的高性能以及記憶體碎片的減少。

GitHub位址：

https://github.com/jemalloc/jemalloc

2、JeMalloc安裝

JeMalloc源碼下載下傳：

git clone https://github.com/jemalloc/jemalloc.git

建構工具生成：

autogen.sh

編譯選項配置：

configure

編譯：

make -j4

安裝：

make install

二、JeMalloc架構

1、JeMalloc架構簡介

C++性能優化（十） —— JeMallocC++性能優化（十） —— JeMalloc

JeMalloc将記憶體分成多個相同大小的chunk，資料存儲在chunks中；每個chunk分為多個run，run負責請求、配置設定相應大小的記憶體并記錄空閑和使用的regions的大小。

2、Arena

Arena是JeMalloc的核心配置設定管理區域，對于多核系統，會預設配置設定4x邏輯CPU的Arena，線程采取輪詢的方式來選擇相應的Arena來進行記憶體配置設定。

每個arena内都會包含對應的管理資訊，記錄arena的配置設定情況。arena都有專屬的chunks, 每個chunk的頭部都記錄chunk的配置設定資訊。在使用某一個chunk的時候，會把chunk分割成多個run，并記錄到bin中。不同size class的run屬于不同的bin，bin内部使用紅黑樹來維護空閑的run，run内部使用bitmap來記錄配置設定狀态。

JeMalloc使用Buddy allocation 和 Slab allocation 組合作為記憶體配置設定算法，使用Buddy allocation将Chunk劃分為不同大小的 run，使用 Slab allocation 将run劃分為固定大小的 region，大部分記憶體配置設定直接查找對應的 run，從中配置設定空閑的 region，釋放則标記region為空閑。

run被釋放後會和空閑的、相鄰的run進行合并；當合并為整個 chunk 時，若發現有相鄰的空閑 chunk，也會進行合并。

3、Chunk

Chunk是JeMalloc進行記憶體配置設定的機關，預設大小4MB。Chunk以Page（預設為4KB)為機關進行管理，每個Chunk的前6個Page用于存儲後面其它Page的狀态，比如是否待配置設定還是已經配置設定；而後面其它Page則用于進行實際的配置設定。

4、Bin

JeMalloc 中 small size classes 使用 slab 算法配置設定，會有多種不同大小的run，相同大小的run由bin 進行管理。

run是配置設定的執行者, 而配置設定的排程者是bin，bin負責記錄目前arena中某一個size class範圍内所有non-full run的使用情況。當有配置設定請求時，arena查找相應size class的bin，找出可用于配置設定的run，再由run配置設定region。由于隻有small region配置設定需要run，是以bin也隻對應small size class。

在arena中，不同bin管理不同size大小的run，在任意時刻， bin中會針對目前size儲存一個run用于記憶體配置設定。

5、Run

Run是chunk的一塊記憶體區域，大小是Page的整數倍，由bin進行管理，比如8位元組的bin對應的run就隻有1個page，可以從裡面選取一個8位元組的塊進行配置設定。

small classes 從 run 中使用 slab 算法配置設定，每個 run 對應一塊連續的記憶體，大小為 page size 倍數，劃分為相同大小的 region，配置設定時從run 中配置設定一個空閑 region，釋放時标記region為空閑，重複使用。

run中采用bitmap記錄配置設定區域的狀态，bitmap能夠快速計算出第一塊空閑區域，且能很好的保證已配置設定區域的緊湊型。

6、TCache

TCache是線程的私有緩存空間，在配置設定記憶體時首先從tcache中配置設定，避免加鎖；當TCache沒有空閑空間時才會進入一般的配置設定流程。

每個TCache内部有一個arena，arena内部包含tbin數組來緩存不同大小的記憶體塊，但沒有run。

三、JeMalloc記憶體配置設定

1、JeMalloc記憶體配置設定

JeMalloc基于申請記憶體的大小把記憶體配置設定分為三個等級：small、large、huge。

Small objects的size以8位元組、16位元組、32位元組等分隔開的，小于Page大小。

Large objects的size以Page為機關，等差間隔排列，小于chunk（4MB）的大小。

Huge objects的大小是chunk大小的整數倍。

JeMalloc通過将記憶體劃分成大小相同的chunk進行管理，chunk的大小為2的k次方，大于Page大小。Chunk起始位址與chunk大小的整數倍對齊，可以通過指針操作在常量時間内找到配置設定small/large objects的中繼資料，在對數時間内定位到配置設定huge objects的中繼資料。為了獲得更好的線程擴充性，JeMalloc采用多個arenas來管理記憶體，減少了多線程間的鎖競争。每個線程獨立管理自己的記憶體arena，負責small和large的記憶體配置設定，線程按第一次配置設定small或者large記憶體請求的順序Round-Robin地選擇arena。從某個arena配置設定的記憶體塊，在釋放時一定會回到原arena。JeMalloc引入線程緩存來解決線程間的同步問題，通過對small和large對象的緩存，實作通常情況下記憶體的快速申請和釋放。

2、small記憶體配置設定

如果請求記憶體size不大于arena的最小的bin，那麼通過線程對應的tcache來進行配置設定。

small objects配置設定流程如下：

（1）查找對應 size classes 的 bin

（2）從 bin 中擷取未滿的run。

（3）從 arena 中擷取空閑run。

（4）從 run 中傳回一個空閑 region。

3、large記憶體配置設定

如果請求記憶體size大于arena的最小的bin，同時不大于tcache能緩存的最大塊，也會通過線程對應的tcache來進行配置設定，但方式不同。

如果tcache對應的tbin裡有緩存塊，直接配置設定；如果沒有，從chunk裡直接找一塊相應的page整數倍大小的空間進行配置設定；

4、Huge記憶體配置設定

如果請求配置設定記憶體大于chunk（4MB）大小，直接通過mmap進行配置設定。

四、多線程支援

1、JeMalloc多線程支援

JeMalloc對于多線程記憶體配置設定與單線程相同，每個線程從 Arena 中配置設定記憶體，但多線程間需要同步和競争，是以提高多線程記憶體配置設定性能方法如下：

（1）減少鎖競争。縮小臨界區，使用更細粒度鎖。

（2）避免鎖競争。線程間不共享資料，使用局部變量、線程特有資料(tsd)、線程局部存儲(tls)等。

2、Arena選擇

JeMalloc會建立多個Arena，每個線程由一個Arena 負責。JeMalloc預設建立4x邏輯CPU個Arena。

arena->nthreads 記錄負責的線程數量。

每個線程配置設定時會首先調用arena_choose選擇一個arena來負責線程的記憶體配置設定。線程選擇 arena 的邏輯如下:

（1）如果有空閑的(nthreads==0)已建立arena，則選擇空閑arena。

（2）若還有未建立的arena，則選擇新建立一個arena。

（3）選擇負載最低的arena (nthreads 最小)。

3、線程鎖

線程鎖盡量使用 spinlock，減少線程間的上下文切換。Linux作業系統可以在編譯時通過定義JEMALLOC_OSSPIN宏可以指定使用自選鎖。

為了縮小臨界區，arena 中提供多個細粒度鎖管理不同部分：

（1）arenas_lock: arena 的初始化、配置設定等

（2）arena->lock: run 和 chunk 的管理

（3）arena->huge_mtx: huge object 的管理

（4）bin->lock: bin 中的操作

4、tsd

當選擇完arena後，會将arena綁定到tsd中，直接從tsd中擷取arena。

tsd用于儲存每個線程本地資料，主要arena和tcache，避免鎖競争。tsd_t中的資料會在第一次通路時延遲初始化，tsd 中各元素使用宏生成對應的 get/set 函數來擷取/設定，線上程退出時，會調用相應的 cleanup 函數清理。

5、tcache

tcache 用于 small object和 large object的配置設定，避免多線程同步。

tcache 使用slab記憶體配置設定算法配置設定記憶體：

（1）tcache中有多種bin，每個bin管理一個size class。

（2）當配置設定時，從對應bin中傳回一個cache slot。

（3）當釋放時，将cache slot傳回給對應的bin。

6、線程退出

線程退出時，會調用 tsd_cleanup() 對 tsd 中資料進行清理：

（1）arena，降低arena負載(arena->nthreads--)

（2）tcache，調用tcache_bin_flush_small/large釋放 tcache->tbins[]所有元素，釋放tcache。

當從一個線程配置設定的記憶體由另一個線程釋放時，記憶體還是由原先arena來管理，通過chunk的extent_node_t來擷取對應的arena。

五、JeMalloc使用指南

1、JeMalloc庫簡介

JeMalloc提供了靜态庫libjemalloc.a和動态庫libjemalloc.so，預設安裝在/usr/local/lib目錄。

2、JeMalloc動态方式

通過-ljemalloc将JeMalloc連結到應用程式。

通過LD_PRELOAD預載入JeMalloc庫可以不用重新編譯應用程式即可使用JeMalloc。

LD_PRELOAD="/usr/lib/libjemalloc.so"

3、JeMalloc靜态方式

在編譯選項的最後加入/usr/local/lib/libjemalloc.a連結靜态庫。

4、JeMalloc生效

JEMALLOC_EXPORT void (*__free_hook)(void *ptr) = je_free;
JEMALLOC_EXPORT void *(*__malloc_hook)(size_t size) = je_malloc;
JEMALLOC_EXPORT void *(*__realloc_hook)(void *ptr, size_t size) = je_realloc;

5、JeMalloc測試

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <time.h>

#define MAX_OBJECT_NUMBER       (1024)
#define MAX_MEMORY_SIZE         (1024*100)

struct BufferUnit{
   int   size;
   char* data;
};

struct BufferUnit   buffer_units[MAX_OBJECT_NUMBER];

void MallocBuffer(int buffer_size) {

for(int i=0; i<MAX_OBJECT_NUMBER; ++i)  {
    if (NULL != buffer_units[i].data)   continue;

    buffer_units[i].data = (char*)malloc(buffer_size);
    if (NULL == buffer_units[i].data)  continue;

    memset(buffer_units[i].data, 0x01, buffer_size);
    buffer_units[i].size = buffer_size;
    }
}

void FreeHalfBuffer(bool left_half_flag) {
    int half_index = MAX_OBJECT_NUMBER / 2;
    int min_index = 0;
    int max_index = MAX_OBJECT_NUMBER-1;
    if  (left_half_flag)
        max_index =  half_index;
    else
        min_index = half_index;

    for(int i=min_index; i<=max_index; ++i) {
        if (NULL == buffer_units[i].data) continue;

        free(buffer_units[i].data);
        buffer_units[i].data =  NULL;
        buffer_units[i].size = 0;
    }
}

int main() {
    memset(&buffer_units, 0x00, sizeof(buffer_units));
    int decrease_buffer_size = MAX_MEMORY_SIZE;
    bool left_half_flag   =   false;
    time_t  start_time = time(0);
    while(1)  {
        MallocBuffer(decrease_buffer_size);
        FreeHalfBuffer(left_half_flag);
        left_half_flag = !left_half_flag;
        --decrease_buffer_size;
        if (0 == decrease_buffer_size) break;
    }
    FreeHalfBuffer(left_half_flag);
    time_t end_time = time(0);
    long elapsed_time = difftime(end_time, start_time);

    printf("Used %ld seconds. \n", elapsed_time);
    return 1;
}

C++性能優化（十） —— JeMallocC++性能優化（十） —— JeMalloc