RetroGit #

tl;dr: RetroGit is a simple tool that sends you a daily (or weekly) digest of your GitHub commits from years past. Use it as a nostalgia trip or to remind you of TODOs that you never quite got around to cleaning up. Think of it as Timehop for your codebase.

It's now been a bit more than two years since I've joined Quip. I recall a sense of liberation the first few months as we were working in a very small, very new codebase. Compared with the much older and larger projects at Google, experimentation was expected, technical debt was non-existent, and in any case it seemed quite likely that almost everything would be rewritten before any real users saw it¹. It was also possible to skim every commit and generally have a sense that you could keep the whole project in your head.

As time passed, more and more code was written, prototypes were replaced with “productionized” systems and whole new areas that I was less familiar with (e.g. Android) were added. After about a year, I started to have the experience, familiar to any developer working on a large codebase for a while, of running blame on a file and being surprised by seeing my own name next to foreign-looking lines of code.

Generally, it seemed like the codebase was still manageable when working in a single area. Problems with keeping it all in my head appeared when doing context switches: working on tables for a month, switching to annotations for a couple of months, and then trying to get back into tables. By that point tables had been “swapped out” and it all felt a bit alien. Extrapolating from that, it seemed like coming back to a module a year later would effectively mean starting from scratch.

I wondered if I could build a tool to help me keep more of the codebase “paged in”. I've been a fan of Timehop for a while, back to the days when they were known as 4SquareAnd7YearsAgo. Besides the nostalgia factor, it did seem like periodic reminders of places I've gone to helped to keep those memories fresher. Since Quip uses GitHub for our codebase (and I had also migrated all my projects there a couple of years ago), it seemed like it would be possible to build a Timehop-like service for my past commits via their API.

I had also wanted to try building something with Go², and this seemed like a good fit. Between go-github and goauth2, the “boring” bits would be taken care of. App Engine's Go runtime also made it easy to deploy my code, and it didn't seem like this would be a very resource-intensive app (famous last words).

I started experimenting over Fourth of July weekend, and by working on it for a few hours a week I had it emailing me my daily digests by the end of the month. At this point I ran into what Akshay described as the “eh, it works well enough” trough, where it was harder to find the motivation to clean up the site so that others could use it too. But eventually it did reach a “1.0” state, including a name change, ending up with RetroGit.

The code ended up being quite straightforward, though I'm sure I have quite a ways to go before writing idiomatic Go. The site employs a design similar to Tweet Digest, where it doesn't store any data beyond an OAuth token, and instead just makes the necessary API calls on the fly to get the commits from years past. The GitHub API behaved as advertised — the only tricky bit was how to handle the my aforementioned migrated repositories. Their creation dates were 2011-2012, but they had commits going back much further. I didn't want to “probe” the interval going back indefinitely, just in case there were commits from that year — in theory someone could import some very old repositories into GitHub³. I ended up using the statistics endpoint to determine when the first commit for a user was in a repository, and persisting that as a “vintage” timestamp.

I'm not entirely happy with the visual design — I like the general “retro” theme, but I think executing it well is a bit beyond my Photoshop abilities. The punch card graphic is based on this “Fortran statement” card from this collection. WhatTheFont! identified the header font as ITC Blair Medium. Hopefully the styling within the emails is restrained enough that it won't affect readability. Relatedly, this was my first project where I had to generate HTML email, and I escaped with most of my sanity intact, though some things were still annoying. I found the CSS compatibility tables from MailChimp and Campaign Monitor, though I'm happy that I don't have care too much about more “mass market” clients (sorry Outlook users).

As to whether or not RetroGit is achieving its intended goal of helping me keep more of the Quip codebase in my head, it's hard to say for sure. One definite effect is that I pay more attention to commit messages, since I know I'll be seeing them a year from now. They're not quite link bait, but I do think that going beyond things like “Fixes #787” to also include a one-line summary in the message is helpful. In theory the issue has more details as to what was broken, but they can end up being re-opened, fixes re-attempted, etc. so it's nice to capture the context of a commit better. I've also been reminded of some old TODOs and done some commenting cleanups when it became apparent a year later that things could have been explained better.

