Home » Posts tagged "branch"

Branchless UTF-8 解碼器

看到「A Branchless UTF-8 Decoder」這篇,先來回憶一下「非常經典的 UTF-8...」這篇,以及裡面提到的 encoding:

因為當初在設計 UTF-8 時就有考慮到,所以 decoding 很容易用 DFA 解決,也就是寫成一堆 if-then-else 的條件。但現代 CPU 因為 out-of-order execution 以及 pipeline 的設計,遇到 random branch 會有很高的效能損失,所以作者就想要試著寫看看 branchless 的版本。

成效其實還好,尤其是 Clang 上說不定在誤差內:

With GCC 6.3.0 on an i7-6700, my decoder is about 20% faster than the DFA decoder in the benchmark. With Clang 3.8.1 it’s just 1% faster.

而後來的更新則是大幅改善,在 Clang 上 DFA 版本比 branchless 的快:

Update: Björn pointed out that his site includes a faster variant of his DFA decoder. It is only 10% slower than the branchless decoder with GCC, and it’s 20% faster than the branchless decoder with Clang. So, in a sense, it’s still faster on average, even on a benchmark that favors a branchless decoder.

所以作者最後也有說這是個嘗試而已 XD:

It’s just a different approach. In practice I’d prefer Björn’s DFA decoder.

cURL 接下來的安全性更新...

cURL 的維護老大放話要大家注意接下來的安全性更新:「An alert on the upcoming 7.51.0 release」。

最少 11 個安全性更新:

This release will bundle no less than _eleven_ security advisories and their associated fixes (unless we get more reported in the time we have left).

由於這些 security issue 的特性,會採取不公開的 branch 修正再 merge 回來,再加上這麼大的數量,對於穩定性的衝擊是未知的:

Merging eleven previously non-disclosed branches into master just before a release is not ideal but done so to minimize the security impact on existing users when the problems get known.

所以目前的規劃是會在 release 的 48 個小時前公開 (希望藉由這封信讓有能力的人一起集中來看),藉此來降低衝擊:

My plan is to merge them all into master and push around 48 hours before release, watch the autobuilds closesly, have a few extra coverity scans done and then fix up what's found before the release.

這安全更新的數量好像有點多 orz

CPU Branch Prediction 的成本...

在公司搞定一個速度最佳化的問題,想到之前在 Stack Overflow 上有看到 CPU branch prediction 的問題 (跟我解的問題應該沒關係,只是剛好想到),把文章找出來...

出自 Stack Overflow 上有人詢問某段 C++ 程式為什麼加上 sort 後快多了:「Why is processing a sorted array faster than an unsorted array?」。

發文者的範例程式已經簡化到很容易理解:先產生一個 32Kytes 的 array,然後裡面塞亂數。

接下來把每個 byte 當作 unsigned char,要找出這個 array 裡面所有值大於等於 128 的元素,把這些元素的值加起來。

原發文者發現,如果先把這個 array 排過再計算,十萬次只要 1.93 秒,但如果不排就直接計算需要 11.54 秒,時間差不多是原來的六倍。

回答的人答的相當詳細,還給了一個 branchless 的 hack 來解這個問題 (於是就不需要先 sort),很值得一看。