最近網上衝浪的時候看到有人分享了自己最近一次性能優化的經驗。我向來對性能是比較敏感的，所以就點進去看了。 然而我越看越覺得蹊蹺，但本著“性能問題和性能優化要靠性能測試做依據”，我不能憑空懷疑別人吧，所以我做了完整的測試並寫下了這篇文章。 可疑的優化方案 分享者遇到的問題很簡單：他發現程式中超過一半的 ...
最近網上衝浪的時候看到有人分享了自己最近一次性能優化的經驗。我向來對性能是比較敏感的，所以就點進去看了。
然而我越看越覺得蹊蹺，但本著“性能問題和性能優化要靠性能測試做依據”，我不能憑空懷疑別人吧，所以我做了完整的測試並寫下了這篇文章。
可疑的優化方案
分享者遇到的問題很簡單：他發現程式中超過一半的時間花在strcmp上，並且在抓取調用棧等深入分析之後，他發現大部分strcmp調用都是在拿各種字元串和某個固定的字元串（比如表示成功狀態的“success”）進行比較，因此他想能不能針對這進行優化。
這裡稍微給不熟悉c/c++的人解釋下，strcmp函數用來比較兩個字元串的大小，當兩個字元串相同的時候，函數會返回0，c語言里想要判斷兩個字元串的內容是否相同只能使用這個函數。
好了，背景交代完，我們來看看他的優化方案：
既然經常和固定的字元串比較，那是不是能節約掉這樣的strcmp調用呢？
我們可以利用hash函數計算出的hash值，先計算出那個固定的字元串的hash值存下來，然後再計算與它比較的字元串的hash值；
現在strcmp就轉換成兩個hash值的比較了，不相同的hash值一定意味著字元串不同，可以直接返回false；
相同hash值的字元串有可能是因為hash衝突，所以還需要回退到調用strcmp；
hash值的比較本身就是一次整數的比較，非常快，比函數調用快得多，因此字元串不相等的情況可以得到優化；
系統里大多數時候和固定字元串比較的結果都是不相等，因此能被優化覆蓋的情況占大多數。
代碼寫出來大致是這樣的：
// 如果覺得inline里放static不舒服，可以把它們移出去變成文件作用域變數，當然不管怎麼樣對測試結果幾乎沒有影響
inline bool optimize_cmp(const char *str) {
static auto hasher = std::hash<std::string_view>{};
// 保存固定字元串的hash值，以後不會重覆計算
static const uint32_t target_hash = hasher(std::string_view{target});
// 計算和固定字元串進行比較的字元串的hash
const uint32_t h = hasher(str);
// hash不相等，則一定不相等
if (h != target_hash) {
return false;
}
// hash相等，得回退到strcmp進行進一步檢查
return std::strcmp(target, str) == 0;
}
看起來好像有幾分道理？但經驗豐富或者對性能優化研究較深的人可能會產生違和感了：
本質上這是把一次strcmp的調用轉換成了一次hash計算加一次整數值比較，但hash計算是比較吃cpu的，它真的能更快嗎？
性能測試
口說無憑，性能優化講究用數據說話。因此我們來設計一個性能測試。
首先當然是測試對象，就是上面的optimize_cmp(待比較字元串)和strcmp(固定字元串，待比較字元串)。
有人會說hash函數對optimize_cmp性能起決定性作用，沒錯是這樣的，所以我選了目前我測試出的在X86-64機器上最快的字元串hash，正好是標準庫（libstdc++）提供的std::hash<std::string_view>。另外我還追蹤了下為什麼libstdc++的hash這麼快，因為它用的是優化版的Murmur Hash演算法。雖說現在需要把字元串字面量轉換成string_view，但std::hash<std::string_view>依然是最快的，而且轉換本身不會花多少時間，對性能的影響幾乎可以忽略不計。
strcmp當然也有優化，x86平臺上它會儘量利用avx2指令。不過c++里還有個殺手鐧constexpr，它能在編譯階段就比較兩個字元串編譯期常量，這相當於是作弊，運行期直接都拿到現成的結果了還能比啥？所以為瞭解決這個問題需要用點小手段。
所以整體上方案是分成兩組測試，一組測試字元串不相等的也就是上面說的優化的場景，另一組測試字元串相等的情況看看性能損失有多少。
因為計算字元串hash需要遍歷整個字元串，因此為了避免strcmp("abcdefg", "a")這種不公平情況（strcmp在這時通常檢查完前幾個字元就知道誰大誰小是否相等了），比較用的字元串除了一個空字元，其他都儘可能和固定字元串一樣長且只修改最後一個字元來製造不相等，這樣大家的計算量至少從理論上來說是差不多的。
代碼如下：
const char *target = "abcdefgh";
// 用數組遍歷避免strcmp被編譯期計算
const char *not_match_data_set[] = {
"abcdefgj",
"abcdefgi",
"abcdefgg",
"abcdefgk",
"",
};
const char *match_data_set[] = {
target,
target,
target,
target,
target,
};
// 這裡開始是測試函數
void bench_strcmp_not_match(benchmark::State &stat)
{
for (auto _ : stat) {
for (const char *s : not_match_data_set) {
// 為了避免調用被優化掉，同時也兼顧測試了函數行為是否正確
if (std::strcmp(target, s) == 0) {
std::abort();
}
}
}
}
BENCHMARK(bench_strcmp_not_match);
void bench_optimized_not_match(benchmark::State &stat)
{
for (auto _ : stat) {
for (const char *s : not_match_data_set) {
if (optimize_cmp(s)) {
std::abort();
}
}
}
}
BENCHMARK(bench_optimized_not_match);
void bench_strcmp(benchmark::State &stat)
{
for (auto _ : stat) {
for (const char *s : match_data_set) {
if (std::strcmp(target, s) != 0) {
std::abort();
}
}
}
}
BENCHMARK(bench_strcmp);
void bench_optimized(benchmark::State &stat)
{
for (auto _ : stat) {
for (const char *s : match_data_set) {
if (!optimize_cmp(s)) {
std::abort();
}
}
}
}
BENCHMARK(bench_optimized);
BENCHMARK_MAIN();
測試使用了google benchmark，不熟悉的可以先看我以前寫的幾篇文章：
- c++性能測試工具：google%20benchmark入門（一）
- c++性能測試工具：google%20benchmark入門（二）
- c++性能測試工具：google%20benchmark進階（一）
測試結果非常喜感：
Running ./a.out
Run on (8 X 2400.01 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x4)
L1 Instruction 32 KiB (x4)
L2 Unified 256 KiB (x4)
L3 Unified 8192 KiB (x1)
Load Average: 0.11, 0.04, 0.01
--------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------
bench_strcmp_not_match 10.6 ns 10.5 ns 65624918
bench_optimized_not_match 23.2 ns 23.2 ns 29860768
bench_strcmp 11.1 ns 11.1 ns 65170113
bench_optimized 32.5 ns 32.5 ns 21280968
可以看到所謂的優化方案幾乎慢了整整一倍。對了，這還是開了-O2優化選項後的結果，不開優化差距更加的大。
會不會是字元串太短了，體現不了優勢？這就是為什麼前面我要啰嗦那麼多告訴你性能測試是怎麼設計的，現在我們只需要改一下數據集，其他原理還是一樣的：
const char *target = "aaabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
const char *not_match_data_set[] = {
"aaabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567891",
"aaabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567892",
"aaabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567899",
"aaabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567898",
"",
};
現在改成64個字元了，對於常見的字元串相等比較來說已經有點長了，然後我們再看測試結果：
Running ./a.out
Run on (8 X 2400.01 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x4)
L1 Instruction 32 KiB (x4)
L2 Unified 256 KiB (x4)
L3 Unified 8192 KiB (x1)
Load Average: 0.04, 0.06, 0.01
--------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------
bench_strcmp_not_match 13.4 ns 13.2 ns 53983729
bench_optimized_not_match 52.0 ns 51.3 ns 10676509
bench_strcmp 13.0 ns 12.9 ns 53231858
bench_optimized 77.8 ns 77.6 ns 9317779
“優化方案”的性能更差了，竟然慢了四倍！而我們早有預期會下降的相等時的性能更是慢了高達6倍。。。
趨勢也很明顯，字元串越長“優化方案”性能越差。
嗯，一般優化都是正向的，逆向的優化確實不多見。
為什麼優化無效
這個分享的“優化方案”在它的優化場景上性能不增反降，在選擇trade-off的場景上產生了無法接受的性能倒退，更感人的是方案的代碼本身也比直接調用strcmp複雜的多。
所以，這個方案既沒有必要性也無法被生產環境接受。
但，這是為什麼？
答案前面就說了：字元串的hash計算是很吃cpu的。計算時不僅要遍歷字元串，為了儘量減少衝突還要和預先定義的素數等做運算，最重要的是還需要利用每個字元的相對位置來計算hash，否則你會看到“abcd”和“dcba”有一樣的hash值。
這些意味著下麵幾點：
- 字元串hash計算時很容易產生數據依賴，這會導致無法有效利用cpu的流水線預執行，相對來說strcmp只是簡單遍歷兩個字元串，數據依賴非常少，這一點導致了一部分性能差異；
- 因為數據依賴，hash計算很難被有效得向量化，而strcmp可以大量利用avx2甚至在新的CPU上已經能利用avx512了。strcmp三四條條指令就能處理完64個字元，但hash計算時三四條指令甚至有可能一個字元都沒處理完；
- 為了減少hash衝突，hash計算需要更多的步驟，和字元的大小比較相比需要花更多時間。
感興趣的可以看看murmur hash是怎麼實現的，上面每條都是它的痛點。
如果是嵌入式環境呢，那裡的cpu功能受限，通常也沒什麼SIMD指令給你用。答案還是一樣的，計算hash比迴圈比較字元大小要花費更多的指令，因此不可能更快最多之後兩者性能差不多，這時候明顯誰的代碼更簡單誰的方案就更好，因此這個“優化方案”又落選了。
還有沒有更快的hash演算法？有是有，但要麼通用性不高要麼功耗太大但無法顯著超越strcmp，總的來說想要在性能上碾壓strcmp，現階段是沒啥希望的。
另外還得給strcmp說句公道話，這個函數是熱點中的熱點，被人優化了幾十年了，大多數常見場景都考慮到了，與其覺得strcmp本身是瓶頸，不如重新考慮考慮自己的設計和演算法是否妥當比較好。
正確的優化
正確的優化該怎麼做呢？由於我沒有分享者的具體使用場景，所以不可能直接給出最優解，因此就泛泛而談幾點吧。
- 不做優化。程式本身的邏輯/演算法就是如此，再怎麼優化這些比較也是省略不掉的。這時候不如考慮考慮升級硬體。
- 如果要比較的字元串的長度都相等，可以試試memcmp，當然收益可能非常小，需要做測試來決定是否採用這個方案，因為本方案很不利於擴展，一不小心就會導致bug甚至高危漏洞。
- 如果在用c++，那麼儘量利用strcmp的編譯期求值的能力，減少運行時的耗時。不過前提是要保證代碼的可讀性不能因為要利用編譯期求值而產生代碼異味。
- 對於某些固定的數據集，需要在數據集上反覆調用strcmp進行等值比較的，可以考慮用二分查找處理數據集或者把這些數據存放進關聯容器里。雖然單次strcmp很快，但大量不必要的重覆計算是會成為性能問題的，這時候hashmap之類關聯性容器的優勢就能體現出來了，一次hash雖然比單次strcmp慢了五倍，但比十次連續的strcmp調用快了一倍。
- 最終極的辦法，像上一節最後說的，重新思考自己的設計或演算法是否合理，重新思考一個更高效的設計/演算法。
還有，別忘了對自己的方案進行測試，免得出現了“負優化”。
總結
那篇分享文的作者最後沒說是否有把這個方案實際應用到生產環境，也沒有說具體帶來了多少提升。但願有人攔住了他吧。
從這裡我們可以得出一個重要的經驗：凡是講優化的，既沒給出性能測試，又沒給出優化應用後的效果，那就得留個心眼了，這多半是有問題的無效優化甚至會是負優化。
最後的最後，還是那句話：性能問題有關的任何事都需要有可靠的性能測試做依據。
