Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S966245AbbBCPy6 (ORCPT ); Tue, 3 Feb 2015 10:54:58 -0500 Received: from mail-ie0-f178.google.com ([209.85.223.178]:63502 "EHLO mail-ie0-f178.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S965999AbbBCPy5 (ORCPT ); Tue, 3 Feb 2015 10:54:57 -0500 MIME-Version: 1.0 In-Reply-To: <1422938501.2293.1.camel@stgolabs.net> References: <1422897162-111998-1-git-send-email-aksgarg1989@gmail.com> <1422938501.2293.1.camel@stgolabs.net> Date: Tue, 3 Feb 2015 21:24:56 +0530 Message-ID: Subject: Re: [PATCH] lib/int_sqrt.c: Optimize square root function From: Anshul Garg To: Davidlohr Bueso Cc: Linus Torvalds , Linux Kernel Mailing List , "anshul.g@samsung.com" 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: 2051 Lines: 64 On Tue, Feb 3, 2015 at 10:11 AM, Davidlohr Bueso wrote: > On Mon, 2015-02-02 at 11:13 -0800, Linus Torvalds wrote: >> IOW, instead of >> >> m = 1UL << (BITS_PER_LONG - 2); >> >> perhaps something like >> >> m = 1UL << (BITS_PER_LONG/2- 2); >> if (m < x) >> m <<= BITS_PER_LONG/2; On doing this change also extra instruction(shown below) will execute if x is small(say 10000). b = y + m; y >>= 1; if (x >= b) { Although i understand your point that we can set value of m according to range of x. But in future also range of x can change if apart from memory some other module starts using this function more extensively. So in worst case it will be almost same as current implementation. So i think its better to scale m according to x by doing while(m > x) m>>=2; rather than according to range of x. Thanks Anshul Garg >> >> (assuming gcc can change that code into a "cmov") might cut down the >> "lots of empty loops" case in half for small values of 'x'. > > Makes a lot of sense. > >> There's probably some other better cheap initial guess value estimator. > > Just to get a feeling for the normal arg range in the non-driver parts > that use this thing: > > fs/ceph/super.h: congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10); > fs/nfs/write.c: nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10); > fs/nfsd/nfscache.c: limit = (16 * int_sqrt(low_pages)) << (PAGE_SHIFT-10); > kernel/rcu/tree_plugin.h: ls = int_sqrt(nr_cpu_ids); > mm/memcontrol.c: inactive_ratio = int_sqrt(10 * gb); > mm/page_alloc.c: ratio = int_sqrt(10 * gb); > mm/page_alloc.c: new_min_free_kbytes = int_sqrt(lowmem_kbytes * 16); > > So mostly values that scale according to mem or cpu. > > > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/