git: e201fa7c98db - stable/13 - cache: comment on FNV

[Mateusz Guzik]

The branch stable/13 has been updated by mjg:

URL: https://cgit.FreeBSD.org/src/commit/?id=e201fa7c98db30b6a3c7c66387df68161b71c1ef

commit e201fa7c98db30b6a3c7c66387df68161b71c1ef
Author:     Mateusz Guzik <mjg at FreeBSD.org>
AuthorDate: 2021-02-03 20:44:54 +0000
Commit:     Mateusz Guzik <mjg at FreeBSD.org>
CommitDate: 2021-04-10 05:57:54 +0000

    cache: comment on FNV
    
    (cherry picked from commit b54ed778fe45d482bd1e2009df802fda26f94495)
---
 sys/kern/vfs_cache.c | 24 +++++++++++++++++++++++-
 1 file changed, 23 insertions(+), 1 deletion(-)

diff --git a/sys/kern/vfs_cache.c b/sys/kern/vfs_cache.c
index db482ea4eba3..47abe0feb152 100644
--- a/sys/kern/vfs_cache.c
+++ b/sys/kern/vfs_cache.c
@@ -704,9 +704,31 @@ out:
 	SDT_PROBE1(vfs, namecache, purge, batch, i);
 }
 
+/*
+ * Hashing.
+ *
+ * The code was made to use FNV in 2001 and this choice needs to be revisited.
+ *
+ * Short summary of the difficulty:
+ * The longest name which can be inserted is NAME_MAX characters in length (or
+ * 255 at the time of writing this comment), while majority of names used in
+ * practice are significantly shorter (mostly below 10). More importantly
+ * majority of lookups performed find names are even shorter than that.
+ *
+ * This poses a problem where hashes which do better than FNV past word size
+ * (or so) tend to come with additional overhead when finalizing the result,
+ * making them noticeably slower for the most commonly used range.
+ *
+ * Consider a path like: /usr/obj/usr/src/sys/amd64/GENERIC/vnode_if.c
+ *
+ * When looking it up the most time consuming part by a large margin (at least
+ * on amd64) is hashing.  Replacing FNV with something which pessimizes short
+ * input would make the slowest part stand out even more.
+ */
+
 /*
  * TODO: With the value stored we can do better than computing the hash based
- * on the address. The choice of FNV should also be revisited.
+ * on the address.
  */
 static void
 cache_prehash(struct vnode *vp)