if条件树给switch语句效率带来麻烦
If conditional tree to switch statement efficiency troubles
我一直在尝试使用一长串 if 语句来优化函数。虽然我找到了一个使用 switch 语句作为替代的解决方案，但在测试和反汇编后，我发现它们只会使问题复杂化。
下面是一些代码来演示；
int ifFunc(int A, int B, int C){
int ret;
if (A > 0){
if (B > 0){
if (C > 0){
ret = C;
}
else{
ret = B;
}
}
else{
if(C > 0){
ret = C;
}
else{
ret = A;
}
}
}
else{
if (B > 0){
if (C > 0){
ret = C;
}
else{
ret = B;
}
}
else{
if (C > 0){
ret = C;
}
else{
ret = 0;
}
}
}
return ret;
}
int swFunc(int A, int B, int C){
int ret; int code = 0;
code += (A > 0) * 4, code += (B > 0) * 2, code += (C > 0) * 1;
switch(code){
case 0: // 000
ret = 0;
break;
case 1: // 001
ret = C;
break;
case 2: // 010
ret = B;
break;
case 3: // 011
ret = C;
break;
case 4: // 100
ret = A;
break;
case 5: // 101
ret = C;
break;
case 6: // 110
ret = B;
break;
case 7: // 111
ret = C;
break;
}
return ret;
}
// All these functions do is select a number that is positive,
// Giving preference to C, then B, then A
我可能犯了一些错误，所以他们做的事情可能不完全一样，但这不是重点。我试图用 switch 语句做的是创建一个只有一个跳转的 ifFunc 版本，方法是将每个 if 语句的结果转换成一个与位对齐的数字代码，这样每个可能的终点都有一个唯一的数字代码。
然而，这是平淡的，因为比较函数 (B > 0) 等在内部使用跳转。最终函数的 switch 版本比 if 版本慢一个数量级。
我想知道是否有一个比较语句，并让它输出零表示假，一个表示真，而不使用（内部或其他方式）if 语句或跳转。
不确定会好得多，但您可以尝试使用位域：
union SOMECONDTIONS {
unsigned char aggregate;
struct {
int c1:1;
int c2:1;
int c3:1;
int c4:1;
int c5:1;
int c6:1;
int c7:1;
int c8:1;
} conditions;
}
SOMECODITIONS c;
c.aggregate = 0;
c.conditions.c1 = A > 0;
c.conditions.c2 = B > 0;
c.conditions.c3 = C > 0;
switch(c.aggregate) {
...
可能这会...?
int ifFunc(int A, int B, int C){
if( C > 0 ) return C;
if( B > 0 ) return B;
if( A > 0 ) return A;
return 0;
}
编辑
对不起，我一定是误会了你——我以为你只需要减少条件分支的数量，而不是完全删除它们。这是解决方案（除非我犯了一些错误...），基于您的系统在 Two's complement 代码中工作的假设：
static const unsigned iMIN = ~(~0u >> 1); // binary 1000...0
static const int BITS_PER_BYTE = 8;
static inline int partialmask( int x ) {
// returns positive (0....) for positive x,
// negative (1....) for negative or zero x
return x | (int)(iMIN - (unsigned)x);
}
static inline int fullmask( int x ) {
// extends the sign bit so that
// positive becomes binary 0000...0 for positive x
// negative becomes binary 1111...1 for negative or zero x
return partialmask( x ) >> (BITS_PER_BYTE * sizeof(int) - 1);
}
int noIfFunc(int A, int B, int C){
int res = 0, mask;
mask = fullmask( A ); // negative or zero A causes an all-ones mask
res &= mask; // to preserve the res value
res |= A & ~mask; // and keep it from overwriting with A
mask = fullmask( B ); // positive B causes
res &= mask; // res to be cleared with all-zeros mask
res |= B & ~mask; // then overwritten with B
mask = fullmask( C );
res &= mask;
res |= C & ~mask;
return res; // finally res == most recent positive value (else zero)
}
可能这不是最短的代码。但是，如果适当减少（内联函数），它应该不包含任何分支。
我希望这段代码能帮助您删除汇编中的跳转...
static const int index[8] = {0, 1, 2, 2, 3, 3, 3, 3};
int ifFunc(int a, int b, int c)
{
const int ret[4] = {0, a, b, c};
const int bits = sizeof(int) * 8 - 1;
//const int i = ((((c - 1) >> bits) + 1) * 4) +
// ((((b - 1) >> bits) + 1) * 2) +
// (((a - 1) >> bits) + 1);
const int i = ((-c >> bits) * -4) -
((-b >> bits) * 2) -
(-a >> bits);
return ret[index[i]];
}
怎么样
if (C > 0) return C;
if (B > 0) return B;
if (A > 0) return A;
return 0;
或
return C > 0 ? C : (B > 0 ? B : (A > 0 ? A : 0)));
?
此外，如果编译器实现了条件赋值，
R= 0;
if (A > 0) R= A;
if (B > 0) R= B;
if (C > 0) R= C;
在最后一种情况下，MSVC 确实使用了条件赋值，但对于第三种情况，因为它更喜欢 return 归零寄存器 :(
; 7 : int R= 0;
; 8 : if (A > 0) R= A;
mov ecx, DWORD PTR _A$[esp-4]
xor eax, eax
test ecx, ecx
cmovg eax, ecx
; 9 : if (B > 0) R= B;
mov ecx, DWORD PTR _B$[esp-4]
test ecx, ecx
cmovg eax, ecx
; 10 : if (C > 0) R= C;
mov ecx, DWORD PTR _C$[esp-4]
test ecx, ecx
jle SHORT $LN1@f1
; 12 : return R;
mov eax, ecx
$LN1@f1:
ret 0
这是一个使用内联汇编几乎胜过编译器版本的解决方案。不好意思，昨晚才学汇编
int swFunc(int A, int B, int C){
int ret; char code;
//code += (A > 0) * 4, code += (B > 0) * 2, code += (C > 0) * 1
asm("movb [=10=], %[out];"
"cmpl [=10=], %[C];"
"setg %%al;"
"addb %%al, %[out];"
"cmpl [=10=], %[B];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
"cmpl [=10=], %[A];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
: [out] "+dl" (code)
: [A] "m" (A), [B] "m" (B), [C] "m" (C)
: "%eax", "%edx");
switch(code){
...
//same old switch statement
...
}
return ret;
}
当我将 asm 更改为；
asm ("cmpl [=11=], %[C];"
"setg %[out];"
"cmpl [=11=], %[B];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
"cmpl [=11=], %[A];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
: [out] "+dl" (code)
: [A] "m" (A), [B] "m" (B), [C] "m" (C)
: "%eax", "%edx");
它应该做同样的事情，但以更短、更甜美的方式，性能是相同的，因为编译器决定像这样引入 %cl 寄存器；
movzbl -0x5(%ebp),%eax // load 'code' into the register (not needed!)
mov %eax,%ecx // load 'code' into ecx?
cmpl [=12=]x0,0x10(%ebp) // compare 'C' and 0
setg %cl // set byte for code imediately, skips zeroing 'code'
cmpl [=12=]x0,0xc(%ebp) // compare 'B' and 0
setg %al
shl %al // set %al, then make it equal to two if not equal to zero
add %al,%cl // add it to code
cmpl [=12=]x0,0x8(%ebp) // compare 'A' and 0
setg %al
shl [=12=]x2,%al // set %al, then make it equal to four if not equal to zero
add %al,%cl // add it to code
mov %cl,-0x5(%ebp) // move the final value back onto the stack
需要注意的是，如果我要求编译器使用%cl，编译器将使用%dl，反之亦然。顽固的机器似乎不想打破它的记录。
直接执行条件似乎是一个好方法，因为这种方法非常接近击败编译器
我一直在尝试使用一长串 if 语句来优化函数。虽然我找到了一个使用 switch 语句作为替代的解决方案，但在测试和反汇编后，我发现它们只会使问题复杂化。 下面是一些代码来演示；
int ifFunc(int A, int B, int C){
int ret;
if (A > 0){
if (B > 0){
if (C > 0){
ret = C;
}
else{
ret = B;
}
}
else{
if(C > 0){
ret = C;
}
else{
ret = A;
}
}
}
else{
if (B > 0){
if (C > 0){
ret = C;
}
else{
ret = B;
}
}
else{
if (C > 0){
ret = C;
}
else{
ret = 0;
}
}
}
return ret;
}
int swFunc(int A, int B, int C){
int ret; int code = 0;
code += (A > 0) * 4, code += (B > 0) * 2, code += (C > 0) * 1;
switch(code){
case 0: // 000
ret = 0;
break;
case 1: // 001
ret = C;
break;
case 2: // 010
ret = B;
break;
case 3: // 011
ret = C;
break;
case 4: // 100
ret = A;
break;
case 5: // 101
ret = C;
break;
case 6: // 110
ret = B;
break;
case 7: // 111
ret = C;
break;
}
return ret;
}
// All these functions do is select a number that is positive,
// Giving preference to C, then B, then A
我可能犯了一些错误，所以他们做的事情可能不完全一样，但这不是重点。我试图用 switch 语句做的是创建一个只有一个跳转的 ifFunc 版本，方法是将每个 if 语句的结果转换成一个与位对齐的数字代码，这样每个可能的终点都有一个唯一的数字代码。
然而，这是平淡的，因为比较函数 (B > 0) 等在内部使用跳转。最终函数的 switch 版本比 if 版本慢一个数量级。
我想知道是否有一个比较语句，并让它输出零表示假，一个表示真，而不使用（内部或其他方式）if 语句或跳转。
不确定会好得多，但您可以尝试使用位域：
union SOMECONDTIONS {
unsigned char aggregate;
struct {
int c1:1;
int c2:1;
int c3:1;
int c4:1;
int c5:1;
int c6:1;
int c7:1;
int c8:1;
} conditions;
}
SOMECODITIONS c;
c.aggregate = 0;
c.conditions.c1 = A > 0;
c.conditions.c2 = B > 0;
c.conditions.c3 = C > 0;
switch(c.aggregate) {
...
可能这会...?
int ifFunc(int A, int B, int C){
if( C > 0 ) return C;
if( B > 0 ) return B;
if( A > 0 ) return A;
return 0;
}
编辑
对不起，我一定是误会了你——我以为你只需要减少条件分支的数量，而不是完全删除它们。这是解决方案（除非我犯了一些错误...），基于您的系统在 Two's complement 代码中工作的假设：
static const unsigned iMIN = ~(~0u >> 1); // binary 1000...0
static const int BITS_PER_BYTE = 8;
static inline int partialmask( int x ) {
// returns positive (0....) for positive x,
// negative (1....) for negative or zero x
return x | (int)(iMIN - (unsigned)x);
}
static inline int fullmask( int x ) {
// extends the sign bit so that
// positive becomes binary 0000...0 for positive x
// negative becomes binary 1111...1 for negative or zero x
return partialmask( x ) >> (BITS_PER_BYTE * sizeof(int) - 1);
}
int noIfFunc(int A, int B, int C){
int res = 0, mask;
mask = fullmask( A ); // negative or zero A causes an all-ones mask
res &= mask; // to preserve the res value
res |= A & ~mask; // and keep it from overwriting with A
mask = fullmask( B ); // positive B causes
res &= mask; // res to be cleared with all-zeros mask
res |= B & ~mask; // then overwritten with B
mask = fullmask( C );
res &= mask;
res |= C & ~mask;
return res; // finally res == most recent positive value (else zero)
}
可能这不是最短的代码。但是，如果适当减少（内联函数），它应该不包含任何分支。
我希望这段代码能帮助您删除汇编中的跳转...
static const int index[8] = {0, 1, 2, 2, 3, 3, 3, 3};
int ifFunc(int a, int b, int c)
{
const int ret[4] = {0, a, b, c};
const int bits = sizeof(int) * 8 - 1;
//const int i = ((((c - 1) >> bits) + 1) * 4) +
// ((((b - 1) >> bits) + 1) * 2) +
// (((a - 1) >> bits) + 1);
const int i = ((-c >> bits) * -4) -
((-b >> bits) * 2) -
(-a >> bits);
return ret[index[i]];
}
怎么样
if (C > 0) return C;
if (B > 0) return B;
if (A > 0) return A;
return 0;
或
return C > 0 ? C : (B > 0 ? B : (A > 0 ? A : 0)));
?
此外，如果编译器实现了条件赋值，
R= 0;
if (A > 0) R= A;
if (B > 0) R= B;
if (C > 0) R= C;
在最后一种情况下，MSVC 确实使用了条件赋值，但对于第三种情况，因为它更喜欢 return 归零寄存器 :(
; 7 : int R= 0;
; 8 : if (A > 0) R= A;
mov ecx, DWORD PTR _A$[esp-4]
xor eax, eax
test ecx, ecx
cmovg eax, ecx
; 9 : if (B > 0) R= B;
mov ecx, DWORD PTR _B$[esp-4]
test ecx, ecx
cmovg eax, ecx
; 10 : if (C > 0) R= C;
mov ecx, DWORD PTR _C$[esp-4]
test ecx, ecx
jle SHORT $LN1@f1
; 12 : return R;
mov eax, ecx
$LN1@f1:
ret 0
这是一个使用内联汇编几乎胜过编译器版本的解决方案。不好意思，昨晚才学汇编
int swFunc(int A, int B, int C){
int ret; char code;
//code += (A > 0) * 4, code += (B > 0) * 2, code += (C > 0) * 1
asm("movb [=10=], %[out];"
"cmpl [=10=], %[C];"
"setg %%al;"
"addb %%al, %[out];"
"cmpl [=10=], %[B];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
"cmpl [=10=], %[A];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
: [out] "+dl" (code)
: [A] "m" (A), [B] "m" (B), [C] "m" (C)
: "%eax", "%edx");
switch(code){
...
//same old switch statement
...
}
return ret;
}
当我将 asm 更改为；
asm ("cmpl [=11=], %[C];"
"setg %[out];"
"cmpl [=11=], %[B];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
"cmpl [=11=], %[A];"
"setg %%al;"
"shlb , %%al;"
"addb %%al, %[out];"
: [out] "+dl" (code)
: [A] "m" (A), [B] "m" (B), [C] "m" (C)
: "%eax", "%edx");
它应该做同样的事情，但以更短、更甜美的方式，性能是相同的，因为编译器决定像这样引入 %cl 寄存器；
movzbl -0x5(%ebp),%eax // load 'code' into the register (not needed!)
mov %eax,%ecx // load 'code' into ecx?
cmpl [=12=]x0,0x10(%ebp) // compare 'C' and 0
setg %cl // set byte for code imediately, skips zeroing 'code'
cmpl [=12=]x0,0xc(%ebp) // compare 'B' and 0
setg %al
shl %al // set %al, then make it equal to two if not equal to zero
add %al,%cl // add it to code
cmpl [=12=]x0,0x8(%ebp) // compare 'A' and 0
setg %al
shl [=12=]x2,%al // set %al, then make it equal to four if not equal to zero
add %al,%cl // add it to code
mov %cl,-0x5(%ebp) // move the final value back onto the stack
需要注意的是，如果我要求编译器使用%cl，编译器将使用%dl，反之亦然。顽固的机器似乎不想打破它的记录。
直接执行条件似乎是一个好方法，因为这种方法非常接近击败编译器