9 ms·
> The fact that this problem is caused by Rockstar's excessive microtransaction policy (the 10MB of JSON causing this bottleneck are all available microtransact
by masklinn 6y 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.
- hanniabu 6y agoThat QA bit is too true, "it works for me!" shrug.
- ldng 6y agoBut 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.
- gridspy 6y agoquadratic 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.
- jack_riminton 6y agoGreat explanation. Thanks
- ldng 6y ago> 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.
- mytherin 6y ago> 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. 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.
- deleted 6y ago[deleted]
- oivey 6y agoIn 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.
- masklinn 6y ago> 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).
- hnick 6y ago> 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?
- simias 6y agoI 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.
- jjoonathan 6y agoBack 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.
- jack_riminton 6y agoThat's hilarious. Out of interest who in the company did you email?
- jjoonathan 6y agoI was only able to find contact information for one person who I knew was probably technical (from their posts), so I sent it to them. 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!"
- nullserver 6y agoWas 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.
- jogjayr 6y ago> Soon noticed that chuck Norris was in our compiled JavaScript Is that a library? Or the string "Chuck Norris"?
- jeffgreco 6y agoOr the actor/martial artist?
- finnh 6y agobravo! i'll take the downvotes that this content-free comment will garner, but you just made my morning.
- kevincox 6y agoI was assuming that someone used the string as a name in the test?
- hnick 6y agoYes I think they meant they saw a weird name that stood out (I've seen Donald Duck at work) and they investigated more, finding it was test data.
- wiz21c 6y agoI've seen "Carmen Electra" myself :-) And other funny (more gross) names in the dark corners of huge databases... 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...
- nicoburns 6y agoYou 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.
- raverbashing 6y agoBut 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?
- nicoburns 6y ago>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.
- bleachisback 6y agoThe first C++ JSON library that appears when you google it is a single header file. https://github.com/nlohmann/json 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 https://github.com/miloyip/nativejson-benchmark#parsing-time) is also header-only and compares its speed to strlen. https://github.com/Tencent/rapidjson https://github.com/Tencent/rapidjson
- nitwit005 6y agoA 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.
- beached_whale 6y agoIt 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
- dijit 6y agoUnlikely 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.
- thw0rted 6y agoIn 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.
- WorldMaker 6y agoVisual 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.
- Agentlien 6y agoFor 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.
- john_minsk 6y agoI 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
- rasz 6y agoGoogle 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.
- raf42 6y agoThank 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.
- Cthulhu_ 6y agoYeah 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.
- saruken 6y agoWow, had no idea about this! Can you link me to a writeup or something?
- rasz 6y agohttps://github.com/Tampermonkey/tampermonkey/issues/1083 https://github.com/Tampermonkey/tampermonkey/issues/1083 confirmed by Tampermonkey dev.
- sundvor 6y agoI hope the Edge team never merges this in.
- thefz 6y ago> 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*.
- tekromancr 6y agoYea, 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.
- ironmagma 6y ago> 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.
- milesward 6y agohmm.. the entire pricing table for Google Cloud (nearly 100k skus and piles of weirdness) was only ~2mb... seems pretty big.
- hinkley 6y agoAnd 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.