Hacker News Reader

Comment by 01100011 | Hacker News Reader

Rule 3 gets me into trouble with CS majors a lot. I'm an EE by education and entered into SW via the bottom floor(embedded C/ASM) so it was late in my career before I knew the formal definition of big-O and complexity.

For most of my career, sticking to rule 3 made the most sense. When the CS major would be annoying and talk about big-O they usually forgot n was tiny. But then my job changed. I started working on different things. Suddenly my job started sounding more like a leetcode interview people complain about. Now n really is big and now it really does matter.

Keep in mind that Rob Pike comes from a different era when programming for 'big iron' looked a lot more like programming for an embedded microcontroller now.

View on HN

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/

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.

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.

Well it is hedged with the word "fancy". I think a charitable reading is to understand the problem domain. If N is always small then trying to minimize the big-O is just showing off and likely counterproductive in many ways. If N is large, it might be a requirement.

Most people don't need FFT algorithm for multiplying large numbers, Karatsuba's algorithm is fine. But in some domains the difference does matter.

Personally I usually see the opposite effect - people first reach for a too-naive approach and implement some O(n^2) algorithm where it wouldn't have even been more complex to implement something O(n) or O(n log n). And n is almost always small so it works fine, until it blows up spectacularly.

> Personally I usually see the opposite effect - people first reach for a too-naive approach and implement some O(n^2) algorithm where it wouldn't have even been more complex to implement something O(n) or O(n log n). And n is almost always small so it works fine, until it blows up spectacularly.

Same. People solve in ways that are very obviously going to cause serious problems in only a few short weeks or months and it’s endlessly frustrating. If you’re building a prototype, fine, but if you’re building for production, very far from fine.

Most frustrating because often there’s next to no cost in selecting and implementing the correct architecture, domain model, data structure, or algorithm up front.

My father did some programming in Fortran and Assembly of various flavors. He was always partial to lookup tables where they could replace complicated conditionals or computations. Memory was precious in his day but it could still be worth it if your program did something repeatedly (which most do).

Reply on news.ycombinator.com