How I cut GTA Online loading times by 70%

For what it's worth, 10MB of JSON is not much. Duplicating the example entry from the article 63000 times (replacing `key` by a uuid4 for unicity) yields 11.5MB JSON.

Deserialising that JSON then inserting each entry in a dict (indexed by key) takes 450ms in Python.

But as Bruce Dawson oft notes, quadratic behaviour is the sweet spot because it's "fast enough to go into production, and slow enough to fall over once it gets there". Here odds are there were only dozens or hundreds of items during dev so nobody noticed it would become slow as balls beyond a few thousand items.

Plus load times are usually the one thing you start ignoring early on, just start the session, go take a coffee or a piss, and by the time you're back it's loaded. Especially after QA has notified of slow load times half a dozen times, the devs (with fast machines and possibly smaller development dataset) go "works fine", and QA just gives up.

The best algorithm for small, medium or a large size are not the same and generally behave poorly in the other cases. And what is small? Medium? Large?

The truth is that there is no one size fits all and assumptions need to be reviewed periodically and adapted accordingly. And they never are... Ask a DBA.

The problem is that when you double the amount of stuff in the JSON document, you quadruple (or more) the scanning penalty in both the string and the list.

Why quadruple? Because you end up scanning a list which is twice as long. You have to scan that list twice as many times. 2x2 = 4. The larger list no longer fits in the fast (cache) memory, among other issues. The cache issue alone can add another 10x (or more!) penalty.

In GTA V, when I tried to enjoy multiplayer with my friends the abysmal load times were what killed it for me.

You actually have to load into the game world - which takes forever - before having a friend invite you to their multiplayer world - which takes forever, again.

So both a coffee, and a piss. Maybe they fixed that now?

It kind of baffles me that they haven't bothered to fix this trivial issue when the result is to cut 4 entire minutes of loading time.

Had been like that for nearly a year. A few minutes of work brought out client js file from 12MB to less then 1mb.

Is that a library? Or the string "Chuck Norris"?

Reminds me on loading "G.I. Joe" (from Epyx) on the C64 with a 1541 floppy disk. However, the long loads came after every time you died and meant you also had to swap 4 disks.

To be fair to GTA V, I don't think my installation was on a SSD because it was 50GB or something at the time (now it's 95GB?), but that said when it released SSDs were not as cheap or widespread as they are now so that's their problem. The linked article shows the initial load to be much shorter which did not match my experience.

Is that... the same problem? Is microtransaction data different in your friend's multiplayer world than it is in the normal online world?

I really liked this article, but I am a bit surprised that this made it into production. I have seen a few instances of this type of slowdowns live for very long, but they tend to be in compile times or development workflow, not in the product itself.

I'm sure there are libraries to parse json in C++ or at least they should have built something internally if it's critical, instead they have someone less experienced build it and not stress test it?

Yes. That is literally the entirety of the issue: online loading takes 5mn because there are two accidentally quadratic loops which spin their wheel.

> The best algorithm for small, medium or a large size are not the same and generally behave poorly in the other cases.

“Behaves poorly” tends to have very different consequences: an algorithm for large sizes tends to have significant set up and thus constant overhead for small sizes. This is easy to notice and remediate.

A naive quadratic algorithm will blow up your production unless you dev with production data, and possibly even then (if production data keeps growing long after the initial development).

I also had a customer discover a playboy center page at the end of a test we sent to them. One of the dev thought it'd be a nice reward. Things went very bad from him right after the phone call...

It certainly caught my attention.

Had someone at work mention they needed to drop off a dog at grooming on the way to pick up Chinese.

I had to walk away for a bit, as I couldn’t hold it in, but didn’t know if that sort of humor would fly with that crowd.