If you'd like to try it yourself, all the site needs is for you to sign in with your GitHub account. There is an FAQ for the security conscious, and for the paranoid running your own instance on App Engine should be quite easy — the README covers the minimal setup necessary.

  1. It took me a while to stop having hangups about not choosing the most optimal/scalable solution for all problems. I didn't skew towards “over-engineered” solutions at Google, but somehow enough of the “will it scale” sentiment did seep in.
  2. My last attempt was pre-Go 1.0, and was too small to really “stick”.
  3. Now that Go itself has migrated to GitHub, the Gophers could use this to get reminders of where they started.

HTML Munging My Way To a React.js Conf Ticket #

Like many others, I was excited to see that Facebook is putting on a conference for the React community. Tickets were being released in three waves, and so for the last three Fridays I have been trying to get one. The first Friday I did not even manage to see an order form. The next week I got as far as choosing a quantity, before being told that tickets were sold out when pushing the “Submit” button.

Today was going to be my last chance, so I enlisted some coworkers to the cause — if any of them managed to get an order form the plan was that I would come by their desk and fill it out with my details. At 12 o'clock I struck out, but Bret and Casey both managed to run the gauntlet and make it to the order screen. However, once I tried to submit I was greeted with:

React.js Conf Order Failure

Based on Twitter, I was not the only one. Looking at the Dev Tools console showed that a bunch of URLs were failing to load from CloudFront, with pathnames like custom-tickets.js and custom-tickets.css. I assumed that some supporting resources were missing, hence the form was not entirely populated¹. After checking that those URL didn't load while tethered to my phone (in case our office network was banned for DDoS-like behavior), I decided to spelunk through the code and see if I could inject the missing form fields by hand. I found some promising-looking JavaScript of the form:

submitPaymentForm({
    number: $('.card-number').val(),
    cvc: $('.card-cvc').val(),
    exp_month: $('.card-expiry-month').val(),
    exp_year: $('.card-expiry-year').val(),
    name: $('.cardholder-name').val(),
    address_zip: $('.card-zipcode').val()
});

I therefore injected some DOM nodes with the appropriate class names and values and tried resubmitting. Unfortunately, I got the same error message. When I looked at the submitPaymentForm implementation, I could see that the input parameter was not actually used:

function submitPaymentForm(fields) {
    var $form = $("#billing-info-form");
    warnLeave = false;
    $form.get(0).submit();
}

I looked at the form fields that had loaded, and they had complex names like order[TicketOrder][email]. It seemed like it would be difficult to guess the names of the missing ones (I checked the network request and they were not being submitted at all). I then had the idea of finding another Splash event order form, and seeing if I could get the valid form fields from there. I eventually ended up on the ticket page for a music video release party that had a working credit card form. Excited, I copied the form fields into the React order page that I still had up, filled them out, and pressed “Submit”. There was a small bump where it thought that the expiration date field was required and not provided, but I bypassed that client-side check and got a promising-looking spinner that indicated that the order was being processed.

I was all set to be done, when the confirmation page finally loaded, and instead of being for the React conference, it was for the video release party. Evidently starting the order in a second tab had clobbered the some kind of cookie or other client-side state from the React tab. I had thus burned the order page on Bret's computer. However, Case had been dutifully keeping the session on his computer alive, so I switched to that one. There I went through the same process, but opened the “donor” order page in a Chrome incognito window. With bated breath I pressed the order button, and was relieved to see a confirmation page for React, and this email to arrive shortly after:

React.js Conf Order Success?

Possibly not quite as epic was my last attempt at working around broken service providers, but it still made for an exciting excuse to be late for lunch. And if anyone wants to go a music video release party tonight in Brooklyn, I have a ticket².

  1. I now see that other Splash order forms have the same network error, so it may have been a red herring.
  2. Amusingly enough, I appeared to have bought the last pre-sale ticket there — they are sold out too.

Two Hard Things #

Inspired by Phil Karlton's (possibly apocryphal) Two Hard Things, here's what I struggle with on a regular basis:

  1. Getting information X from system A to system B without violating the N layers of abstraction in between.
  2. Naming X such that the name is concise, unique (i.e. greppable) and has the right connotations to someone new to the codebase (or myself, a year later).

Gmail's HTML Tag Whitelist #

I couldn't find a comprehensive list of the HTML tags that Gmail's sanitizer allows through, so I wrote one up.

The Modern WebKit API is Open Source #

