Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753015AbcD3BMc (ORCPT ); Fri, 29 Apr 2016 21:12:32 -0400 Received: from mail-io0-f173.google.com ([209.85.223.173]:36617 "EHLO mail-io0-f173.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752300AbcD3BMb (ORCPT ); Fri, 29 Apr 2016 21:12:31 -0400 MIME-Version: 1.0 In-Reply-To: <20160430003206.25509.qmail@ns.horizon.com> References: <20160430003206.25509.qmail@ns.horizon.com> Date: Fri, 29 Apr 2016 18:12:29 -0700 X-Google-Sender-Auth: E_kICBg-kzJK_9hPPd6OGj2M6iY Message-ID: Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism From: Linus Torvalds To: George Spelvin Cc: Linux Kernel Mailing List , Thomas Gleixner Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 847 Lines: 25 On Fri, Apr 29, 2016 at 5:32 PM, George Spelvin wrote: > > Odd is important. If the multiplier is even, the msbit of the input > doesn't affect the hash result at all. Fair enough. My test-set was incomplete. >> Yeah. gcc will actually do the clever stuff for the 32-bit case, afaik. > > It's not as clever as it could be; it just does the same Booth > recoding thing, a simple series of shifts with add/subtract. Ahh. I thought gcc did the Bernstein's algorithm thing, which is exponential in the bit size. That would have explained why it only does it for 32-bit constants. Not doing it for 64-bit constants makes no sense if it just uses the trivial Booth's algorithm version. So the odd "we don't do it for 64-bit" is apparently just an oversight, not because gcc does something clever. Oh well. Linus