assembly 转换为连续if语句的无分支

68bkxrlz  于 12个月前  发布在  其他
关注(0)|答案(2)|浏览(146)

我一直在试图弄清楚如何将下面代码的最后两个“if”语句转换为无分支状态。

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

u = rand() % 4;
if ( y > x) u = 5;
if (-y > x) u = 4;

字符串
或者,如果上面的内容太难,你可以把它们看作:

if (x > 0) u = 5;
if (y > 0) u = 4;


我认为让我感到困惑的是,这些函数没有else捕捉器。如果是这样的话,我可能会采用无分支abs(或max/min)函数的变体。
您看到的rand()函数并不是真实的代码的一部分,我这样添加它们只是为了提示变量xyu在两个分支发生时可能具有的预期范围。
为此目的允许使用汇编机器代码。
编辑:
经过一番思考,我成功地把一个工作的无分支版本放在一起:

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

u = rand() % 4;
u += (4-u)*((unsigned int)(x+y) >> 31);
u += (5-u)*((unsigned int)(x-y) >> 31);


不幸的是,由于涉及整数运算,带有if语句的原始版本的速度提高了30%。
他知道派对在哪里。

xnifntxz

xnifntxz1#

[All:这个答案是在假设对兰德()的调用是问题的一部分的情况下写的。我在这个假设下提供了下面的改进。OP后来澄清了他只使用rand告诉我们x和y值的范围(以及可能的分布)。不清楚他是否也意味着u的值。无论如何,享受我对他没有真正提出的问题的改进答案]。
我想你最好把它重新编码为:

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

if ( y > x) u = 5;
else if (-y > x) u = 4;
else u = rand() % 4;

字符串
由于我假设rand(和除法)比compare-and-分支要昂贵得多,这将是一个显著的节省。
如果你的兰德生成器在每次调用时产生了很多真正的随机位(例如16),你可以只调用一次(我假设rand比divide更昂贵,YMMV):

int u, x, y, t;
t = rand() ;
u = t % 4;
t = t >> 2;
x = t % 100 - 50;
y = ( t / 100 ) %100 - 50;

if ( y > x) u = 5;
else if (-y > x) u = 4;


我认为MS C库中的兰德函数不足以满足这个要求,如果你想要真正的随机值,我不得不编写自己的代码;无论如何,结果更快。
你也可以通过使用倒数乘法(未经测试)来摆脱除法:

int u, x, y;
unsigned int t;
unsigned long t2;
t = rand() ;
u = t % 4;

{ // Compute value of x * 2^32 in a long by multiplying.
  // The (unsigned int) term below should be folded into a single constant at compile time.
  // The remaining multiply can be done by one machine instruction
  // (typically 32bits * 32bits --> 64bits) widely found in processors.
  // The "4" has the same effect as the t = t >> 2 in the previous version
  t2 = ( t * ((unsigned int)1./(4.*100.)*(1<<32));
}
x = (t2>>32)-50; // take the upper word (if compiler won't, do this in assembler)
{ // compute y from the fractional remainder of the above multiply,
  // which is sitting in the lower 32 bits of the t2 product
  y = ( t2 mod (1<<32) ) * (unsigned int)(100.*(1<<32));
}

if ( y > x) u = 5;
else if (-y > x) u = 4;


如果你的编译器不能产生“正确”的指令,那么编写汇编代码来完成这个任务应该是很简单的。

xqnpmsa8

xqnpmsa82#

一些使用数组索引的技巧,如果编译器/CPU有一步指令将比较结果转换为0-1值(例如x86的“塞特”和类似的),它们可能会非常快。

int ycpx[3];

/* ... */
ycpx[0] = 4;
ycpx[1] = u;
ycpx[2] = 5;
u = ycpx[1 - (-y <= x) + (y > x)];

字符串
替代形式

int v1[2];
int v2[2];

/* ... */
v1[0] = u;
v1[1] = 5;
v2[1] = 4;
v2[0] = v1[y > x];
u = v2[-y > x];


几乎无法阅读...
注意事项:在这两种情况下,包含4和5的数组元素的初始化可以包含在声明中,如果可重入性对您来说不是问题,则可以将数组设置为静态。

相关问题