两个数组的按位与优化

Question

看起来是个简单的问题；我必须对两个数组进行按位与运算，如果任何两位匹配，则 return 为真，基本上：return ((dataArray & maskArray) != 0).

当然，这不是合法的 C++。目前的解决方案类似于：

uint32_t dataArray[BIG_NUM] //Pretend it's initialized
uint32_t maskArray[BIG_NUM] //Pretend it's initialized
bool returnVal = false;

for(int i = 0; i < BIG_NUM; i++)
{
    if((dataArray[i] & maskArray[i]) != 0)
    {
        returnVal = true;
        break;
    }
}
return returnVal;

虽然功能正常，但既不能并行化也不能矢量化，因此很痛苦，CPU 周期的 10% 在此函数中被烧毁。关于如何清理它有什么想法吗？

编辑：意识到我不应该将底层成员 sizeof() 作为数组大小的一部分。

Answer 1

在这里，这应该有助于矢量化，因为它只存在 8 的倍数并且每八次计算只有一个分支预测（可能更快）。

for(int i = 0; i < BIG_NUM; i+=8)
{
    uint32_t branch_once_per_8_calcs=0;
    branch_once_per_8_calcs+=dataArray[i+0] & maskArray[i+0];
    branch_once_per_8_calcs+=dataArray[i+1] & maskArray[i+1];
    branch_once_per_8_calcs+=dataArray[i+2] & maskArray[i+2];
    branch_once_per_8_calcs+=dataArray[i+3] & maskArray[i+3];
    branch_once_per_8_calcs+=dataArray[i+4] & maskArray[i+4];
    branch_once_per_8_calcs+=dataArray[i+5] & maskArray[i+5];
    branch_once_per_8_calcs+=dataArray[i+6] & maskArray[i+6];
    branch_once_per_8_calcs+=dataArray[i+7] & maskArray[i+7];
    if(branch_once_per_8_calcs!= 0)
    {
        returnVal = true;
        break;
    }
}

您还可以将步长增加到 64 或 128，并在每个步骤结束时使用嵌套循环检查一次，这样速度会更快。

或

for(int i = 0; i < BIG_NUM; i+=8)
{
    uint32_t branch_once_per_8_calcs=0;
    branch_once_per_8_calcs+=(dataArray[i+0] & maskArray[i+0]) | (dataArray[i+1] & maskArray[i+1]);
    branch_once_per_8_calcs+=(dataArray[i+2] & maskArray[i+2]) | (dataArray[i+3] & maskArray[i+3]);
    branch_once_per_8_calcs+=(dataArray[i+4] & maskArray[i+4]) | (dataArray[i+5] & maskArray[i+5]);
    branch_once_per_8_calcs+=(dataArray[i+6] & maskArray[i+6]) | (dataArray[i+7] & maskArray[i+7]);
    if(branch_once_per_8_calcs!= 0)
    {
        returnVal = true;
        break;
    }
}

使用更少的添加和分配。不要忘记检查可能导致漏报的溢出。

Answer 2

如果您通常 return false，以下可能会更快：

bool res = 0;
for (int i = 0; i < BIG_NUM; i++)
{
    res|= dataArray[i] & maskArray[i];      
}   
return res;

甚至

bool res = 0;
for (int i = 0; i < BIG_NUM; i++)
{
    resArray[i] = dataArray[i] & maskArray[i];
}

for (int i = 0; i < BIG_NUM; i++)
{
    res |= resArray[i];
}
return res;

取决于您的编译器

两个数组的按位与优化

Optimization of bitwise AND of two arrays

c++

optimization

c++03