11 ms·

I find that the biggest misunderstanding happens because "new grads" (and I happen to be one) confuse _asymptotic complexity_ with actual complexity. I'm not s

I find that the biggest misunderstanding happens because "new grads" (and I happen to be one) confuse _asymptotic complexity_ with actual complexity. I'm not sure sure why, but CS courses and interview questions mostly focus on _asymptotic complexity_ and usually forget to take into consideration the complexity for "little values of n". And funnily enough, in real life n never goes to infinity! In a strict sense big O notation only cares about what happens when n goes to infinity. The algorithm could behave in any way up to numbers unimaginable (like TREE(3)) but still, its big O wouldn't change. Maybe what is missing to those "new grad" is a felling of real world data, and how a computer behave in the real world (with caches, latencies, optimised instructions etc...) not just having an ideal computer model in their mind when they design algorithms.

kevinventullo 7y ago
To be fair, in my experience it is often the case that asymptotic complexity is a good proxy for real-world performance, even for small values of n. Not always, but often. I think it's fine that the academic courses focus a bit more on what's better in theory than in practice, because there are always caveats to "in practice"; the person who writes the special-purpose genomics libraries was also once a new grad.
- saagarjha 7y ago
  Often, for small values of n performance matters less anyways matching that as n gets larger is often a nice bonus. Sometimes this makes the code more complicated, yes, but occasionally it can even make the code simpler, especially in a language with good data structures and algorithms (C++ is a shining example.)
  - monocasa 7y ago
    What if you have a large number of small N lists to be sorted?
- RookyNumbas 7y ago
  I like to start by thinking about cache locality and ensuring linear layout. Next focus on one-time, or minimal memory allocation. Then there are a bunch of small, systemic things you need to get right. After that you can start worrying about worst case big O scenarios. Of course this depends on your language. A c programmer will have a different mental model than a python one.
  - lonelappde 7y ago
    In Python performance is your last consideration, and that's OK. Most things computers do don't need to be fast. Only the innermost loops run the most do.
    - why_only_15 7y ago
      i used to think this was true, but theres a lot of stuff recently where there really aren't such hotspots everywhere. when i profile UI stuff for instance there isn't some big obvious hotspot to optimize, the runtime is spread all throughout the app doing random things. if all the regular code you write is just ludicrously slow, you're going to end up with something that's just laggy and without any way to fix it other than rewriting it
    - SaxonRobber 7y ago
      This is the philosophy that has led to our software becoming slower despite improvements in hardware. Performance is always important. Especially for consumer applications, where your software will probably need to run alongside many other processes each competing for resources.
      - celeritascelery 7y ago
        > This is the philosophy that has led to our software becoming slower despite improvements in hardware. I disagree. Software has gotten slower over time because we are adding more fluff to it (SDK’s, libraries, electron, GUI animations, web interactions, frameworks, etc). Not because the developers are failing to focus on code optimizations.
- monocasa 7y ago
  Eh, bubble sort can be quicker than q sort for samll values of N for instance.
samfisher83 7y ago
When you do big O analysis you get best case, worst case, and average case. You have to do some thinking about the structure of you data when doing big O analysis.
- saagarjha 7y ago
  No, the point here is that big-O analysis means nothing if n is small. If n < 10 your algorithm could be exponential and still do better than a linear algorithm with a constant factor a thousand times larger.
- TeMPOraL 7y ago
  It's not that. Something not properly covered in CS courses is that very often, performance is dominated by things that are not evaluated as a part of big O analysis. Like, memory allocations, cache friendliness, and other constant factors. For example, according to the theory, a hash table is much better suited for key lookup and random additions than a vector. In practice, if you're storing a couple hundred elements, a flat array (with objects stored directly) will be faster because of data locality. If your problems are mostly "do a lot of small N ops" and not "do some large N ops", then big O analysis isn't all that useful anymore.
  - seanmcdirmid 7y ago
    This is covered in computer architecture, at least, and sometimes (but not often) in compilers.
  - samfisher83 7y ago
    That is taught in your compilers class.
