Comment by masklinn
5 years ago
> The fact that this problem is caused by Rockstar's excessive microtransaction policy (the 10MB of JSON causing this bottleneck are all available microtransaction items) is the cherry on top.
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.
> 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.
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?
Then when you want to actually do an activity like a deathmatch you have to wait for matchmaking and then the loading - takes forever. Once you are finally in a match it's okay but as soon as the match ends you have to wait for the world to load again and then queue again which takes bloody forever. Spend 2hrs playing the game and have only a few matches, more time spent looking at loading screens than actually playing anything.
> more time spent looking at loading screens than actually playing anything.
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.
Judging from your word choice "deathmatch" and your experience with long loading/matchmaking times I guess you might be a fellow Quake Champions player. Even if you are not, I agree that long loading times are a mood killer when you just want to play a couple of quick matches after work in your limited free time. It is even worse when you know the game's development is abandoned and it will never get fixed, even though you enjoy the game itself.
2 replies →
I agree. I played GTA online for a bit and quite enjoyed it but I haven't touched it in a while and the insane loading times are a big reason why.
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.
Back in dialup/DSL days I discovered a texture compression issue in America's Army (the free US Army game) that doubled its download/install size. Typical download times were about a day and the resume mechanism was poor, so this had the potential to save a lot of grief, not to mention hosting costs. I emailed them, they banned me for hacking, and the next version still had the same issue. Shrug.
4 replies →
> So both a coffee, and a piss.
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.
I remember as a kid I went to someone's birthday party in the 80s and we wanted to play a karate themed game on something that used a cassette tape. It took so long to load we went and played outside!
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.
9 replies →
They didn't fix it. I tried a few days ago, because it's a really fun game... except for these seemingly easy to fix issues that are huge barriers.
> 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.
Is that... the same problem? Is microtransaction data different in your friend's multiplayer world than it is in the normal online world?
The article mentions story mode loading as well as online loading, but as I mentioned in another comment the story time shown there is much lower than what I experienced, probably because SSDs are now standard and were rarer in 2013 (I could not justify 50GB+ on this one game at the time). So it may be a mixture of factors.
Was new guy at a startup. Soon noticed that chuck Norris was in our compiled JavaScript. Turned out Someone had included the entire test suite in production deploy.
Had been like that for nearly a year. A few minutes of work brought out client js file from 12MB to less then 1mb.
Ha, this is one of the reasons why I also include outlandish and wrong-looking stuff in unit tests. If we see where it doesn't belong, then we know for sure that we are doing something wrong.
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.
That just seems pointless
> Soon noticed that chuck Norris was in our compiled JavaScript
Is that a library? Or the string "Chuck Norris"?
String. Used as factory test for populating objects in tests.
It certainly caught my attention.
I was assuming that someone used the string as a name in the test?
3 replies →
Or the actor/martial artist?
1 reply →
related: Guy Fieri in node https://nodesource.com/blog/is-guy-fieri-in-your-node-js-pac...
You mention quadratic behaviours and there's probably some truth to that, but it seems to me that it's partly a C++ problem. In any other langauge nobody would even consider hacking up JSON parsing using a string function. They'd use the stdlib functional if available or import a library, and this problem wouldn't exist.
A lot of other languages make use of the c standard library functions to parse floats (and to do various trigonometric functions), so they may be more similar than you imagine.
Not super relevant, though. The average standard library from another language is a lot more hardened than the function written by Joe Sixpack in C last night.
But C++ had at least a hash_set/hash_map since forever (or just set/map which are still better than this)
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?
>I'm sure there are libraries to parse json in C++
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.
1 reply →
Rapidjson
That QA bit is too true, "it works for me!" shrug.
> 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.
Might be, but this particular issue has been raised by thousands of players and ignored for *years*.
Yea, given how easy it was for the author of the post to find it, I would guess that literally nobody in the last decade bothered to run a profiler to see where they were spending time.
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.
> management never made it a priority
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.
For the online games I worked on (a few of the recent NFS games) the items database was similar to the final set quite early in production and we kept an ongoing discussion about load times.
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.
And because a merchandising push in many games may be another 10-50 items, the first couple times the % increase is high but the magnitude is low (.5s to 1s) and by the time you're up to 1000, the % increase is too small to notice. Oh it took 30 seconds last week and now it's 33.
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.
I heard that Chrome team had this KPI from very early on - how much time it takes for Chrome to load and it stayed the same to date. i.e. they can't make any changes that will increase this parameter. Very clever if you ask me
Google lately "optimized" Chrome "time for the first page to load" by no longer waiting for extensions to initialize properly. First website you load bypasses all privacy/ad blocking extensions.
Yeah I think that's the kind of odd behaviour that those KPI's end up causing; they 'cheat' the benchmark by avoiding certain behaviour, like loading extensions later.
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.
Thank you for confirming this, I thought I was going crazy seeing it happen a bunch recently. I assumed my system was just on the fritz.
Wow, had no idea about this! Can you link me to a writeup or something?
1 reply →
I hope the Edge team never merges this in.
1 reply →
It would be interesting to see what JSON library they used that uses scanf for parsing numbers. Nothing like a painters algorithm type scenario to really slow things down, but also JSON numbers are super simple and don't need all that work. That is hundreds of MB's of unneeded searching for 0s
Unlikely to be a library, either it's libc or it's homegrown.
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.
Visual Studio keeps toying with the idea of a "NuGet for C++" and it is amazing that it still hasn't happened yet. It may seem to indicate that it isn't necessarily the IDE that can fix it, but the user's attitude. How much of the NIH and "just copy that dependency into the tree" is still encouraged for "security" [0] and "control"/"proprietary source"/"management" reasons?
[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.
2 replies →
In another decade, there's going to be a story here about somebody getting their hands on the original source for this game, and the JSON parser will be a 10-line function with "//TODO: optimize later" at the top.
hmm.. the entire pricing table for Google Cloud (nearly 100k skus and piles of weirdness) was only ~2mb... seems pretty big.
But is quadratic the real issue ? Isn't that a developer answer ?
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.
> But is quadratic the real issue ?
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).
quadratic is a fancy way of saying "this code is super fast with no data, super slow once you have a decent amount"
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.
> quadratic is a fancy way of saying "this code is super fast with no data, super slow once you have a decent amount"
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.
2 replies →
Great explanation. Thanks
In the small case here, there is no meaningful difference in speed between parsers. Using a quadratic algorithm has no advantage and is just an incorrect design.