magic number
今日は県立図書館に昨日購入したナニとメモ用端末を持ち込み勉強。
# 結局メモは取ってないんですが ...
で、件のテキストに magic number なソレに関する記述あり。Knuth 先生は_乗数が 2^32 の黄金比に近いほどよい結果が得られる_と言われているとの事。hash_long の定義は include/linux/hash.h にて以下。
#if BITS_PER_LONG == 32 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ #define GOLDEN_RATIO_PRIME 0x9e370001UL #elif BITS_PER_LONG == 64 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL #else #error Define GOLDEN_RATIO_PRIME for your wordsize. #endif static inline unsigned long hash_long(unsigned long val, unsigned int bits) { unsigned long hash = val; #if BITS_PER_LONG == 64 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ unsigned long n = hash; n <<= 18; hash -= n; n <<= 33; hash -= n; n <<= 3; hash += n; n <<= 3; hash -= n; n <<= 4; hash += n; n <<= 2; hash += n; #else /* On some cpus multiply is faster, on others gcc will do shifts */ hash *= GOLDEN_RATIO_PRIME; #endif /* High bits are more random, so use them. */ return hash >> (BITS_PER_LONG - bits); }
いやはや、と言いつつ gauche な hash も TAOCP 云々なコメントがあったな、と思いつつ探してみたらあった。hash.c な記述にて以下。
/* Integer and address. */ /* Integer and address hash is a variation of "multiplicative hashing" scheme described in Knuth, TAOCP, section 6.4. The final shifting is done by HASH2INDEX macro */ #define SMALL_INT_HASH(result, val) \ (result) = ((val)*2654435761UL) #define ADDRESS_HASH(result, val) \ (result) = ((SCM_WORD(val) >> 3)*2654435761UL)
数値に微妙な差がありますが (0x9e370001 は 2654404609UL との事)、その差について云々できる知識は無いです。あ、でもカーネルの方が掛けた値をさらにシフトしてますな。
って gauche もコメント見たら shift は別途みたいな事が書いてある。HASH2INDEX マクロは直下で定義されてて以下。
/* HASH2INDEX Map a hash value to bucket number. We fix the word length to 32bits, since the multiplication constant above is fixed. */ #define HASH2INDEX(tabsiz, bits, hashval) \ (((hashval)+((hashval)>>(32-(bits)))) & ((tabsiz) - 1))
ここまで来るとワタシなんかがコメント云々な世界をはるかに超越しとります。