7 ms·

IME, it has always turned out to be the correct decision to eliminate any n^2 operation in anything I’ve written. I don’t write exotic algorithms, but it’s alw

IME, it has always turned out to be the correct decision to eliminate any n^2 operation in anything I’ve written. I don’t write exotic algorithms, but it’s always astounding how small n needs to be to become observably problematic.

parthdesai 1y ago
My rule of thumb for 80%-90% of the problems is, if you need complicated algorithm, it means your data model isn't right. Sure, you do need complicated algorithms for compilers, db internals, route planning et all, but all things considered, those are minority of the use cases.
- anttihaapala 1y ago
  This is not a complicated algorithm. A hash map (dictionary) or a hash set is how you would always do deduplication in Python, because it is easiest to write / least keystrokes anyway. That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.
  - throwaway2037 1y ago
    > That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps. I am confused. There are plenty of open source, fast hash map impls in C.
    - saagarjha 1y ago
      Yes, the problem is getting them into your project.
      - account42 1y ago
        That's only a problem if you have never done any C development.
- paulddraper 1y ago
  This isn't knapsack. This is a dict lookup.
- LtWorf 1y ago
  I wrote a funny algorithm to group together words that end the same way to write them once in my binary wordlist file, since there is an array that points to the start character and a \0 to end the word. My initial solution was O(n²) but it was too slow on a real wordlist so I had to come up with something better. In the end I just sort the list with quicksort, but revert the order of the words and then the groupable ones end up nearby each other.
koala_man 1y ago
Good call. O(N^2) is the worst time complexity because it's fast enough to be instantaneous in all your testing, but slow enough to explode in prod. I've seen it several times before, and it's exactly what happened here.
- david422 1y ago
  We just had this exact problem. Tests ran great, production slowed to a crawl.
  - bcrl 1y ago
    I was just helping out with the network at an event. Worked great in testing, but it failed in production due to unicast flooding the network core. Turns out that some of the PoE Ethernet switches had an insufficiently sized CAM for the deployment combined with STP topology changes reducing the effective size of the CAM by a factor of 10 on the larger switches. Gotta love when packet forwarding goes from O(1) to O(n) and O(n^2)! Debugging that in production is non-trivial as the needle is in such a large haystack of packets so as to be nearly impossible to find in the output of tcpdump and wireshark. The horror... The horror...
  - hinkley 1y ago
    First big project I worked on a couple of us sped up the db initialization scripts so we could use a less trivial set of test data to stop this sort of shenanigans. Things like inserting the test data first and turning on constraints and possibly indexes afterward.
- deleted 1y ago
  [deleted]
SAI_Peregrinus 1y ago
I'd say the exception is when `n` is under about 10, and is counting some sort of hardware constrained thing (e.g. some operation over all CAN interfaces pesent on an OBDII connector can be O(n^(2)) since n will always be between 1 and 4). If you wouldn't have to physically replace hardware for `n` to increase, you really need to avoid n^2 operations. And even then consider them carefully, perhaps explicitly failing if `n` gets too big to allow for noticing rework is needed before new hardware hits the field.
- echelon 1y ago
  > perhaps explicitly failing if `n` gets too big That's the problem. A lot of these quadratic time algorithms don't set limits. Even 'n!' is fine for small 'n'. Real production use cases don't have small 'n'.
  - lassejansen 1y ago
    Or, phrased differently, if n has an upper limit, the algorithm is O(1).
    - connicpu 1y ago
      As long as you have tests that regularly exercise your algorithm at n=max where you would notice if they were exceptionally slow
  - masklinn 1y ago
    > Real production use cases don't have small 'n'. Real production use cases absolutely have small n. You don't hear about them, because it's very hard for them to cause issues. Unless the use case changes and now the n is not small anymore and nobody noticed the trap.
  - haiku2077 1y ago
    I have an app that's been running an O n^2 algorithm in "production" (free open source app used by various communities) for about half a year now. It's been fine because "n" is "number of aircraft flying in this flight simulator" - and the simulator's engine starts to fail above around 2000 anyway. So even in the worst case it's still going to run within milliseconds.
