Python is slow. It’s still faster than a lot of other languages, but describing Python code as “fast” will probably get some weird looks from people who use compiled or JITted languages.

Still, I love Python for its design and speed at which I can write good code. Most of the time, when writing Python for distributed or web applications, it doesn’t matter. Your runtime is usually dominated by network traffic or data accesses than it is by raw computational speed. In those cases, the correct optimization is often reducing network requests or indexing your data.

Sometimes—just occasionally—we actually do need fast computation. Traditional Python wisdom has been to profile your code (perhaps using cProfile), identify the hot spot, and rewrite it in C as a Python extension. I’ve had to do that before for a handwriting recognition algorithm with great success (it turned a 2–3 second computation into a practically real-time one), but writing C code and then figuring out the FFI was a pain. I had to rewrite the algorithm in C, verify that my C version was correct and didn’t have memory errors, and then figure out the right incantations to get it to cooperate with Python.

Let’s try something different this time.

Problem

At DoubleMap, geographic distance calculation is something that gets used a lot, and we use the haversine function to calculate distance between two points on Earth. In some of our data analysis, we might run the haversine function millions of times in a tight loop, and it was causing some reports to take way too long.

Profiling the code showed that the two heaviest operations were fetching data from the data store and the haversine function.

Play along at home: Clone the repo at https://github.com/doublemap/haversine-optimization and start from the first commit to see how the code changes step by step.

The commands you should know are pip install cython and python setup.py build_ext --inplace.

Original code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from math import sin, cos, acos


def haversine(coord1, coord2):
    """Given two (lat, lng) tuples, returns the distance between them in
    meters."""
    lat1, lng1 = coord1
    lat2, lng2 = coord2

    if lat1 > 90 or lat1 < -90 or lat2 > 90 or lat2 < -90:
        raise ValueError("Invalid latitude (should be between +/- 90)")
    if lng1 > 180 or lng1 < -180 or lng2 > 180 or lng2 < -180:
        raise ValueError("Invalid longitude (should be between +/- 180)")

    phi1 = (90.0 - lat1) * 0.0174532925
    phi2 = (90.0 - lat2) * 0.0174532925
    theta1 = lng1 * 0.0174532925
    theta2 = lng2 * 0.0174532925

    c = (sin(phi1) * sin(phi2) * cos(theta1 - theta2) + cos(phi1) * cos(phi2))
    arc = acos(c)
    return arc * 6367444.7

Also, here’s the benchmark code that is used throughout:

1
2
3
4
5
6

from __future__ import print_function
from timeit import timeit

print(timeit("haversine((39.132213, -86.12439), (38.55213, -86.94910))",
             setup="from haversine import haversine",
             number=300000))

Pretty straightforward. Let’s try pre-compiling this code into a C extension to see if that helps.

Following the Cython Basic Tutorial, I renamed haversine.py to haversine.pyx and created a setup.py file:

1
2
3
4
5
6

from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules = cythonize("haversine.pyx")
)

Running python setup.py build_ext --inplace built haversine.so out of my unmodified Python code. Easy-peasy.

Benchmark results (300,000 iterations):

Original code: 2.85 seconds
Compiled: 2.01 seconds

So, 29% time savings without any modification to the original code.

C math functions

Currently, we’re still using Python’s math functions. Let’s see if we can cut out some overhead by importing math.h instead.

Except, since this is Cython, all we need to do is:

1
2
3
4
5

--- a/haversine.pyx
+++ b/haversine.pyx
@@ -1,4 +1,4 @@
-from math import sin, cos, acos
+from libc.math cimport sin, cos, acos

Benchmark results (300,000 iterations):

Original code: 2.85 seconds
Compiled: 2.01 seconds
libc.math: 1.33 seconds

So far we’ve saved 53% of the time from the original code.

C types

