Messages in this thread | | | Date | Mon, 30 May 2016 18:27:21 +0200 | From | Peter Zijlstra <> | Subject | Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function |
| |
On Mon, May 30, 2016 at 12:06:18PM -0400, George Spelvin wrote: > Not quite. The fold_hash() you quote is used only on 64-bit systems, > which can be assumed to have a reasonable 64-bit multiply. On 32-bit > platforms, I avoid using GOLDEN_RATIO_64 at all, since 64x64-bit > multiplies are so expensive.
Right; as stated performance really isn't a goal here.
> You actually have only 96 bits of input. The correct prototype is: > > static inline u64 iterate_chain_key(u64 key, u32 idx)
Indeed, although I conveniently ignored that because I didn't think it'd matter :-)
> If performance mattered, I'd be inclined to use one or two iterations > of the 32-bit HASH_MIX() function, which is specifically designed > to add 32 bits to a 64-bit hash value.
Ah, I missed that HASH_MIX() had 64 bit state, so much for being able to read it seems. Also; should we not move that entire section of fs/namei.c into linux/hash.h ?
These two primitives seem generally useful.
> A more thorough mixing would be achieved by __jhash_mix(). Basically: > > static inline u64 iterate_chain_key(u64 key, u32 idx) > { > u32 k0 = key, k1 = key >> 32; > > __jhash_mix(idx, k0, k1) /* Macro that modifies arguments! */ > > return k0 | (u64)k1 << 32; > } > > (The order of arguments is chosen to perserve the two "most-hashed" values.)
(I'd never have managed to deduce that property given the information in jhash.h)
OK, that looks good to me, thanks! I'll go use that then.
> Also, I just had contact from the hppa folks who have brought to my > attention that it's an example of an out-of-order superscalar CPU that > *doesn't* have a good integer multiplier. For general multiplies, > you have to move values to the FPU and the code is a pain.
Egads, that's horrible, but sounds exactly like the thing you 'like' given these patches :-) Good luck with that.
| |