2 ms·
> That's an over-generalization I think most people here will interpret the word "can" in the sentence you're quoting as a caveat emptor; and I would add the s
by astrobe_ 4y ago
> That's an over-generalization
I think most people here will interpret the word "can" in the sentence you're quoting as a caveat emptor; and I would add the same applies to TFA. Loop fusion can etc. but measure if it actually does in your exact context.
> You can improve constant factors all day, but that won't obviate the need for doing millions comparisons.
> You can only take a dumb algorithm so far before it breaks down completely in practice.
If the dumb algorithm relies entirely on arithmetic while the better algorithm has conditional jumps, branch prediction misses can play against it for unexpectedly large input sizes.
Micro-optimizations may fall short quickly, but big-O() approved algorithms don't always win either, in practice.
- pclmulqdq 4y agoPeople usually underestimate where that line is. In my past experience, I ended up benchmarking binary search vs linear search on a collection of small objects. The breakeven point on a modern CPU was at 10 megabytes of data. Although this is a particularly extreme example, most people assume that collections of a few thousand items are where you should switch to big-O-optimal algorithms, but the breakeven is usually several orders of magnitude higher.
- AgentOrange1234 4y agoThat’s very surprising to me. My intuition screams that surely a binary search is competitive with a linear search even at small sizes. I would love to see benchmarks and code for this if you have them handy.