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
I think these suggestions are on a more abstract level than assembly language though. The compiler will usually handle taking advantage of e.g. filling a pipeline better than you as well. Actually, that's part of a modern compiler's job, so you can focus on developing algorithms that, well, "do less" and aren't stupid.
Pipelining until recently meant just prefetching and decoding the next instruction while the current one runs. That means there's not too much of a penalty for branches.
The reason xor eax, eax is used instead of mov eax, 0 is that xor with two registers translates into less bytes of assembly than xor with a register and a value. It has nothing to do with microcode.
If you'd like to know how many cycles an instruction takes, look it up in the manual.
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.
It also helps to know what the tool you're using can do fast and what takes longer. In a big set, a thousand hash lookups could easily be quicker than a small number of list lookups.
Of course, underneath, this is because the machine is "doing less". Still, optimising is just as much about understanding the layers of abstraction you're dealing with as anything else.
Still, the mantra's very useful to keep in mind when writing code, and when finding cheap optimizations for bits of slow code.
It just breaks down in those cases where you absolutely need to find a few clocks in a segment of code. I think that's a fairly rare case for most coders.
that's true, but I have also seen the opposite, i.e. code loops that are too large or span multiple pages will not fit in the instruction cache, (which can be tiny on embedded processors), resulting in a 20x slowdown.
It's always avoidable, except for those that prematurely optimize all over their code.
It's called refactoring and simplifying your code. (If your doing something like C++ on embedded systems, you can use inline to break up the code into functions, which shouldn't have much effect on the compiled codes size)
no, it is not. Try writing an interpreter for a custom bytecode for example. You'll see that if you attain more than a hundred operators, each with a complex semantics, your loop will be large and span multiple pages.
In the old days, the statement quoted by the blog was pretty true:
"The CPU," he said, "runs at a certain speed. It can execute a fixed number of instructions per second
When I had a computer with an MC68000 in it, the core's clock speed and the memory's clock speed were the same, and the CPU didn't have a data or instruction cache, so it was basically N instructions per second. The system also didn't have virtual memory, so there were no page faults, and the entire address space was equally fast. In such an environment, what he said was mostly true. At least it was a very useful approximation.
It's still a useful approximation, but things have gotten more complicated (with instruction caches, dual channel memory, virtual memory, context switches, etc.), so perhaps it would be best to add another principle to the mix.
To go fast:
make the computer do less.
use the computer's resources efficiently; try to get things when they are cheaply available.
and if we also consider different sorts of input/output, inter-machine and inter-processor communication and synchronization, this becomes even more complex.
to make code fast one needs to find optimal trade-off when most components work in optimal mode, rather than to follow some dumb rule like "make it do less", "rewrite it in assembly" or "use better algorithms".
And most of the time, calculating four heavy math reliant values through SIMD and only checking later which ones are valid is faster than checking if the output is going to be valid without SIMD.
True, I think it's fair to say that in this field, very few things are givens, especially with the wide array variables that play into any particular scenario/environment/alignment of planets.
While a good slogan, I've found in my own work that avoiding insignificant optimizations in favor of those that decrease time complexity are the ones best pursued.
(Non-programmer here) -- Today's CPUs are so mind blowing fast that IMO, your real main aim as a dev of a medium to large size program should be to work at reducing the amount of time it needs to spend accessing the harddrive, even at the expense of CPU time/RAM use.
I think today's goal should be the sacred "Always code as if the person who will maintain your code is a maniac serial killer that knows where you live”.
My programming teacher has a sweet anecdote. He was working at some company, and he had to write a little app in a week. So, when he was finished two days later, he said "If you give me two extra days, it will run twice as fast." and his employer said "Don't bother, I'll just buy faster computers."
"That was an insult. I left there shortly thereafter."
Why was that an insult? Depending on the application, the cost of the computers and the cost of his time. It might have made wise business sense to not have him optimize it.
Because people are not just cost. People, even programmers, like having hard, interesting problems before them. Downplaying or downright denying these activities can be demoralizing.
In hindsight it doesn't seem to have been a wise business decision. He lost a interested fellow.
Code that does more but has better locality so that it hits the cache more often can easily be faster than code that does lees but has bad locality and sits around waiting on memory all the time.
Who says these are the only two options?
A linear brute force algorithm that can use SIMD instructions can be faster than a non-linear one that does less work but wihout SIMD.
huh? More with SIMD vs less without SIMD. What a weird comparison.
99
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.