非常特殊的情况下的快速点产品

这确实需要分析,但您可能需要考虑另一种选择:

int result=0;
int mask=1;
for ( int i = 0; i < L; i++ ){
    if ( X & mask ){
        result+=Y[i];
    }
    mask <<= 1;
}

通常位移动和位操作比乘法快,然而,if语句可能比乘法慢,尽管使用分支预测和大L,我猜它可能更快。不过,你真的需要对它进行分析,以确定它是否会导致加速。

正如下面的注释中指出的,手动或通过编译器标志(如GCC上的“-funcroll loops”)展开循环也可以加快速度(消除循环条件)。

编辑
在下面的评论中,提出了以下好的调整:

int result=0;
for ( int i = 0; i < L; i++ ){
    if ( X & 1 ){
        result+=Y[i];
    }
    X >>= 1;
}

研究SSE2的建议有用吗?它已经有了点产品类型的操作,另外你可以做4次(或者8次,我忘记了寄存器的大小)简单的并行迭代。 SSE还具有一些简单的逻辑类型操作,因此它可以在不使用任何条件操作的情况下进行加法而不是乘法…你得再看看有什么行动。

试试这个:

int result=0;
for ( int i = 0; i < L; i++ ){
    result+=Y[i] & (~(((X>>i)&1)-1));
}

这将避免使用条件语句,并使用位运算符来用零或一屏蔽标量值。

因为尺寸明确 不存在 重要的是,我认为以下可能是最有效的通用代码:

int result = 0;
for (size_t i = 0; i < 32; ++i)
    result += Y[i] & -X[i];

位编码 X 只是没有将任何东西带到表中(即使循环可能提前终止,如@mathieu正确指出的那样)。但省略了 if 环内 做 .

当然,正如其他人所指出的,循环展开可以极大地加快速度。

此解决方案与Micheal Aaron的相同,但速度稍快(根据我的测试):

long Lev=1;
long Result=0
for (int i=0;i<L;i++) {
  if (X & Lev)
     Result+=Y[i];
  Lev*=2;
}

我认为有一种数字方法可以快速建立一个字中的下一个集合位,如果你的X数据非常稀疏,但目前找不到所说的数字公式,这将提高性能。

我已经看到了一些有点诡计的响应(为了避免分支),但没有一个正确的循环imho:。/

优化 @Goz 答:

int result=0;
for (int i = 0, x = X; x > 0; ++i, x>>= 1 )
{
   result += Y[i] & -(int)(x & 1);
}

优势:

• 无需做 i 每次移位操作( X>>i )
• 如果 X 以高位包含0

现在,我想知道它是否运行得更快,特别是因为for循环的过早停止可能不像展开循环那样容易(与编译时常量相比)。

把一个移位循环和一个小的查找表结合起来怎么样?

    int result=0;

    for ( int x=X; x!=0; x>>=4 ){
        switch (x&15) {
            case 0: break;
            case 1: result+=Y[0]; break;
            case 2: result+=Y[1]; break;
            case 3: result+=Y[0]+Y[1]; break;
            case 4: result+=Y[2]; break;
            case 5: result+=Y[0]+Y[2]; break;
            case 6: result+=Y[1]+Y[2]; break;
            case 7: result+=Y[0]+Y[1]+Y[2]; break;
            case 8: result+=Y[3]; break;
            case 9: result+=Y[0]+Y[3]; break;
            case 10: result+=Y[1]+Y[3]; break;
            case 11: result+=Y[0]+Y[1]+Y[3]; break;
            case 12: result+=Y[2]+Y[3]; break;
            case 13: result+=Y[0]+Y[2]+Y[3]; break;
            case 14: result+=Y[1]+Y[2]+Y[3]; break;
            case 15: result+=Y[0]+Y[1]+Y[2]+Y[3]; break;
        }
        Y+=4;
    }

这将取决于编译器对switch语句的优化程度,但根据我的经验,他们现在非常擅长于此……

这个问题可能没有一般性的答案。您需要在所有不同的目标下分析您的代码。性能将取决于编译器优化,如循环展开和SIMD指令,这些指令在大多数现代CPU上都可用(x86、PPC、ARM都有自己的实现)。

为了 小的 l,可以使用switch语句而不是循环。例如,如果L=8,则可以有:

int dot8(unsigned int X, const int Y[])
{
    switch (X)
    {
       case 0: return 0;
       case 1: return Y[0];
       case 2: return Y[1];
       case 3: return Y[0]+Y[1];
       // ...
       case 255: return Y[0]+Y[1]+Y[2]+Y[3]+Y[4]+Y[5]+Y[6]+Y[7];
    }
    assert(0 && "X too big");
}   

如果l=32,可以编写一个dot32()函数,调用dot8()。 四 时间,如果可能,内联。(如果编译器拒绝内联dot8(),可以将dot8()重写为宏以强制内联。) 补充 :

int dot32(unsigned int X, const int Y[])
{
    return dot8(X >> 0  & 255, Y + 0)  +
           dot8(X >> 8  & 255, Y + 8)  +
           dot8(X >> 16 & 255, Y + 16) +
           dot8(X >> 24 & 255, Y + 24);
}

正如Mikera指出的,这个解决方案可能有一个指令缓存成本;如果有,使用 DOT4 ()函数可能有帮助。

进一步更新 :这可以与Mikera的解决方案相结合:

