6

四分木エントリを格納するハッシュテーブルがあります。
ハッシュ関数は次のようになります。

四分木ハッシュ 

#define node_hash(a,b,c,d) \
  (((int)(d))+3*(((int)(c))+3*(((int)(b))+3*((int)(a))+3)))

この操作の結果は、次のように剰余素数を使用して常に分割されることに注意してください。 

h = node_hash(p->nw, p->ne, p->sw, p->se) ;
h %= hashprime ;
...

最適なハッシュとの比較
いくつかの統計分析は、このハッシュが衝突の削減に関して最適であることを示しています。バケットとエントリ
を含むハッシュテーブルが与えられます。完全ハッシュを使用した場合の衝突リスクは次のとおりです。 n = b の場合、これは 37% の衝突リスクを意味します。 bn
(n - b * (1 - power((b-1)/b,n)))) * 100 / n

いくつかのテストでは、上記のハッシュが (ハッシュテーブルのすべての塗りつぶしレベルに対して) 標準と非常にうまく一致していることが示されています。

実行時間 実行時間
は、次の値に大きく依存します。hashprime

タイミング (1000 回の実行で最適) は次のとおりです。 

hashprime   CPU-cycles per run
--------------------------------
 4049               56
16217               68
64871              127    <-- whoooh

最適な衝突リスクを維持しながら、これを改善する方法はありますか?

モジュラス演算を最適化する（ループ外の「マジック」ナンバーコンピューターを使用した乗算に置き換える）。
ハッシュ関数を他のハッシュ関数に置き換えます。

背景
以下のアセンブリが生成されます。

//--------h = node_hash(p->nw, p->ne, p->sw, p->se) ;
mov eax,[rcx+node.nw]       <<+
lea eax,[eax+eax*2+3]         |
add eax,[rcx+node.ne]         |
lea eax,[eax+eax*2]           +-  takes +/- 12 cycles
add eax,[rcx+node.sw]         |
lea eax,[eax+eax*2]           |
add eax,[rcx+node.se]       <<+
//--------h %= hashprime ;
mov esi,[hashprime]
xor edx,edx
div esi
mov rax,rdx                    <<--- takes all the rest

[編集]
私は次の事実で何かをすることができるかもしれません:

C = A % BC = A – B * (A / B)
は、整数の除算がその逆数による乗算と同じであるという事実を使用することと同等です。 整数除算の場合、逆数は魔法の数であること
に注意してください。 http://www.hackersdelight.org/magic.htm C コードはこちら: http://web.archive.org/web/20070713211039/ http://hackersdelight.org/HDcode/magic.cC = A - B * (A * rB)

[FNV ハッシュ]

参照: http://www.isthe.com/chongo/tech/comp/fnv/#FNV-1a 

hash = offset_basis
for each byte to be hashed
 hash = hash xor octet_of_data
 hash = hash * FNV_prime (for 32 bits = 16777619)
return hash

32 ビットに切り捨てられた 4 つのポインター = 16 バイトの場合、FNV ハッシュには27 サイクルかかります (手作りのアセンブリ)
残念ながら、これにより 37% になるはずの場所で 81% のハッシュ衝突が発生します。
15 回の乗算をすべて実行するには、179 サイクルかかります。

4

3 に答える 3

3

逆数乗算によるモジュラスの置き換え
このハッシュ関数の主なサイクルイーターは、モジュラス演算子です。

この除算を逆数による乗算に置き換えると、計算ははるかに高速になります。
逆数の計算には 3 つの除算が含まれるため、これは逆数を十分に再利用できる場合にのみ行う必要があります。

OK、使用したコードは次のとおりです: http://www.agner.org/optimize/asmlib.zip

出典: http://www.agner.org/optimize/

// ;*************************  divfixedi64.asm  *********************************
// ; Author:           Agner Fog

//extern "C" void setdivisoru32(uint Buffer[2], uint d)
asm
  mov     r8d, edx               // x
  mov     r9, rcx                // Buffer
  dec     r8d                    // r8d = r8d or esi
  mov     ecx, -1                // value for bsr if r8d = 0
  bsr     ecx, r8d               // floor(log2(d-1))
  inc     r8d
  inc     ecx                    // L = ceil(log2(d))
  mov     edx, 1
  shl     rdx, cl                // 2^L (64 bit shift because cl may be 32)
  sub     edx, r8d
  xor     eax, eax
  div     r8d
  inc     eax
  mov     [r9], eax              // multiplier
  sub     ecx, 1
  setae   dl
  movzx   edx, dl                // shift1
  seta    al
  neg     al
  and     al,cl
  movzx   eax, al                // shift 2
  shl     eax, 8
  or      eax, edx
  mov     [r9+4], eax            // shift 1 and shift 2
  ret
end;

モジュラス演算のコード:

//extern "C" uint modFixedU32(uint Buffer[2], uint d)
asm
  mov     eax,  edx
  mov     r10d, edx                // x
  mov     r11d, edx                 // save x
  mul     dword [rcx]              // Buffer (i.e.: m')
  sub     r10d, edx                // x-t
  mov     ecx, [rcx+4]             // shift 1 and shift 2
  shr     r10d, cl
  lea     eax, [r10+rdx]
  mov     cl,  ch
  shr     eax, cl
  // Result:= x - m * fastDiv32.dividefixedu32(Buffer, x);
  mul     r8d                    // m * ...
  sub     r11d, eax              // x - (m  * ...)
  mov     eax,r11d
  ret
end;

時間差は以下の通りです。

hashprime   classic hash (mod)  new hash        new          old  
(# of runs)    cycles/run       per run       (no cache)   (no cache)
--------------------------------------------------------------------
 4049               56             21            16.6        51
16217               68           not measured
64871              127             89            16.5        50

キャッシュの問題
サイクル タイムの増加は、データがキャッシュをオーバーフローし、メイン メモリへのアクセスが発生することが原因です。
これは、同じ値を何度もハッシュしてキャッシュ効果を取り除くとはっきりとわかります。

于 2013-09-28T04:56:13.083 に答える
0

が定数であると仮定するhashprimeと、モジュロ演算をビットごとのマスクとして実装できます。詳細についてはわかりませんが、この回答が正しい方向に進む可能性があります。

于 2013-09-27T07:23:13.687 に答える