justinmeiners 7y ago
I regularly see people make this mistake and don't grasp it after correction. You could make a hash table with a constant time lookup, but the hash takes 1 hour. Big oh only tells you how it scales, not it's performance (runtime).
- TeMPOraL 7y ago
  It's not even that. You could have a normal hash table with a decent hashing function, and you'll still get beaten by a flat array for small n (hundreds, low thousands), because the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache.
  - dmoy 7y ago
    > the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache Also - if I see someone try to use a linked list for an enormous data structure again.... Wow it does not scale worth crap because it turns out that the hardware is actually important, and contiguous memory is amazing.
    - TeMPOraL 7y ago
      Oh god. Don't talk to me about linked lists. One of the bigger performance improvements I've made in a certain company is taking the code working with lots of numerical data in linked lists because they had easier syntax, and rewriting it using honest-to-god, contiguous-memory arrays of doubles. After that, we could process three orders of magnitude more numbers per operation, and one order of magnitude more of operations, and we still came ahead.
      - matwood 7y ago
        Maybe you knew the scale up front, but if you didn’t the easier syntax was the right first choice. It may have been the right first choice because it was easier to code even with the scale known up front. Only after measuring and understanding the trade offs should the easier to reason about code have been removed. IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer.
vvanders 7y ago
Yup, linear data reads are easily 10-30x faster than random thanks to cache miss penalty staying static since the 90s. If you want to see real-world DDR speeds figure out what algorithms do linear reads.
corysama 7y ago
It’s because Big O is Computer Science. Cache effects are Software Engineering. Professors of CS do a fine job of teaching CS. They even briefly mention that there is a implicit constant factor k in O(k n log(n)) and then they never mention it again. They certainly don’t mention that k can easily vary by 128x between algos. AKA: 7 levels of a binary tree. Or that most of the data they will be dealing with in practice not only won’t be infinite, but will actually be less than 128 bytes. Or, that even with huge data and an proven-ideal O() algo, there is often 10x speed-up to be had with a hybrid algo like a b-tree instead of a binary tree. And, another 2-10x with SIMD vs scalar. 100x isn’t infinite, but it’s still counts. So, grads listen to their CS professors and that’s what they know. It’s not until they get lectures from greybeard software engineers that they learn about the reality algos and not just the idealized algos.
- dilyevsky 7y ago
  Every good cs course has a section on cache aware algorithms. And i call bullshit that constant factor is not mentioned too
  - dwheeler 7y ago
    Mentioned, yes, but often not learned. In many situations the only thing that matters is the constant factor. If the number of data items is relatively small, the difference between N log N and and N squared may be completely dominated by the constant factor. In addition, there is the challenge of maintaining the code later and making sure it's correct.
    - vvanders 7y ago
      Yup, so much truth here. Take a look at Real-time Collision Detection[1]. I takes a great look at both algorithmic complexity and cache awareness. That's how it should be done. [1] https://www.amazon.com/dp/1558607323 https://www.amazon.com/dp/1558607323
  - corysama 7y ago
    It wasn’t taught to me. And, in my previous job I interviewed many dozen fresh grads. One of my questions was “How much slower is it to sum integers in a trivial linked list vs. a trivial array?” 90% answered “Umm... I don’t know. 2x?” When asked why, they all said “1 op to sum the int +1 op to traverse the pointer.” It was amazingly consistent.
