Skip to contentSkip to conversation

dentry and inode cache hash algorithm performance changes.

PATCH Jose R. Santos 3 participants 8 messages Apr 30, 2004 – May 8, 2004 2 messages not in the archive VFS

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

#2 lore raw
Quoted 20 lines · Andrew Morton
Quoted 6 lines · Jose R. Santos

diff -Nru a/fs/inode.c b/fs/inode.c

fs/inode.c +0 -0
@@ -671,8 +671,9 @@
 

fs/inode.c line 679

Quoted 10 lines
fs/inode.c +3 -2
 static inline unsigned long hash(struct super_block *sb, unsigned long hashval)
 {
-	unsigned long tmp = hashval + ((unsigned long) sb / L1_CACHE_BYTES);
-	tmp = tmp + (tmp >> I_HASHBITS);
+	unsigned long tmp = (hashval + ((unsigned long) sb) ^ (GOLDEN_RATIO_PRIME + hashval)
+			/ L1_CACHE_BYTES);
+	tmp = tmp + ((tmp ^ GOLDEN_RATIO_PRIME) >> I_HASHBITS);
 	return tmp & I_HASHMASK;
 }
 

Are you sure about this? It's doing:

Quoted 7 lines

tmp = hashval + sb ^ ((GOLDEN_RATIO_PRIME + hashval) / L1_CACHE_BYTES)

should it not be:

tmp = hashval + (sb ^ (GOLDEN_RATIO_PRIME + hashval)) / L1_CACHE_BYTES

?

err... Wrote the patch to fast. It should read

tmp = (hashval * sb) ^ (GOLDEN_RATIO_PRIME + hashval) / L1_CACHE_BYTES

I screw up... I'll send a fixed patch in a while.

-JRS

#3 lore raw
Quoted 5 lines · Jose R. Santos

err... Wrote the patch to fast. It should read

tmp = (hashval * sb) ^ (GOLDEN_RATIO_PRIME + hashval) / L1_CACHE_BYTES

I screw up... I'll send a fixed patch in a while.

Just notice I've made another error in the inode hash code.

Fixed patch (I hope) with beautification.

-JRS

fs/dcache.c +3 -2
diff -Nru a/fs/dcache.c b/fs/dcache.c
@@ -28,6 +28,7 @@
 #include <asm/uaccess.h>
 #include <linux/security.h>
 #include <linux/seqlock.h>
+#include <linux/hash.h>
 
 #define DCACHE_PARANOIA 1
 /* #define DCACHE_DEBUG 1 */
@@ -799,8 +800,8 @@
 
 static inline struct hlist_head * d_hash(struct dentry * parent, unsigned long hash)
 {
-	hash += (unsigned long) parent / L1_CACHE_BYTES;
-	hash = hash ^ (hash >> D_HASHBITS);
+	hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
+	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
 	return dentry_hashtable + (hash & D_HASHMASK);
 }
 
fs/inode.c +5 -4
diff -Nru a/fs/inode.c b/fs/inode.c
@@ -671,12 +671,13 @@
 
 static inline unsigned long hash(struct super_block *sb, unsigned long hashval)
 {
-	unsigned long tmp = hashval + ((unsigned long) sb / L1_CACHE_BYTES);
-	tmp = tmp + (tmp >> I_HASHBITS);
+	unsigned long tmp;
+	
+	tmp = (hashval * (unsigned long)sb) ^ (GOLDEN_RATIO_PRIME + hashval) /
+			L1_CACHE_BYTES;
+	tmp = tmp ^ ((tmp ^ GOLDEN_RATIO_PRIME) >> I_HASHBITS);
 	return tmp & I_HASHMASK;
 }
