Yes, so the burden of proof is on the algorithm. Adding more lines of code, by default, makes the code slower. If the algorithm is more efficient, it can make the code faster. But it must be more efficient.
This logic seems to hold up to me, but maybe I’m missing something here?
The key is that code isn't running in a vacuum. It's operating on data (or controlling systems, etc). A smaller amount of code may be operating on the data in an inefficient manner, whereas a larger amount may be doing it more efficiently.
In the above talk, this contrast is very stark, because the "more code" version does some stuff and then does the exact thing the "less code" version does, yet is faster.
This kind of thing is common enough (albeit less stark than in the above example), that "less code is faster" is not a great "default" assumption to make.
I’m not arguing that a more complex algorithm can do the same stuff quicker. Of course you can do that. There’s plenty of examples of that. But in the general case, doing more things takes longer.
Of course, the CPU can execute instructions in parallel, it can pipeline instructions and gain a higher throughput, it can predict branches, etc. But those are things you have to be intentional about enabling more often than not. Making small changes in the higher level code can ruin whatever performance gains you had gained because you accidentally trashed the throughput or something.
Generally, more instructions takes longer to process. Of course, a more complex algorithm can do the stuff quicker. But it’s not the default and depending on the problem, it can be very difficult to get it to go quicker with more instructions.
This isn’t even something that should be hard to conceptualize. Getting an element out of an array using an index is O(1). Getting an element out of a hashmap is also O(1) (when there’s no collisions). Even though these both perform the same in terms of complexity (“constant” time) the array will win every time if you already know the index. Why? Because the hashmap uses more instructions to figure out where the index is.
So I really don’t understand why the assumption that: generally, more code = slower is a bad one to make. Unless you explicitly try to make the code with more instructions faster, it will usually be slower than if you did it with less instructions.
It is actually the core of the entire understanding. There is no mapping whatsoever lines of code and instructions executed. A finite program that doesn't halt will result in infinite instructions. Less pedantically a sorting function that is far more efficient will result in the instructions corresponding to individual operations being called thousands of times less.
Basically everything from function calls to loops ruins any mapping between brevity and execution time.
And just to be clear, I do agree with everything you’re saying here, but I do think you’re still being overly pedantic.
> Less pedantically a sorting function that is far more efficient will result in the instructions corresponding to individual operations being called thousands of times less.
Exactly. The goal is to spend fewer instructions to achieve the same outcome. As soon as you start thinking about how different instructions take different amounts of cycles and you can speed up an algorithm by using more instructions that are cheaper, that kind of proves my whole point. You can speed up an algorithm by using more instructions, but you have to be intentional about it. The default will never be: more instructions = faster.
Basically,
> You can speed up an algorithm by using more instructions, but you have to be intentional about it.
I feel like most code is written with some intention. It depends on whether or not you believe that most code is written competently, I guess.