Date: Sat, 10 Apr 2021 06:01:59 GMT From: Mateusz Guzik <mjg@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org Subject: git: e201fa7c98db - stable/13 - cache: comment on FNV Message-ID: <202104100601.13A61xb0015072@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch stable/13 has been updated by mjg: URL: https://cgit.FreeBSD.org/src/commit/?id=e201fa7c98db30b6a3c7c66387df68161b71c1ef commit e201fa7c98db30b6a3c7c66387df68161b71c1ef Author: Mateusz Guzik <mjg@FreeBSD.org> AuthorDate: 2021-02-03 20:44:54 +0000 Commit: Mateusz Guzik <mjg@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)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202104100601.13A61xb0015072>