6 ms·

"Instead of indexing the geofences using R-tree or the complicated S2, we chose a simpler route..." "While the runtime complexity of the solution remains O(N),

"Instead of indexing the geofences using R-tree or the complicated S2, we chose a simpler route..." "While the runtime complexity of the solution remains O(N), this simple technique reduced N from the order of 10,000s to the order of 100s." It seems odd to me that they're posting about the performance of Go, yet they deliberately chose a less optimal algorithm because the better ones were "complicated". Or, if their simpler approach did in fact run faster than R-trees or S2, it would have been nice to see some benchmarks and a clearer explanation for why. Choosing the best algorithm seems more important than the language in a case like this one.

brianwawok 11y ago
Sometimes a worse O algo is way better in real life, due to things such as memory alignment and page size. The more time you spend writing high performance code, the more you learn that the kind of algorithm analysis you learn in school is crap in the real world. If my O(N^2) also is 3 lines and smoking in real benchmarks your 600 line O(n log n) algo, guess which one I am using?
- buckhx 11y ago
  Raycasting is a pretty expensive operation since you have to check every edge of the polygon. Honestly I'm guessing they implemented the brute force method and called it good enough. Otherwise they would have posted comparisons as to why they stuck with brute force.
  - brianwawok 11y ago
    Well they had a clearly defined goal (which is rare!). 99% of requests in <= 100ms. So if brute force was a very simple algo and met the goal - hey why not? If you can come up with a goal of what you need the response times to be, I think the easiest (in terms of readability, testability, length, etc) solution to meet the goal should win.
  - sesquipedalian 11y ago
    I've found that BSP trees are a quite elegant, albeit, more complicated alternative for handling point-in-polygon queries compared to raycasting. Essentially, it decomposes an arbitrary non-convex polygon into a binary tree of half-spaces. A point-in-poly test then just becomes a binary search. That being said sometimes brute force is good enough.
- vvanders 11y ago
  Yup, so much this. I always have fun trotting out Radix Sort and watching fresh CS grads try to understand how a O(kN) walks over O(NlogN) by a factor of 10x+.
  - brianwawok 11y ago
    I also have fun busting out O(N^2) and getting a death stare. Then I ask them the biggest N could possibly be and get an answer like "16"...
    - vvanders 11y ago
      Haha yeah, Fun bit about Radix is it really scales well if your dataset fits in memory. Last time I benched my lame Java implementation it was about 2-5x faster than the built in Arrays.sort() on native values(float, int) and 20x faster when you started putting it up against Comparable. Trended that way well up to 65k+ entries. It gets even better if you can drop down to a proper native language that lets you prefetch.
  - chris_overseas 11y ago
    Absolutely. But the impression I get from the article isn't that they benchmarked their solution vs R-trees or S2 and it proved quicker, rather it seems to me they didn't bother trying the other approaches at all because of their perceived complexity. I might have the wrong end of the stick because the article doesn't go into enough detail to truly know either way. If they really didn't benchmark any other algorithms then talking about the performance of the language seems somewhat moot.
- rifung 11y ago
  I'm not sure that your example shows that the analysis you learn in school is "crap in the real world". Using O analysis is for seeing how an algorithm scales with respect to the input size. If anything, the fact that someone believes a O(nlogn) algorithm is always faster than O(n^2) is a failure on that person's part in properly understanding what O is used to measure.
buckhx 11y ago
Yep, I do not get that. Indexing by city first or another single dimensional key (quadkey/geohash) and having an rtree of your geometries inside of that is simple enough. Maybe if they're dealing w/ < 100 geometries per city it would be negligible but I'd assume NYC has more than that. Also don't know why they chose raycasting over winding number. I've been working on geo stuff in golang and building the geometry libraries for spatial indexing was easy enough to do in my spare time, so I don't know why they couldn't at least try.
openasocket 11y ago
FYI, searching the R-tree also has runtime complexity of O(N) in the worst case. I believe there is some R-tree variant which actually provides asymptotically better performance than the naive case, but it is very complicated and tends to perform worse on average in practice. Source: just spent two months implementing R-trees in Rust
- urschrei 11y ago
  Was just looking for an implementation last week. Is it public?
  - openasocket 11y ago
    Not yet, but it will probably be open sourced sometime soon.