When doing web development (or really any development on a complex enough platform), sometimes the best course of action for understanding puzzling behavior is to read the source. It's therefore been fortunate that Chrome/Blink, WebKit (though not Safari) and Firefox/Gecko are all open source (and often the source is easily searchable too).

One of exceptions has been mobile WebKit when accessed via a UIWebView on iOS. Though it's based on the same components (WebCore, JavaScriptCore, WebKit API layer) as its desktop counterpart, there is enough mobile-specific behavior (e.g. interaction with auto-complete and the on-screen keyboard) that source access would come in handy. Apple would periodically do code dumps on opensource.apple.com, but those only included the WebCore and JavaScriptCore components¹ and in any case there hasn't been one since iOS 6.1.

At WWDC, as part of iOS 8, Apple announced a modern WebKit API that would be unified between the Mac and iOS. Much of the (positive) reaction has been about the new API giving third-party apps access to faster, JITed, JavaScript execution. However, just as important to me is the fact that implementation of the new API is open source.

Besides browsing around the source tree, it's also possible to track its development more closely, via an RSS feed of commits. However, there are no guarantees that just because something is available in the trunk repository that it will also be available on the (presumed) branch that iOS 8 is being worked on. For example, [WKWebView evaluateJavaScript:completionHandler:] was added on June 10, but it didn't show up in iOS 8 until beta 3, released on July 7 (beta 2 was released on June 17). More recent changes, such as the ability to control selection granularity (added on June 26) have yet to show up. There don't seem to be any (header) changes² that live purely in the iOS 8 SDK, so I'm inclined to believe that (at least at this stage) there's not much on-branch development, which is encouraging.

Many thanks to Anders, Benjamin, Mitz and all the other Apple engineers for doing all in the open.

Update on July 21, 2014: The selection granularity API has shown up in beta 4, which was released today.

  1. IANAL, but my understanding is that WebCore and JavaScriptCore are LGPL-licensed (due to its KHTML heritage) and so modifications in shipping software have to distributed as source, while WebKit is BSD-licensed, and therefore doesn't have that requirement.
  2. Modulo some munging done as part of the release process.

Using ASan with iOS Applications #

I've written up a quick guide for getting ASan (Address Sanitizer) working with iOS apps. This is the kind of thing I would have put directly into this blog in the past, but:

  1. Blogger's editor is not pleasant to use — I usually end up editing the HTML directly, especially for posts with code blocks. Not that Quip doesn't have bugs, but at least they're our bugs.
  2. Quip has public sharing now, so in theory that doc should be just as accessible (and indexable) as a regular post.

However, I still like the idea of this blog being a centralized repository of everything that I've written, hence this "stub" post.

Adding Keyboard Shortcuts For Inspecting iOS Apps and Web Pages in Safari #

Back in iOS 6 Apple added the ability to remotely inspect pages in mobile Safari and UIWebViews. While I'm very grateful for that capability, the fact that it's buried in a submenu in Safari's “Develop” menu means that I have to navigate a maze with a mouse every time I relaunch the app. I decided to investigate adding a way of triggering the inspector via a keyboard shortcut.

iPhone Simulator menu
The target

My first thought was that I could add a keyboard shortcut via OS X's built-in support. After all, “mobile.html” is just another menu item. Something like:

iPhone Simulator menu
If only it were so easy

Unfortunately, while that worked if I opened the “Develop” menu at least once, it didn't on a cold start of Safari. I'm guessing that the contents of the menu are generated dynamically (and lazily), and thus there isn't a “mobile.html” item initially for the keyboard shortcut system to hook into.

