Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932219AbcLLVhI (ORCPT ); Mon, 12 Dec 2016 16:37:08 -0500 Received: from mail-io0-f194.google.com ([209.85.223.194]:36322 "EHLO mail-io0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751427AbcLLVhF (ORCPT ); Mon, 12 Dec 2016 16:37:05 -0500 MIME-Version: 1.0 In-Reply-To: References: <20161211204345.GA1558@kroah.com> <20161212034817.1773-1-Jason@zx2c4.com> From: Linus Torvalds Date: Mon, 12 Dec 2016 13:37:03 -0800 X-Google-Sender-Auth: CNjdDRrAbvmP2Ww-Z1idMUlNmYU Message-ID: Subject: Re: [PATCH v2] siphash: add cryptographically secure hashtable function To: "Jason A. Donenfeld" Cc: "kernel-hardening@lists.openwall.com" , LKML , Linux Crypto Mailing List , George Spelvin , Scott Bauer , Andi Kleen , Andy Lutomirski , Greg KH , Jean-Philippe Aumasson , "Daniel J . Bernstein" 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: 1500 Lines: 32 On Sun, Dec 11, 2016 at 9:48 PM, Jason A. Donenfeld wrote: > I modified the test to hash data of size 0 through 7 repeatedly > 100000000 times, and benchmarked that a few times on a Skylake laptop. > The `load_unaligned_zeropad & bytemask_from_count` version was > consistently 7% slower. > > I then modified it again to simply hash a 4 byte constant repeatedly > 1000000000 times. The `load_unaligned_zeropad & bytemask_from_count` > version was around 6% faster. I tried again with a 7 byte constant and > got more or less a similar result. > > Then I tried with a 1 byte constant, and found that the > `load_unaligned_zeropad & bytemask_from_count` version was slower. > > So, it would seem that between the `if (left)` and the `switch > (left)`, there's the same number of branches. Interesting. For the dcache code (which is where that trick comes from), we used to have a loop (rather than the duff's device thing), and it performed badly due to the consistently badly predicted branch of the loop. But I never compared it against the duff's device version. I guess you could try to just remove the "if (left)" test entirely, if it is at least partly the mispredict. It should do the right thing even with a zero count, and it might schedule the code better. Code size _should_ be better with the byte mask model (which won't matter in the hot loop example, since it will all be cached, possibly even in the uop cache for really tight benchmark loops). Linus