优化循环内的重复模数

Question

我在我的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位int(基本上是64字节的chuck).

Answer 1

所以本质上你正在做

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;
    }
}