博客原文：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就行了

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

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

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

=====

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

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

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

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

感觉比较吊诡，这个 hashmap 本身已经是个开链表的结构了，查找 key 时竟然要遍历 slot。除非不能用这个 key 哈希出 slot。
这又是个链表遍历，比素组遍历还要严重一些。

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

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

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

这种 json 的 parser 不都是用开源库吗，各种向量化用得飞起

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

标准库stl对于游戏开发来说还是太慢了。然而r星这么多年了肯定有自己的一套标准库啊，难道一直没发现，或者开发gtaol时重写了？

泥潭程序员还挺多

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

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

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

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

我一直以为是网络问题
hdd，ssd众生平等

—— 来自 Xiaomi Redmi K30 Pro, Android 11上的S1Next-鹅版v2.4.4

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

感觉是厂商故意的

你看代码，就不是退化

就是直接while loop直接遍历

更有可能是原来商店里面东西少的时候，比如1000个item的时候，list来dedup速度不会比hashmap慢到可见的程度，瓶颈在其他地方

结果商店的东西日积月累，越来越多，这个瓶颈就越来越明显

可以去应聘了

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

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

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

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

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

提前破解ps5版的加速秘方

还有人玩也是服

为什么gta ol会没人玩

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

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

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