From owner-dev-commits-src-branches@freebsd.org Sat Apr 10 06:01:59 2021
Return-Path: <owner-dev-commits-src-branches@freebsd.org>
Delivered-To: dev-commits-src-branches@mailman.nyi.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1])
by mailman.nyi.freebsd.org (Postfix) with ESMTP id C4AED5CF99C;
Sat, 10 Apr 2021 06:01:59 +0000 (UTC) (envelope-from git@FreeBSD.org)
Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org
[IPv6:2610:1c1:1:606c::19:3])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256
client-signature RSA-PSS (4096 bits) client-digest SHA256)
(Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK))
by mx1.freebsd.org (Postfix) with ESMTPS id 4FHPXR59wYz4RFK;
Sat, 10 Apr 2021 06:01:59 +0000 (UTC) (envelope-from git@FreeBSD.org)
Received: from gitrepo.freebsd.org (gitrepo.freebsd.org
[IPv6:2610:1c1:1:6068::e6a:5])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256)
(Client did not present a certificate)
by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id A269440A0;
Sat, 10 Apr 2021 06:01:59 +0000 (UTC) (envelope-from git@FreeBSD.org)
Received: from gitrepo.freebsd.org ([127.0.1.44])
by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 13A61xhA015073;
Sat, 10 Apr 2021 06:01:59 GMT (envelope-from git@gitrepo.freebsd.org)
Received: (from git@localhost)
by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 13A61xb0015072;
Sat, 10 Apr 2021 06:01:59 GMT (envelope-from git)
Date: Sat, 10 Apr 2021 06:01:59 GMT
Message-Id: <202104100601.13A61xb0015072@gitrepo.freebsd.org>
To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org,
dev-commits-src-branches@FreeBSD.org
From: Mateusz Guzik <mjg@FreeBSD.org>
Subject: git: e201fa7c98db - stable/13 - cache: comment on FNV
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Git-Committer: mjg
X-Git-Repository: src
X-Git-Refname: refs/heads/stable/13
X-Git-Reftype: branch
X-Git-Commit: e201fa7c98db30b6a3c7c66387df68161b71c1ef
Auto-Submitted: auto-generated
X-BeenThere: dev-commits-src-branches@freebsd.org
X-Mailman-Version: 2.1.34
Precedence: list
List-Id: Commits to the stable branches of the FreeBSD src repository
<dev-commits-src-branches.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/dev-commits-src-branches>,
<mailto:dev-commits-src-branches-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/dev-commits-src-branches/>
List-Post: <mailto:dev-commits-src-branches@freebsd.org>
List-Help: <mailto:dev-commits-src-branches-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/dev-commits-src-branches>,
<mailto:dev-commits-src-branches-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sat, 10 Apr 2021 06:01:59 -0000
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)