static int dot4(unsigned int X, const int Y[])
{
    switch (X)
    {
        case 0: return 0;
        case 1: return Y[0];
        case 2: return Y[1];
        case 3: return Y[0]+Y[1];
        //...
        case 15: return Y[0]+Y[1]+Y[2]+Y[3];
    }
}

使用-s-o3选项查看生成的汇编程序代码 海湾合作委员会 4.3.4在cygwin上,看到它在dot32()中自动内联,我有点惊讶,因为 八 16个入口跳台。

但是添加属性(noinline)似乎可以产生更好的汇编程序。

另一种变化是在switch语句中使用fall through,但是 海湾合作委员会 添加了JMP指令,它看起来不会更快。

编辑--全新答案: 在考虑了蚂蚁AASMA提到的100次循环惩罚以及其他答案之后,上述问题可能不是最佳的。相反,你可以 手动 展开循环,如下所示:

int dot(unsigned int X, const int Y[])
{
    return (Y[0] & -!!(X & 1<<0)) +
           (Y[1] & -!!(X & 1<<1)) +
           (Y[2] & -!!(X & 1<<2)) +
           (Y[3] & -!!(X & 1<<3)) +
           //...
           (Y[31] & -!!(X & 1<<31));
}

在我的机器上,它生成32 x 5=160个快速指令。一个聪明的编译器可以想当然地展开其他建议的答案,得到相同的结果。

但我还是在复查。

result = 0;
for(int i = 0; i < L ; i++)
    if(X[i]!=0)
      result += Y[i];

很可能是加载所花费的时间 X 和 Y 从主存储器将占主导地位。如果您的CPU体系结构就是这样,那么当加载较少时,算法会更快。这意味着存储 X 作为一个位掩码,将其扩展到一级缓存将加速整个算法。

另一个相关的问题是编译器是否会为 Y . 这高度依赖于CPU和编译器。但是,一般来说,如果编译器能够预先看到在什么时候需要哪些值,这会有所帮助。您可以手动展开循环。但是,如果l是一个contant,则将其留给编译器:

template<int I> inline void calcZ(int (&X)[L], int(&Y)[L], int &Z) {
  Z += X[I] * Y[I]; // Essentially free, as it operates in parallel with loads.
  calcZ<I-1>(X,Y,Z);
}
template< > inline void calcZ<0>(int (&X)[L], int(&Y)[L], int &Z) {
  Z += X[0] * Y[0];
}
inline int calcZ(int (&X)[L], int(&Y)[L]) {
    int Z = 0;
    calcZ<L-1>(X,Y,Z);
    return Z;
}

(康拉德·鲁道夫在评论中质疑这一点,对记忆感到疑惑 使用 . 这不是现代计算机体系结构中真正的瓶颈,内存和CPU之间的带宽是。如果y已经在缓存中,那么这个答案几乎是不相关的。)

您可以将位向量存储为一个int序列,其中每个int将几个系数打包为位。然后,分量相乘等于位和。有了这个,您只需要计算可以这样做的设置位数:

inline int count(uint32_t x) {
    // see link
}

int dot(uint32_t a, uint32_t b) {
    return count(a & b);
}

要想计算设定位,请参见 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

编辑:抱歉,我刚刚意识到只有一个向量包含0,1的元素,而另一个不包含0,1的元素。这个答案只适用于两个向量都限于0,1集的系数的情况。

代表 X 使用位置的链接列表 x[i] = 1 . 找到你需要的金额 O(N) 在哪里操作 N 是列表的大小。

如果它是1,你希望所有的位都过去;如果它是0,你希望所有的位都过去。所以你想以某种方式把1变成-1(即0xffffffff),0保持不变。那只是-x……所以你…

Y & (-X)

对于每个元素…工作完成了吗?

edit2:要给出一个代码示例,您可以这样做并避免使用分支:

int result=0;
for ( int i = 0; i < L; i++ )
{
   result+=Y[i] & -(int)((X >> i) & 1);
}

当然,最好是将1和0保持在整数数组中,从而避免移位。

编辑:值得注意的是,如果y中的值的大小为16位,那么您可以执行其中的2个操作和每个操作(如果您有64位寄存器,则为4个)。但是,它确实意味着将x值1乘以1求反为一个更大的整数。

ie yvals=-4,3 in 16位=0xfffc,0x3…放入1个32位,得到0xfffc0003。如果你有1,0作为x值,那么你就形成了一个0xffff0000的位掩码,2加在一起,你得到了2个1位和op的结果。

另一个编辑:

如果你想要关于如何做第二种方法的代码 喜欢 这应该可以工作(尽管它利用了未指定的行为,因此可能无法在每个编译器上工作)。在我遇到的每个编译器上工作)。

union int1632
{
     int32_t i32;
     int16_t i16[2];
};

int result=0;
for ( int i = 0; i < (L & ~0x1); i += 2 )
{
    int3264 y3264;
    y3264.i16[0] = Y[i + 0];
    y3264.i16[1] = Y[i + 1];

    int3264 x3264;
    x3264.i16[0] = -(int16_t)((X >> (i + 0)) & 1);
    x3264.i16[1] = -(int16_t)((X >> (i + 1)) & 1);

    int3264 res3264;
    res3264.i32  = y3264.i32 & x3264.i32;

    result += res3264.i16[0] + res3264.i16[1];    
}

if ( i < L )
    result+=Y[i] & -(int)((X >> i) & 1);

希望编译器会优化分配(我不确定,但这个想法可以重新实现,所以它们肯定是),并给你一个小的速度,因为你现在只需要做1位,而不是2位。但是速度会很小…