Received: by 2002:ac0:bc90:0:0:0:0:0 with SMTP id a16csp801010img; Fri, 22 Mar 2019 08:51:18 -0700 (PDT) X-Google-Smtp-Source: APXvYqywmeAKVlXOyag/M9J41jPrveYIpwZeehEbmO2J2zdH8QlZ6pqsnSj+vD8vDaNPDy+Q88Vl X-Received: by 2002:aa7:8694:: with SMTP id d20mr9746287pfo.81.1553269878351; Fri, 22 Mar 2019 08:51:18 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1553269878; cv=none; d=google.com; s=arc-20160816; b=jSV265iFVKZMnfxptIArsEYnPN8/KHMwThGkvUqX3Nny+QKVej+B+wCcV+2/7e61SP CwvHrYNrxPCmbJzFuUa5aHQsk+R7P/7SdrY1kFVLZZkx2j/veDuco05RlBt8U+XsIKz9 7sg3edtrxh0rXNR7YDXwg7LNkiOovIo5VBLliZ2oLrI++W7AiXc1Il4wNKyRrecyNlDh e7zDHc2TwjQY8AvHz7H+3MqTVJ802MvLhAKwrIn1Z7TbcQAaP8EE9/+eBZS2HmBGEfH8 +fpZFHx/jYmaS+vVsovu75FU/Cc+bAX73A4fBuId1N5X6tHQhMLsGcq5lCdR1rcbpiM4 AgJQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=ADd/WlX24cMYXST+eM5ecQSFrL8rYUZAcSMyeV6d0fI=; b=SEWvuu7ppARVg7lsbYpHcsimXW3Nz+dzVVVHXT22EMnyP2Zxzkwr0oKgEJtbyJi77P yyltcgCF8bHwtZXrzhr+hyya0A13UndVbjAZl0vdsb/bDJG2rRv25M5TtqUj1Wms7PKU 9/Njs0qfJB5ElGwRJD0WdUBGIm3L4j7zFcHxiEMFsNH6StKfOWYkvj4SsJOcvXJPVk4Z R75/n+M52BSosFxq7Qi5YLlcVnjk80mpzo9gKXDNueer4hOmst2fgoQKhBdoG/1lOcGh bH8B74jfIBldcMKz2tiwANsx10WYa490mA+p70bKj3stjC228UkOox16MyEC6wsUQZG/ sRcQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id f6si6852727pfn.108.2019.03.22.08.51.00; Fri, 22 Mar 2019 08:51:18 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728352AbfCVPuT (ORCPT + 99 others); Fri, 22 Mar 2019 11:50:19 -0400 Received: from mout.kundenserver.de ([212.227.17.13]:45707 "EHLO mout.kundenserver.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727843AbfCVPuR (ORCPT ); Fri, 22 Mar 2019 11:50:17 -0400 Received: from wuerfel.lan ([149.172.19.189]) by mrelayeu.kundenserver.de (mreue108 [212.227.15.145]) with ESMTPA (Nemesis) id 1MbRbr-1gaEfE3zyb-00bqAN; Fri, 22 Mar 2019 16:49:50 +0100 From: Arnd Bergmann To: stable@vger.kernel.org, Will Deacon , Florian La Roche Cc: Peter Zijlstra , Anshul Garg , Linus Torvalds , Davidlohr Bueso , Thomas Gleixner , Ingo Molnar , Joe Perches , David Miller , Matthew Wilcox , Kees Cook , Michael Davidson , Andrew Morton , Arnd Bergmann , linux-kernel@vger.kernel.org Subject: [BACKPORT 4.4.y 24/25] lib/int_sqrt: optimize small argument Date: Fri, 22 Mar 2019 16:44:15 +0100 Message-Id: <20190322154425.3852517-25-arnd@arndb.de> X-Mailer: git-send-email 2.20.0 In-Reply-To: <20190322154425.3852517-1-arnd@arndb.de> References: <20190322154425.3852517-1-arnd@arndb.de> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Provags-ID: V03:K1:ihhiFo5aEMgWh25D9Bhc7/1vpeO4x1oikMd7eBfRIzsE2G0q9Gr hIr6QmP9RMez6Ix4DFFMIQDzR3YaedPi3Pz/K1W8ErI+BdhZVywglbZcwR6f+6SJT27oNm8 g1lGrthhnwWUDhmA10q3KnEkYDrWCtlwdZ320LWQYbCb/IEQT/+zYeBzFZsmA/cbli652aU JgBDPkDU+yn7METUKJ6wA== X-Spam-Flag: NO X-UI-Out-Filterresults: notjunk:1;V03:K0:qJH3pP5UbgI=:5C8uo+IYJWNbuNNH4ebN7V n+nS75jqFZYRqIoFCQJuhd0TKUszs2S1oxLhtAZZ2qw1FAGKe+PHCsAUkAj+pWLRZbwTy9oMO 1zjhMB6R4xJ27YZ+aiMCGtzxKTsu/hvRCKdfPQhq83Sj2ruvf6VmWAqypgwwolJDxWRXzi3QZ 0nz6xh65GlJfbrNJSbYL764ctj/c1X9NtyW/OUcqlxWWMGOPL67fErX6VNiQSpv1Q7VwnzSse pBodOqvkkOiNKioaSB3+SERQyrEAzMFI7VVA1vAoo5Mb2CGpkpM6dyX7DcaAk1FsbcDZHLum/ 5eHtD3DIDfsQDyXg63QDDIt+cBdFqFt8OBi/rZSAmotk700OJP3NmWnEtGJZl7P6vHW9dOeDC XBgDvomnu0vW2pmAwKle5/xZz2R/jlwBthWjnqXhpm2QPud/mMtvs2hX6zvuuFwew7+SAFI6a gGHNijLlQjhb6lC6QYRKaSSmt+Q7s6yMbcvrCO4lUA5QMhkfVMz086ERooqoCqc9GyG6xk6+F 6GmbJoOrolBgua1CPxiKQMtqUUiV7bkjrTXWXadJNkK+B+W8FrSUITKfmLH5BcIp7cREVQeLT HMc2bKZCYn8/b/7OJ/bcZaBbUurg+tg5pMDvBM90HjS+zPez3e2RkwUxcJSjm6jpsh/Eh2QCr aHhlGBFFYreiAceCa3bQBzjSYHbM3A7yHLqFWHaquOAXJK0FvtylFK0poLwjwGimBcYPOEiTZ Jq1hnSGHJTGHTBpUP3EVCwv+7F0ytysK1XPMZA== Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Peter Zijlstra The current int_sqrt() computation is sub-optimal for the case of small @x. Which is the interesting case when we're going to do cumulative distribution functions on idle times, which we assume to be a random variable, where the target residency of the deepest idle state gives an upper bound on the variable (5e6ns on recent Intel chips). In the case of small @x, the compute loop: while (m != 0) { b = y + m; y >>= 1; if (x >= b) { x -= b; y += m; } m >>= 2; } can be reduced to: while (m > x) m >>= 2; Because y==0, b==m and until x>=m y will remain 0. And while this is computationally equivalent, it runs much faster because there's less code, in particular less branches. cycles: branches: branch-misses: OLD: hot: 45.109444 +- 0.044117 44.333392 +- 0.002254 0.018723 +- 0.000593 cold: 187.737379 +- 0.156678 44.333407 +- 0.002254 6.272844 +- 0.004305 PRE: hot: 67.937492 +- 0.064124 66.999535 +- 0.000488 0.066720 +- 0.001113 cold: 232.004379 +- 0.332811 66.999527 +- 0.000488 6.914634 +- 0.006568 POST: hot: 43.633557 +- 0.034373 45.333132 +- 0.002277 0.023529 +- 0.000681 cold: 207.438411 +- 0.125840 45.333132 +- 0.002277 6.976486 +- 0.004219 Averages computed over all values <128k using a LFSR to generate order. Cold numbers have a LFSR based branch trace buffer 'confuser' ran between each int_sqrt() invocation. Link: http://lkml.kernel.org/r/20171020164644.876503355@infradead.org Fixes: 30493cc9dddb ("lib/int_sqrt.c: optimize square root algorithm") Signed-off-by: Peter Zijlstra (Intel) Suggested-by: Anshul Garg Acked-by: Linus Torvalds Cc: Davidlohr Bueso Cc: Thomas Gleixner Cc: Ingo Molnar Cc: Will Deacon Cc: Joe Perches Cc: David Miller Cc: Matthew Wilcox Cc: Kees Cook Cc: Michael Davidson Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds (cherry picked from commit 3f3295709edea6268ff1609855f498035286af73) Signed-off-by: Arnd Bergmann --- lib/int_sqrt.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index 1ef4cc344977..1afb545a37c5 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -22,6 +22,9 @@ unsigned long int_sqrt(unsigned long x) return x; m = 1UL << (BITS_PER_LONG - 2); + while (m > x) + m >>= 2; + while (m != 0) { b = y + m; y >>= 1; -- 2.20.0