[devel] Re: cmdcache hash function

[Alexey Tourbin <at@altlinux.ru>]

[-- Attachment #1: Type: text/plain, Size: 1659 bytes --]

On Wed, Sep 14, 2005 at 09:10:04PM +0400, Alexey Tourbin wrote:
> Букв нет, есть только st_ino+st_size+st_mtime.
> 
> at@solemn ~/.cmdcache 4 $ ls -1 rpmfile |head
> i10003s62465m1079085926
> i10226s323862m1079960217
> i10287s367587m1080138012
> i10366s1535556m1077197737
> i10552s68368m1077197738
> i10580s107898m1078145421
> i10723s828128m1076422307
> i1090192s13734m1125334673
> i11055s406941m1079109059
> i1166331s4611m1125335339
> at@solemn ~/.cmdcache 4 $
> 
> К тому же по буквам получится плохое распределение, а кеш всё равно
> "не прозрачный" (то есть reverse lookup затруднён).  Можно сделать
> одноуровневую прослойку из каталогов по последним цифрам ino и size.
> Получится 100 файлов на 100 каталогов для 10k capacity.  Надо посмотреть
> как в ccache сделано.

Okay, есть три числа: st_ino, st_size и st_mtime.  Как их по-грамотному
захешировать?  Нужно сделать одноуровневую прослойку из каталогов.  Для
capacity порядка 10k выбираем число каталогов (buckets) в районе 100:

$ for n in `seq 50 150`; do factor $n; done |awk NF==2
53: 53
59: 59
61: 61
67: 67
71: 71
73: 73
79: 79
83: 83
89: 89
97: 97
101: 101
103: 103
107: 107
109: 109
113: 113
127: 127
131: 131
137: 137
139: 139
149: 149
$

Значит хешируем по модулю например 97.

cmdcache_hash()
{
	local c_st
	c_st="$(stat -L -c '%i %s %Y' -- "$1")" || return
	set -- $c_st
	local c_hashfile="i${1}s${2}m${3}"
	local c_hashdir=$(( ( $1 + $2 + $3 ) % 97 ))
	echo "$c_hashdir/$c_hashfile"
}

bash-2.05b$ cmdcache_hash /etc/passwd
70/i22612s2957m1119749776
bash-2.05b$ exit

Коллеги!  Как по-грамотному три числа захешировать?

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]