Re: [PATCH] : struct dentry : place d_hash close to d_parent and d_name to speedup lookups

Eric Dumazet
2005-09-01T19:52:56Z

Dipankar Sarma a écrit :
> On Thu, Sep 01, 2005 at 05:48:28PM +0200, Eric Dumazet wrote:
>
>>dentry cache uses sophisticated RCU technology (and prefetching if
>>available) but touches 2 cache lines per dentry during hlist lookup.
>>
>>This patch moves d_hash in the same cache line than d_parent and d_name
>>fields so that :
>>
>>1) One cache line is needed instead of two.
>>2) the hlist_for_each_rcu() prefetching has a chance to bring all the
>>needed data in advance, not only the part that includes d_hash.next.
>>
>>I also changed one old comment that was wrong for 64bits.
>>
>>A further optimisation would be to separate dentry in two parts, one that
>>is mostly read, and one writen (d_count/d_lock) to avoid false sharing on
>>SMP/NUMA but this would need different field placement depending on 32bits
>>or 64bits platform.
>
>
> Do you have performance numbers that show the benefits ? In the
> past, I did try some optimizations like this but found no demonstrable
> benefits. If it ain't broken .....
>

You mean... a microbenchmark ? :)

Well, the dentry cache hash table is so large that it's difficult to see the
benefit, because chain length average is < 1 on most setups.
I suspect the sizing strategy of this hash table was made a long time ago...
Reducing the number of cache lines touched per dentry in lookup could let us
shrink the hash table and save some ram.

Facts now :
------------

On a 512MB ia32 machine, the default sizing of the hash table gives 131072
slots (0.5 MB of ram). So it's quite hard to populate the cache without eating
all ram.

To see a benefit, I had to force a smaller hash size (appending in kernel
params "dhash_entries=8191")

On this 512MB PIII 866MHz machine (L1_CACHE_SIZE=32), with 563887 files or
directories the results are :

Remount the disk with noatime to make sure no disk access will be done

# mount -o remount /dev/hda2 / -o noatime

Populate the caches (dentry and disk buffers for directories)
# find / -name foofoo >/dev/null

# grep dentry_cache /proc/slabinfo
dentry_cache 131104 131370 136 29 1 : tunables 120 60 0 :
slabdata 4530 4530 0

So average chain length is now 16

then time new searches using data in cache
time / -name foofoo >/dev/null

# time find / -name foofoo

real 0m3.077s
user 0m1.724s
sys 0m1.344s
# time find / -name foofoo

real 0m3.077s
user 0m1.728s
sys 0m1.348s
# time find / -name foofoo

real 0m3.084s
user 0m1.784s
sys 0m1.276s
# time find / -name foofoo

real 0m3.108s
user 0m1.716s
sys 0m1.348s
# time find / -name foofoo

real 0m3.061s
user 0m1.672s
sys 0m1.384s
# time find / -name foofoo

real 0m3.067s
user 0m1.644s
sys 0m1.424s
# time find / -name foofoo

real 0m3.061s
user 0m1.804s
sys 0m1.252s

kernel 2.6.13 build time
------------------------
mount -o remount /dev/hda2 /
make clean
time make bzImage
real 12m21.755s
user 11m5.070s
sys 1m0.756s

------------------------------------------------------------------

Results with a patched kernel

# time find / -name foofoo

real 0m3.017s
user 0m1.700s
sys 0m1.316s
# time find / -name foofoo

real 0m3.018s
user 0m1.592s
sys 0m1.424s
# time find / -name foofoo

real 0m3.017s
user 0m1.624s
sys 0m1.396s
# time find / -name foofoo

real 0m3.019s
user 0m1.680s
sys 0m1.340s
# time find / -name foofoo

real 0m3.021s
user 0m1.676s
sys 0m1.344s
# time find / -name foofoo

real 0m3.022s
user 0m1.644s
sys 0m1.376s
# time find / -name foofoo

real 0m3.021s
user 0m1.620s
sys 0m1.404s

kernel 2.6.13 build time
------------------------
mount -o remount /dev/hda2 /
make clean
time make bzImage
real 12m8.814s
user 11m2.129s
sys 0m52.187s

Conclusions:
-----------

1) There is a clear benefit, even without a microbenchmark :)

2) As sizeof(struct dentry)=136 on ia32 UP (140 on SMP), and dentry slab is
not using SLAB_HWCACHE_ALIGN, I suspect lot of dentries are not aligned on a
cache line boundary, so maybe reducing DNAME_INLINE_LEN_MIN (or increasing it)
so that sizeof(struct dentry)%L1_CACHE_BYTES = {0 or (L1_CACHE_BYTES/2)} would
even give better results.

Thank you

Eric