51–60 of 92 posts
I’m amused to see a for loop in a function that is purportedly branchless (not a critique)
Great article, triggers some memories. When you get to think about branchless programming, especially for SIMD optimizations in the real world, you always learn a lot and it’s as if you get a +1 level on your algorithmic skills. The hardest part then is make sure the tricks are clearly laidout so that someone else can take it from here next time
On leetcode the "elegant" and fastest solution was something like this:
class Solution {
public:
int trap(vector& height) {
int i = 1;
int n = height.size();
int j = n - 1;
int leftmax = height[0];
int rightmax = height[n - 1];
int tw = 0;
while (i height[i]) {
tw += leftmax - height[i];
} else {
leftmax = height[i];
}
i++;
} else {
if (rightmax > height[j]) {
tw += rightmax - height[j];
} else {
rightmax = height[j];
}
j--;
}
}
return tw;
}
};
class Solution {
public:
int trap(const vector& height) {
int mx = 0;
long long sum = 0;
for (const auto h : height) {
mx = max(mx, h);
sum += mx - h;
}
int rMx = 0, h, i;
for (i = height.size() - 1; (h = height[i]) != mx; --i) {
rMx = max(h, rMx);
sum += rMx;
}
return sum - (height.size() - 1 - i) * mx;
}
};
Earlier quoted context omitted.
If you look at compiler output, you will always see plenty of small stupidities.
So why does conventional wisdom say that compilers will, in the vast majority of the time, outperform programmers doing assembly by hand? It seems contradictory to me.
But rules of thumb are like this. If you know enough to question the rule of thumb, go ahead. Hand assembly in hot code can be worth the cost.
It's also possible the value in ecx is used again outside the snippet?
Is cmov branchless, or just branching by another name?
JZ, JE - Jump if Zero, Jump if Equal
JNZ, JNE - Jump if Not Zero, Jump if Not Equal
JC - Jump if Carry
JNC - Jump if No Carry
JO - Jump if Overflow
JNO - Jump if No Overflow
JS - Jump if Signed (Negative)
JNS - Jump if Not Signed (Positive or Zero)
JP, JPE - Jump if Parity, Jump if Parity is Even
JNP, JPO - Jump if Not Parity, Jump if Parity is OddEarlier quoted context omitted.
So why does conventional wisdom say that compilers will, in the vast majority of the time, outperform programmers doing assembly by hand? It seems contradictory to me.
Because the cost of that unnecessary mov is very small, so the win from human assembly is very small. But rules of thumb are like this. If you know enough to question the rule of thumb, go ahead. Hand assembly in hot code can be worth the cost. It's also possible the value in ecx is used again outside the snippet?
Yes, there's the possibility that ecx is used elsewhere, and in that case, my second comment is irrelevant, because I was answering to the possibility that such big wart is to be expected from compilers because they crop up regularly.
But then again, it's unlikely that it's used elsewhere, because eax has the return value of the C snippet, there's nothing else to do, the function can return. So the original question remains: did this come from a C compiler? If yes, it's crappy code.
In the part about "abs", there's an assembly breakdown: mov eax, edi sar eax, 31 mov ecx, eax add edi, ecx xor eax, edi Has this been generated by a C compiler? If yes, it's a bit puzzling, because can't you remove "mov ecx, eax", replace "add edi, ecx" by "add edi, eax" and have the exact same result?
abs_branchless(int):
mov eax, edi
neg eax
cmovs eax, edi
ret
abs_branch(int):
mov eax, edi
neg eax
cmovs eax, edi
retEarlier quoted context omitted.
Because the cost of that unnecessary mov is very small, so the win from human assembly is very small. But rules of thumb are like this. If you know enough to question the rule of thumb, go ahead. Hand assembly in hot code can be worth the cost. It's also possible the value in ecx is used again outside the snippet?
In that context, it's not very small, it's 20% (all instructions are register-to-register instructions, so they all have the same weight). It's huge. Yes, there's the possibility that ecx is used elsewhere, and in that case, my second comment is irrelevant, because I was answering to the possibility that such big wart is to be expected from compilers because they crop up regularly. But then again, it's unlikely that…
Huge in space sure. Not in execution time.
Is cmov branchless, or just branching by another name?
From my understanding branches are about conditional jump instructions. Here are some of them: JZ, JE - Jump if Zero, Jump if Equal JNZ, JNE - Jump if Not Zero, Jump if Not Equal JC - Jump if Carry JNC - Jump if No Carry JO - Jump if Overflow JNO - Jump if No Overflow JS - Jump if Signed (Negative) JNS - Jump if Not Signed (Positive or Zero) JP, JPE - Jump if Parity, Jump if Parity is Even JNP, JPO - Jump if Not Pari…
This is just cutesy on CPUs, but is a big part of GPU programming.