Comment by xyzelement
4 years ago
This is both annoying and understandable. For the dev team, to dive into this performance optimization would mean punting something else from their roadmap. I suspect they weighed their perceived chances of success against the projected cost and reached a certain conclusion which in retrospect seems wrong. The independent developer did not have that "hurdle" as he simply did this at the expense of whatever other fun programming challenges he may have done those weekends. It's awesome that he turned out to be right. But I suspect if he turned out wrong we'd never hear about it. There was likely no tradeoff analysis on his part in undertaking this project, while the dev team did have to do one.
On the flip side, I have seen developers get really hung up on what is academically difficult rather than what is practically doable. I had a young developer who worked for me get really upset and hung up on the fact that something he was asked to do was NP equivalent, meaning there's no non-exponential time algorithm to implement what I was asking for. It took me weeks to realize this was messing with him and then about 5 mins to dig into the data and show that input length never practically exceeds like 7, so an exponential algorithm was fine. So I can see how a dev could get stuck thinking something is really hard when it really isn't. But I don't think it makes them a bad dev, it's just hard to transcend your own perspective.
I remember clearly when I first gained a real appreciation for the importance of measuring and considering your actual data.
I was trying to optimize a slow project doing some polyhedron dissection on large (~1M polyhedrons) meshes in real-time. As a first attempt I had my sights set on a function which tried to find a certain point on a surface by making an educated guess and then iteratively bumping its estimate in the right direction. I figured "I can solve this analytically instead!".
I did, and it made things approximately twice as slow. After scratching my head and outputting some data I realized my constant time solution required a number of expensive operations including sqrt and the iterative approach ran on average ~1 iteration and at most 3 iterations for just a handful of these millions of triangles.
> I realized my constant time solution required a number of expensive operations including sqrt and the iterative approach ran on average ~1 iteration
Yeah! It's deeply unsatisfying to forego algorithmic optimization but it often isn't necessary.
EG, when I do Advent of Code, I often write a naive algorithm that works correctly on the sample input, and then runs a really long time on the actual problem input. Before I go redo the algorithm, I often run it with PyPy instead of the standard Python, and 80% of the time it terminates quickly enough.
Similarly, whenever I happen to do AoC in C++, my naive algorithms happen to magically be fast enough out of the box so I don't even think about better algorithms. It's unfortunately counter to the intuition that you get from a CS programs that obsess with Big-O notation rather than implementation speed.
Big-O is really important but it seems like the input size where it starts to dominate implementation is much larger than our intuition suggests.
(of course it's also easy to write really bad algos that suck even on small input)
Unfortunately this was a case where the naive algorithm wasn't fast enough so we needed to optimise. But this particular part of it wasn't the solution.
We instead ended up changing our data format in a way which reduced cache misses.
Reminds me of the time I spent ten days building a memory allocator based on a red-black tree to optimize lookup times for an interpreter that needed to be fast. When I compared its performance against a linear search, it failed miserably. Turns out the fixed overhead in implementing a red-black tree vastly outweighs a naive approach when you're only dealing with 20 terms or so.