Most often I use unicode strings in unexpected alphabets (i.e. from languages that are not supported by our application and that are not used by the mother tongue of any developer from our team). This includes Chinese, Malayalam, Arabic and a few more. There was a time when I wanted to test the "wrong data" cases for some deserialising function, and I was part annoyed and part amusingly surprised to discover that doing Integer.parseInt("٤٣٠٤٦٧٢١") in Java does parse the arabic digits correctly even without specifying any locale.

The only thing most game companies do when it comes to external libraries is to copy the source code of it into their repo and never update it, ever.

OpenSSL is this way, it's a required installation for Playstation but debugging it is seriously hard, and perforce (the games industries version control of choice) can't handle external dependencies. Not to mention visual studio (the game industries IDE of choice..) can't handle debugging external libraries well either.

So, most game studios throw up the hands, say "fuck it" and practice a heavy amount of NIH.

This could easily compete for the most expensive bug in history, up there with the Pentium Bug. It might have halved the revenue potential of a billion dollar franchise.

There certainly are, but adding a library is much more difficult in C++ than pretty much any other language which seems to tempt people into hacky self-built parsing when they really ought to know better.

I mean I can understand it, a lot of extensions don't need to be on the critical path.

But at the same time, I feel like Chrome could do things a lot better with extensions, such as better review policy and compiling them to wasm from the extensions store.

Well, that is an abuse of the term, by people that sometimes don't actually know what that really means. Up to a point, quadratic IS faster than linear after all for example. Too many developer love too abuse the word blindly.

If it is badly tested with no data, it is badly tested with no data. Period. Not "quadratic".

> The problem is that when you double the amount of stuff in the JSON document, you quadruple (or more) the scanning penalty in both the string and the list.

My point was precisely it depends on the data and initial assumption are to be routinely revised. I was making a general point.

Maybe the guy was pinky-sworn that the JSON would hardly change and that the items were supposed to be ordered, sequential and no more than 101. For all you know it is even documented and nobody cared/remembered/checked when updating the JSON. But we don't know, obfuscated code don't comes with comments and context ...

Or, it is actually a real rookie mistake. It probably was, but we don't have all the facts.

There is absolutely no guarantee that a quadratic algorithm has to be faster than a linear algorithm for small N. It can be, in some situations for some algorithms, but the complexity class of the algorithm has nothing to do with that. A quadratic algorithm may well be slower than a linear algorithm for any N.

The only thing the complexity class tells us is that starting from some N the linear algorithm is faster than the quadratic algorithm. That N could be 0, it could be 100, or it could be 1 billion.

In my experience it's usually between 0~1000, but again, that depends. The complexity class makes no such guarantees. The complexity class tells us the general shape of the performance graph, but not exactly where the graphs will intersect: this depends on the constants.

> If it is badly tested with no data, it is badly tested with no data. Period. Not "quadratic".

It is both. The problem is that the algorithm has quadratic complexity. The fact that it was badly tested caused this fact to remain hidden while writing the code, and turn into a real problem later on.

Which meant the game displayed "rewind to mark 500 and then hit play" and you had to do that to restart lolsob.

Might be, but this particular issue has been raised by thousands of players and ignored for *years*.

I suppose devs dont care about that as long as their QA allows it.

I never learned the "other side" of this story, but a few years later the same dev team tried to recruit me at a CS contest, to which I politely declined.

