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 14th 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:
JSON{
"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
String
s, I used &str
s inside my deserialized struct
s. 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.
A word of warning from u/ectonDev on Reddit:
Only use
&str
if you can guarantee there won't be escaped characters in the source string. Otherwise, parsing will fail because escapes can only be dealt with by allocating.
You can allocate only when needed with a Cow<'_, str>. KhorneLordOfChaos's link has an example of that.
You have to use the
#[serde(borrow)]
attribute, otherwise it never borrows.
- Which explains the Perl part of it. I only broke the habit after 2015.↩