在循环中优化重复的取模运算

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，但这不是问题，我们可以将其四舍五入到下一个质数（但对于较大的值，二的幂增加得很快，这将导致浪费大量内存）。 h_two是一个64位整数（基本上是64字节的块）。

- Aman Deep Gautam

---

我已经根据您的要求编辑了问题，以澄清一些事情。 - Aman Deep Gautam

有一些方法可以使对同一个数字进行重复除法/取模变得非常高效。但这并不是微不足道的。 - Mysticial

你能给我推荐一些阅读的链接吗？ - Aman Deep Gautam

这是链接：http://gmplib.org/~tege/divcnst-pldi94.pdf 但像我说的，不是一件简单的事情。 - Mysticial

我已经更新了您的标题，以更好地突出问题。它不像之前那样普遍，但模数无疑会是有趣的部分。如果您不喜欢，请随意回滚。 - Mysticial

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

- KillianDS

---

+1 如果你能证明 k_hash[i-1] + h_two 永远不会导致整数溢出，那么在你的第一种方法中完全可以去掉模运算。但考虑到这是一个哈希函数，我假设这些数字几乎是随机的。 - Mysticial

@Mysticial size 是一个 int，而其余的是 uint_64，所以它们不应该溢出（当然 h_two 可以预先缩减）。 - harold

@哈罗德，看起来我们有了一个解决方案。预先计算h_two％size，并从h_one％size开始。然后在每次迭代中将其添加到累加器中。然后使用if语句测试它是否大于size，如果必要，则进行减法运算。 - Mysticial

@Mysticial：实际上我的第二个解决方案或多或少就是这样，只不过我预先确定了模数应该发生的步骤。不过一个简单的>可能更易读且同样高效，我会添加它的。 - KillianDS

Answer 2

如果大小是2的幂，则将按位与应用于大小-1可以优化“％size”：

(uint64_t *)k_hash[i] = (h_one + i * h_two) & (size - 1)

- Chris K

---

将“size”设置为2的幂有些过高，但我们可以将其设置为质数，所以在这种情况下，你能提出一些建议吗？ - Aman Deep Gautam