Received-SPF: pass (google.com: domain of linux-kernel+bounces-125319-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3;
Message-ID: <be8e14ec-3d46-4d67-88b0-f3dbf7ff22b2@kernel.dk>
Date: Fri, 29 Mar 2024 13:12:56 -0600
Precedence: bulk
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: [PATCH] blk-wbt: Speed up integer square root in rwb_arm_timer
To: Bart Van Assche <bvanassche@acm.org>,
 I Hsin Cheng <richard120310@gmail.com>
Cc: akpm@linux-foundation.org, linux-block@vger.kernel.org,
 linux-kernel@vger.kernel.org
References: <20240329091245.135216-1-richard120310@gmail.com>
 <848d1259-ff6e-4732-b840-a02a5e5fe2cb@acm.org>
Content-Language: en-US
From: Jens Axboe <axboe@kernel.dk>
In-Reply-To: <848d1259-ff6e-4732-b840-a02a5e5fe2cb@acm.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit

On 3/29/24 12:15 PM, Bart Van Assche wrote:
> On 3/29/24 2:12 AM, I Hsin Cheng wrote:
>> As the result shown, the origin version of integer square root, which is
>> "int_sqrt" takes 35.37 msec task-clock, 1,2181,3348 cycles, 1,6095,3665
>> instructions, 2551,2990 branches and causes 1,0616 branch-misses.
>>
>> At the same time, the variant version of integer square root, which is
>> "int_fastsqrt" takes 33.96 msec task-clock, 1,1645,7487 cyclces,
>> 5621,0086 instructions, 321,0409 branches and causes 2407 branch-misses.
>> We can clearly see that "int_fastsqrt" performs faster and better result
>> so it's indeed a faster invariant of integer square root.
> 
> I'm not sure that a 4% performance improvement is sufficient to
> replace the int_sqrt() implementation. Additionally, why to add a
> second implementation of int_sqrt() instead of replacing the
> int_sqrt() implementation in lib/math/int_sqrt.c?

That's the real question imho - if provides the same numbers and is
faster, why have two?

I ran a quick test because I was curious, and the precision is
definitely worse. The claim that it is floor(sqrt(val)) is not true.
Trivial example:

1005117225
	sqrt()		31703.58
	int_sqrt()	30703
	int_fastsqrt()	30821

whether this matters, probably not, but then again it's hard to care
about a slow path sqrt calculation. I'd certainly err on the side of
precision for that.

-- 
Jens Axboe