Received: by 2002:a05:6a10:5bc5:0:0:0:0 with SMTP id os5csp886723pxb; Wed, 27 Oct 2021 14:29:17 -0700 (PDT) X-Google-Smtp-Source: ABdhPJy0YMDDGG5QSx1zH+FQrZ2HAkratXLuA4E9/UFg85M0XNpl9eFuO9WdtiCNDRLJGF8tv8Xh X-Received: by 2002:a17:90a:19e:: with SMTP id 30mr8422618pjc.140.1635370058303; Wed, 27 Oct 2021 14:27:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1635370058; cv=none; d=google.com; s=arc-20160816; b=WYPSgIWu1QOwMOM8JUe+mHuW8Yv0P7qLSQEpNVutX4cSwWZvMpMWmDI+U0gOo7sKcX XHP0PV2/mIOTL5kFMFBeP6dXpGKoCYutJ/tAIun6AmYM7aKr8THLZwc5KktTxVdH1H3I 7wErjOQAfegNylixtwarPQtibHi+4EeIumwxt0w94gjsVT2CwvoyIVUktmcjJNwCYNn/ 1bzGThaAKTMEF4Yqnwy3g+LsPKDNrESas4kQ9HtB/IJF1+PAdJ0N3Y4/WYP6NnQHQBHZ CAanzl4MwLwW3rD3+ipwlpeOp3emCmL03Ff1VzQqxSvHxRnescK3Yhl2RT3o9VZn5DQ/ 4Pxw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:subject:cc:to:from:date; bh=y1DL2z4XQvr7T76TKy9oxAOl6rDSeO8mtd5Sle6IRuw=; b=MhINC8PR5nREbsu5SSUTTsO7H0iYnR2HiUS/VSD5YE0k3NbbT2/YBrmXiLwGu7ezTZ 666hwI/DYqOPVAwp/U0ATahqQtbspgBLTxgBajp95l6pq2xIoHR7L87aKx5VHFwFYxEK KGaofcD7V/9ADYB6jOeJAIOLqTUkRJ1N85AIrocBFWrGrsuZ3gAMMggu44Rs3vuIQLf1 RzlTH8YG1xCDIHOY0uGZp0Il1BshtxIlG5qQ6Yi4036wQPWKF8AnTI8gGtChYbFbPFdv WEZJggpb40VY7KFhj8FuMKQi3KkY1j48DY0A8bGmDQ4oryq3iXBGLr4c5rQmn24G8LVI IToA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id d191si1263991pgc.410.2021.10.27.14.27.25; Wed, 27 Oct 2021 14:27:38 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S242397AbhJ0OJ2 (ORCPT + 97 others); Wed, 27 Oct 2021 10:09:28 -0400 Received: from mail.kernel.org ([198.145.29.99]:38966 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S242392AbhJ0OJ1 (ORCPT ); Wed, 27 Oct 2021 10:09:27 -0400 Received: from gandalf.local.home (cpe-66-24-58-225.stny.res.rr.com [66.24.58.225]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id D544260F38; Wed, 27 Oct 2021 14:07:00 +0000 (UTC) Date: Wed, 27 Oct 2021 10:06:59 -0400 From: Steven Rostedt To: Kalesh Singh Cc: surenb@google.com, hridya@google.com, namhyung@kernel.org, kernel-team@android.com, Jonathan Corbet , Ingo Molnar , Shuah Khan , Masami Hiramatsu , Tom Zanussi , linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org Subject: Re: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2 Message-ID: <20211027100659.00ec702b@gandalf.local.home> In-Reply-To: References: <20211025200852.3002369-1-kaleshsingh@google.com> <20211025200852.3002369-7-kaleshsingh@google.com> <20211026151451.7f3e09a4@gandalf.local.home> <20211026201846.08990d1d@rorschach.local.home> <20211026211511.403d76ca@rorschach.local.home> <20211026222123.5e206fcf@rorschach.local.home> <20211026231557.1eedad9b@rorschach.local.home> X-Mailer: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, 26 Oct 2021 21:04:29 -0700 Kalesh Singh wrote: > On Tue, Oct 26, 2021 at 8:16 PM Steven Rostedt wrote: > > > > On Tue, 26 Oct 2021 22:21:23 -0400 > > Steven Rostedt wrote: > > > > > I'm sure there's an algorithm somewhere that can give as the real max. > > > > You got me playing with this more ;-) > > > > OK, I added the rounding in the wrong place. I found that we can make > > the max_div to be the same as the shift! The bigger the shift, the > > bigger the max! > > Nice! :) > > > > mult = (1 << shift) / div; > > max_div = (1 << shift) > > > > But the rounding needs to be with the mult / shift: > > > > return (val * mult + ((1 << shift) - 1)) >> shift; > > > > > > When val goes pass 1 << shift, then the error will be off by more than > > one. > Did you mean, val should be such that when we do the (val * mult) we > only get rounding errors less than (1 << shift)? We get rounding errors when val is greater than (1 << shift) because then it exposes the bits that are not shifted out. > > I think we also need to flip the delta now since we round down initially: > > delta = (1 << shift) - (mult * div) > Actually, we don't need the delta at all. Just what I showed above. Pick some arbitrary shift (let's say 20 as that seems to be commonly used, and works for 32 bit as well) and then we figure out the multiplier. mult = (1 << shift) / div; No delta needed. Our max is going to be 1 << shift, and then all we need is: if (val < (1 << shift)) return (val * mult + ((1 << shift) - 1)) >> shift; else return val / div; All we need to save to do the operation is the shift, the constant div and the calculated constant mult. -- Steve