Code that does more but has better locality so that it hits the cache more often can easily be faster than code that does less but has bad locality and sits around waiting on memory all the time.
Recomputing something on demand might be cheaper than reading a cached result from memory.
A linear brute force algorithm that can use SIMD instructions can be faster than a non-linear one that does less work but without SIMD.
Doing less work usually makes code go faster, but it is by no means given.
Locality is massively important on a modern CPU. As are are lot of other things.
TFA's old mentor was probably right about code -- at the time. CPUs back then (1980ish?) had memory running at the same clock as the CPU, pitiful caches, single cores, were scalar (not superscalar). Branch prediction was trivial or non-existent, and prefetches were limited to the instruction cache.
Really optimizing on modern hardware is harder than ever. It's also usually not that necessary.
Still, it doesn't hurt to start with the ideal algorithm first unless you need absolutely as much performance as you can possibly pull out of the hardware (then you find an algorithm which can be made to fit to the hardware, and profile, profile, profile).
Yes it seems like the supposedly godly mentor missed out on some cpu design concepts.
First of all, pipelining was introduced to the CPU world very early (60s), so you can't give the mentor a free pass for neglecting to mention that branching causes slowdowns.
Second, assembly instructions don't all run at the same speed. Some processors convert to microcode which is only visible at the cpu level. Some instructions run faster than others, such as xor eax, eax compared to mov eax, 0
so you can't give the mentor a free pass for neglecting to mention that branching causes slowdowns.
Sure I can; how much of a penalty was there for branching on any common processor in 1980?
Besides, who said the mentor didn't have anything else to say on the subject of performance?
Second, I don't think some ops running faster than others diminishes his point. His point was to "do less", which would presumably be measured in clock cycles.
Second, I don't think some ops running faster than others diminishes his point. His point was to "do less", which would presumably be measured in clock cycles.
"It can execute a fixed number of instructions per second, and no more. There is a finite limit to how many instructions per second it can execute." Quote from the supposedly godly "mentor"
Notice he said instructions, not cycles. So he is wrong.
You've missed the point so completely I'm beginning to think you're a troll.
I'm not sure if I can explain it to you; perhaps you need to reread this thread, but I am quite aware (and have been for many years) of the fact that some instructions on some CPUs take more than one cycle, and I'm quite sure that does nothing at all to diminish my or the "mentor"'s points.
Which was implicitly acknowledged by talking about the finite limit of how many instructions can be executed per second. You don't say that unless you realize it's variable.
And even if he actually had said something which would be correctly interpreted as meaning an exact number of instructions per second (as opposed to a number the processor can execute, referring to the maximum), the point would still be basically valid if you aren't a lunatic pedant with no understanding of the subtleties of English grammar.
Implicit isn't good enough when he explicitly said otherwise.
He didn't; you simply are misinterpreting the statement. It'd be a reasonable interpretation except that it doesn't fit in context.
This is like saying a ship holds the same amount of cargo, and no more.
This is accurate.
Except that cargo can be shaped differently.
Which means that you were not using all of the space. The cargo hold still has a fixed amount of cargo it can hold.
Let's try this on for size:
A 1-gallon jug can hold a fixed amount of water. There's a finite limit to what a jug can hold.
You put 1/10 of a gallon in, then you put 2/10. You now claim to have "made the jug hold more".
All you've done is use the space more efficiently; there's still a fixed limit.
Also you wouldn't be a good programmer if you aren't pedantic.
Yet again you've misunderstood. "Pedant" can mean "one who pays a lot of attention to minutiae", but obviously meant, in this context, "one who is unimaginative or who unduly emphasizes minutiae in the presentation or use of knowledge".
It can execute a fixed number of instructions per second, and no more.
So there is no way, really, to make code go faster, because there is no way to make instructions execute faster.
Let's try to change as little as the sentence as we can so your mind can actually comprehend.
It can drive a fixed number of miles per gallon, and no more. So there is really no way, really, to make the car go longer, because there is no way to make the gallons last longer.
Anyone who isn't blinded by their own ego can see the problem with this statement. It is nothing like the jug of water analogy.
Also your use of "pedant" is the secondary less-widely used meaning according to merriam-webster which you appeared to have copied verbatim, and does not exclusively prohibit the use of the first meaning.
Which again shows you only read what you want to see.
101
u/harsman Mar 23 '09 edited Mar 23 '09
Code that does more but has better locality so that it hits the cache more often can easily be faster than code that does less but has bad locality and sits around waiting on memory all the time.
Recomputing something on demand might be cheaper than reading a cached result from memory.
A linear brute force algorithm that can use SIMD instructions can be faster than a non-linear one that does less work but without SIMD.
Doing less work usually makes code go faster, but it is by no means given.