Speedily Parsing JSON in Rust with Serde

I tend to have hundreds of tabs open in Firefox. This is a habit I developed many years ago, around the same time I started installing masses of extensions, the cause of many strange bugs and crashes. I often ended up with corrupted sessions as a result, where my previous session would remain intact but everything after would be forgotten or corrupted.

As is my wont, I decided the problem was one that could be solved by a Simple Matter Of Programming, so I wrote a Perl script I could run after every session to perform rotating backups of the session files. I haven’t been able to track down the date of its creation, but I first imported it into the version control for my ‘miscellaneous computer-related files’ directory in 2013, and it must have been running for years before that.^[1]

When I was introduced to Rust in 2016, one of the first things I thought of was porting over my somewhat sluggish and ad hoc backup script. According to the Git log, I committed the first passing tests (tests! For a utility script! The wonder!) on the 14^th of July, under the name simple-backups (having by this time understood there was nothing Firefox-specific about the script), and renamed it two years later to rotating-backups (having by this time understood what I was doing).

Now, this program sufficed for the purpose, but it annoyed me that there was useful data in the session files (like the tab count and the last updated timestamp) that was ignored. Once every six months for the next couple of years, I would make an attempt to build something smarter (manage-firefox-sessions) on top of what I had. That’s where Serde came in.

The data

Firefox stores its sessions as .js files—actually plain JSON that looks a bit like this:

{
  "version": [
    "sessionrestore",
    1
  ],
  "windows": [
    {
      "tabs": [{
                  "entries": [
                    {
                      "url": "http://www.example.com/",
                      "title": "Example",
                      "charset": "UTF-8",
                      "ID": 1,
                      "docshellID": 1,
                      "originalURI": "http://www.example.com/",
                      "triggeringPrincipal_b64": "dHJpZ2dlcmluZ1ByaW5jaXBhbF9iNjQ=",
                      "principalToInherit_base64": "dHJpZ2dlcmluZ1ByaW5jaXBhbF9iYXNlNjQ=",
                      "triggeringPrincipal_base64": "cHJpbmNpcGFsVG9Jbmhlcml0X2Jhc2U2NA==",
                      "docIdentifier": 233,
                      "persist": true,
                      "referrer": "http://www.example.com/"
                    }
                  ],
                  "lastAccessed": 1496640858597,
                  "hidden": false,
                  "attributes": {},
                  "userContextId": 0,
                  "index": 1,
                  "image": "http://www.example.com/",
                  "iconLoadingPrincipal": ""
                }]
    }
  ],
  "selectedWindow": 0,
  "_closedWindows": [
    {
      "tabs": [
        {
          "entries": [
            {
              "url": "http://www.example.com/",
              "title": "Example",
              "charset": "UTF-8",
              "ID": 1,
              "docshellID": 1,
              "triggeringPrincipal_base64": "cHJpbmNpcGFsVG9Jbmhlcml0X2Jhc2U2NA==",
              "docIdentifier": 1574,
              "persist": true,
              "referrer": "http://www.example.com/",
              "originalURI": "http://www.example.com/",
              "triggeringPrincipal_b64": "dHJpZ2dlcmluZ1ByaW5jaXBhbF9iNjQ=",
              "principalToInherit_base64": "dHJpZ2dlcmluZ1ByaW5jaXBhbF9iYXNlNjQ="
            }
          ],
          "lastAccessed": 1496043942814,
          "hidden": false,
          "attributes": {},
          "userContextId": 0,
          "index": 1,
          "image": "http://www.example.com/",
          "iconLoadingPrincipal": ""
        }
      ],
      "selected": 1,
      "_closedTabs": [],
      "isPopup": true,
      "width": 800,
      "height": 600,
      "screenX": 0,
      "screenY": 0,
      "sizemode": "normal",
      "hidden": "menubar,toolbar,locationbar,personalbar,statusbar",
      "title": "Preferences",
      "closedAt": 1496043942816,
      "closedId": 8
    }
  ],
  "session": {
    "lastUpdate": 1496646054676,
    "startTime": 1496604632970,
    "recentCrashes": 0
  },
  "global": {}
}

In my case, this file would invariably fluctuate in size between 1 and 4 MB.

The first thing I did was to try and parse it with Serde, the de facto Rust (de)serialization library, in a straightforward way. I created a Session struct with a windows: Vec<Window>, where each Window has a tabs: Vec<Tab> and each Tab a Vec<Entry>. I painstakingly mapped each property in the JSON, set it up to parse the files, and ran it. It took 1.5 seconds per file.

I thought it might be because I was running in the default debug mode, so I tried with --release. That saved maybe 50 milliseconds. I pulled the parser out into a separate project and tried the same thing, with a little more brute force, using the json crate, which doesn’t use derive: it parses JSON into arrays, objects, numbers, and so on. It parsed the same files in 4–5 milliseconds each.

I didn’t think Serde itself could be responsible for the long parse times I was seeing, so I tried removing all the properties I didn’t care about, but it made no difference. I thought it was time to try profiling. I’d never done this before (except for JavaScript), and being on Windows made it much more complicated. Fortunately, I found a great post on profiling using perf in Docker. I followed it loosely and wound up peering at a fancy flamegraph. Sadly, all I understood was that it was spending a lot of time in Serde routines.

The last thing I tried, out of desperation, was to switch to a zero-copy model. Instead of Strings, I used &strs inside my deserialized structs. This meant adding lifetimes to the leaves and propagating those upwards, leaving me with strange code like #[serde(borrow)] windows: &'a Vec<Window<'a>>. I assumed I had missed some important steps, but I would let the compiler tell me what those were.

I built the project. There were no errors. I ran the tests. They passed. I ran the benchmark. The new time was… 6 milliseconds per file.

I rubbed my eyes and looked again. I hadn’t misread it. I went in and added some code to use the results, because, as you can imagine, this stark difference made me think the compiler might have been too smart for me and inferred that the parsing was unnecessary. The results didn’t change. Just switching to a zero-copy model, with minimal changes to my code, had given me a 250× speedup. In this very, very specific case. I’m unsure whether that’s impressive or concerning! Either way, what I learnt is that even if you’re not deep inside system code, given the right quantity of data, allocation matters.