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_two64 ビット int (基本的には 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;
}

使用する最適化フラグによっては、コンパイラが既にこの形式になっている可能性があることに注意してください。

もちろん、これは 1 つの乗算を削除しただけです。モジュロを排除または削減したい場合は、に基づいて、明示的に呼び出す必要があるステップを事前に決定できる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;
    }
}
于 2012-06-15T20:17:26.643 に答える
0

size が 2 の累乗の場合、ビットごとの AND を size - 1 に適用すると、"% size" が最適化されます。

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