C/C++优化:快速否定双打

Question

我需要迅速否定大量的双打.如果bit_generator生成0,则必须更改符号.如果bit_generator生成1,则没有任何反应.循环运行多次,bit_generator非常快.在我的平台上,案例2明显快于案例1.看起来我的CPU不喜欢分支.有没有更快,更便携的方式来做到这一点？您如何看待案例3？

// generates 0 and 1
int bit_generator();

// big vector (C++)
vector<double> v;

// case 1
for (size_t i=0; i<v.size(); ++i)
    if (bit_generator()==0)
        v[i] = -v[i];

// case 2
const int sign[] = {-1, 1};
for (size_t i=0; i<v.size(); ++i)
        v[i] *= sign[bit_generator()];

// case 3
const double sign[] = {-1, 1};
for (size_t i=0; i<v.size(); ++i)
        v[i] *= sign[bit_generator()];

// case 4 uses C-array
double a[N];
double number_generator(); // generates doubles
double z[2]; // used as buffer
for (size_t i=0; i<N; ++i) {
        z[0] = number_generator();
        z[1] = -z[0];
        a[i] = z[bit_generator()];
}

编辑:添加了案例4和C标签,因为矢量可以是普通数组.由于我可以控制如何生成双精度,我重新设计了代码,如案例4所示.它避免了额外的乘法和分支.我认为它应该在所有平台上都非常快.

Answer 1

除非你想在循环中调整向量的大小,否则将v.size()从for表达式中提取出来,即

const unsigned SZ=v.size();
for (size_t i=0; i<SZ; ++i)
    if (bit_generator()==0)
        v[i] = -v[i];

如果编译器无法看到bit_generator()中发生了什么,那么编译器可能很难证明v.size()没有改变,这使得循环展开或矢量化成为不可能.

更新:我做了一些测试,在我的机器上方法2似乎是最快的.但是,使用我称之为"群组行动"的模式似乎更快:-).基本上,您将多个决策分组为一个值并切换它:

const size_t SZ=v.size();
for (size_t i=0; i<SZ; i+=2) // manual loop unrolling
{
 int val=2*bit_generator()+bit_generator();
 switch(val) // only one conditional
 {
  case 0: 
     break; // nothing happes
  case 1: 
     v[i+1]=-v[i+1]; 
     break; 
  case 2: 
     v[i]=-v[i]; 
     break; 
  case 3: 
    v[i]=-v[i];
    v[i+1]=-v[i+1]; 
 }
}
// not shown: wrap up the loop if SZ%2==1 

Answer 2

如果您可以假设该符号由一个特定位表示,例如在x86实现中,您可以简单地执行:

v[i] ^= !bit_generator() << SIGN_BIT_POSITION; // negate the output of
                                               // bit_generator because 0 means 
                                               // negate and one means leave 
                                               // unchanged.

在x86中,符号位是MSB,因此对于位63的双精度:

#define SIGN_BIT_POSITION 63 

会做的.

编辑:

根据评论,我应该补充一点,你可能需要做一些额外的工作来进行编译,因为v是一个数组double,而bit_generator()返回int.你可以这样做:

union int_double {
    double d;        // assumption: double is 64 bits wide
    long long int i; // assumption: long long is 64 bits wide
};

(C语法可能有点不同,因为您可能需要typedef.)

然后定义v为矢量int_double并使用:

v[i].i ^= bit_generator() << SIGN_BIT_POSITION;