在這里主要向大家做一個(gè) Databend 性能調(diào)優(yōu)相關(guān)的分享，共會(huì)分為三次向大家介紹，如下所示：
1、基礎(chǔ)篇：代碼調(diào)優(yōu)的前置知識(shí)（https://mp.weixin.qq.com/s/WTCL6w9ur6DyIBUWt1TvQA ）
2、實(shí)踐篇1：Databend 源碼性能調(diào)優(yōu)實(shí)踐
3、實(shí)踐篇2：Databend 的 Group By 聚合查詢(xún)?yōu)槭裁磁艿倪@么快？
Databend 是基于 Rust 語(yǔ)言開(kāi)發(fā)面向云原生設(shè)計(jì)的數(shù)據(jù)倉(cāng)庫(kù)。Rust 是近幾年比較火的系統(tǒng)編程語(yǔ)言，它具有零額外開(kāi)銷(xiāo)的抽象成本，并且有貼近 C++ 的運(yùn)行性能。
但這并不意味著使用 Rust 實(shí)現(xiàn)的代碼一定比使用 Python 實(shí)現(xiàn)的開(kāi)發(fā)要快，在沒(méi)有理解本質(zhì)的情況下，Rust 依然能寫(xiě)出低效率的代碼，這其實(shí)取決于編程人員的水平，只是 Rust 讓我們更容易寫(xiě)出高效的代碼。
下面將根據(jù)多個(gè)例子，來(lái)講講編程中常見(jiàn)的一些優(yōu)化點(diǎn)，這些優(yōu)化點(diǎn)多以 Rust 實(shí)現(xiàn)為例，但其原理可以運(yùn)用在其他語(yǔ)言中。
本系列課程的視頻回放，可以點(diǎn)擊 https://www.bilibili.com/video/BV1zM4y1c7aW?spm_id_from=333.999.0.0 查看。
inline vs no inline
在 Rust 中，有三個(gè) hint 去做代碼的內(nèi)聯(lián)，如下所示：
#[inline],
#[inline(never)],
#[inline(always)]
在寫(xiě)代碼時(shí)，我們也盡量告訴編譯器我們所期望采用的方式。
內(nèi)聯(lián)有以下優(yōu)點(diǎn)：
a.內(nèi)聯(lián)作為一種優(yōu)化轉(zhuǎn)換，它可以取代對(duì)函數(shù)的調(diào)用，節(jié)省代碼的開(kāi)銷(xiāo)。
缺點(diǎn)
a. 代碼二進(jìn)制體積變大，使得編譯時(shí)間更糟。
b. 泛型函數(shù)可能會(huì)導(dǎo)致內(nèi)聯(lián)代碼膨脹.
注：
a.對(duì)于私有函數(shù)可能不需要內(nèi)聯(lián)，因?yàn)?LLVM 具有啟發(fā)式內(nèi)聯(lián)。
b.私有函數(shù)具有隱式內(nèi)聯(lián)。
Case 1
下圖所示代碼展示了兩段函數(shù) default_crc32() 和 inlined_crc32()，這兩段代碼所實(shí)現(xiàn)的功能為做一個(gè) crc32 的哈希，在 default_crc32() 是直接調(diào)用一個(gè) crc32 fast 的哈希庫(kù)，算出哈希值后，對(duì)數(shù)組進(jìn)行一次遍歷，得到其加總的結(jié)果；而在 inlined_crc32() 中，在 new() 函數(shù)、update() 函數(shù)加入了 inline。他們的運(yùn)行時(shí)間如下：
default_crc32 time: [16.184 ms 16.196 ms 16.209 ms]
inlined_crc32 time: [1.6317 ms 1.6353 ms 1.6396 ms]
從數(shù)據(jù)中，我們可以明顯的看出使用內(nèi)聯(lián)后性能有接近 10 倍的改善。
Case 2
在前面一個(gè)例子中，大家可以感受到內(nèi)聯(lián)對(duì)代碼性能帶來(lái)的提升。而不恰當(dāng)?shù)氖褂?，同時(shí)也會(huì)讓性能更差。但內(nèi)聯(lián)不是銀彈，下面這段代碼是使用了 inline（never）這段代碼。當(dāng)我們不使用這個(gè) hint 時(shí)候，我們的整個(gè)函數(shù)會(huì)被編譯器優(yōu)化成 inline 的，進(jìn)一步會(huì)導(dǎo)致 aggregate 里面的子函數(shù)就不會(huì)被 inline 了，但我們的程序執(zhí)行耗時(shí)大多在子函數(shù)中，因?yàn)樽雍瘮?shù)中使用了 loop 循環(huán)執(zhí)行 CPU 密集型操作。所以我們需要顯式地告訴編譯器不要 inline 外層函數(shù)，來(lái)達(dá)到 10% 左右的性能提升。
No extra allocation/copy
在寫(xiě)代碼時(shí)候，可能會(huì)存在著一些額外的分配及拷貝。我們可以通過(guò)對(duì)其進(jìn)行優(yōu)化，也能提升我們代碼的性能。
Case 3
select sum(number) from numbers_mt(10000000000)
再來(lái)看第三個(gè)例子，這個(gè)例子源于 Databend 開(kāi)發(fā)初期，當(dāng)我們生成 numbers 表時(shí)求一個(gè)到10000000000的加總值。在這個(gè)代碼中通過(guò)生成一個(gè) Vec<u64> 的數(shù)組，我們將其轉(zhuǎn)換成 Arrow 格式時(shí)，我們調(diào)用了 UInt64 Array::from() 這個(gè)函數(shù)，雖然我們將 data move 進(jìn)去了，但這個(gè)函數(shù)內(nèi)部還是調(diào)用了內(nèi)存拷貝，通過(guò) perf 工具可以看到 SQL 執(zhí)行的開(kāi)銷(xiāo)多在內(nèi)存拷貝中。
我們優(yōu)化的方式是去掉多余的內(nèi)存拷貝，使用了 unsafe 去生成 Arrydata，然后生成 Arrow 格式的 Array，最后讓整體性能提升了 2-3 倍。
Case 4.1
cast(number as Varchar) 這個(gè)例子是將一個(gè) NumberArray 轉(zhuǎn)換成 StringArray。在左邊的代碼中，邏輯是遍歷 NumberArray 將每行的數(shù)值轉(zhuǎn)換為字符串，然后返回一個(gè)迭代器，迭代器再去生成StringArray。但這段代碼產(chǎn)生了非常多的額外開(kāi)銷(xiāo)，由于他遍歷到每一個(gè)元素時(shí)，都會(huì)產(chǎn)生一個(gè)局部的 Vec<u8>，這里的 Vec<u8> 是非常離散的，并且使用一次后就會(huì)被丟棄，在這里就會(huì)產(chǎn)生大量的小內(nèi)存分配和回收，進(jìn)而導(dǎo)致性能變差。
在第一個(gè)版本的優(yōu)化中，我們?cè)谏闪艘粋€(gè)局部的 buffer，在數(shù)值轉(zhuǎn)為 string 的過(guò)程中，我們把序列化寫(xiě)入到這個(gè) buffer 中，再通過(guò) builder 去把數(shù)據(jù) push 進(jìn) arrow 的內(nèi)存格式中。這使得其性能提升至兩倍，但這個(gè) case 并沒(méi)有被優(yōu)化到極致。
Case 4.2
經(jīng)過(guò) Case 4.1 的優(yōu)化，我們繼續(xù)對(duì)其優(yōu)化。因?yàn)樵谏鲜?Case 中我們用到了一個(gè) buffer，但其實(shí)我們可以直接移除 buffer。這里我們用一個(gè)閉包函數(shù)，在數(shù)值轉(zhuǎn) String 的過(guò)程中，直接往 arrow 的內(nèi)存模型中進(jìn)行寫(xiě)入，無(wú)需額外的內(nèi)存分配和拷貝，對(duì)比前一個(gè)版本，可以再提升兩倍左右的性能。
Case 5
Databend 在開(kāi)發(fā)的過(guò)程中，也會(huì)有一些些早期的代碼寫(xiě)的不夠好，比如我們?cè)谑占瘍?nèi)存分配的時(shí)候，我們個(gè) MemoryTracker 變量存儲(chǔ)在 thread_local 中，去獲取 runtime_tracker 的時(shí)候，左邊的代碼多了一個(gè) Arc 的 clone，右邊的代碼是返回的引用，雖然clone 本身開(kāi)銷(xiāo)并不是很大，但是在 SQL 執(zhí)行過(guò)程中，我們會(huì)臨時(shí)地去分配很多小的內(nèi)存，所以每一次分配的都會(huì)去調(diào)用這個(gè) get 方法，就會(huì)大大降低其性能。
另外，我們還做了一次優(yōu)化是，并不是每次內(nèi)存分配都會(huì)去實(shí)時(shí)反饋到全局統(tǒng)計(jì)變量中，因?yàn)槎嗑€(xiàn)程去更新全局變量需要同步操作，所以我們這里做了統(tǒng)計(jì)值的線(xiàn)程內(nèi)部緩沖更新，避免小內(nèi)存分配統(tǒng)計(jì)影響性能。
Less extra function call
Case 6
下面的例子是 Arrow 中的一個(gè)排序函數(shù)，例如在 SQL:
排序的列是 a，但其余的列也要跟著 a 的順序走，arrow 的執(zhí)行流程是先將索引按照 a 進(jìn)行排序，下面的例子就是索引排序的過(guò)程，排序我們需要按照 a 列在不同 index 中的值進(jìn)行比較，然后根據(jù)結(jié)果決定是否交換 index。
左邊的實(shí)現(xiàn)是閉包捕獲了array，但我們根據(jù) index 那對(duì)應(yīng)的值需要調(diào)用 array.values().as_slice().get_unchecked(), 這里有 3 次函數(shù)調(diào)用，如果 array 的長(zhǎng)度很長(zhǎng)，這個(gè)調(diào)用開(kāi)銷(xiāo)的放大是非?？捎^(guān)的。我們的優(yōu)化過(guò)程也非常簡(jiǎn)單，我們把 values 先引用到一個(gè)變量中，之后閉包就會(huì)直接去捕獲 values。這個(gè)優(yōu)化大約可以達(dá)到 25% 的性能提升。
Less branch prediction miss
大家應(yīng)該都熟悉分支預(yù)測(cè)可以利用 CPU 亂序執(zhí)行來(lái)提升性能。但是分支預(yù)測(cè)失敗了，返回會(huì)大大影響性能性能 。請(qǐng)大家來(lái)看以下的幾個(gè)例子。
Case 7
下面的例子是在一個(gè)循環(huán)中，每次循環(huán)都會(huì)調(diào)用 unwrap 函數(shù)，這個(gè) unwrap 函數(shù)在 Rust 其實(shí)就是一次 if else 封裝，因此這里會(huì)有分支預(yù)測(cè)的開(kāi)銷(xiāo)。分支預(yù)測(cè)通常來(lái)說(shuō)是有緩存的，但在這個(gè)函數(shù)中，分支預(yù)測(cè)的緩存似乎工作的不太友好。
對(duì)他優(yōu)化的方式是迭代器生成封裝到一個(gè)方法中，從而去除多余的分支預(yù)測(cè)。
Case 8
這個(gè)例子是 abs 函數(shù)的實(shí)現(xiàn)。在這里我們是去對(duì) int8 這個(gè)函數(shù)進(jìn)行一次遍歷并求絕對(duì)值，map 判斷了 null 的情況，如果原始值是 null，結(jié)果依然需要為 null。Arrow 的內(nèi)存模型是有兩個(gè) array 的，它的第一個(gè) array 是一個(gè) int8 的數(shù)組，第二個(gè) array 是一個(gè) bitmap。我們的優(yōu)化方式是先忽略 null，直接遍歷 int8 數(shù)組，進(jìn)行 abs 的 transform，然后將輸入的 bitmap 進(jìn)行 clone 給結(jié)果數(shù)組，從而去除了分支預(yù)測(cè)。由于類(lèi)似函數(shù)會(huì)很多，所以我們封裝了多個(gè) apply 函數(shù)進(jìn)行數(shù)組到數(shù)組的轉(zhuǎn)換。
Case 9
這里來(lái)自 ClickHouse 的一個(gè)例子。
SQL:
這個(gè) SQL 通常會(huì)有 2 個(gè)分支預(yù)測(cè)，一個(gè)判斷 number > 3，第二個(gè)判斷 number 是否有 null 值。在向量化 sum 中，我們用一些位操作來(lái)優(yōu)化分支開(kāi)銷(xiāo)。
SIMD
SIMD 指的是單指令多數(shù)據(jù)執(zhí)行。接下來(lái)我們會(huì)講到兩個(gè)關(guān)于 simd 的例子。
Case 10：simd sum
在我們的列數(shù)據(jù)庫(kù)中，非常常用的就是向量化執(zhí)行。首先，我們先來(lái)看第一段代碼，做的是對(duì) double 數(shù)組的一次求和。理想化的情況的是，我們的 CPU 執(zhí)行的如果最佳流水線(xiàn)，ADD 執(zhí)行的次數(shù)是 N 次。
現(xiàn)代的 CPU 中通常有一些特殊的優(yōu)化指令集，比如 SSE,AVX，通過(guò)這些指令對(duì)數(shù)據(jù)進(jìn)行批量的求和，這樣可以讓整體性能提升至 4 倍左右。
AVXAdd 的函數(shù)實(shí)現(xiàn)看起來(lái)比較丑陋，通常來(lái)說(shuō)我們不需要顯示的使用 AVXAdd，因?yàn)楝F(xiàn)代的編譯器已經(jīng)足夠智能優(yōu)化上面的代碼成 AVXAdd 方式執(zhí)行了，比如 GCC 的自動(dòng)向量化。
Case 11: null sum in arrow2
求和運(yùn)算中，我們通常要忽略 null 值，這樣可能會(huì)破壞自動(dòng)向量化的優(yōu)化，因?yàn)?null 值是 runtime 才能感知的。Rust有一些向量化的 crate 非常有用，比如說(shuō) Arrow2 中使用了packed_simd2, Rust 也即將迎來(lái)標(biāo)準(zhǔn)的 simd 庫(kù)。下面的例子是對(duì)含有 null 值得數(shù)組求和向量化代碼。
整體的原理是將數(shù)據(jù)按 chunk 分桶在一個(gè) simd 位寬中，然后運(yùn)用向量化的 select 將非 null 的值抽出到一個(gè)新的 selected 中求和。
自動(dòng)向量化
通常來(lái)說(shuō)，我們不會(huì)主動(dòng)編寫(xiě)向量化的代碼，而是讓循環(huán)中的邏輯盡量簡(jiǎn)單 （不引入分支），編譯器往往能給我們優(yōu)化出高效的代碼，比如在 not nullable 的 array 中進(jìn)行求和，自動(dòng)向量化的代碼反而比手動(dòng)向量化的代碼更加高效。
通過(guò)以上的 11 個(gè)例子，希望你已經(jīng)對(duì)代碼調(diào)優(yōu)有了更深入的了解，在下一次的分享中我們將介紹 Databend 的 group by 查詢(xún)?yōu)槭裁茨芘艿倪@么快。
想要了解更多資訊，歡迎關(guān)注公眾號(hào)：Databend
如果想了解更多，可以關(guān)注公眾號(hào)： Databend
