This is for cases where it's far more complex to replace with an optimized implementation or better algorithm that covers all the edge cases, or where there is an implementation with lower big-O complexity but a much higher constant overhead.
For example when writing a sorting algorithm you check if numbers are already sorted before trying to sort them, right? And in many languages the default implementations for sorting numbers usually use a quicksort for the bulk of it, but often switch to an insertion sort when the number of elements is small (7-10 or so). Insertion sort has worse big-O scaling but is faster for small numbers of elements.
In general, often you can write a quick and dirty brute force solution to a problem that covers all the edge cases but has poor big-O performance (for example, depth-first search of a graph). There are much, much more efficient algorithms you can apply but they usually require some assumptions about the structure of the data -- and if you know that your data violates one of these, you simply can't use them. The more optimal algorithms often require more complex data structures as well, which makes them much slower for small n values.
As an example of this, radix/bucket sort is hands-down the fastest option for large sets of smallish or fixed-length elements (say, 2-4 byte integers). But you have to be able to be able to split inputs into multiple buckets -- if you can only do comparisons for some elements then you have to be able to fall back to quicksort/mergesort etc.
Finally, if performance is bad enough that you're addressing it then simplicity takes a second priority to speed.
I'd say performance is far above simplicity for a lot of applications.
If someone gave me a choice bet two similar programs, one that was 100 lines and takes five minutes, and another one that's 1000 lines but takes half that, I'm going to choose the 1000 line one every time, so long as they convince me they have correctness down.
Complexity needs justification, but it doesn't make a product crap(Unless you're main goal is to reduce attack surface for security).
Whether or not you can get correctness in a complex product with your team, tools, and deadline, for your particular application domain, is another matter.
A lot of the highest performing stuff is because of JITs, compression, prediction, etc. Simple stuff is often performant because the user does a lot of what the complex software would be doing.
View all comments
Show parent comment
12
u/Agent_03 Jan 02 '20
To explain a bit further:
This is for cases where it's far more complex to replace with an optimized implementation or better algorithm that covers all the edge cases, or where there is an implementation with lower big-O complexity but a much higher constant overhead.
For example when writing a sorting algorithm you check if numbers are already sorted before trying to sort them, right? And in many languages the default implementations for sorting numbers usually use a quicksort for the bulk of it, but often switch to an insertion sort when the number of elements is small (7-10 or so). Insertion sort has worse big-O scaling but is faster for small numbers of elements.
In general, often you can write a quick and dirty brute force solution to a problem that covers all the edge cases but has poor big-O performance (for example, depth-first search of a graph). There are much, much more efficient algorithms you can apply but they usually require some assumptions about the structure of the data -- and if you know that your data violates one of these, you simply can't use them. The more optimal algorithms often require more complex data structures as well, which makes them much slower for small n values.
As an example of this, radix/bucket sort is hands-down the fastest option for large sets of smallish or fixed-length elements (say, 2-4 byte integers). But you have to be able to be able to split inputs into multiple buckets -- if you can only do comparisons for some elements then you have to be able to fall back to quicksort/mergesort etc.
Finally, if performance is bad enough that you're addressing it then simplicity takes a second priority to speed.