c - 优化循环内的重复模数

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

注意我不确定这个公式(没有测试)，它更像是一个普遍的想法。这在很大程度上取决于您的分支预测有多好(以及错误预测对性能的影响有多大)。此外，它只有在步幅较大时才有帮助。

编辑:或更简单(可能具有相同的性能)-感谢 Mystical:

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