EdwardCoffin 1y ago
Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there. https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6st7nc2e https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
- paulddraper 1y ago
  The second law is that O(n * log n) is for practical intents and purposes O(n).
  - EdwardCoffin 1y ago
    To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6stamk2e https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
    - to11mtm 1y ago
      Fair, but `n log n` definitely is the historical "good enough to actually sleep at night" in my head, every time I see it I think of the prof who taught my first CSC course and our data structures course due to how often it came up. Also, the wise statement that 'memory is fairly cheap compared to CPU for scaling'. It's insane to see how often folks would rather manually open and scan a 'static-on-deploy' 20-100MB Json file for each request vs just parsing it into structures in memory (where, for most cases, the in memory usage is a fraction of the json itself) and just caching the parsed structure for the length of the application.
      - hinkley 1y ago
        Not often but occasionally I will chose the nlogn algorithm which obviously has no bugs over the O(n) algorithm with no obvious bugs. Less brittleness is worth paying a few percent. Especially if it unmuddies the waters enough for someone to spot other accidental (time) complexity.
vlovich123 1y ago
I have an n^3 operation that's currently a huge bottleneck at only 10k elements. Not sure how to fix it.
- IshKebab 1y ago
  I once looked into tree diffing algorithms (the literature is all about diffing XML even though it's really trees). The obvious dumb algorithm (which seems to be what everyone uses) is n^4.
esprehn 1y ago
Modern computers are pretty great at scanning small blocks of memory repeatedly, so n^2 can be faster than the alternative using a map in cases for small N. I spent a lot of time fixing n^2 in blink, but there were some fun surprises: https://source.chromium.org/chromium/chromium/src/+/main:third_party/blink/renderer/core/dom/nth_index_cache.h;l=5;drc=d0e504d96a8bb6f112afe38b626e929a95292758 https://source.chromium.org/chromium/chromium/src/+/main:thi... For large N without a cache :nth-child matching would be very slow doing n^2 scans of the siblings to compute the index. On the other hand for small sibling counts it turned out the cache overhead was noticably worse than just doing an n^2. (See the end of the linked comment). This turns out to be true in a lot of surprising places, both where linear search beats constant time maps, and where n^2 is better than fancy algorithms to compensate. Memory latency and instruction timing is the gotcha of many fun algorithms in the real world.
- throwaway2037 1y ago
  > where linear search beats constant time maps Can you give an example? You said lots of good things in your post, but I struggling to believe this one. Also, it would help to see some wall clock times or real world impact.
  - hansvm 1y ago
    Pick any compiled language and test it. Pick an algorithm making heavy use of a small (<10, maybe up to a hundred elements) hashset, and try using a linear structure instead. The difference will be most apparent with complicated keys, but even strings of more than a few characters should work. Some example workloads include: 1. Tokenization (checking if a word is a keyword) 2. Interpretation (mapping an instruction name to its action) 3. ML (encoding low-cardinality string features in something like catboost) 4. JSON parsers (usually key count is low, so parse into a linear-scan hashmap rather than a general-purpose hashmap) Details vary in the exact workload, the hardware you're using, what other instructions you're mixing in, etc. It's a well-known phenomenon though, and when you're doing a microoptimization pass it's definitely something to consider. 2x speedups are common. 10x or more happen from time to time. It's similar to (but not _quite_ the same as) the reason real-world binary search uses linear scans for small element counts. When you go to really optimize the system, you'll also find that the linear scan solution is often more amenable to performance improvements from batching. As to how much it matters for your composite program? Even at a microoptimization level I think it's much more important to pay attention to memory access patterns. When we wrote our protobuf parser that's all we really had to care about to improve performance (33% less execution time for the entire workload, proto parsing being much better than that). You're much more likely to be able to write sane code that way (contrasted with focusing on instructions and whatnot first), and it's easier to layer CPU improvements on top of a good memory access pattern than to go the other way around.
solardev 1y ago
For those of us without a formal comp sci background, is there a way for the IDE to detect and warn about these automatically? Or any other easy telltale signs to look for? As a self taught dev, when I encounter nested loops, I have to mentally go through them and try to see if they iterate through each item more than once. But that's not a very foolproof method.
- chacha102 1y ago
  Too much domain knowledge for an IDE to catch. I'm self taught as well, and it comes down to spending more time thinking about the code than writing the code. It's a fairly simple thought experiment to ask yourself what if there was 10x items in this array? 100x? That is essentially what the O(n) notation is trying to quantify. You just don't need to do it that formally.

parthdesai 1y ago

My rule of thumb for 80%-90% of the problems is, if you need complicated algorithm, it means your data model isn't right. Sure, you do need complicated algorithms for compilers, db internals, route planning et all, but all things considered, those are minority of the use cases.

anttihaapala 1y ago
This is not a complicated algorithm. A hash map (dictionary) or a hash set is how you would always do deduplication in Python, because it is easiest to write / least keystrokes anyway. That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.
- throwaway2037 1y ago
  > That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps. I am confused. There are plenty of open source, fast hash map impls in C.
  - saagarjha 1y ago
    Yes, the problem is getting them into your project.
    - account42 1y ago
      That's only a problem if you have never done any C development.
paulddraper 1y ago
This isn't knapsack. This is a dict lookup.
LtWorf 1y ago
I wrote a funny algorithm to group together words that end the same way to write them once in my binary wordlist file, since there is an array that points to the start character and a \0 to end the word. My initial solution was O(n²) but it was too slow on a real wordlist so I had to come up with something better. In the end I just sort the list with quicksort, but revert the order of the words and then the groupable ones end up nearby each other.

koala_man 1y ago

Good call. O(N^2) is the worst time complexity because it's fast enough to be instantaneous in all your testing, but slow enough to explode in prod. I've seen it several times before, and it's exactly what happened here.

david422 1y ago
We just had this exact problem. Tests ran great, production slowed to a crawl.
- bcrl 1y ago
  I was just helping out with the network at an event. Worked great in testing, but it failed in production due to unicast flooding the network core. Turns out that some of the PoE Ethernet switches had an insufficiently sized CAM for the deployment combined with STP topology changes reducing the effective size of the CAM by a factor of 10 on the larger switches. Gotta love when packet forwarding goes from O(1) to O(n) and O(n^2)! Debugging that in production is non-trivial as the needle is in such a large haystack of packets so as to be nearly impossible to find in the output of tcpdump and wireshark. The horror... The horror...
- hinkley 1y ago
  First big project I worked on a couple of us sped up the db initialization scripts so we could use a less trivial set of test data to stop this sort of shenanigans. Things like inserting the test data first and turning on constraints and possibly indexes afterward.
deleted 1y ago
[deleted]

SAI_Peregrinus 1y ago

I'd say the exception is when `n` is under about 10, and is counting some sort of hardware constrained thing (e.g. some operation over all CAN interfaces pesent on an OBDII connector can be O(n^(2)) since n will always be between 1 and 4). If you wouldn't have to physically replace hardware for `n` to increase, you really need to avoid n^2 operations. And even then consider them carefully, perhaps explicitly failing if `n` gets too big to allow for noticing rework is needed before new hardware hits the field.

echelon 1y ago
> perhaps explicitly failing if `n` gets too big That's the problem. A lot of these quadratic time algorithms don't set limits. Even 'n!' is fine for small 'n'. Real production use cases don't have small 'n'.
- lassejansen 1y ago
  Or, phrased differently, if n has an upper limit, the algorithm is O(1).
  - connicpu 1y ago
    As long as you have tests that regularly exercise your algorithm at n=max where you would notice if they were exceptionally slow
- masklinn 1y ago
  > Real production use cases don't have small 'n'. Real production use cases absolutely have small n. You don't hear about them, because it's very hard for them to cause issues. Unless the use case changes and now the n is not small anymore and nobody noticed the trap.
- haiku2077 1y ago
  I have an app that's been running an O n^2 algorithm in "production" (free open source app used by various communities) for about half a year now. It's been fine because "n" is "number of aircraft flying in this flight simulator" - and the simulator's engine starts to fail above around 2000 anyway. So even in the worst case it's still going to run within milliseconds.

EdwardCoffin 1y ago

Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there. https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6st7nc2e https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...

paulddraper 1y ago
The second law is that O(n * log n) is for practical intents and purposes O(n).
- EdwardCoffin 1y ago
  To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6stamk2e https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
  - to11mtm 1y ago
    Fair, but `n log n` definitely is the historical "good enough to actually sleep at night" in my head, every time I see it I think of the prof who taught my first CSC course and our data structures course due to how often it came up. Also, the wise statement that 'memory is fairly cheap compared to CPU for scaling'. It's insane to see how often folks would rather manually open and scan a 'static-on-deploy' 20-100MB Json file for each request vs just parsing it into structures in memory (where, for most cases, the in memory usage is a fraction of the json itself) and just caching the parsed structure for the length of the application.
    - hinkley 1y ago
      Not often but occasionally I will chose the nlogn algorithm which obviously has no bugs over the O(n) algorithm with no obvious bugs. Less brittleness is worth paying a few percent. Especially if it unmuddies the waters enough for someone to spot other accidental (time) complexity.

vlovich123 1y ago

I have an n^3 operation that's currently a huge bottleneck at only 10k elements. Not sure how to fix it.

IshKebab 1y ago
I once looked into tree diffing algorithms (the literature is all about diffing XML even though it's really trees). The obvious dumb algorithm (which seems to be what everyone uses) is n^4.

esprehn 1y ago

Modern computers are pretty great at scanning small blocks of memory repeatedly, so n^2 can be faster than the alternative using a map in cases for small N. I spent a lot of time fixing n^2 in blink, but there were some fun surprises: https://source.chromium.org/chromium/chromium/src/+/main:third_party/blink/renderer/core/dom/nth_index_cache.h;l=5;drc=d0e504d96a8bb6f112afe38b626e929a95292758 https://source.chromium.org/chromium/chromium/src/+/main:thi... For large N without a cache :nth-child matching would be very slow doing n^2 scans of the siblings to compute the index. On the other hand for small sibling counts it turned out the cache overhead was noticably worse than just doing an n^2. (See the end of the linked comment). This turns out to be true in a lot of surprising places, both where linear search beats constant time maps, and where n^2 is better than fancy algorithms to compensate. Memory latency and instruction timing is the gotcha of many fun algorithms in the real world.

throwaway2037 1y ago
> where linear search beats constant time maps Can you give an example? You said lots of good things in your post, but I struggling to believe this one. Also, it would help to see some wall clock times or real world impact.
- hansvm 1y ago
  Pick any compiled language and test it. Pick an algorithm making heavy use of a small (<10, maybe up to a hundred elements) hashset, and try using a linear structure instead. The difference will be most apparent with complicated keys, but even strings of more than a few characters should work. Some example workloads include: 1. Tokenization (checking if a word is a keyword) 2. Interpretation (mapping an instruction name to its action) 3. ML (encoding low-cardinality string features in something like catboost) 4. JSON parsers (usually key count is low, so parse into a linear-scan hashmap rather than a general-purpose hashmap) Details vary in the exact workload, the hardware you're using, what other instructions you're mixing in, etc. It's a well-known phenomenon though, and when you're doing a microoptimization pass it's definitely something to consider. 2x speedups are common. 10x or more happen from time to time. It's similar to (but not _quite_ the same as) the reason real-world binary search uses linear scans for small element counts. When you go to really optimize the system, you'll also find that the linear scan solution is often more amenable to performance improvements from batching. As to how much it matters for your composite program? Even at a microoptimization level I think it's much more important to pay attention to memory access patterns. When we wrote our protobuf parser that's all we really had to care about to improve performance (33% less execution time for the entire workload, proto parsing being much better than that). You're much more likely to be able to write sane code that way (contrasted with focusing on instructions and whatnot first), and it's easier to layer CPU improvements on top of a good memory access pattern than to go the other way around.

solardev 1y ago

For those of us without a formal comp sci background, is there a way for the IDE to detect and warn about these automatically? Or any other easy telltale signs to look for? As a self taught dev, when I encounter nested loops, I have to mentally go through them and try to see if they iterate through each item more than once. But that's not a very foolproof method.

chacha102 1y ago
Too much domain knowledge for an IDE to catch. I'm self taught as well, and it comes down to spending more time thinking about the code than writing the code. It's a fairly simple thought experiment to ask yourself what if there was 10x items in this array? 100x? That is essentially what the O(n) notation is trying to quantify. You just don't need to do it that formally.