- rosshemsley 11y ago
  Yes, but the O(N) is generally only for pathological inputs. Geo data is generally nicely distributed. R-tree (or similar) is the correct solution here.
azth 11y ago
> yet they deliberately chose a less optimal algorithm because the better ones were "complicated". Or the fact that due to the lack of generics in golang, it would make things even more complicated, and perhaps losing performance as well.

brianwawok 11y ago

Sometimes a worse O algo is way better in real life, due to things such as memory alignment and page size. The more time you spend writing high performance code, the more you learn that the kind of algorithm analysis you learn in school is crap in the real world. If my O(N^2) also is 3 lines and smoking in real benchmarks your 600 line O(n log n) algo, guess which one I am using?

buckhx 11y ago
Raycasting is a pretty expensive operation since you have to check every edge of the polygon. Honestly I'm guessing they implemented the brute force method and called it good enough. Otherwise they would have posted comparisons as to why they stuck with brute force.
- brianwawok 11y ago
  Well they had a clearly defined goal (which is rare!). 99% of requests in <= 100ms. So if brute force was a very simple algo and met the goal - hey why not? If you can come up with a goal of what you need the response times to be, I think the easiest (in terms of readability, testability, length, etc) solution to meet the goal should win.
- sesquipedalian 11y ago
  I've found that BSP trees are a quite elegant, albeit, more complicated alternative for handling point-in-polygon queries compared to raycasting. Essentially, it decomposes an arbitrary non-convex polygon into a binary tree of half-spaces. A point-in-poly test then just becomes a binary search. That being said sometimes brute force is good enough.
vvanders 11y ago
Yup, so much this. I always have fun trotting out Radix Sort and watching fresh CS grads try to understand how a O(kN) walks over O(NlogN) by a factor of 10x+.
- brianwawok 11y ago
  I also have fun busting out O(N^2) and getting a death stare. Then I ask them the biggest N could possibly be and get an answer like "16"...
  - vvanders 11y ago
    Haha yeah, Fun bit about Radix is it really scales well if your dataset fits in memory. Last time I benched my lame Java implementation it was about 2-5x faster than the built in Arrays.sort() on native values(float, int) and 20x faster when you started putting it up against Comparable. Trended that way well up to 65k+ entries. It gets even better if you can drop down to a proper native language that lets you prefetch.
- chris_overseas 11y ago
  Absolutely. But the impression I get from the article isn't that they benchmarked their solution vs R-trees or S2 and it proved quicker, rather it seems to me they didn't bother trying the other approaches at all because of their perceived complexity. I might have the wrong end of the stick because the article doesn't go into enough detail to truly know either way. If they really didn't benchmark any other algorithms then talking about the performance of the language seems somewhat moot.
rifung 11y ago
I'm not sure that your example shows that the analysis you learn in school is "crap in the real world". Using O analysis is for seeing how an algorithm scales with respect to the input size. If anything, the fact that someone believes a O(nlogn) algorithm is always faster than O(n^2) is a failure on that person's part in properly understanding what O is used to measure.

buckhx 11y ago

Yep, I do not get that. Indexing by city first or another single dimensional key (quadkey/geohash) and having an rtree of your geometries inside of that is simple enough. Maybe if they're dealing w/ < 100 geometries per city it would be negligible but I'd assume NYC has more than that. Also don't know why they chose raycasting over winding number. I've been working on geo stuff in golang and building the geometry libraries for spatial indexing was easy enough to do in my spare time, so I don't know why they couldn't at least try.

openasocket 11y ago

FYI, searching the R-tree also has runtime complexity of O(N) in the worst case. I believe there is some R-tree variant which actually provides asymptotically better performance than the naive case, but it is very complicated and tends to perform worse on average in practice. Source: just spent two months implementing R-trees in Rust

urschrei 11y ago
Was just looking for an implementation last week. Is it public?
- openasocket 11y ago
  Not yet, but it will probably be open sourced sometime soon.
rosshemsley 11y ago
Yes, but the O(N) is generally only for pathological inputs. Geo data is generally nicely distributed. R-tree (or similar) is the correct solution here.

azth 11y ago

> yet they deliberately chose a less optimal algorithm because the better ones were "complicated". Or the fact that due to the lack of generics in golang, it would make things even more complicated, and perhaps losing performance as well.