[Linux Kernel慢慢學]likely and unlikely macro

前言

在linux kernel source code中，有時候會看到在if內的邏輯判斷加上likely或unlikely的敘述來幫助compiler做最佳化，例如下方的兩個例子，我們從linux kernel source code中找了一些部分程式碼:

static ssize_t display_show_contrast(struct device *dev,
				struct device_attribute *attr, char *buf)
{
    struct display_device *dsp = dev_get_drvdata(dev);
    ssize_t rc = -ENXIO;

    mutex_lock(&dsp->lock);
    if (likely(dsp->driver) && dsp->driver->get_contrast)
        rc = sprintf(buf, "%d\n", dsp->driver->get_contrast(dsp));
    mutex_unlock(&dsp->lock);
    return rc;
}

139
140
141

 /* linux/drivers/video/display/display-sysfs.c, line=139 */
if (unlikely(!driver))
    return ERR_PTR(ret);

到底這樣寫有什麼用呢? 又是如何幫助compiler做最佳化的?

下面將會做一些簡單的介紹

likely / unlikely macro introduction

在Linux kernel 2.6之後提供了likely, unlikely 這兩個macro，他們被定義在/include/linux/compiler.h中

0 1	# define likely(x) __builtin_expect(!!(x), 1) # define unlikely(x) __builtin_expect(!!(x), 0)

__built_expect()是gcc的內建function，用來將branch的相關資訊提供給compiler，告訴compiler設計者期望的比較結果，以便對程式碼改變分支順序來進行優化。

而!!(x)是什麼意思，為什麼要這樣寫?

透過兩次NOT op來確保值一定是0 或 1
因為if內邏輯敘述的值可以是0或是非0的整數的，所以如果不做!!(x)就無法確保值一定是0或1
類似的技巧在[Linux Kernel慢慢學]ARRAY_SIZE macro in linux kernel這篇中也有用到

透過這兩個macro，可以讓compiler在編譯assembly code的時候做一些最佳化，考慮以下pseudo code:

if (likely(x)) {
    /* execute when x is true */ 
}
else {
    /* execute when x is false */
}

使用likely macro表示這段敘述(x)為true的機率比較大(比較常發生)，告訴compiler將x==ture的對應執行程式碼接在判斷後面
使用unlikely macro表示這段敘述(x)為true的機率比較小(不常發生)，告訴compiler將x==false的對應執行程式碼接在判斷後面

這樣做有什麼好處呢?

Advantage of using likely / unlikely

這和cache和memory的機制有關，有上過計算機組織的可能就比較了解，今天當我們需要某些資料時，我們會先去檢查cache是否有我們需要的資料:

cache hit: 如果有則從cache直接拿
cache miss: 如果沒有則從memory搬到cache中，但這裡一次是搬一個區塊的資料

而Spatial Locality這個特性就是在說，一記憶體位置被存取後，其附近的記憶體位置也極可能一同被存取。

題外話，cache還有一種特性叫做Temporal Locality，不過這裡就不講了

聰明的你應該知道了，如果程式碼被放到比較相近的位置，那他們就可能一起被搬到cache中，增加cache hit的機率，有可能可以提升程式的執行效能。

而likely / unlikely macro就是在將比較可能的部分往前移 / 比較不可能的部分往後移。

Assembly code analysis

實際上assembly code到底會發生什麼改變呢? 我們來做個簡單的觀察

給一段簡單的c code，使用了likely macro:

//#include <stdio.h>
#define likely(x)    __builtin_expect(!!(x), 1)
#define unlikely(x)  __builtin_expect(!!(x), 0)

void foo();
void bar();

int main(char *argv[], int argc)
{
   if (likely (argc == 2))
      foo();
   else
      bar();
}

組譯出來的結果會是(ARM gcc 8.2, with O2 optimization):

main:
        cmp     r1, #2
        push    {r4, lr}
        bne     .L2
        bl      foo
.L3:
        mov     r0, #0
        pop     {r4, pc}
.L2:
        bl      bar
        b       .L3

可以發現在bne後面接的是foo

那如果我們將likely改成unlikely，我們會得到:

main:
        cmp     r1, #2
        push    {r4, lr}
        beq     .L6
        bl      bar
.L3:
        mov     r0, #0
        pop     {r4, pc}
.L6:
        bl      foo
        b       .L3

變成bar被移上去了，不過為了將bar放在前面，指令變成了beq

最後，這是gcc的optimization，所以如果在編譯的時候沒有開最佳化，__builtin_expect()並不會有任何效果，詳見gcc likely() unlikely() macros and assembly code 。

前言

likely / unlikely macro introduction

Advantage of using likely / unlikely

Assembly code analysis

References