From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753685AbcENDyI (ORCPT ); Fri, 13 May 2016 23:54:08 -0400 Received: from ns.horizon.com ([71.41.210.147]:40196 "HELO ns.horizon.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1753459AbcENDyG (ORCPT ); Fri, 13 May 2016 23:54:06 -0400 Date: 13 May 2016 23:54:03 -0400 Message-ID: <20160514035403.365.qmail@ns.horizon.com> From: "George Spelvin" To: torvalds@linux-foundation.org Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Cc: eric.dumazet@gmail.com, linux@horizon.com, linux-kernel@vger.kernel.org, riel@redhat.com, tglx@linutronix.de In-Reply-To: Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On May 1, 2016 at 9:51 AM, Lnus Torvalds wrote: > On Sun, May 1, 2016 at 2:43 AM, George Spelvin wrote: >> * If you feel ambitious, add a 32-bit CONFIG_ARCH_HAS_SLOW_MULTIPLIER >> exception path. > Let's make that a separate worry, and just fix hash_64() first. > > In particular, that means "let's not touch COLDEN_RATIO_32 yet". I > suspect that when we *do* change that value, we do want the > non-multiplying version you had. I've been working on this, and just a brief status update: it's definitely one of those rabbit holes. There are exactly three architectures which (some models) don't have an efficient 32x32->32-bit multiply: - arch/m58k: MC68000 (and 68010 and 68328) no-mmu - arch/h8300: Most (all?) of the H8 processor series - arch/microblaze: Depending on Verilog compilation options The thing is, they all don't have a barrel shifter, either. Indeed, only the m68k even has multi-bit shift instructions. So the upshot is that it's not clear that shift-and-add is a whole lot better. Working out the timing on the 68000, I can beat the multiply code, but not by much. So I'm working on arch-specific solutions for those three cases. H8 and 68000 have 16x16->32-bit multiplies, which can be used to make a reasonable hash function (some H8 models can multiply faster than they can shift!), but if you configure a Microblaze with neither multiplier nor barrel shifter (which arch/microblaze/Kconfig.platform lets you do), I have no idea what to do.