loosetypes 7y ago
Complexity yes, but I feel scalability is similarly a word with a misleadingly narrow connotation in practice. Is an approach dependent on swathes of training data truly scalable if it doesn’t work for the first n attempts?
gorloth 7y ago
Taking the difference between normal complexity and asymptotic complexity to the extreme you have https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm which do have the best asymptotic performance, but only on values of n so large they never come up in real life.
tmpz22 7y ago
And they never factor in training or maintenance level complexity, i.e. your ball of mud runs fast but have fun teaching ~5 juniors how to use it two years from now.
- michaelchisari 7y ago
  This is key. If the number of objects processed will never be large, then it makes more sense to write a quick, easily understood O(n^2) loop in under a minute and move on. Taking an extra 30 minutes to an hour or longer to optimize and test for large inputs that will realistically never exist is a waste of time and money. If you feel that the value of N might, in some strange and rare combination of success and changed requirements, exceed the expected amount, add a check for the lowest value that may signify a problem and throw a warning. if N > 1000: debug.warn("N count of %d may be too large for existing algorithm. Consider optimizing.", N) Leave it at that and get on to more important things.
gok 7y ago
It's mostly a shibboleth to make sure you actually did the coursework on your resume.
GuB-42 7y ago
I am always uncomfortable with high "big O" algorithms. For example I know that with the data we have now, O(n^2) is fine, but if there is no strict bound on n, we don't know how far n will go in the future. It may also be a vulnerability, where the attacker uses data that is designed to exploit the worst case scenario. It is more about peace of mind. By using the more efficient algorithm (by asymptotic complexity), I know that my code won't become a bottleneck. That's like using "size_t" instead of "int" in C. I know my array will not exceed 4GB in any practical application, but by using size_t, I know it won't crash if it happens one day. One less thing to worry about. Almost all well designed libraries use hybrid approaches, switching from an algorithm optimized for low level efficiently for low N to a theoretically more efficient algorithm for high N. For example a sorting algorithm can go from insertion sort (good for low N) to quicksort (very efficient most cases) to merge sort (guaranteed nlog(n), highly parallelizable).
Zarel 7y ago
After a few years working on real-world code, I understood that faster asymptotic complexity was often slower on average. After a few more years working on real-world code, I understood that it's usually better to choose the algorithm with better asymptotic complexity, anyway. Like, sure, my O(n) algorithm will be 10x slower than your O(n^2) algorithm for small n. But users aren't going to notice a few microseconds. Users ARE going to notice my O(n) algorithm being 100000x faster for large n, when it's the difference between milliseconds and minutes.
- 3pt14159 7y ago
  It's a tough call sometimes. Code legibility is important and an O(n^2) is so often fast enough (microseconds!) that a more complex algorithm may be faster for the 0.001%ile and you're right that sometimes that means we should select it, because it makes the worst case still microseconds, but realistically speaking some codepaths change frequently enough that the true metric of a codebase is how easily it's adapted, understood, or modified. Let the guy with the big n eat cake, so to speak.

kevinventullo 7y ago

To be fair, in my experience it is often the case that asymptotic complexity is a good proxy for real-world performance, even for small values of n. Not always, but often. I think it's fine that the academic courses focus a bit more on what's better in theory than in practice, because there are always caveats to "in practice"; the person who writes the special-purpose genomics libraries was also once a new grad.

saagarjha 7y ago
Often, for small values of n performance matters less anyways matching that as n gets larger is often a nice bonus. Sometimes this makes the code more complicated, yes, but occasionally it can even make the code simpler, especially in a language with good data structures and algorithms (C++ is a shining example.)
- monocasa 7y ago
  What if you have a large number of small N lists to be sorted?
RookyNumbas 7y ago
I like to start by thinking about cache locality and ensuring linear layout. Next focus on one-time, or minimal memory allocation. Then there are a bunch of small, systemic things you need to get right. After that you can start worrying about worst case big O scenarios. Of course this depends on your language. A c programmer will have a different mental model than a python one.
- lonelappde 7y ago
  In Python performance is your last consideration, and that's OK. Most things computers do don't need to be fast. Only the innermost loops run the most do.
  - why_only_15 7y ago
    i used to think this was true, but theres a lot of stuff recently where there really aren't such hotspots everywhere. when i profile UI stuff for instance there isn't some big obvious hotspot to optimize, the runtime is spread all throughout the app doing random things. if all the regular code you write is just ludicrously slow, you're going to end up with something that's just laggy and without any way to fix it other than rewriting it
  - SaxonRobber 7y ago
    This is the philosophy that has led to our software becoming slower despite improvements in hardware. Performance is always important. Especially for consumer applications, where your software will probably need to run alongside many other processes each competing for resources.
    - celeritascelery 7y ago
      > This is the philosophy that has led to our software becoming slower despite improvements in hardware. I disagree. Software has gotten slower over time because we are adding more fluff to it (SDK’s, libraries, electron, GUI animations, web interactions, frameworks, etc). Not because the developers are failing to focus on code optimizations.