Cython’s biggest extension of the Python language is its type annotations. Speed ups can be had by telling Cython the types of each variable in advance. We are dealing with geographic coordinates, so we’ll be using doubles for pretty much everything:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def haversine(tuple coord1, tuple coord2):
    """Given two (lat, lng) tuples, returns the distance between them in
    meters."""
    cdef double lat1
    cdef double lng1
    cdef double lat2
    cdef double lng2
    lat1, lng1 = coord1
    lat2, lng2 = coord2

    if lat1 > 90 or lat1 < -90 or lat2 > 90 or lat2 < -90:
        raise ValueError("Invalid latitude (should be between +/- 90)")
    if lng1 > 180 or lng1 < -180 or lng2 > 180 or lng2 < -180:
        raise ValueError("Invalid longitude (should be between +/- 180)")

    cdef double ph1
    cdef double ph2
    cdef double theta1
    cdef double theta2
    cdef double c
    cdef double arc

    phi1 = (90.0 - lat1) * 0.0174532925
    phi2 = (90.0 - lat2) * 0.0174532925
    theta1 = lng1 * 0.0174532925
    theta2 = lng2 * 0.0174532925

    c = (sin(phi1) * sin(phi2) * cos(theta1 - theta2) + cos(phi1) * cos(phi2))
    arc = acos(c)
    return arc * 6367444.7

Original code: 2.85 seconds
Compiled: 2.01 seconds
libc.math: 1.33 seconds
C types: 0.466 seconds

In three easy steps, we’ve reduced the run time of this function by 84%. More importantly, we’re still writing what’s basically Python. We don’t have to remember to free our variables or check our array bounds. That additional safety is not free (and there are various flags to disable Cython safety checks) but with Cython, optimizing a Python function doesn’t have to be a rewrite-everything task.

We probably could have gone further in optimizing this, but these speed-ups got us into “good enough” territory, and that’s good enough.

Distribution

Our optimized haversine function is available on PyPI under the name “cHaversine”. One key difference is that the distributed tarball includes the C code generated by Cython so that you, as the package user, don’t need Cython to download and build the C extension.

Comments on Hacker News

Uptime Robot (free) + App Engine (free) + Twilio (cheap) = almost free downtime alerts!

1. Uptime Robot notices that your website is not responding.
2. Everyone Panic! checks Uptime Robot and sees that something is down.
3. You get a call through Twilio telling you to panic.
4. You get another call 15 minutes later because you still haven’t fixed the problem.

Sure, it’s easy to get emailed when your website goes down, but real honest-to-goodness phone calls have an immediacy that’s hard to beat.

Since our GPS bus-tracking system is used at all hours of the day, early on we introduced automated monitoring. But when everyone is asleep, emails and text messages go unnoticed until the morning and it sucks to not know where your bus is at 1am.

We quickly whipped an app together using Python to tie Uptime Robot and Twilio together. If one of the items in Uptime Robot goes down then the Python app will ask Twilio to call us. We made it, put it on App Engine, and haven’t touched it since. Even though our automated monitoring has grown since then, this little app, with zero maintenance, still dutifully watches Uptime Robot for any websites that are down.

Literally, there have been zero commits to the original repo since the first day. Now the code’s been cleaned up and put on GitHub. You can download it, configure it, and throw it onto App Engine or Heroku in a few minutes.

It’s not entirely free – you’ll need to pay Twilio for voice calls, but the price is $0.02 per call and it’s hard to think of a situation where knowing your website is down isn’t worth two cents. And, of course, you should keep your Twilio account balance in the black.

But for the hobbyist who doesn’t mind trying out a new app, this is a really simple way to have your phone ring when Hacker News tramples your latest pet project.

Everyone Panic! on GitHub

Comments on Hacker News

This past week, we here at DoubleMap made a big change that users probably won’t notice. Instead of Google Maps, all of our public maps are now powered by MapBox with OpenStreetMap data.

We have hundreds of thousands of hits per month to our online maps from people using our real-time bus tracking to find out where their bus is. This number doesn’t even include transit riders using their agency’s custom app or public TV displays.

For a company whose main feature is showing buses move on a map, it was a big deal for everyone – we had to make sure that data at each of our client transit agencies was good, update some of our sales material that specifically mentioned Google Maps, decide on new providers, and figure out the overall costs of switching and not switching. We didn’t want to disrupt our transit agencies and the riders that use our service to catch the bus every day. The actual coding changes were relatively straightforward.

Thanks to MapBox, were able to switch everything over almost seamlessly without interrupting our users or creating a jarring change.

Evaluation

It shouldn’t be a surprise that the main motivation was simply cost. Google doesn’t publish its enterprise maps pricing, but it’s orders of magnitude more expensive than MapBox.

We took a careful look at what we would have lost by switching away from Google. The main feature that we can’t get anywhere else is Street View, something that nobody has come close to replicating. We also lost out on angled aerial imagery. Both of these are cool, but ultimately not worth the price difference.