-
-/* Yeah, I know about quadratic hash. Maybe, later. */
 
 /**
  *	iunique - get a unique inode number
#4 lore raw
Quoted 11 lines · Jose R. Santos
Quoted 5 lines · Jose R. Santos

err... Wrote the patch to fast. It should read

tmp = (hashval * sb) ^ (GOLDEN_RATIO_PRIME + hashval) / L1_CACHE_BYTES

I screw up... I'll send a fixed patch in a while.

Just notice I've made another error in the inode hash code.

Fixed patch (I hope) with beautification.

Does this mean you need to redo the instrumentation and benchmarking? If so, please do that and send the numbers along? There's no particular urgency on that, but we should do it.

Also, I'd be interested in understanding what the input to the hashing functions looked like in this testing. It could be that the new hash just happens to work well with one particular test's dataset. Please convince us otherwise ;)

#5 lore raw
Quoted 3 lines · Andrew Morton

Does this mean you need to redo the instrumentation and benchmarking? If so, please do that and send the numbers along? There's no particular urgency on that, but we should do it.

No, the screw up was made we I created the patch on a clean source tree. This patch represents the actual data gather on those graphs.

Quoted 4 lines

Also, I'd be interested in understanding what the input to the hashing functions looked like in this testing. It could be that the new hash just happens to work well with one particular test's dataset. Please convince us otherwise ;)

hehehe... I knew it could't be that easy. :)

For the dentry hash function, some of my other coorkers had put this hash function through various testing and have concluded that the hash function was equal or better than the default hash function. These runs were done with a (hopefully to be Open Source soon) benchmark called FFSB which can simulate various io patters across many filesystems and variable file sizes.

SpecSFS fileset is basically a lot of small file which varies depending on the size of the run. For a not so big SMP system the number of file is in the +20 Million files range. Of those 20 million files only 10% are access randomly by the client. The purpose of this is that the benchmark tries to stress not only the NFS layer but, VM and Filesystems layers as well. The filesets are also hundreds of gigabytes in size in order to promote disk head movement by guaranteeing cache misses in memory. SFS 27% of the workload are lookups __d_lookup has showing high in my profiles.

For the inode hash the problem that I see is that when running a benchmark with this huge fileset we end up trying to free a lot of inode entries during the run while trying to put new entries in cache. We end up calling ifind_fast() which calls find_inodes_fast() held under inode_lock. In order to avoid holding the inode_lock we needed to avoid having long chains in that hash function.

When I took a look at the original hash function, I found it to be a bit to simple for any workload. My solution (which I took advantage of Dominique's work) was to create a hash that function that could generate completely different hashes depending on the hashval and the superblock in order to have the hash scale as we added more filesystems to the machine.

Both of these problems can be somewhat tuned out by increasing the number of buckets of both d and i cache but it got to a point were I had 256MB of inode and 128MB in dentry hash buckets on a not so large SMP. With the hash changes I have been able to reduce the number of buckets to 128MB for inode cache and to 32MB for dentry cache and still get better performance.

If it help my case... I haven't been running this benchmark for long, so I haven't been able to find a way to cheat. I need to come up with generic solutions until I can find a cheat for the benchmark. :)

-JRS

#6 lore raw
In reply to Andrew Morton
Quoted 4 lines · Andrew Morton

Also, I'd be interested in understanding what the input to the hashing functions looked like in this testing. It could be that the new hash just happens to work well with one particular test's dataset. Please convince us otherwise ;)

Andrew - Is there any workload you want me to run to show that this hash function is going to be equal or better that the one already provided in Linux?

Remember that my claim is not the this hash function will be better for every IO workload. I claim it should not have worst performance than the default hash function but on some workloads it should perform better. The workloads that this should show improvements are those that use GB of memory to store inode and dentry cache data. I have run some test on my old BP6 machine and other than a small improvements while running find, I did not see any improvements but no regressions either. Again, if you have a particular workload in mind, Ill be happy to run it on some of my systems.

Thanks,

-JRS

#7 lore raw
Quoted 10 lines · Jose R. Santos
Quoted 4 lines · Andrew Morton

Also, I'd be interested in understanding what the input to the hashing functions looked like in this testing. It could be that the new hash just happens to work well with one particular test's dataset. Please convince us otherwise ;)

Andrew - Is there any workload you want me to run to show that this hash function is going to be equal or better that the one already provided in Linux?

Not really - it sounds like you've covered it pretty well. Did you try SDET?

It could be that reducing the hash table size will turn pretty much any workload into a test of the hash quality.

#8 lore raw
Quoted 8 lines · Andrew Morton
Quoted 3 lines

Andrew - Is there any workload you want me to run to show that this hash function is going to be equal or better that the one already provided in Linux?

Not really - it sounds like you've covered it pretty well. Did you try SDET?

It could be that reducing the hash table size will turn pretty much any workload into a test of the hash quality.

Sorry for the late reply...

Steve Pratt seem to have a SDET setup already and he did me the favor of running SDET with a reduce dentry entry hash table size. I belive that his table suggest that less than 3% change is acceptable variability, but overall he got a 5% better number using the new hash algorith.

-JRS

=========================================================================
A) x4408way1.sdet.2.6.5100000-8p.04-05-05_12.08.44 vs
B) x4408way1.sdet.2.6.5+hash-100000-8p.04-05-05_11.48.02

<6>Dentry cache hash table entries: 131072 (order: 7, 524288 bytes) <4>Inode-cache hash table entries: 1048576 (order: 10, 4194304 bytes)

Results:Throughput

                                          tolerance = 0.00 + 3.00% of A
                      A            B
   Threads      Ops/sec      Ops/sec    %diff         diff    tolerance
---------- ------------ ------------ -------- ------------ ------------
         1    4341.9300    4401.9500     1.38        60.02       130.26 
         2    8242.2000    8165.1200    -0.94       -77.08       247.27 
         4   15274.4900   15257.1000    -0.11       -17.39       458.23 
         8   21326.9200   21320.7000    -0.03        -6.22       639.81 
        16   23056.2100   24282.8000     5.32      1226.59       691.69  * 
        32   23397.2500   24684.6100     5.50      1287.36       701.92  * 
        64   23372.7600   23632.6500     1.11       259.89       701.18 
       128   17009.3900   16651.9600    -2.10      -357.43       510.28 

=========================================================================

#9 lore raw
Quoted 10 lines · Jose R. Santos
Quoted 8 lines · Andrew Morton
Quoted 3 lines

Andrew - Is there any workload you want me to run to show that this hash function is going to be equal or better that the one already provided in Linux?

Not really - it sounds like you've covered it pretty well. Did you try SDET?

It could be that reducing the hash table size will turn pretty much any workload into a test of the hash quality.

Quoted 6 lines

Sorry for the late reply...

Steve Pratt seem to have a SDET setup already and he did me the favor of running SDET with a reduce dentry entry hash table size. I belive that his table suggest that less than 3% change is acceptable variability, but overall he got a 5% better number using the new hash algorith.

It's usually best to keep increasing the number of SDET iterations that you average against, at least until the averages start to become a bit less bouncy. Also, mounting ramfs on /tmp can _really_ help lower its variability, probably because of gcc.

You might be lucky enough to get some consistently good numbers that way.

-- Dave