6 ms·

> Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, d

> Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 first.) Another point on this, which I really saw in action on a recent project - a "big" n is probably much bigger than you think. Sometimes it can be easy to think "oh, this is going to have to do 100,000 operations, I definitely need to optimize it" - but computers are fast, and 100,000 multiplications (for example) happens so fast you probably don't need to think too hard about it. That's not to say you shouldn't think at all, just that it's often surprising how insanely fast modern computing hardware is.

nine_zeros 3y ago
I also keep seeing leetcode interview problems about iterating over a list of 100k items a few times. I can see that it is not optimal but iterating over 100k items is NOTHING compared to the network call you made right after that iteration - in terms of actual production time. And every time I interview, the hiring managers want me but my hiring decision gets vetoed by a leetcode newbie who hasn't experienced production scars yet.
- deleted 3y ago
  [deleted]
- diarrhea 3y ago
  In an async framework of execution, this doesn't apply. A lot of programming happens in that space, and in it, the network call is "free", but you're clogging the thread(s) with actual CPU work. If execution is single-threaded, the problem becomes very relevant, but it applies to multi-threaded async just the same (you might exhaust the pool of workers). Keeping this in mind isn't esoteric either, as it applies to JavaScript, Python, Rust, C#, and probably others.
  - nine_zeros 3y ago
    > In an async framework of execution, this doesn't apply. That's right. Async execution prevents the IO from being the bottleneck by offloading it to a different thread. There are 3 situations where this statement falls apart: 1. If the execution is single threaded, as you rightly pointed out 2. If the response of the async execution matters to the final response of your service. In this case, the primary thread may finish its work but its still waiting for IO to complete. Basically making it synchronous but using async primitives. 3. The CPU utilization of iterating over 100k items in a list is negligible compared to the hundreds of daemons and services running on the host. Even a docker container will utilize more CPU than iteration over 100k items. The point is: over-indexing over iteration and time-complexity in interviews is pointless as real systems are going to face challenges far beyond that.
- mikhailfranco 3y ago
  So true. Managers really want to hire architects/seniordevs who are experienced, practical, smart and get things done. But if they let the other devs into the interview process they will get vetoes all the way down, because the reports will be: - envious of your amazing pragmatic and effective skills - jealous guarding of the architect promotion that they covet for themselves
  - wizofaus 3y ago
    Good managers for dev teams should have enough technical knowledge themselves and demand explanations from participating devs why a candidate is or isn't good enough to see through that though. Further personally as a tech lead I've always been keen to take on new devs that clearly are a cut above, as they usually mean an opportunity to work more effectively as a team. And I really don't want to spend even more of day doing reviews of mediocre code.
    - foobarian 3y ago
      > And I really don't want to spend even more of day doing reviews of mediocre code. Or writing essentially pseudocode in Jira description for the dev who can't figure things out. Ask me how I spent my day
    - nine_zeros 3y ago
      > Good managers for dev teams should have enough technical knowledge themselves and demand explanations from participating devs why a candidate is or isn't good enough to see through that though. I have a hunch that this is quite rare in most companies. Most managers are unskilled enough to override their own intuitions in favor of the mediocre leetcode dev that just vetoed a strong engineer.
mumblemumble 3y ago
The memory hierarchy plays into this, too. A lot of fancy algorithms have poor locality of reference and additional branching, so they tended to work better 40 years ago when CPUs weren't that much faster than memory and branch misprediction wasn't a thing that people had to worry about on consumer-grade hardware.
mikhailfranco 3y ago
The canonical reference for this: Scalability! But at what COST? https://www.frankmcsherry.org/assets/COST.pdf https://www.frankmcsherry.org/assets/COST.pdf
kagakuninja 3y ago
I was testing something, and wanted to add some useless for-loop addition code to simulate "doing work". I had to make huge nested loops before I noticed any significant CPU usage on my laptop.
- cratermoon 3y ago
  Were you using a language where the compiler/interpreter was smart enough to optimize out certain kinds of busy loops? It can sometimes take a little extra work to convince the compiler or runtime. In C the keyword 'volatile' can help.
- ska 3y ago
  Optimizing compilers are tricky this way, if you want to do it with optimzations turned on, you usually have to make the work "real" in some sense. Sometimes making enough nesting depth that the compiler can't fully reason it out works, but usually it's easier to modify some memory it can't be sure isn't touched otherwise (and hence elide or register allocate it or whatever).