What’s in a map?

Part of the thinking change that most people have to go through when switching is that maps don’t always come in one giant bundle. “Google Maps” can refer to everything from the JavaScript library to the pop-ups with user reviews to the navigation to Street View. With OpenStreetMap, you get your choice of JavaScript mapping engine and different tile sets.

For example, you might choose to use Leaflet with OpenCycleMap and MapBox Satellite as your layers, or you might use OpenLayers with your own tileserver plus the Thunderforest Landscape map.

Everything is swappable. When we were testing, it was a one-line change to switch between MapQuest Open, CloudMade, and MapBox tiles.

We ended up using Leaflet with a custom MapBox style plus MapBox Satellite, and it looks pretty awesome.

Map styling

One of the complaints levied against OpenStreetMap is that their map style looks ugly. That’s not really fair, because OSM is there to provide the map data, and most people who see OSM data see it through a custom map style, like on FourSquare or Pinterest (or DoubleMap).

The power and curse of OSM is that you have total control over how the map looks. The power is that if you want a bubble-gum-pink map with 36pt Comic Sans labels and no roads, that’s easily doable. The curse is that it can get complicated, such as when you decide that you need to label each US highway using its state-specific shield image. As TileMill matures, there will hopefully be more and more styles to build on rather than starting from scratch.

One of the reasons why we initially went with CloudMade was because they had an easy online map styler that let you point and click a feature, and then change that feature class’s colors. This let us mostly duplicate our custom style we were using with Google Maps. CloudMade, however, decided to get out of non-enterprise services not too long after I had gotten the map to look the way I wanted it to.

Enter MapBox. MapBox has a really slick desktop program, TileMill, that lets you generate map tiles using a CSS-ish language called CartoCSS. The downside of TileMill is that you have to download raw map data, render the tiles you need (which easily gets into the gigabytes), and then upload them somewhere. We have clients internationally and we would have had to download each region’s OSM data and render new tiles every time we got another customer.

This is all fixed in TM2, which downloads vector map tiles from MapBox on the fly so you can upload just the compiled map style to MapBox and they’ll handle all the data and rendering as needed.

Here’s our result:

Our custom style is designed to be muted with a limited color palette to let our agencies’ custom route colors pop when overlaid. I hope to write about TileMill 2 in the future, but right now it’s in “experimental” status.

Porting the source code

Our original front-end code was written to use v2 of the Google Maps JS API. Once that was deprecated, we eventually rewrote it to use v3 of the Google Maps API. When we started investigating OSM as a replacement, we noticed how polished the Leaflet library was. The Leaflet API is based on v2 of the Google Maps API so we were essentially doing the reverse of what we had done in the past. All of the concepts mapped almost 1-to-1, and there was nothing that Leaflet lacked in terms of functionality.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

-    r.polyline = new google.maps.Polyline({
-        path: points,
-        map: r.visible ? map : null,
-        strokeColor: "#"+r.color,
-        strokeOpacity: 0.6,
-        strokeWeight: 4,
-        zIndex: 1
-    })
-    google.maps.event.addListener(r.polyline, 'mouseover',
-        function(routeId) {
+    r.polyline = new L.Polyline(points, {
+        color: "#"+r.color,
+        opacity: 0.6,
+        weight: 4
+    });
+    if(r.visible)
+        map.addLayer(r.polyline);
+
+    r.polyline.on('mouseover', function(routeId) {
             return function () { highlightRoute(routeId, true); };
         }(r.id));

This above snippet shows how a bit of our polyline code changed.

One happy side effect of this conversion was that the mobile web page (for users who can’t or don’t use our iPhone and Android apps) runs better. Animating markers on Google Maps with a Chrome-on-Android user agent would cause unbearable flickering. Leaflet runs smoothly on mobile.

OpenStreetMap for the future

We’re excited about joining the OpenStreetMap ecosystem. There’s an incredible amount of work that’s been put into OSM by its contributors, and we hope to contribute back what we can. One of our iPhone apps is already using MapBox on top of Apple Maps, and OSM might be what bring sanity back to mobile maps. We’re also looking at how we can use OSM data for geocoding, routing, and any other geo needs we might have – saving money while helping an open community grow is a win-win for the years to come.

You can check out one of live bus-tracking maps at iub.doublemap.com.

Comments on Hacker News