GTA5线上模式加载缓慢竟然是因为一条命令执行了19.8亿次

再买自检星剁手 · 发表于 2021-3-3 01:46

本帖最后由再买自检星剁手于 2021-3-3 02:32 编辑

博客原文：https://nee.lv/2021/02/28/How-I- ... oading-times-by-70/

GTA5线上模式（下文简称为GTAOL）载入速度奇慢，快则6分钟，慢则需要20分钟，而线上和线下模式的加载速度差别简直像是两个公司开发的游戏

一位老哥坐不住了，打算分析一下原因，他从任务管理器看出，载入线下模式时，CPU占用率不高，载入线上模式内容时，CPU占用率却暴增：

而像网络、显卡、内存、硬盘的占用率几乎没变化，老哥因此推测GTAOL载入慢是因为烂代码造成的，老哥用着amd fx8350和nvidia gtx1070，初步判断载入慢是单核性能拖了后腿

从性能分析的结果看，有两个函数的执行占据了加载时间的半壁江山，一个48.8%，一个22%：

如果我们能优化这两个函数，就能大幅缩短GTAOL的加载时间了

老哥说干就干，对GTAOL进行逆向，一开始遇到了点困难，是R星为了挡住作弊者和mod作者的，不过老哥还是分析出了瓶颈所在，问题出在sscanf函数上：

而sscanf在读取一个10MB大小的JSON文件，老哥猜测读取的是GTAOL的内购项目，约六万三千个JSON对象。

用sscanf本身不会造成那么大的问题，老哥推测sscanf的内部实现用了strlen，也就是计算字符串的长度，每次调用sscanf都要在读取到的10MB字符串上用strlen一个字一个字地数一遍字符串长度，因而会比较慢。

然而这还不是最关键的，在读取完后，需要把读取到的项目存入数组中，数组元素除了项目本身外，还有一个项目的哈希值。

关键的部分来了：在项目存入数组前，需要遍历一遍数组，查看哈希值是否有重复的，没有就插入数组。注意，任何一个元素要插入数组，都得先遍历一遍，对于六万三千个元素的数组来说，每次插入都要遍历一次就相当耗时了。数组元素越多，耗时越长，插入操作的时间复杂度达到了O(n)，把n个元素插入数组的时间复杂度达到了O(n^2)

不了解编程的朋友就想象成你要往书柜里放书，每放一本书之前，要把书柜里的书挨个数一遍，那么显然书柜里的书越多，你往书柜里放新书花费的时间就越长

这位老哥粗略计算这样的元素比较次数为1+2+3+4+...+63000，也就是1984531500，19.8亿次

这位老哥到这里给R星开发跪了：既然都用哈希值了，干嘛不用哈希表呢？

既然定位到了问题，那么就可以动手了，一开始想hook sscanf，后来觉得hook strlen函数，缓存长度结果，而不是每次sscanf调用strlen的时候就一个字一个字重新数一次。

而“哈希表”的问题就更简单了，我们知道每个值都是不一样的，自然就能直接插入，跳过无效的检查

结果是什么呢？在同样的硬件上，GTAOL的载入时间缩短了70%之多！

这位老哥解决了这个问题，帮助广大GTAOL玩家节省了时间，也把这个方案共享了出来

https://github.com/tostercx/GTAO_Booster_PoC

玩家只需要替换dll就行了

偶滴小乔 · 发表于 2021-3-3 02:06

把内购删了岂不是一了百了

Tring · 发表于 2021-3-3 02:09

本帖最后由 Tring 于 2021-3-3 02:31 编辑

就是用了一个平方复杂度的插入算法维护数组而已。
讲道理，区区6W3项，这对于今天的CPU来说根本不是个事。

就算真的是这个插入导致拖慢，也不应该是插入这个内存操作行为本身所致，而应该是其他的某种伴随的硬件访问所致。
我对这老哥的结论持怀疑态度。

=====

https://jsbench.me/27klscavyz/1
拿JS跑着试了下。
第一项是按主楼描述的直接插入6W3项；
第二项是一样的逻辑不过用内置includes方法来检查；
第三项是插入用哈希表的Set对象。