monocasa 7y ago
Eh, bubble sort can be quicker than q sort for samll values of N for instance.

samfisher83 7y ago

When you do big O analysis you get best case, worst case, and average case. You have to do some thinking about the structure of you data when doing big O analysis.

saagarjha 7y ago
No, the point here is that big-O analysis means nothing if n is small. If n < 10 your algorithm could be exponential and still do better than a linear algorithm with a constant factor a thousand times larger.
TeMPOraL 7y ago
It's not that. Something not properly covered in CS courses is that very often, performance is dominated by things that are not evaluated as a part of big O analysis. Like, memory allocations, cache friendliness, and other constant factors. For example, according to the theory, a hash table is much better suited for key lookup and random additions than a vector. In practice, if you're storing a couple hundred elements, a flat array (with objects stored directly) will be faster because of data locality. If your problems are mostly "do a lot of small N ops" and not "do some large N ops", then big O analysis isn't all that useful anymore.
- seanmcdirmid 7y ago
  This is covered in computer architecture, at least, and sometimes (but not often) in compilers.
- samfisher83 7y ago
  That is taught in your compilers class.

justinmeiners 7y ago

I regularly see people make this mistake and don't grasp it after correction. You could make a hash table with a constant time lookup, but the hash takes 1 hour. Big oh only tells you how it scales, not it's performance (runtime).

TeMPOraL 7y ago
It's not even that. You could have a normal hash table with a decent hashing function, and you'll still get beaten by a flat array for small n (hundreds, low thousands), because the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache.
- dmoy 7y ago
  > the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache Also - if I see someone try to use a linked list for an enormous data structure again.... Wow it does not scale worth crap because it turns out that the hardware is actually important, and contiguous memory is amazing.
  - TeMPOraL 7y ago
    Oh god. Don't talk to me about linked lists. One of the bigger performance improvements I've made in a certain company is taking the code working with lots of numerical data in linked lists because they had easier syntax, and rewriting it using honest-to-god, contiguous-memory arrays of doubles. After that, we could process three orders of magnitude more numbers per operation, and one order of magnitude more of operations, and we still came ahead.
    - matwood 7y ago
      Maybe you knew the scale up front, but if you didn’t the easier syntax was the right first choice. It may have been the right first choice because it was easier to code even with the scale known up front. Only after measuring and understanding the trade offs should the easier to reason about code have been removed. IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer.

vvanders 7y ago

Yup, linear data reads are easily 10-30x faster than random thanks to cache miss penalty staying static since the 90s. If you want to see real-world DDR speeds figure out what algorithms do linear reads.

corysama 7y ago

It’s because Big O is Computer Science. Cache effects are Software Engineering. Professors of CS do a fine job of teaching CS. They even briefly mention that there is a implicit constant factor k in O(k n log(n)) and then they never mention it again. They certainly don’t mention that k can easily vary by 128x between algos. AKA: 7 levels of a binary tree. Or that most of the data they will be dealing with in practice not only won’t be infinite, but will actually be less than 128 bytes. Or, that even with huge data and an proven-ideal O() algo, there is often 10x speed-up to be had with a hybrid algo like a b-tree instead of a binary tree. And, another 2-10x with SIMD vs scalar. 100x isn’t infinite, but it’s still counts. So, grads listen to their CS professors and that’s what they know. It’s not until they get lectures from greybeard software engineers that they learn about the reality algos and not just the idealized algos.

