From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1161590AbcE3Q10 (ORCPT ); Mon, 30 May 2016 12:27:26 -0400 Received: from merlin.infradead.org ([205.233.59.134]:47364 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933000AbcE3Q1Z (ORCPT ); Mon, 30 May 2016 12:27:25 -0400 Date: Mon, 30 May 2016 18:27:21 +0200 From: Peter Zijlstra To: George Spelvin Cc: bfields@redhat.com, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org Subject: Re: [PATCH v3 06/10] fs/namei.c: Improve dcache hash function Message-ID: <20160530162721.GG3193@twins.programming.kicks-ass.net> References: <20160530151129.GO3206@twins.programming.kicks-ass.net> <20160530160618.22150.qmail@ns.sciencehorizons.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20160530160618.22150.qmail@ns.sciencehorizons.net> User-Agent: Mutt/1.5.21 (2012-12-30) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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.