Comment by baobabKoodaa
4 years ago
> My original point was that the reason for the performance drop likely wasn't related to algorithms. In practice, algorithms rarely are the issue. To clarify, in practice, what you use 90% of the time are plain arrays and indices / pointers. Occasionally you'll use a hashmap to lookup (distributed) or cache something.
This doesn't make any sense. It sounds like you're implying that algorithms are not... using plain arrays and pointers? But that's exactly how algorithms are usually constructed. Even the HashMaps you mentioned are typically implemented by using arrays and pointers. If you use arrays and pointers to write something that, let's say, has O(n^3) time complexity when the same operation could be written with O(n) time complexity, then you have an algorithm problem.
> Performance drops in the real world are most often explained by lack of understanding what certain library calls do, lack of understanding what are their performance characteristics, and/or lack of understanding what needs to be done to satisfy the requirements, or what the requirements should even be.
This is such a weak excuse. If you don't understand why a library call is crushing your performance, then stop using that library. People typically use libraries to do the tiniest of tasks, tasks that could often be solved with custom code that can be written in an hour. As the result of this attitude we have terminals that have performance issues... for rendering colored text. That's insane! Sometimes it feels like this whole field is just people gluing together pieces made by other people, with no understanding whatsoever about how everything works. There's no excusing for this behavior.
No need to get condescending.
> It sounds like you're implying that algorithms are not... using plain arrays and pointers?
Ok, but no, I did not mean to imply that. What I mean is that most programs are either straightforward linear scans over whole arrays, or working on data that was specifically requested by some index requested by a separate entity. Using a hashmap to lookup items faster is almost at the ceiling of complexity of most real-world programs.
And really, that's sufficient to do most things at max speed. "Algorithms" (meaning stuff like interval trees, Fenwick trees, LCA computation, square root decomposition...) is irrelevant academic exercise for the vast majority of applications (including kernels and games).
At the stage of using the most optimal algorithm (which is probably so simple that it doesn't deserve that name) we're still frequently dealing with factors of 10x to 1000x of inefficiencies - optimal code from an algorithms / asymptotic standpoint but just badly implemented.
> Sometimes it feels like this whole field is just people gluing together pieces made by other people, with no understanding whatsoever about how everything works.
That's exactly how it is. To people who want to do better I recommend to check out programmers like Casey Muratori (original poster of the github issue), and to check out Handmade Network community for example.
> There's no excusing for this behavior.
They didn't know better. Not particularly flattering though.
> No need to get condescending.
I apologize.
> Ok, but no, I did not mean to imply that. What I mean is that most programs are either straightforward linear scans over whole arrays, or working on data that was specifically requested by some index requested by a separate entity. Using a hashmap to lookup items faster is almost at the ceiling of complexity of most real-world programs.
Ok, now I see what you mean. I mean, I disagree with you, but I understand your point now.
> And really, that's sufficient to do most things at max speed. "Algorithms" (meaning stuff like interval trees, Fenwick trees, LCA computation, square root decomposition...) is irrelevant academic exercise for the vast majority of applications (including kernels and games).
Yes, all of the examples you provided are irrelevant for your average project. I don't mean that your average project would run into a need to optimize range queries with Fenwick trees. I mean your average project will run into situations where someone needs to write a simple O(n) list traversal, and they somehow manage to write it as O(n^2) because they have no understanding or interest towards algorithms. If the organization has staffed at least some people who care and have algorithm skills, they will spot these "low hanging fruit inefficiencies" and fix them.