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.
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 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.
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.