结果不用说当然用Set当然是压倒性的快。但是前两项也没那么慢。在JS这种低效环境下我这台垃圾电脑都能3秒跑完一次。

INDIASH · 发表于 2021-3-3 02:25

讲道理不应该是O(n^2)么？

Tring · 发表于 2021-3-3 02:29

INDIASH 发表于 2021-3-3 02:25
讲道理不应该是O(n^2)么？

插入一项是O(n)，全部插入完是O(n^2)。

whzfjk · 发表于 2021-3-3 02:38

提示: 作者被禁止或删除内容自动屏蔽

再买自检星剁手 · 发表于 2021-3-3 02:39

Tring 发表于 2021-3-3 02:09
就是用了一个平方复杂度的插入算法维护数组而已。
讲道理，区区6W3项，这对于今天的CPU来说根本不是个事。
...

老哥还hook了strlen，它可能才是主因

如果10MB的字符串还得逐字节计数也挺耗时的

darkfall · 发表于 2021-3-3 02:44

本帖最后由 darkfall 于 2021-3-3 03:01 编辑

大概load factor设太大导致元素过多的情况下退化成链表，修过一个类似的bug。
sscanf用来parse JSON也是intern写的等级

whzfjk · 发表于 2021-3-3 02:50

提示: 作者被禁止或删除内容自动屏蔽

darkfall · 发表于 2021-3-3 02:56

本帖最后由 darkfall 于 2021-3-3 03:10 编辑

whzfjk 发表于 2021-3-3 02:50
这种 json 的 parser 不都是用开源库吗，各种向量化用得飞起

也不是很奇怪，写引擎大家喜欢的东西之一就是自己实现的一切才是最好的(像是EA STL)。
大概哪个背锅的intern被要求我们要parse一个JSON随手写了个，然后因为更新这个JSON越来越大退化厉害

孤蜀安安 · 发表于 2021-3-3 05:46

提示: 作者被禁止或删除内容自动屏蔽

FanKiE · 发表于 2021-3-3 07:05

泥潭程序员还挺多

-- 来自能手机投票的 Stage1官方 Android客户端

丹德里恩 · 发表于 2021-3-3 09:04

在还没有那么多内购的时候social club就成功把我逼退了

cnwind042 · 发表于 2021-3-3 09:11

我RDR2启动也慢的一批，严重打压我打开来玩的心情

Evilgurren · 发表于 2021-3-3 09:12

逻辑运算比网络io耗时久导致载入缓慢，迷惑

紫苑寺友子MKIII · 发表于 2021-3-3 09:49

提示: 作者被禁止或删除内容自动屏蔽

dumplingpro · 发表于 2021-3-3 10:03

玩家男儿亲自上阵代替厂商修BUG

wgoenitz · 发表于 2021-3-3 10:07

感觉是厂商故意的

Redis · 发表于 2021-3-3 10:20

提示: 作者被禁止或删除内容自动屏蔽

Redis · 发表于 2021-3-3 10:22

提示: 作者被禁止或删除内容自动屏蔽

cloudian · 发表于 2021-3-3 10:30

可以去应聘了

—— 来自 OnePlus GM1910, Android 10上的 S1Next-鹅版 v2.4.4.1

otakun · 发表于 2021-3-3 19:43

...有没有人能解释下要怎么操作，下载完压缩包解压之后怎么处理

Trompete · 发表于 2021-3-3 19:56

有人试了没，真的能缩短70%？？

非典型叶子 · 发表于 2021-3-3 20:20

dll注入等同于使用外挂，这个老哥发github只是poc而不能算补丁，建议等官方采纳修复

Prolun · 发表于 2021-3-3 22:48

json库这种东西也要自己造轮子是真的疯了。第一你性能不一定比开源的好，第二你处理不了大量corner case的测试。

nianiania · 发表于 2021-3-4 09:22

重复造轮子要不得，虽然每家大公司都会把这个当kpi

