Skip to content
Rabin Poudyal
Page 9-1
9-1 Incidents

9.14GTA Online's six-minute load

A player profiled GTA Online's released binary from outside and found two quadratic loops in its loading code, a JSON (JavaScript Object Notation) parse and a duplicate check, that together cost most of a six-minute load.

Rockstar Games · 28 February 2021 · Performance

  1. 1Read
    Blast radius
    Players of GTA Online on PC, every time they loaded into the online game. On the author's machine the online load took about six minutes, with one processor core maxed out for about four of them.
    Duration
    Sixteen days from the write-up to the fix: the post was published on 28 February 2021, and Rockstar's title update with improved PC loading times followed on 16 March 2021. How long the slow load had existed before that is not stated in the sources used here.
  2. 2Follow

    What happened, in order

    1. Then

      On an AMD FX-8350 with a solid-state drive, t0st times GTA Online at about 6 minutes from the Rockstar logo to in-game, against about 1 minute 10 seconds for story mode.

    2. Then

      Task Manager shows one CPU (processor) core at full load for about four minutes, with no disk, network or GPU (graphics processor) activity. A stack-sampling profiler, Luke Stackwalker, finds two hot spots, not one.

    3. Then

      With no debug symbols and an obfuscated binary, t0st dumps the running game's memory and reads the disassembly. The first hot spot is strlen, called through what he is fairly confident is sscanf, parsing a 10 megabyte JSON file of about 63,000 store catalogue items.

    4. Then

      The second hot spot is a duplicate check that compares each item's hash, one by one, against every item already loaded.

    5. Then

      He writes a DLL (dynamic-link library) that hooks both functions: it caches the length of the long string, and inserts items directly. The online load falls to 1 minute 50 seconds.

    6. 28 Feb 2021

      He publishes "How I cut GTA Online loading times by 70%", with the proof of concept on GitHub. It reaches the top of Hacker News.

    7. 15 Mar 2021

      t0st reports that Rockstar has confirmed a fix is coming and has awarded him US$10,000 through its bug bounty, as an exception to a programme usually reserved for security issues.

    8. 16 Mar 2021

      Rockstar's title update notes list "Improvements to PC loading times", with thanks to t0st. On the same machine, his stopwatch reads about 1 minute 55 seconds.

  3. 3Find

    Root cause

    Note

    The first loop was hidden inside a library call. The loader read numbers out of the 10 megabyte JSON text with sscanf, a value at a time. Many C library implementations of sscanf call strlen on the input string first, and strlen walks every character until it finds the end. So reading each tiny value cost a pass over the rest of the 10 megabytes, and reading all of them cost a number of steps that grows with the square of the file size. In t0st's profile strlen alone took 22 percent of the samples.

    The second loop was in the game's own code. Each of the roughly 63,000 items was checked against the list of items already stored, entry by entry, before being added. By t0st's count that is (63,000 squared plus 63,000) divided by two, about 1.98 billion comparisons. The structure held hashes but was a plain array, "clearly not_a_hashmap", in his words; it started empty, every item in the file was unique, and the game already had a function to insert items directly.

    Fixing either loop helped. With only the duplicate check patched the load took 4 minutes 30 seconds; with only the parser patched, 2 minutes 50 seconds; with both, 1 minute 50 seconds, a 69.4 percent improvement on his machine.

    Two loops inside a six-minute load GTA Online's loader parsed a 10 megabyte JSON file of about 63,000 items with sscanf, which ran strlen over the rest of the file for every value read, then checked each item against every item already stored. Both costs grow with the square of the input, and one processor core sat at full load for about four minutes. Bars drawn to scale for t0st's AMD FX-8350: about 6 minutes originally, 4 minutes 30 seconds with only the duplicate check fixed, 2 minutes 50 seconds with only the parser fixed, and 1 minute 50 seconds with both, 69.4 percent less. After Rockstar's fix of 16 March 2021 the same machine loaded in about 1 minute 55 seconds. The data Loop one Loop two The symptom 10 MB of JSON about 63,000 items sscanf per value strlen over the rest Duplicate check each item vs all One core at 100% about four minutes Online load time on t0st's AMD FX-8350, drawn to scale Original ~6m flat Duplicate check fixed 4m 30s Parser fixed 2m 50s Both fixed 1m 50s, 69.4% less after Rockstar's own fix of 16 March 2021: about 1m 55s on the same machine
    Two pieces of work that grew with the square of the catalogue, and how much of the six minutes each one cost on t0st's machine.
  4. 4Trace

    Why it got through

    Both loops are linear work repeated inside a loop, so they are cheap when the data is small and get worse with the square of its size. A catalogue that is small when the code is written gives no sign of trouble, and the code that runs a strlen per value looks like one ordinary sscanf call. Nothing about the code reads as slow; only measuring the running program shows where the time goes.

    Measuring was all it took. t0st had no source code, no symbols and an obfuscated binary, and found both problems with Task Manager, a profiler that had not been updated in over ten years, and a disassembler. The evidence pointed at one core doing one thing for four minutes. The sources do not say what Rockstar measured internally, so this page does not guess why its own profiling did not catch it.

  5. 5Check

    The lesson

    Profile before you guess, and treat every library call inside a loop as a loop of its own. Work that grows with the square of the input hides in plain sight until the input grows.

  6. 6Change

    What changed afterwards

    Rockstar's Title Update 1.53 notes, under 16 March 2021, list "Improvements to PC loading times" and thank t0st for his contributions. Rockstar gave no figure and no technical detail, and t0st writes that it could not share more.

    Rockstar paid t0st US$10,000 through its HackerOne bug bounty, by his account as an exception, since the programme usually covers only security issues. His proof of concept, hardcoded for one game version, is archived with the note that Rockstar officially fixed the problem on 16 March 2021.

  7. 7Verify

    Where the sources differ

    • The 70 percent in the title is 69.4 percent in t0st's own arithmetic: about 6 minutes cut to 1 minute 50 seconds, on an AMD FX-8350. After Rockstar's update his stopwatch screenshot reads 1:54.88.
    • That the parse calls sscanf is t0st's inference from the disassembly ("fairly confident it's sscanf"), not something Rockstar confirmed. The duplicate check is often described as a hash map scanned linearly; t0st says it was not a hash map at all, but an array of hash and item pointers.
    • Rockstar confirmed the finding to PC Gamer, as PC Gamer reported, and its own notes thank t0st. The US$10,000 and the bounty being an exception come from t0st, and Rockstar published no figure.
    • A common telling credits Ghidra. t0st used an unnamed disassembler, Process Dump to dump the obfuscated binary and x64dbg for data samples. The sources used here do not say how long the slow loading had existed, so this page does not say it lasted years.
  8. 8Source

    Sources

  9. 9Go