如何制作无网段代码? [英] How can I make branchless code?

查看:189
本文介绍了如何制作无网段代码?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

与此答案相关: https://stackoverflow.com/a/11227902/4714970

在上面的答案中,提到了如何通过避免分支来避免分支预测失败。

In the above answer, it's mentioned how you can avoid branch prediction fails by avoiding branches.

用户通过替换来证明这一点:

The user demonstrates this by replacing:

if (data[c] >= 128)
{
    sum += data[c];
}

使用:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这两个等价物如何(对于特定的数据集,不是严格等同的)?

How are these two equivalent (for the specific data set, not strictly equivalent)?

在类似的情况下,我可以做些类似事情的一般方法是什么?总是使用>>

What are some general ways I can do similar things in similar situations? Would it always be by using >> and ~?

推荐答案

int t = (data[c] - 128) >> 31;

这里的诀窍是,如果 data [c]> = 128 ,然后 data [c] - 128 是非负的,否则为负数。符号位 int 中的最高位是1,当且仅当该数字为负时。 >>> 是一个扩展符号位的移位,因此右移31会使整个结果为0,如果它曾经是非负的,如果以前是负数,则全部为1位(表示-1)。所以 t 0 如果 data [c]> = 128 ,否则 -1 ~t 切换这些可能性,所以 ~t -1 if data [c]> = 128 0 否则。

The trick here is that if data[c] >= 128, then data[c] - 128 is nonnegative, otherwise it is negative. The highest bit in an int, the sign bit, is 1 if and only if that number is negative. >> is a shift that extends the sign bit, so shifting right by 31 makes the whole result 0 if it used to be nonnegative, and all 1 bits (which represents -1) if it used to be negative. So t is 0 if data[c] >= 128, and -1 otherwise. ~t switches these possibilities, so ~t is -1 if data[c] >= 128, and 0 otherwise.

x& (-1)总是等于 x x& 0 始终等于 0 。所以 sum + = ~t&数据[c] 0 增加总和如果数据[ c]< 128 ,否则按 data [c]

x & (-1) is always equal to x, and x & 0 is always equal to 0. So sum += ~t & data[c] increases sum by 0 if data[c] < 128, and by data[c] otherwise.

其中许多技巧可以应用于其他地方。当且仅当一个值大于或等于另一个值且 -1时,此技巧当然可以通常应用于具有 0 的数字否则,您可以更多地使用它来获得< = < ,依此类推。像这样的小辫子是使数学运算无分支的常用方法,尽管它肯定不会总是用相同的操作构建; ^ (xor)和 | (或)有时也会发挥作用。

Many of these tricks can be applied elsewhere. This trick can certainly be generally applied to have a number be 0 if and only if one value is greater than or equal to another value, and -1 otherwise, and you can mess with it some more to get <=, <, and so on. Bit twiddling like this is a common approach to making mathematical operations branch-free, though it's certainly not always going to be built out of the same operations; ^ (xor) and | (or) also come into play sometimes.

这篇关于如何制作无网段代码?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