From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753750AbdJSUcH (ORCPT ); Thu, 19 Oct 2017 16:32:07 -0400 Received: from mail-io0-f194.google.com ([209.85.223.194]:55994 "EHLO mail-io0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752007AbdJSUcG (ORCPT ); Thu, 19 Oct 2017 16:32:06 -0400 X-Google-Smtp-Source: ABhQp+RRPu17Faj60vSKReJMe7rcN2U71uyFbxDXT90LSnGOXQ0rxrnguzN02I8HaWUx0z+rDBNPOg== From: Michael Davidson To: Andrew Morton , Ingo Molnar , David Miller , Matthew Wilcox , Kees Cook Cc: linux-kernel@vger.kernel.org, Michael Davidson Subject: [PATCH] lib/int_sqrt.c: optimize for small argument values Date: Thu, 19 Oct 2017 13:31:37 -0700 Message-Id: <20171019203137.131042-1-md@google.com> X-Mailer: git-send-email 2.15.0.rc1.287.g2b38de12cc-goog Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org int_sqrt() currently takes approximately constant time regardless of the value of the argument. By using the magnitude of the operand to set the initial conditions for the calculation the cost becomes proportional to log2 of the argument with the worst case behavior not being measurably slower than it currently is. Signed-off-by: Michael Davidson --- lib/int_sqrt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index 1ef4cc344977..8394b0dcecd4 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -21,7 +21,7 @@ unsigned long int_sqrt(unsigned long x) if (x <= 1) return x; - m = 1UL << (BITS_PER_LONG - 2); + m = 1UL << (__fls(x) & ~1UL); while (m != 0) { b = y + m; y >>= 1; -- 2.15.0.rc1.287.g2b38de12cc-goog