Re: [Lse-tech] [PATCH] New dcache / inode hash tuning patch

[Martin J. B. <mb...@ar...>]

>> One other possibility here...  On x86, you have 4-byte pointers,
>> which gives you 8 such pointers per 32-byte cache line.  This means
>> that an insertion at the head of one hash chain will force an L2
>> miss for any other CPU attempting to traverse any of these 8 chains.
>> 
>> Now, if there is per-CPU locality of reference (and there might
>> or might not be, depending on the workload, the filesystem layout,
>> and the hash function), then inserting the new element after the
>> first element in the chain would cause only those CPUs traversing
>> that particular chain to see the L2 miss.
> 
> I would have expected that with a 16K entry hash table such conflicts are 
> statistically rare. Of course it really depends on the hash function.
> 
> It may be possible to not insert at the head,
> but behind the second entry in the bucket to avoid the problem you
> describe.  But I'm not sure it is worth it.
> 
> Just making the hash function better would be probably the biggest win.
> 
> I coded up FNV now and a hash bucket statistics patch now and after
> some reasonable load (lots of find /, many parallel kernel compiles) 
> I get this distribution:
> 
> worst case bucket length 32 
> average bucket length    13.4637 
> total number of entries  220388
> 
> average length of 13 is not very good 
> 
> Probably need a bigger table again. 16K entries seems to be too small.
> 
> The hash is actually not pure FNV, but combined r5 hash for the string
> and then combination using FNV with the parent address.
> it may be worth trying to put both into the same FNV.
> 
> Unfortunately I'm running out of time on this so won't be able to do
> further experiments on that for now.
> 
> Latest patch including FNV and hashtable dumper attached in case anybody
> wants to play further with this.

 fs/dcache.c: In function `dcache_seq_show':
fs/dcache.c:1675: warning: long unsigned int format, unsigned int arg (arg 3)
make[1]: warning: jobserver unavailable: using -j1.  Add `+' to parent make rule.
fs/built-in.o(.text+0x164da): In function `dcache_seq_next':
: undefined reference to `__divdi3'
make: *** [.tmp_vmlinux1] Error 1

http://www.aracnet.com/~fletch/linux/config.25