[C++] 在 Windows 用 WSL + Callgrind 加速 LeetCode C++ 程式碼
最近無聊開始玩玩看 LeetCode，想說用一些奇怪的方法來解經典的第一題 Two Sum。果然用奇怪的方法就會產生很爛的結果:
時間不僅慢，也花得比別人多記憶體。排行爛到炸。其實原因就是因為我想要用 array 來當 hash 看能不能讓他更快一點，不過 array 的 size 太大他要 initialize 也是很花時間的:
static const int BUCKET_SIZE = 10;
class Solution {
public:
std::vector<int> twoSum(std::vector<int> &nums, int target) {
char bits[(250000000 + 1) / BUCKET_SIZE + 1] = {0};
for (size_t i = 0; i < nums.size(); i++) {
const int num = nums[i];
const int nonnegNum = (num + 1000000000) / BUCKET_SIZE;
// Check if the number exists
const int bucketIndex = nonnegNum / 8;
const int offset = nonnegNum % 8;
if (bits[bucketIndex] & (1 << offset)) {
// Only knows the bit is set, but we don't know the index
// So we need to find where the other number is
const int other = target - num;
for (size_t otherIndex = 0; otherIndex < nums.size(); otherIndex++) {
if (nums[otherIndex] == other && i != otherIndex) {
return {(int)i, (int)otherIndex};
}
}
}
// Either the bit is not set, or it fails to find the other number
// We calculate target - num and set the bit for future lookup
const int other = target - num;
// Check if the other number is possible
if (other < (-1000000000) || other > 1000000000) continue;
const int nonnegOther = (other + 1000000000) / BUCKET_SIZE;
const int otherBucketIndex = nonnegOther / 8;
const int otherOffset = nonnegOther % 8;
bits[otherBucketIndex] |= (1 << otherOffset);
}
return {}; // Should not happen
}
};
到底是哪一行在慢?
不過到底有多花時間，我們真的確定是他造成的嗎?
如果不用 profiling 的工具我們也只能不斷 submit 來 trial and error。所以我就來用我常用的招數，先在其他地方偷偷 profile 再把程式碼真正放到該放的地方去:
- 開一個 Visual Studio Code 資料夾
- 自己產生 input data，把自己當作是 LeetCode server 來去跑 Solution class 的 twoSum
- 在 Windows 10 上面架 WSL2 + Ubuntu
- 在 WSL 中安裝 clang, valgrind, g++ 等開發用的東西
- 用簡易的 Makefile 在 WSL 上 compile C++ code
- 在 WSL 上跑 Valgrind
- 在 Windows 10 上用 QCachegrind 看 Valgrind 結果
詳細的運作流程實在太過細節，我就乾脆放上 GitHub 有興趣的可以參考一下跑的流程。
QCachegrind: 找出問題
跑完 Valgrind 的 tool Callgrind 之後他會產生一個 xxx.out.<pid> 檔，但由於是在 WSL Linux 環境底下跑的所以你的 source code 會變成是 /mnt/c/Users/... 開頭，我在 script 裡面用 sed 簡單把他替換成 C:/Users 這樣 Windows 10 上面的 QCachegrind 就能在 Windows 10 路徑上找的到檔案。
不過如果你有一台可以顯示螢幕的 Linux，直接在上面開 KCachegrind 就可以看了，甚至可以看到底下的 library code。
我們可以看到宣告一個非常大的 array 再去 zero initialize 其實底層是呼叫類似 memset 的東西，他花了整個程式 70% 的時間實在是很久。
知道問題後，那我就開始把 hash 的大小縮小，就是把 BUCKET_SIZE 變大一點。
題外話: LeetCode 或 Valgrind 有可能會產生 segmentation fault 但其實這邊的罪魁禍首就是 array 太大超過 stack 使用量。LeetCode 應該是沒解，我也不知道他設多大。不過 Valgrind 可以用 --main-stacksize 來指定更大的 stack size，他的 log 其實也會跟你提示這件事。
QCachegrind: 優化後
把 BUCKET_SIZE 從 10 拉大到 1000 之後原本 70% 的地方就縮減為 3% 了:
但如果你改用不是 % 數來呈現的話，會發現他的 Ir 還是高得嚇人，誰叫我要 initialize 這麼大的 array 呢:
到底是 IR 還是 LR?
LeetCode: 優化後
試過了很多次發現他不是 4ms 就是 8ms，記憶體也是 9MB 上下浮動。跟用 STL 的 hash 解其實差不多:
留言
發佈留言