—— 来自 Xiaomi M2007J3SC, Android 10上的 S1Next-鹅版 v2.4.4.1

masonknight · 发表于 2021-3-4 12:53

有没有人试了？？？是不是真的能缩短加载时间？

未平真人 · 发表于 2021-3-4 19:27

提前破解ps5版的加速秘方

九十九忍 · 发表于 2021-3-4 19:28

还有人玩也是服

zhangqq_008 · 发表于 2021-3-4 20:16

九十九忍发表于 2021-3-4 19:28
还有人玩也是服

为什么gta ol会没人玩

—— 来自 OnePlus KB2000, Android 11上的 S1Next-鹅版 v2.4.4.1

stygianlunar · 发表于 2021-3-4 20:20

这算是内购系统有BUG但不是游戏本身的BUG所以懒得修|？

莫夜戎 · 发表于 2021-3-4 21:16

masonknight 发表于 2021-3-4 12:53
有没有人试了？？？是不是真的能缩短加载时间？

keylol论坛看到讨论有人试了，从五分钟加载到了一分钟，所以应该是挺有效的。

linuy · 发表于 2021-3-16 10:03

提示: 作者被禁止或删除内容自动屏蔽

wuzhou6058 · 发表于 2021-3-16 10:08

提示: 作者被禁止或删除内容自动屏蔽

ArowRocher · 发表于 2021-3-16 10:22

抄一个评论

最后，R星奖励了制作了GTA6的玩家，并发布了该游戏。

dumplingpro · 发表于 2021-3-16 10:44

linuy 发表于 2021-3-16 10:03
【R星将使用玩家制作的代码来缩短《GTA Online》加载时间】

据外媒报道，R星将在《GTA Online》即将发布的 ...

玩家帮厂商开发游戏，武德丰沛。

凶手 · 发表于 2021-3-16 10:48

linuy 发表于 2021-3-16 10:03
【R星将使用玩家制作的代码来缩短《GTA Online》加载时间】

据外媒报道，R星将在《GTA Online》即将发布的 ...

优化json性能厉害的要是我这一起弄的朋友直接转grpc + pb了囧

观自在 · 发表于 2021-3-16 10:57

提示: 作者被禁止或删除内容自动屏蔽

2659646573 · 发表于 2021-3-16 11:41

观自在发表于 2021-3-16 10:57
贝塞斯达：还要给钱的吗？

—— 来自 HUAWEI CDY-AN90, Android 10上的 S1Next-鹅版 v2.4.4.1 ...

如果是杯赛，那应该用了也不会说

GMJ · 发表于 2021-3-16 11:53

为啥不把6W3个对象打个包直接下载然后只针对整个包做一次哈希对比

		自动登录	找回密码
密码			立即注册

[新闻] GTA5线上模式加载缓慢竟然是因为一条命令执行了19.8亿次

评分

whzfjk whzfjk 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2015-5-11 头像被屏蔽	发表于 2021-3-3 02:38 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

whzfjk whzfjk 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2015-5-11 头像被屏蔽	发表于 2021-3-3 02:50 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

孤蜀安安孤蜀安安当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2020-2-7 头像被屏蔽	发表于 2021-3-3 05:46 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

紫苑寺友子MKIII 紫苑寺友子MKIII 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2021-1-12 头像被屏蔽	发表于 2021-3-3 09:49 来自手机 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

Redis Redis 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2013-11-27 头像被屏蔽	发表于 2021-3-3 10:20 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

Redis Redis 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2013-11-27 头像被屏蔽	发表于 2021-3-3 10:22 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

linuy linuy 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2011-6-27 头像被屏蔽	发表于 2021-3-16 10:03 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

wuzhou6058 wuzhou6058 当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2019-3-2 头像被屏蔽	发表于 2021-3-16 10:08 来自手机 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报

观自在观自在当前离线禁止发言精华 \| 战斗力鹅 \| 回帖 0 注册时间 2019-3-15 头像被屏蔽	发表于 2021-3-16 10:57 来自手机 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽

	回复使用道具举报