kevincox 3y ago
I don't know how strongly I agree with this one. Quadratic algorithms are the kind of thing that bite you when you least expect it. I have seen production outages due to accidentally quadratic code and it is also the type of code where some users are suffering with a really slow application because they are frequently experiencing a big N even though 99% of users have a small N all the time. In most cases I would prefer to pick a less than quadratic algorithm even if it is a bit slower for the common case and a bit more complex to implement. Slow common cases get optimized, slow in rare cases often slips by the developers (who don't hit those cases) or break in production. Of course this is a tradeoff with Rule 4. If the fancy algorithm is much more complicated I will be more likely to pick the simple one even if it is quadratic and the data has the chance of occasionally being large. But by default I try to stick sub-quadratic if possible. I wrote an article about this relatively recently: https://kevincox.ca/2023/05/09/less-than-quadratic/ https://kevincox.ca/2023/05/09/less-than-quadratic/
- lynguist 3y ago
  We recently had a HN article about it: https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339 Some amazing person found that the load time of GTA V Online was awfully slow. It was slow because the developers put in a quadratic function at a time when the iteration object was small. But over time that object grew and so grew the load times quadratically until it was unbearable. And it was unbearable for millions of GTA V Online users. I fully agree that the accidentally quadratic functions will eventually come back to bite you/the user.
zoogeny 3y ago
When I got my first real programming job at a games company in the early 2000s, the Technical Director of the project once gave me some advice: if the number of things you are working with is on the order of 10,000 then don't bother optimizing it. Given the increase in computer power in the last 20 years I believe bumping that to 100,000 is pretty appropriate.
- wizofaus 3y ago
  And yet some of the worst performance issues I've had to deal with were in code typically dealing will merely 100s of items, but using algorithms and slow network-based operations that caused everything to run sluggishly most of the time and not infrequently making the resulting user experience intolerable. I do agree though that a lot of time is wasted on premature or even completely counterproductive optimisations for situations where the data being processed is too small to cause noticeable slowness in processing.
fasterik 3y ago
Not only that, but often our intuitions about what is "fast" are wrong if we are basing them on theoretical big-O concerns rather than the specifics of modern hardware. One example that's ubiquitous is using a hash table with chaining when a linear array lookup would be faster due to cache locality.

nine_zeros 3y ago

I also keep seeing leetcode interview problems about iterating over a list of 100k items a few times. I can see that it is not optimal but iterating over 100k items is NOTHING compared to the network call you made right after that iteration - in terms of actual production time. And every time I interview, the hiring managers want me but my hiring decision gets vetoed by a leetcode newbie who hasn't experienced production scars yet.

deleted 3y ago
[deleted]
diarrhea 3y ago
In an async framework of execution, this doesn't apply. A lot of programming happens in that space, and in it, the network call is "free", but you're clogging the thread(s) with actual CPU work. If execution is single-threaded, the problem becomes very relevant, but it applies to multi-threaded async just the same (you might exhaust the pool of workers). Keeping this in mind isn't esoteric either, as it applies to JavaScript, Python, Rust, C#, and probably others.
- nine_zeros 3y ago
  > In an async framework of execution, this doesn't apply. That's right. Async execution prevents the IO from being the bottleneck by offloading it to a different thread. There are 3 situations where this statement falls apart: 1. If the execution is single threaded, as you rightly pointed out 2. If the response of the async execution matters to the final response of your service. In this case, the primary thread may finish its work but its still waiting for IO to complete. Basically making it synchronous but using async primitives. 3. The CPU utilization of iterating over 100k items in a list is negligible compared to the hundreds of daemons and services running on the host. Even a docker container will utilize more CPU than iteration over 100k items. The point is: over-indexing over iteration and time-complexity in interviews is pointless as real systems are going to face challenges far beyond that.
