Tag: hash

這件事情也已經過了一個禮拜，來整理一下發生什麼事情...

起因是 GTA Online 的遊戲開啟速度很慢，而有人一路 reverse engineering 找出問題並且解決：「How I cut GTA Online loading times by 70%」，對應的 Hacker News 討論有提到其他有趣的事情也可以看看：「How I cut GTA Online loading times by 70% (nee.lv)」。

作者的電腦不算太差，但光開啟 GTA Online 就需要六分鐘，網路上甚至有辦投票蒐集大家的等待時間，發現也有很多人反應類似的問題：

接下來就開始 reverse engineering 了，先觀察各種狀態後發現是卡在 CPU，而不是網路或 Disk I/O，然後就拿出 Luke Stackwalker 這個工具 profiling，不過因為沒有 debug symbol 幫忙 group，所以只能人工判斷後，可以看到兩個問題：

第一個問題發現效能是卡在 strlen()，而 call stack 可以看出來是從 sscanf() 一路打進去的：

反追發現是在處理 10MB 的 JSON 檔造成的，裡面 sscanf() 因為拉出 strlen()，於是就造成把整個 10MB 的 JSON 掃過很多次 (一開始是 10MB，掃到後面會愈來愈少，平均下來應該是 5MB)：

第二個問題產生的時間會在第一個問題跑完後，另外看問題的性質，應該跟第一個 JSON 處理有關，他會把 JSON 處理過的資料丟進 array，每個 entry 長這樣：

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

丟進 array 是 OK 的，但問題在於他需要判斷 entry 是否重複，卻沒有用 hash 或是 tree 的結構，而這邊大約有 63k 筆資料，用 array 實做就產生了 O(n^2) 的演算法：

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

作者在 PoC 的章節裡面描述他怎麼解這兩個問題。

第一個問題比較好的解法是修正 JSON Parser，但這太複雜，所以他用 workaround 解：把 strlen() 包起來，針對長字串加上一層 cache：

• hook strlen
• wait for a long string
• “cache” the start and length of it
• if it’s called again within the string’s range, return cached value

而第二個問題他直接把檢查是否有重複的跳過，因為資料本身不重複：

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

整個開啟的速度從六分鐘降到一分五十秒，還是偏慢，但算是大幅緩解的 GTA Online 啟動速度的問題了。

不過故事到這邊還沒結束，有人一路去挖，發現其實 sscanf() 的效能地雷已經不是第一次了：YAML 的 Parser 也中過一樣的問題：「Parsing can become accidentally quadratic because of sscanf」，這篇也一樣上了 Hacker News：「Parsing can become accidentally quadratic because of sscanf (github.com/biojppm)」。

然後這又帶出了六年前在 StackOverflow 上就有人問過這個問題：「Why is glibc's sscanf vastly slower than fscanf on Linux?」。

另外也有人整理出來，應該是大家把同樣的演算法拿來實做：

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

後續的更新動作可以再追一下進度 (包括 GTA Online 與各家的 libc)。