Inspired by a similar BBEdit script, I then decided to experiment with AppleScript and the System Events UI automation framework. After cursing at AppleScript for a while (can't wait for JavaScript for Automation), I ended up with:

tell application "Safari" to activate
tell application "System Events" to ¬
    click menu item "mobile.html" of menu ¬
        "iPhone Simulator" of menu item "iPhone Simulator" of menu ¬
        "Develop" of menu bar item "Develop" of menu bar 1 of process "Safari"

That seemed to work reliably, now it was just a matter of binding it to a keyboard shortcut. There apps like FastScripts that provide this capability, but to make the script more portable, I wanted a way that didn't depend on third-party software. It turned out that Automator can be used to do this, albeit in a somewhat convoluted fashion:

  1. Launch Automator
  2. Create a new “Service” workflow
  3. Add a “Run AppleScript” action¹
  4. Change the setting at the top of the window to “Service receives no input in any application“
  5. Replace the (* Your script goes here *) placeholder with the script above (your workflow should end up looking like this)
  6. Save the service as “Inspect Simulator”

I wanted to attach a keyboard shortcut to this service when either Safari or the simulator were running, but not in other apps. I therefore then went to the “App Shortcuts” keyboard preferences pane (pictured above) and added shortcuts for that menu item in both apps (to add shortcuts for the simulator, you need to select the “Other…” option in the menu and select it from /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/Applications/iPhone Simulator.app).

One final gotcha is that the first time the script is run in either app, you will get a “The action 'Run AppleScript' encountered an error.” dialog. Immediately behind that dialog is another, saying “'Safari.app' would like to control this computer using accessibility features.” You'll need to open the Security & Privacy preferences pane and enable Safari (and the simulator's) accessibility permissions.

  1. Not be confused with the “Execute AppleScript” action, which is a Remote Desktop one — I did that and was puzzled by the “no computers” error message for a good while.

Per-Package Method Counts for Android's DEX Format #

Quip's Android app recently ran into the Android DEX/Dalvik 64K method limit. We suspected that this was due to code generated by the Protocol Buffer compiler¹, but we wanted to get more specific numbers, to both understand the situation better and track our progress. As a starting point, we figured per-package method counts would give us what we needed.

The Android SDK ships with a dexdump tool that disassembles .dex (or .apk files) and dumps certain information out of it. Running it with the -f flag generated a method_ids_size line that showed that we were indeed precariously close to the limit. The script supports an XML output and per-class output of methods, so it seemed like a straightforward task to group methods and classes by package. However, once I actually processed its output, I got a much lower number than expected (when I did a sanity check to add up all the per-package counts). It turned out that the XML output is hardcoded to only output public classes and methods.

I then held my nose and rewrote the script to instead parse dexdump's text format. Unfortunately, even then there was some undercounting — not as significant, but I was missing a few thousand methods. I looked at the counts for a few classes, and nothing seemed to be missing, so this was perplexing. After some more digging, it turned out that the limit counts referenced methods too, not just those defined in the DEX file. Therefore iterating over the methods defined in each class was missing most of the android.* methods that we were calling.

Mohammad then pointed me at a script that used the smali/baksmali assembler/disassembler to generate per-package counts. However, when I ran it, it seemed to overcount. Looking into it a bit more, it looked like the script disassembled the .apk, re-assembled it to generate a .dex per package, and then ran dexdump on each one. However, this meant that referenced methods were counted by each package that used them, thus the overall count would include them more than once.

I briefly considered modifying dexdump to extract the information that I needed, but it didn't seem like a fun codebase to work in; besides being in C++ it had lots of dependencies into the rest of the Android tree. Looking around for other DEX format parses turned up smali's, dexinfo, dexinsight, dexterity, dexlib and a few others. All seemed to require a bit more effort to build and understand than I was willing to put in late on a Friday night. However, after browsing around through the Android tree more, I came across the dexdeps tool². It is designed for separating referenced and defined methods (and classes), but its DEX file parser looked simple enough to modify to extract the data that I was interested in. Better yet, it had no other dependencies, and looked straightforward to build.

Sure enough, it was pretty easy to modify it to create a per-package method counting tool. After a few more commits, I ended up with a dex-method-counts tool that can be pointed at an APK (or DEX file) and provide a package hierarchy tree-view of defined and referenced method counts. The README has a few more details, including a few flags that I've found useful when looking at protocol buffer compiler-generated code.

As for how we solved our actual method count limit problem, we've so far managed to stave off doom by refactoring our .proto files to include fewer messages in our Java build (we were picking up some that were for other platform or server use only). That is, nothing too crazy yet.

  1. For others in this situation, Square's Wire library may be an alternative.
  2. Somewhat amusingly, this is not the only Java-based DEX parser in the Android source tree, there is also dex-tools in the Compatibility Test Suite area.

Getting ALL your data out of Quip #

No, Quip is not shutting down. But we did just launch an API, so I thought I would take my experience with doing data export to write a backup tool that exports as much data as can be obtained via the API into a local folder. It's missing a few things (images most notably), but you do end up with a folder with all your documents (rendered to HTML) and conversations.

