Comment by kevincox | Hacker News Reader

Comment by kevincox | Hacker News Reader

Parent Full thread

I actually disagree with Rule 3! While numbers are usually small being fast on small cases generally isn't as important as performing acceptably on large cases. So I prefer to take the better big-O so that it doesn't slow down unacceptably on real-world edge-case stresses. (The type of workloads that the devs often don't experience but your big customers will.)

Of course there is a balance to this, the engineering time to implement both options is an important consideration. But given both algorithms are relatively easy to implement I will default to the one that is faster at large sizes even if it is slower at common sizes. I do suspect that there is an implicit assumption that "fancy" algorithms take longer and are harder to implement. But in many cases both algorithms are in the standard library and just need to be selected. If this post focused on "fancy" in terms of actual time to implement rather than speed for common sizes I would be more inclined to agree with it.

I wrote an article about this a while back: https://kevincox.ca/2023/05/09/less-than-quadratic/

I think it's important to think about architectural and domain bounds on problems and check if the big-O-optimal algorithm ever comes out on top. I remember Bjarne Stroustrup did a lecture where he compared a reasonably-implemented big-O-optimal algorithm on linked lists to a less optimal algorithm using arrays, and he used his laptop to test at what data size the big-O-optimal algorithm started to beat the less optimal algorithm. What he found was that the less optimal algorithm beat the big-O-optimal algorithm for every dataset he could process on the laptop. In that case, architectural bounds meant that the big-O-optimal algorithm was strictly worse. That was an extreme case, but it shows the value of testing.

Domain bounds can be dangerous to rely on, but not always. For example, the number of U.S. states is unlikely to change significantly in the lifetime of your codebase.

Rule 3 was true 1989, back then computers were so slow and had barely any ram so most things you did only was reasonable for small number of inputs. Today we almost always have large amounts of inputs so its different.

This very much depends on where you work... and basically isn't true for most people. It's extremely true for some people.

Rule 3 is still very much real. Fancy fast algorithms often have other trade-offs. The best algorithm for the job is the one that meets all requirements well... Big-O is one aspect, data is another, determinism of the underlying things that are needed (dynamic memory allocation, etc) can be another.

It is important to remember that the art of sw engineering (like all engineering) lives in a balance between all these different requirements; not just in OPTIMIZE BIG-O.

Sure but the default (and usually correct) assumption when working at google (as an example) is basically "all numbers are big", so you you have to cluey about algorithms and data structures and not default to brute forcing something.

At 99% of shops it should be the other way around .

Even when you are working with large numbers, most numbers are usually small. Most of the code is probably not dealing with the large things, and a large thing may consist of a large number of instances that are individually small.

I've personally found it useful to always have concrete numbers in mind. An algorithm or data structure designed for N will probably be fine for N/10 and 10N, but it will often be inefficient for N/1000 or 1000N.

Reply on news.ycombinator.com