More details: I was young, without credit card, and gaming on a mac. AA was free and mac compatible. For a while -- apparently mac ports of unreal engine games were approximately all done by a single very productive contractor and from what I understand the US Army, uhh, stopped paying him at some point. So he stopped releasing the mac ports. From my point of view, this meant that I could only play with other mac users and couldn't use any of the fancy new maps. Logs indicated that the compatibility problems with the new maps were not particularly deep, so I got to parsing the unreal map files and was able to restore compatibility by deleting the offending objects. I implemented texture decoding/encoding mostly for curiosity and because textures were well documented in the reverse engineering "literature." I imagined a workflow where someone would bulk export and re-import textures and aside from the texture names the one piece of metadata I needed was the format: RGBA (uncompressed) or DXT (compressed)? I realized that I could easily identify DXT compression from the image histogram, so I didn't need to store separate metadata. Nifty! But it didn't work. Lots of textures stored in uncompressed RGBA8888 "erroneously" round-tripped to DXT. After poring over my own code, I eventually realized that this was because on many of the textures someone had enabled DXT compression and then disabled it, dropping the texture quality to that of DXT while bloating the texture size to that of RGBA8888 (other textures were still stored as DXT, so compression itself was still working). I wrote a quick tool to add up the wasted space from storing DXT compressed textures in uncompressed RGB format and it came out to about half the total disk space, both before and after the top level installer's lossless compression. They could have re-enabled compression on most of the textures where they had disabled it without loss in quality, and if they had wanted a list of such textures I would have been able to provide it, but it didn't go down that way. When I shared what happened with my father, who had served, his reaction was "Now that's the Army I know!"

Many 8bit Atari owners will have horror memories of aborted Tape loads. After over 20 years someone finally discovered a bug in original ATARI Tape loading ROM routine resulting in randomly corrupted loads, no amount of sitting motionless while the game loads would help in that case :)

The only possible explanation is that management never made it a priority.

I could see this happening. A project/product manager thinking "We could spend $unknown hours looking for potential speedups, or we could spend $known hours implementing new features directly tied to revenue"

Which is kind of ironic since this fix would keep players playing for more time, increasing the chances that they spend more money.

confirmed by Tampermonkey dev.

Boiling the frog, as it were. This class of problems is why I want way more charts on the projects I work on, especially after we hit production. I may not notice an extra 500ms a week, but I'm for damn sure going to notice the slope of a line on a 6 month chart.

[0] Despite it being an obvious anti-pattern that you aren't going to update dependencies that require copy/paste and manual merge reviews, so security problems should be obviously more rampant than in systems where updating a dependency to the latest security patch is a single install command line (or update button in a GUI), there still seems to be so many C++ devs that love to chime in to every HN thread on a package manager vulnerability that they don't have those vulnerabilities. They don't "have" dependencies to manage, no matter how many stale 0-Days they copied and pasted from outside projects, they don't count as "dependencies" because they are hidden who knows where in the source tree.

Call of Duty: Black Ops Cold War is around 200GB fully installed with all features (HD textures etc).

Some people have insinuated this is intentional to crowd out other games on console hard disks and make moving away from CoD have an opportunity cost. It's probably just laziness.

I haven't looked into it in the past but some prior offenders had a lot of space wasted from uncompressed multi-lingual audio. Instead of letting us choose a language it installs them all so you can switch in game, and uncompressed for saving the CPU for game logic. For CoD the optional HD texture pack is 38GB so that's still a lot unaccounted for.

I think we need a new vocabulary to cover situations like this one. It's not just that other issues took priority here, it's that this wasn't even entered into the list of things to give a crap about. It's something like digital squalor.

https://github.com/nlohmann/json

I know because I used it years ago in school.

One of the fastest libraries (https://github.com/miloyip/nativejson-benchmark#parsing-time) is also header-only and compares its speed to strlen.

https://github.com/Tencent/rapidjson

The problem with this argument is that if the data size and constants are sufficiently small enough people don't care about whether the linear algorithm is slow. In the case of JSON parsing the constants are exactly the same no matter what string length algorithm you use. Thus when n is small you don't care since the overall loading time is short anyway. When n is big you benefit from faster loading times.

I honestly don't understand what goal you are trying to accomplish. By your logic it is more important to keep short loading times short and long loading times long rather than do the conventional engineering wisdom of lowering the average or median loading time which will sometimes decrease the duration of long loading screens at the expensive of increasing the duration of short loading screens.

It's not like decoding audio takes enough time on any modern multi-core processor to disrupt the game loop. It's not even on the radar.