黄金比と素数とハッシュと

by syoyo

最近は linux
のソースコード、ひいては OS のしくみなんかを
ちょくちょくと調べるようになっています。

これからレンダラをさらに頑健なものにしていったり、
メモリ効率よくレンダリングを
行うようにするにはどうしたらよいかを考えていくと、
レンダラがやっていることと
OS
のカーネルがやっていること(つまり資源の管理方法)との関連性が深いと感じているためです。

そこで、
今回はテクスチャのキャッシュ管理でタイルベース以外で良いものがないかと思い、

linux のメモリ管理の部分を読んでみました。

linux の実装では、キャッシュのタグ計算に黄金比で
ハッシュを計算するのが見受けられました。
該当のハッシュ関数のソースコードは

include/linux/hash.h

にあります。

ハッシュ関数は、32bit マシンでは 2^32 に、64bit
マシンでは
2^64
の黄金比に近い素数(GOLDEN_RATIO_PRIME)を乗するという、
非常にシンプルなものとなっています。

hash = GOLDEN_RATIO_PRIME *
val

この、
黄金比に近い素数がハッシュの計算に適している理由は、
Knuth
先生のライフワーク本の三巻で詳しく説明されているとこのことです。

The Art of Computer Programming:
Sorting and Searching (Art of
Computer Programming Volume
3)

http://www.amazon.co.jp/exec/obidos/ASIN/0201896850

さらに、この素数には、
乗算が遅いマシンでもシフト演算で計算できるような組み合わせが選ばれており、

32bit の場合は

/* 2^31 + 2^29 – 2^25 + 2^22 – 2^19
– 2^16 + 1 */
#define GOLDEN_RATIO_PRIME
0x9e370001UL

が設定されています。

ちなみに、黄金比といえば、
いとしさと切なさと心強さの黄金比の正確な計算は、
膨大な計算量が必要であり、スーパーコンピュータで計算しても 2, 3
年は
かかると言われています。

Advertisements