Daniel Compton

Suspiciously slow code

I’ve recently been working on a new ClojureScript application as part of a contract, and I was digging around for things to polish before launch. The app was mostly fast, but I noticed that when the main list of content got to around 40 items, it was a little bit slow to render. I also noticed that it seemed like it got almost twice as slow when I added another 10 items. At this point, you might already be having alarm bells go off in your head suggesting what the problem was likely to be. I didn’t, so I dived into the code to look at the part of the app rendering the main list.

Analysis

I looked over the code path that rendered the list, and wrapped time around a few suspect pieces of code. After a few checks, I found that a sort-by function in the view was the slow part, though it wasn’t immediately clear why sorting a list of 40 items would take a second. We were using a custom comparison function with sort-by to order items by state (flagged, unread, read, etc.), then reverse date order (newest items first).

sort-by takes a custom sort key function. Our comparison parsing the ISO 8601 timestamp into a date, then subtracting the current Unix time from the parsed Unix time to get an integer. The lowest numbers are the most recent dates and would be sorted first. I suspected that the date parsing could be the problem, but I wasn’t really sure. As an experiment, I disabled all of the date parsing, and returned the string directly for comparison. My sorting was the wrong way around, but it went from taking 1000 ms to 10 ms, a factor of 100x speedup!

A fix

A standard sort of the dates (which were in ISO 8601 order, e.g. 2016-04-02T08:24:31+00:00) sorted the oldest dates as the first ones in the list. After a few minutes thinking, I remembered I had recently read the clojure.org guide on comparators. In it, it discusses a reverse comparator:

(fn [a b] (compare b a))

This comparator is exactly the same as a normal comparator, but it will return the opposite result to what the normal one would. Passing this comparator to sort-by kept the 100x speedup, but sorted in the correct order. The list rendered in 10-15 ms, and was now plenty fast enough.

One question remained though, why was the list getting so much slower to render as I added a few more items to it? Of course reading this now, you Dear Reader are probably thinking to yourself, “aha! JavaScript’s sorting algorithm will be O(n log(n)), and the slow comparison function will therefore be called O(n log(n)) times.” It took me a bit more thinking than you (I didn’t have a blog post explaining why my code was slow to work from), but I got to this conclusion in the end too.

I really enjoyed this debugging session, as it is not very often that I can both speed up real world code by 100x, and get exposed directly to algorithmic complexity issues. A++, would debug again.