dilyevsky 7y ago
Every good cs course has a section on cache aware algorithms. And i call bullshit that constant factor is not mentioned too
- dwheeler 7y ago
  Mentioned, yes, but often not learned. In many situations the only thing that matters is the constant factor. If the number of data items is relatively small, the difference between N log N and and N squared may be completely dominated by the constant factor. In addition, there is the challenge of maintaining the code later and making sure it's correct.
  - vvanders 7y ago
    Yup, so much truth here. Take a look at Real-time Collision Detection[1]. I takes a great look at both algorithmic complexity and cache awareness. That's how it should be done. [1] https://www.amazon.com/dp/1558607323 https://www.amazon.com/dp/1558607323
- corysama 7y ago
  It wasn’t taught to me. And, in my previous job I interviewed many dozen fresh grads. One of my questions was “How much slower is it to sum integers in a trivial linked list vs. a trivial array?” 90% answered “Umm... I don’t know. 2x?” When asked why, they all said “1 op to sum the int +1 op to traverse the pointer.” It was amazingly consistent.

loosetypes 7y ago

Complexity yes, but I feel scalability is similarly a word with a misleadingly narrow connotation in practice. Is an approach dependent on swathes of training data truly scalable if it doesn’t work for the first n attempts?

gorloth 7y ago

Taking the difference between normal complexity and asymptotic complexity to the extreme you have https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm which do have the best asymptotic performance, but only on values of n so large they never come up in real life.

tmpz22 7y ago

And they never factor in training or maintenance level complexity, i.e. your ball of mud runs fast but have fun teaching ~5 juniors how to use it two years from now.

michaelchisari 7y ago
This is key. If the number of objects processed will never be large, then it makes more sense to write a quick, easily understood O(n^2) loop in under a minute and move on. Taking an extra 30 minutes to an hour or longer to optimize and test for large inputs that will realistically never exist is a waste of time and money. If you feel that the value of N might, in some strange and rare combination of success and changed requirements, exceed the expected amount, add a check for the lowest value that may signify a problem and throw a warning. if N > 1000: debug.warn("N count of %d may be too large for existing algorithm. Consider optimizing.", N) Leave it at that and get on to more important things.

gok 7y ago

It's mostly a shibboleth to make sure you actually did the coursework on your resume.

GuB-42 7y ago

I am always uncomfortable with high "big O" algorithms. For example I know that with the data we have now, O(n^2) is fine, but if there is no strict bound on n, we don't know how far n will go in the future. It may also be a vulnerability, where the attacker uses data that is designed to exploit the worst case scenario. It is more about peace of mind. By using the more efficient algorithm (by asymptotic complexity), I know that my code won't become a bottleneck. That's like using "size_t" instead of "int" in C. I know my array will not exceed 4GB in any practical application, but by using size_t, I know it won't crash if it happens one day. One less thing to worry about. Almost all well designed libraries use hybrid approaches, switching from an algorithm optimized for low level efficiently for low N to a theoretically more efficient algorithm for high N. For example a sorting algorithm can go from insertion sort (good for low N) to quicksort (very efficient most cases) to merge sort (guaranteed nlog(n), highly parallelizable).

Zarel 7y ago

After a few years working on real-world code, I understood that faster asymptotic complexity was often slower on average. After a few more years working on real-world code, I understood that it's usually better to choose the algorithm with better asymptotic complexity, anyway. Like, sure, my O(n) algorithm will be 10x slower than your O(n^2) algorithm for small n. But users aren't going to notice a few microseconds. Users ARE going to notice my O(n) algorithm being 100000x faster for large n, when it's the difference between milliseconds and minutes.

3pt14159 7y ago
It's a tough call sometimes. Code legibility is important and an O(n^2) is so often fast enough (microseconds!) that a more complex algorithm may be faster for the 0.001%ile and you're right that sometimes that means we should select it, because it makes the worst case still microseconds, but realistically speaking some codepaths change frequently enough that the true metric of a codebase is how easily it's adapted, understood, or modified. Let the guy with the big n eat cake, so to speak.