News for hackers. Stuff that matters.
Re:How We Built Uber’s Highest Query per Second Service Usin... by brianwawok on Tuesday March 01, 2016 @04:56PM (#11206416)
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?
Re:How We Built Uber’s Highest Query per Second Service Usin... by vvanders on Tuesday March 01, 2016 @05:15PM (#11206554)
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+.

Re:How We Built Uber’s Highest Query per Second Service Usin... by brianwawok on Tuesday March 01, 2016 @05:21PM (#11206596)
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"...
Re:How We Built Uber’s Highest Query per Second Service Usin... by vvanders on Tuesday March 01, 2016 @05:33PM (#11206673)
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.

Re:How We Built Uber’s Highest Query per Second Service Usin... by chris_overseas on Tuesday March 01, 2016 @05:29PM (#11206646)
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.
Re:How We Built Uber’s Highest Query per Second Service Usin... by rifung on Tuesday March 01, 2016 @06:41PM (#11207074)
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.

Re:How We Built Uber’s Highest Query per Second Service Usin... by buckhx on Tuesday March 01, 2016 @05:03PM (#11206476)
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.
Re:How We Built Uber’s Highest Query per Second Service Usin... by brianwawok on Tuesday March 01, 2016 @05:05PM (#11206483)
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.

Re:How We Built Uber’s Highest Query per Second Service Usin... by sesquipedalian on Tuesday March 01, 2016 @07:16PM (#11207263)
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.