The tool is one of the samples¹ in our API repository, feel free to give it a spin. Pull requests are also welcome.

  1. The Webhook one is also mine. Party like it's 2009!

Saving The Day For (A Few) Veronica Mars Fans #

Yesterday was the release day of the Veronica Mars movie. As a Kickstarter backer, Ann got a digital copy of the movie. For reasons that I'm sure were not entirely technical, it was only available via Flixster/UltraViolet¹, so getting access to it involved registering for a new account and jumping through some hoops.

To actually download the movie for offline viewing, Flixster said it needed a “Flixster Desktop” client app. It was served as a ~29 MB .zip file, so it seemed like a straightforward download. I noticed that I was only getting ~ 30K/second download speeds, but I wasn't in a hurry, so I let it run. The download finished, but with only a ~21MB file that was malformed when I tried to expand it. I figured the WiFi of the hotel that we were staying at was somehow messing with the connection, so I tried again while tethered to my phone. I was still getting similarly slow download speeds, and the “completed” download was still too small. Since 30K/second was definitely under the expected tethered LTE throughput, I began to suspect Flixster's servers as the root cause. It certainly seemed plausible given that the file was served from desktop.flixster.com, which did not seem like a CDN domain². I guess ~60,000 fans were enough to DDoS it; from reading a Reddit thread, it seemed like I was not the only one.

The truncated downloads were of slightly different sizes, but it seemed like they finished in similar amounts of time, so I decided to be more scientific and timed the next attempt. It finished in exactly 10 minutes. My hypothesis was now that Flixster's server (or some intermediary) was terminating connections after 10 minutes, regardless of what was being transferred or what state it was in.

Chrome's download manager has a Pause/Resume link, so my next thought was to use it to break up the download into two smaller chunks. After getting the first 10 MB, I paused the download, disconnected the laptop from WiFi (to make sure the connection would not be reused) and then reconnected and tried resuming. Unfortunately, the download never restarted. I did a HEAD request on the file, and since the response headers did not include an Accept-Ranges header, I assumed that the server just didn't support resumable downloads, and that this path was a dead end.

After spending a few minutes trying to find a mirror of the app on sketchy download sites, a vague memory of Chrome's download manager not actually supporting HTTP range requests came to me. I did some quick tests with curl and saw that if I issued requests with --range parameters I got different results back. So it seemed like despite the lack of Accept-Ranges headers, the server (Apache fronted by Varnish) did in fact support range requests³.

I therefore downloaded the file in two chunks by using --range 0-10000000 and --range 10000000- and concatenated them with cat. Somewhat surprisingly, the resulting zip file was well-formed and expanded correctly. I put a copy of the file in my Dropbox account and shared it on the Reddit thread, it seemed to have helped a few others.

Of course, by the end of all this, I was more excited about having successfully downloaded the client app than getting or watching the movie itself⁴.

  1. As opposed to say, iTunes or Amazon.
  2. Now that I check the download page a day later, it seems to be served from static.flixstercdn.com, so I guess Flixster realized what was going on and fixed the problem.
  3. A closer reading of section 14.5 of the HTTP 1.1 spec showed that servers MAY respond with Accept-Ranges: bytes, but are not required to.
  4. Downloading the actual movie worked fine, I assume it was distributed over a CDN and thus wasn't quite so easily overwhelmed.

Finding Messages Explicitly Marked as Spam in Gmail #

tl;dr: Search Gmail for “is:spam -label:^os” to find messages that you manually marked as spam (as opposed to ones that Gmail automatically marked for you).

Gmail recently had a bug where some emails were accidentally moved to the trash or marked as spam. Google “encouraged” users that might have been affected to check their trash and spam folders for any messages that didn't belong. Since I get a lot of spam (one of the perks of having the same email address since 1996), I didn't relish the thought of going through thousands of messages to see if any of them were mislabeled¹.

