Wow, that there's a video on haversine is uniquely interesting to me. We used that to compute "all points within a circle", which is basically a loop over your candidate points, compute the distance from the circle's center, and then discard those too far away. (The candidates are generated by some conservative approximation, such as by geohashes or R-trees. And there's all sorts of room in that first approximation for optimizing too.)
There's all sorts of room for optimization. Those familiar with 3D programming probably know the "use distance², not distance" to avoid needing to sqrt(), and similar tricks apply (you don't need to work in miles: e.g., you can convert the target distance to arc distance, and use that, which is what haversine speaks natively). We were also trying to get Go to inline some of the wrapper calls (so that we could work in more sane units, like lat/lng, and have a wrapper convert to, IIRC, radians) … but alas, Go only inline leaf functions, and the trig calls haversine requires basically meant we were never a leaf.
Also hit the uniquely human problem of: if you compute the query, you can spend infinitely long doing it: the right circle is fine if centered over Wyoming, but quite a problem if centered between NYC & Philly. (So as to overlay both.) If you don't detect the case, you'll time out, and users are unhappy. If you detect it and abort, users don't get data … and are unhappy. There's no way to win.
… then the "higher level" stuff knocks you down three pegs for trying to eek a few milliseconds out of haversine when you find out the protobuf library encodes the response slower than JSON, despite being binary. (But protobuf was written in Python, vs. the JSON library is in C. There's a C protobuf lib … but its own unittest segfaulted at the time. I hope it has been since fixed, but ugh.)
Also looked at our point type in Python. As you can imagine we alloc'd a few million of those, and the simple definition in Python of,
class Point:
__slots__ = ('x', 'y')
def __init__(self, x, y):
self.x = x
self y = y
contains
three heap allocations, and not small ones either, for what can be done for 16 B on the stack in some languages.
(And then we'd done some rather dumb things … which I see repeated a lot, not just at this job, like SQL databases with an ENUM column declared as VARCHAR, and the same string repeated forever and ever through the DB. All you needed was a SMALLINT, an ENUM if its supported…
And so much CSV.)