Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1411735 > unrolled thread

Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function Linus Torvalds <torvalds@linux-foundation.org> - 2016-06-02 03:20 +0200
    Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function "George Spelvin" <linux@sciencehorizons.net> - 2016-06-02 04:40 +0200
      Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function Linus Torvalds <torvalds@linux-foundation.org> - 2016-06-02 18:40 +0200
        Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function "George Spelvin" <linux@sciencehorizons.net> - 2016-06-02 20:30 +0200

#1411735 — Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function

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

[toc] | [next] | [standalone]

#1411778

Linus Torvalds wrote:
> On Mon, May 30, 2016 at 11:10 AM, George Spelvin 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()".

I do wonder about the second multiply in fold_hash().

For the 32-bit version, the outer __hash_32() could safely be deleted.
The 32-bit hash gets fed to hash_32() to reduce it to a hash table
index anyway.

(Specifically, it can be deleted from fs/namei.c and moved into
hash_str() and hash_mem() where it's useful in folding the hash value to
less than 32 bits.)

It's the 64-bit version that's an issue.  I need to reduce 128 bits of
weakly mixed hash state to 32, and on x86 and PPC, two multiplies seems
like the fastest way.  The second one could be done with a 32-bit multiply
instead, but 64-bit has been the same latency as 32 ever since Prescott
and Saltwell (Agner Fog says it's one cycle *faster* in many cases, which
I find hard to believe), so re-using the large immediate is a net win.

I could use two more iterations of HASH_MIX() or something similar,
then just take the x value, but that's 6 cycles.  If a multiply is
4 or 5 cycles, that's a net loss.


An issue with the 64-bit version which I hadn't thought through is
false sharing with the length.  As the comments say, nobody actually
uses the hash value until after some code that checks for special cases
like . and .. using the length.

On a 32-bit machine, the length and hash are in separate registers (%edx
and %eax) and scoreboarded separately, so it's possible to examine the
length without stalling on the hash.

But on a 64-bit machine, they're merged in %rax, and it's not possible to
extract the length without waiting for the hash.  :-(

That puts the hash folding on the critical path, so maybe it needs
more attention.

> 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.

The problem is it's so damn useful as a mixing function.  When a multiplier
*is* available, with 3-4 cycle latency, it's hard to beat.

But worrying about that is the reason I left provision for arch-specific
hooks, and I'm already working on the first: the PA-RISC doesn't have
an integer multiplier at all, although the FPU can do 32-bit integer
multiplies.

(So much for my theory that 64-bit OOO CPUs always have grunty
multipliers!  That said, the last PA-RISC came out in 2005.)

But it tries to be good at shift-and-add sequences for multiplies by
fixed integers.

Unfortnately, the best 64-bit multiply sequence I've come up with is
13 cycles, which is a mite painful.  A few more HASH_MIX rounds looks
attractive in that case.

[toc] | [prev] | [next] | [standalone]

#1412424

On Wed, Jun 1, 2016 at 7:31 PM, George Spelvin
<linux@sciencehorizons.net> wrote:
>
> I could use two more iterations of HASH_MIX() or something similar,
> then just take the x value, but that's 6 cycles.  If a multiply is
> 4 or 5 cycles, that's a net loss.

Yes. Especially since the multiply will often end up more able to be
run in parallel with other things.

> But worrying about that is the reason I left provision for arch-specific
> hooks, and I'm already working on the first: the PA-RISC doesn't have
> an integer multiplier at all, although the FPU can do 32-bit integer
> multiplies.

Don't worry about pa-risc. There may be a handful of users, where even
"users" is more of a "boot up occasionally just for perverse fun"
rather than anything else.

That's true of at least half the architectures we support - the only
ones that really matter and where performance is a real isseu are
currently x86, arm and powerpc.

                  Linus

[toc] | [prev] | [next] | [standalone]

#1412486

Linus Torvalds wrote:
> Don't worry about pa-risc. There may be a handful of users, where even
> "users" is more of a "boot up occasionally just for perverse fun"
> rather than anything else.

Yes, I'm quite aware that, like alpha and ia64, it's purely of historical
interest.  It's not even in the second tier of chips that are still being
bought to get real work done, like MIPS (a lot of consumer routers!) and
SPARC.

(Offended Itanium fanbois, please go back to sleep until Kittson is
atually for sale.)

But it's an interesting architecture (in the same sense that a platypus
is an "interesting animal"), the maintainers are happy to test patches,
and I presume I'm permitted to amuse muself messing with it as long as it
doesn't cause problems for the non-Jamaican bobsled teams.

(Note that PA-RISC does't support unaligned loads, so it doesn't use the
word-at-a-time code path at all.)

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web