I figured that Gmail must keep track of which messages were explicitly marked as spam by the user versus one that it automatically classifies (though I get a lot of spam, almost all of it is caught by Gmail's filters). Gmail (like Google Reader) keeps track of per-message state via internal system labels. For example, others have discovered that Gmail's Smart Labels are represented as ^smartlabel_type labels while Superstars uses names like ^ss_sy. Indeed, if you try to use a caret in a label name, Gmail says that it is not allowed.

It therefore seemed like a reasonable assumption that there was a system label that would tell us how a message came to be marked as spam. The problem was to figure out what it was called.

Thinking back to Reader (where all label operations went through an edit-tag HTTP API call, which listed the labels to added or removed), I figured I would see what the request was when marking a message as spam. Unfortunately, it looked like Gmail's requests were of slightly higher abstraction level, where marking a message as spam would send a request with an act=sp parameter (while marking as read uses act=rd, and so on).

I then figured I should look at HTTP response when loading the spam folder. There appeared to be a bunch of system label names associated with each message. One that I explicitly marked as spam had the labels:

"^a", "^ad_1391126400000", "^all", "^bsm"," ^clu_group", "^clu_unim", "^cob-processed-gmr", "^cob_pevent", "^oc_group", "^os_group", "^s", "^smartlabel_group", "^u"

Meanwhile, another that had been automatically marked as spam used:

"^ad_1391126400000", "^all"," ^bsm", "^clu_notification", "^cob-processed-gmr", "^oc_notification", "^os", "^os_notification", "^s", "^smartlabel_notification", "^u”

^s was present on all of them, and indeed doing a search for label:^s shows all spam messages (and the UI rewrites the search to in:spam). Others could also be puzzled out based on name, for example ^u is for unread messages. The more mysterious ones like ^cob_pevent I figured I could ignore².

After looking at a bunch of messages, both automatically and manually marked as spam, ^os stood out. It only seemed to be present on messages that Gmail itself had decided were spam. Doing the search is:spam -label:^os seemed to show only messages that I had marked as spam. Indeed, each of the messages in the result displayed the header: "Why is this message in Spam? You clicked 'Report spam' for this message." Thus I was able to go through the much shorter list and see if any where mistakenly marked (they weren't).

Seeing the plethora of labels that were present on all messages, I got curious what other internal labels there were. Between examining HTTP responses, looking through Gmail's JavaScript for strings that start with ^ and a simple dictionary attack for two-letter names, here's some others that I've found (those that are marked as “unknown” are ones that match some messages in my account, but with no apparent pattern):

  • ^a: archived conversations
  • ^b: chat transcripts (equivalent to is:chat, presumably the “b” is for “Buzz”, Google Talk's codename)
  • ^f: sent messages (equivalent to is:sent)
  • ^g: muted conversations (equivalent to is:muted, the “g” is most likely for “ignore”)
  • ^i: inbox (equivalent to in:inbox)
  • ^k: trashed messages (equivalent to in:trash, unclear why “k” is the abbreviation)
  • ^o: unknown
  • ^p: messages that were marked as phishing attempts
  • ^r: drafts (equivalent to is:draft)
  • ^s: spam (equivalent to is:spam)
  • ^t: starred messages (equivalent to is:starred, the “t” is most likely for “to do”)
  • ^u: unread messages (equivalent to is:unread)
  • ^ac: Google Buzz messages (equivalent to is:buzz)
  • ^act: Google Buzz messages (unclear how it's different from ^ac)
  • ^af: unknown
  • ^bc: unknown subset of chat transcripts
  • ^p_cc: another unknown subset of chat transcripts
  • ^fs: unknown
  • ^ia: unknown
  • ^ii: unknown
  • ^im: unknown
  • ^iim: Priority Inbox (based on Android's documentation)
  • ^mf: unknown
  • ^np: unknown
  • ^ns: unknown
  • ^bsm: unknown
  • ^op: messages that were automatically marked as phishing attempts
  • ^os: messages that were automatically marked as spam
  • ^vm: Google Voice voicemails (equivalent to is:voicemail)
  • ^pop: unknown, seems to match some (very old messages) that I imported via POP
  • ^ss_sy, ^ss_so, ^ss_sr, ^ss_sp, ^ss_sb, ^ss_sg, ^ss_cr, ^ss_co, ^ss_cy, ^ss_cg, ^ss_cb, ^ss_cp: Superstar stars
  • ^sl_root, ^smartlabel_promo, _receipt, _travel, _event, _group, _newsletter, _notification, _personal, _social, _receipt and _finance: Smart Labels
  • ^io_im: important messages (equivalent to is:important)
  • ^io_imc1 through ^io_imc5, ^io_lr: unknown, possibly more degrees of importance (“Info Overload” was the project that resulted in the importance filtering)
  • ^clu_unim: unknown, possibly unimportant messages
  • ^unsub and ^hunsub: messages where an unsubscribe link has been detected (when marking one as spam, the “In addition to marking this message as spam, you can unsubscribe...” dialog appears). ^unsub seems to be for messages where there's an unsubscribe link you have to click while ^hunsub is for ones where Gmail offers to unsubscribe on your behalf.
  • ^cff: sender is in a Google+ circle (equivalent to has:circle)
  • ^sps: unknown (no matches in my account, but it was referenced in the JavaScript next to ^p, if I had to guess I would say it's something related to spear phishing)
  • ^p_esnotif: Google+ notifications ("es" presumably being "Emerald Sea", Google+'s code name)
  1. Of course, in deciding to automate this task, I doomed myself to spend more time that I would have if I'd just gone through the messages by hand.
  2. It's somewhat interesting to see how features that were developed later (like Smart Labels — ^smartlabel_group) use longer system label names than ones of medium age (like Superstars — ^ss_sy) which are in turn longer than the original system labels (^u for unread, etc.). Bytes 10 years ago were clearly more precious.

JavaScript Array Sorting Performance Puzzler #

I recently fixed a small performance problem in Quip. Since it ended up being yet another tidbit in my mile-long list of factoids that are necessary to keep in your head when doing web development, I thought I would write up the process.

To implement search-as-you-type for contacts, documents, etc., Quip maintains a sorted array of index terms. Occasionally, this index needs to be updated on the client (for example, when a new contact is added). I noticed that the index updates were taking longer than expected, to the point where they were impacting typing latency if they happened at the wrong time.

As initially implemented the index update involving making the additions and modifications to the array, and then re-sorting it. It was the sort operation that was taking a while: up to a few hundred milliseconds in the case of an index with 10,000 terms. Given that in the grand scheme of things that is not a very big array and the sort was pure computation (with no need to touch the DOM or otherwise do anything expensive) that was surprising.

To be a bit more specific, the array that was being re-sorted was of the form:

[
    ["termA", ["id1", "id2", ...],
    ["termB", ["id7", "id9", ...],
    ...
]

I've created a jsPerf test case that simulates it (array1 in the setup code). On my machine that test runs at 4.23 runs/second, which works out to 236ms, which lines up well with that I was seeing within the Quip codebase.

My first guess was that the fact that the array was nearly in sorted order already was somehow triggering some pathological behavior in v8's sort implementation. I tested this guess by shuffling the array (array in the jsPerf test case), but sorting time was not affected. From reading the source this makes sense — for large arrays v8 uses Quicksort where the pivot point is picked as the median of the first, middle and last elements, thus it should still have O(N log N) running time regardless of the input's ordering.

I then wondered if the fact that the array members were arrays themselves was a factor. I created a simplified test case (array3 in the jsPerf test case) where the term was used as the array member directly, instead of being the first element in a sub-array. This resulted in significantly higher speeds (163 runs/second or 6.1ms). That was a bit surprising, since the effective thing being compared should have been the same (the terms were all unique, thus the list of IDs should not be a factor in the sorting).

I then decided to read the documentation a bit more carefully, which said “If [a comparator] is not supplied, elements are sorted by converting them to strings and comparing strings in lexicographic order.”¹ Though that behavior did result in a correct sort order, it did mean that each comparison involved the stringification of each of the sub-arrays, which meant a lot of needless memory allocations and computations.

Changing the sort to use a very simple comparator (function (a, b) { return a[0] < b[0] ? -1 : (a[0] > b[0] ? 1 : 0); }, see “array1 with comparator” on jsPerf) resulted in 302 runs/second, or 3.3ms. This was more inline with my expectations. Mystery solved.

Though as it turned out, in Quip's specific case, this optimization ended up not being needed, since I removed the need for the re-sorting altogether. It was instead more efficient to do an in-place modification or insertion in the right spot into the array. The correct index can be determined via binary search (i.e. O(log N)) and the insertion may involve O(N) operations to move the other array elements around, but that's still better than then O(N log N) of the re-sort.

  1. This default behavior also explains the seemingly non-intuitive result when sorting an array of numbers without a comparator.