mikhailfranco 3y ago
So true. Managers really want to hire architects/seniordevs who are experienced, practical, smart and get things done. But if they let the other devs into the interview process they will get vetoes all the way down, because the reports will be: - envious of your amazing pragmatic and effective skills - jealous guarding of the architect promotion that they covet for themselves
- wizofaus 3y ago
  Good managers for dev teams should have enough technical knowledge themselves and demand explanations from participating devs why a candidate is or isn't good enough to see through that though. Further personally as a tech lead I've always been keen to take on new devs that clearly are a cut above, as they usually mean an opportunity to work more effectively as a team. And I really don't want to spend even more of day doing reviews of mediocre code.
  - foobarian 3y ago
    > And I really don't want to spend even more of day doing reviews of mediocre code. Or writing essentially pseudocode in Jira description for the dev who can't figure things out. Ask me how I spent my day
  - nine_zeros 3y ago
    > Good managers for dev teams should have enough technical knowledge themselves and demand explanations from participating devs why a candidate is or isn't good enough to see through that though. I have a hunch that this is quite rare in most companies. Most managers are unskilled enough to override their own intuitions in favor of the mediocre leetcode dev that just vetoed a strong engineer.

mumblemumble 3y ago

The memory hierarchy plays into this, too. A lot of fancy algorithms have poor locality of reference and additional branching, so they tended to work better 40 years ago when CPUs weren't that much faster than memory and branch misprediction wasn't a thing that people had to worry about on consumer-grade hardware.

mikhailfranco 3y ago

The canonical reference for this: Scalability! But at what COST? https://www.frankmcsherry.org/assets/COST.pdf https://www.frankmcsherry.org/assets/COST.pdf

kagakuninja 3y ago

I was testing something, and wanted to add some useless for-loop addition code to simulate "doing work". I had to make huge nested loops before I noticed any significant CPU usage on my laptop.

cratermoon 3y ago
Were you using a language where the compiler/interpreter was smart enough to optimize out certain kinds of busy loops? It can sometimes take a little extra work to convince the compiler or runtime. In C the keyword 'volatile' can help.
ska 3y ago
Optimizing compilers are tricky this way, if you want to do it with optimzations turned on, you usually have to make the work "real" in some sense. Sometimes making enough nesting depth that the compiler can't fully reason it out works, but usually it's easier to modify some memory it can't be sure isn't touched otherwise (and hence elide or register allocate it or whatever).

kevincox 3y ago

I don't know how strongly I agree with this one. Quadratic algorithms are the kind of thing that bite you when you least expect it. I have seen production outages due to accidentally quadratic code and it is also the type of code where some users are suffering with a really slow application because they are frequently experiencing a big N even though 99% of users have a small N all the time. In most cases I would prefer to pick a less than quadratic algorithm even if it is a bit slower for the common case and a bit more complex to implement. Slow common cases get optimized, slow in rare cases often slips by the developers (who don't hit those cases) or break in production. Of course this is a tradeoff with Rule 4. If the fancy algorithm is much more complicated I will be more likely to pick the simple one even if it is quadratic and the data has the chance of occasionally being large. But by default I try to stick sub-quadratic if possible. I wrote an article about this relatively recently: https://kevincox.ca/2023/05/09/less-than-quadratic/ https://kevincox.ca/2023/05/09/less-than-quadratic/

lynguist 3y ago
We recently had a HN article about it: https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339 Some amazing person found that the load time of GTA V Online was awfully slow. It was slow because the developers put in a quadratic function at a time when the iteration object was small. But over time that object grew and so grew the load times quadratically until it was unbearable. And it was unbearable for millions of GTA V Online users. I fully agree that the accidentally quadratic functions will eventually come back to bite you/the user.

zoogeny 3y ago

When I got my first real programming job at a games company in the early 2000s, the Technical Director of the project once gave me some advice: if the number of things you are working with is on the order of 10,000 then don't bother optimizing it. Given the increase in computer power in the last 20 years I believe bumping that to 100,000 is pretty appropriate.

wizofaus 3y ago
And yet some of the worst performance issues I've had to deal with were in code typically dealing will merely 100s of items, but using algorithms and slow network-based operations that caused everything to run sluggishly most of the time and not infrequently making the resulting user experience intolerable. I do agree though that a lot of time is wasted on premature or even completely counterproductive optimisations for situations where the data being processed is too small to cause noticeable slowness in processing.

fasterik 3y ago

Not only that, but often our intuitions about what is "fast" are wrong if we are basing them on theoretical big-O concerns rather than the specifics of modern hardware. One example that's ubiquitous is using a hash table with chaining when a linear array lookup would be faster due to cache locality.