From: Linus Torvalds <torvalds@linux-foundation.org>
To: George Spelvin <linux@sciencehorizons.net>
Cc: Peter Zijlstra <peterz@infradead.org>,
"J. Bruce Fields" <bfields@redhat.com>,
Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function
Date: Wed, 1 Jun 2016 18:18:55 -0700 [thread overview]
Message-ID: <CA+55aFzZwOm3352HXgMqvSpgmTms-fqLfiu1ZYFO5DhOoiqv7g@mail.gmail.com> (raw)
In-Reply-To: <20160530181024.5606.qmail@ns.sciencehorizons.net>
On Mon, May 30, 2016 at 11:10 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
>
> I understand, but 64x64-bit multiply on 32-bit is pretty annoyingly
> expensive. In time, code size, and register pressure which bloats
> surrounding code.
Side note, the code seems to work fairly well, but I do worry a bit
about the three large multiplies in link_path_walk().
There's two in fold_hash(), and one comes from "find_zero()".
It turns out to work fairly well on at least modern big-core x86
CPU's, because the multiplier is fairly beefy: low latency (3-4 cycles
in the current ctop) and fully pipelined.
Even atom should be 5 cycles and a multiplication result every two
cycles for 64-bit results.
Maybe we don't care, because looking around the modern ARM and POWER
cores do similarly, but I just wanted to point out that that code does
seem to fairly heavily rely on "everybody has bug and pipelined hw
multipliers" for performance.
.. and it's probably true that transistors are cheap, and crypto and
other uses have made CPU designers spend the effort on good
multipliers. I just remember a time when you definitely couldn't rely
on fast multiplies.
Linus
next prev parent reply other threads:[~2016-06-02 1:18 UTC|newest]
Thread overview: 55+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CA+55aFxPSW+84KfQ1N_WmND-wtvgj2zQm8nFPkRcc+gyU=uing@mail.gmail.com>
2016-05-25 7:20 ` [PATCH 00/10] String hash improvements George Spelvin
2016-05-25 8:00 ` Geert Uytterhoeven
2016-05-25 8:11 ` George Spelvin
2016-05-25 8:50 ` Geert Uytterhoeven
2016-05-25 9:07 ` George Spelvin
2016-05-25 16:08 ` Linus Torvalds
2016-05-28 19:57 ` [PATCH v3 " George Spelvin
2016-05-28 19:57 ` [PATCH v3 01/10] Pull out string hash to <linux/stringhash.h> George Spelvin
2016-05-28 19:57 ` [PATCH v3 02/10] fs/namei.c: Add hashlen_string() function George Spelvin
2016-05-28 19:57 ` [PATCH v3 03/10] <linux/sunrpc/svcauth.h>: Define hash_str() in terms of hashlen_string() George Spelvin
2016-05-28 19:57 ` [PATCH v3 04/10] Change hash_64() return value to 32 bits George Spelvin
2016-05-28 19:57 ` [PATCH v3 05/10] Eliminate bad hash multipliers from hash_32() and hash_64() George Spelvin
2016-05-28 19:57 ` [PATCH v3 06/10] fs/namei.c: Improve dcache hash function George Spelvin
2016-05-30 15:11 ` Peter Zijlstra
2016-05-30 16:06 ` George Spelvin
2016-05-30 16:27 ` Peter Zijlstra
2016-05-30 18:10 ` George Spelvin
2016-06-02 1:18 ` Linus Torvalds [this message]
2016-06-02 2:31 ` George Spelvin
2016-06-02 16:35 ` Linus Torvalds
2016-06-02 18:23 ` George Spelvin
2016-05-28 19:57 ` [PATCH v3 07/10] <linux/hash.h>: Add support for architecture-specific functions George Spelvin
2016-05-29 7:57 ` Geert Uytterhoeven
2016-05-28 19:57 ` [PATCH v3 08/10] m68k: Add <asm/hash.h> George Spelvin
2016-05-28 19:57 ` [PATCH v3 09/10] microblaze: " George Spelvin
2016-05-28 19:57 ` [PATCH v3 10/10] h8300: " George Spelvin
2016-05-28 20:47 ` [PATCH v3 00/10] String hash improvements Linus Torvalds
2016-05-28 20:54 ` George Spelvin
2016-06-02 22:59 ` [PATCH " Fubo Chen
2016-05-26 17:09 ` [PATCH v2 " George Spelvin
2016-05-25 7:21 ` [PATCH 01/10] Pull out string hash to <linux/stringhash.h> George Spelvin
2016-05-25 7:22 ` [PATCH 02/10] fs/namei.c: Add hash_string() function George Spelvin
2016-05-25 7:26 ` [PATCH 03/10] <linux/sunrpc/svcauth.h>: Define hash_str() in terms of hash_string() George Spelvin
2016-05-25 7:28 ` [PATCH 04/10] Change hash_64() return value to 32 bits George Spelvin
2016-05-25 7:29 ` [PATCH 05/10] Eliminate bad hash multipliers from hash_32() and hash_64() George Spelvin
2016-05-25 7:31 ` [PATCH 06/10] fs/namei.c: Improve dcache hash function George Spelvin
2016-05-25 7:33 ` [PATCH 07/10] <linux/hash.h>: Add support for architecture-specific functions George Spelvin
2016-05-26 17:16 ` [PATCH v2 " George Spelvin
2016-05-25 7:34 ` [PATCH 08/10] m68k: Add <asm/archhash.h> George Spelvin
2016-05-25 7:34 ` George Spelvin
2016-05-25 8:07 ` Geert Uytterhoeven
2016-05-25 8:19 ` George Spelvin
2016-05-25 8:24 ` [PATCH 08v2/10] " George Spelvin
2016-05-25 8:48 ` Geert Uytterhoeven
2016-05-25 8:56 ` [PATCH 08/10] " Philippe De Muyter
2016-05-25 9:14 ` George Spelvin
2016-05-25 9:31 ` Andreas Schwab
2016-05-25 9:51 ` Philippe De Muyter
2016-05-25 13:24 ` Philippe De Muyter
2016-05-25 13:42 ` George Spelvin
2016-05-26 17:19 ` [PATCH v2 08/10] m68k: Add <asm/hash.h> George Spelvin
2016-05-25 7:37 ` [PATCH 09/10] microblaze: Add <asm/archhash.h> George Spelvin
2016-05-26 17:21 ` [PATCH v2 09/10] microblaze: Add <asm/hash.h> George Spelvin
2016-05-25 7:38 ` [PATCH 10/10] h8300: Add <asm/archhash.h> George Spelvin
2016-05-26 17:23 ` [PATCH v2 10/10] h8300: Add <asm/hash.h> George Spelvin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CA+55aFzZwOm3352HXgMqvSpgmTms-fqLfiu1ZYFO5DhOoiqv7g@mail.gmail.com \
--to=torvalds@linux-foundation.org \
--cc=bfields@redhat.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@sciencehorizons.net \
--cc=peterz@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).