PTT推薦

Re: [心得] 如何減少 GTA Online 70% 載入時間?(轉)

看板Soft_Job標題Re: [心得] 如何減少 GTA Online 70% 載入時間?(轉)作者
oopFoo
(3d)
時間推噓 9 推:9 噓:0 →:8

※ 引述《alihue (wanda wanda)》之銘言:
: 原始文章: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/: 如何減少 GTA Online 70% 載入時間?
: 作者覺得 GTA Online 載入時間機八久,因此想要一探究竟
: 首先作者做 benchmark 發現
: Story mode load time: ~1m 10s
: Online mode load time: ~6m flat
: 然後看看 cpu usage 同時在這段時間燃燒
: 第一步,作者先做 profiling 可以得知哪一些 function 佔了最多 CPU 資源
: 第二步,用 disassembler 去看程式碼
: 問題1. It’s… strlen?!
: 好像會 parse 一個高達 10MB 的 json 檔案,其中包含 63k items
: 這些資料是遊戲中的線上商城的
: 問題不是 10MB,而是讀取資料的方式
: https://i.imgur.com/ZHLlEDJ.png

圖 如何減少 GTA Online 70% 載入時間?(轉)
: 讀法是用 sscanf 一次讀一個 char,讀完馬上呼叫 strlen,
: 再繼續讀下一個 char....
: 然後當要讀的檔案有 10mb 這麼大就有很重的 overhead
是sscanf的function裡會呼叫strlen,也不是一次讀一個char。
https://opensource.apple.com/source/xnu/xnu-792/libkern/stdio/scanf.c.auto.html雖然不知微軟如何implement sscanf,不過應該大致相同。

這10mb的json是一個string。迴圈裡的sscanf會讀一個item(key:value)。
所以這個parser裡的strlen的complexity是
strlen(10mb)+strlen(10mb-length(key:value))+strlen(10mb-2*length(key:value)......
這迴圈會跑63k次。很不幸的一個quadratic time的parser就出現了,因為程式師不知sscanf裡有strlen。

GTA的insert也是quadratic time,但這真的蠢,有code review應該都會抓的到

無論如何,json parser不應該自己寫。
https://github.com/simdjson/simdjson - 最快的parser
https://rapidjson.org/ - 實際上快又準確,最多人建議的parser
https://github.com/nlohmann/json - 好用也多人建議的parser
google 一下,有超多的選擇。

上面任何一個都可以在幾秒(0.幾秒吧)內處理完10mb 63k的json。

而現在優化的GTA還是需要快一分鐘處理!對sscanf is slooooooow。


--

※ PTT留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.27.86 (臺灣)
PTT 網址

alihue03/29 22:25謝謝補充說明

nh60211as03/29 23:11所以這算是自己造輪子失敗的案例嗎

對,遊戲業的習慣,喜歡自己造輪子。十幾二十幾年前,因為各種限制,造輪子還有道理,現在還不趁機導入業界好用的lib就是怠惰了。

jasonwung03/29 23:43

viper970903/30 00:00原來是這樣

※ 編輯: oopFoo (59.115.98.214 臺灣), 03/30/2021 10:52:24

dreamnook03/30 14:14

Barchem03/30 14:44

tsairay03/30 18:13怕找開源的lib商用要付錢吧

oopFoo03/30 18:36mit/bsd/apache license的libs超多,這幾個json libs都是

hduek15303/30 19:43

superpandal03/30 19:53這事情有應不應該? 不過M$就不說了

superpandal03/30 20:07不過 XD

OppOops03/30 21:48事實上我認為他是用 recursive 的方式去處理 json

OppOops03/30 21:49所以才會重複展開 sscanf

oopFoo03/30 23:03很早就知道sscanf有strlen的問題。

oopFoo03/30 23:04跟重複展開無關

wangm4a104/01 16:09