6

我的 c 程序中有这个语句，我想优化。通过优化，我特别想参考按位运算符（但任何其他建议也可以）。

uint64_t h_one = hash[0];
uint64_t h_two = hash[1];
for ( int i=0; i<k; ++i )
{
    (uint64_t *) k_hash[i] = ( h_one + i * h_two ) % size;   //suggest some optimization for this line.
}

任何建议都会有很大帮助。

编辑：到目前为止size可以是任何int但它不是问题，我们可以将它四舍五入到下一个素数（但可能不是 2 的幂，因为对于较大的值，2 的幂会迅速增加，这将导致大量浪费内存）

h_two是一个 64 位整数（基本上是 64 字节的卡盘）。

4

2 回答 2

4

所以本质上你在做

k_0 = h_1 mod s
k_1 = h_1 + h_2 mod s = k_0 + h_2 mod s
k_2 = h_1 + h_2 + h_2 mod s = k_1 + h_2 mod s
..
k_n = k_(n-1) + h_2 mod s

根据溢出问题（如果大小小于一半，则不应与原始问题不同2**64），这可能会更快（虽然不太容易并行化）：

uint64_t h_one = hash[0];
uint64_t h_two = hash[1];
k_hash[0] = h_one % size;
for ( int i=1; i<k; ++i )
{
    (uint64_t *) k_hash[i] = ( k_hash[i-1] + h_two ) % size;
}

请注意，您的编译器可能已经采用这种形式，具体取决于您使用的优化标志。

当然，这只消除了一次乘法。h_two%size如果你想消除或减少模数，我想基于h_1%size你可以预先确定你必须明确调用的步骤%size，如下所示：

uint64_t h_one = hash[0]%size;
uint64_t h_two = hash[1]%size;
k_hash[0] = h_one;
step = (size-(h_one))/(h_two)-1;
for ( int i=1; i<k; ++i )
{
    (uint64_t *) k_hash[i] = ( k_hash[i-1] + h_two );
    if(i==step)
    {
        k_hash[i] %= size;
    }
}

注意我不确定公式（没有测试过），这是一个更笼统的想法。这在很大程度上取决于您的分支预测有多好（以及错误预测对性能的影响有多大）。也只有在步幅很大的情况下才有帮助。

编辑：或更简单（并且可能具有相同的性能）-感谢神秘：

uint64_t h_one = hash[0]%size;
uint64_t h_two = hash[1]%size;
k_hash[0] = h_one;
for ( int i=1; i<k; ++i )
{
    (uint64_t *) k_hash[i] = ( k_hash[i-1] + h_two );
    if(k_hash[i] > size)
    {
        k_hash[i] -= size;
    }
}
于 2012-06-15T20:17:26.643 回答
0

如果 size 是 2 的幂，则对 size - 1 应用按位与优化 "% size"：

(uint64_t *)k_hash[i] = (h_one + i * h_two) & (size - 1)
于 2012-06-15T19:37:59.227 回答