linux-kernel - [PATCH] blk-wbt: Speed up integer square root in rwb_arm

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date: Fri, 29 Mar 2024 17:12:45 +0800
From: I Hsin Cheng <richard120310@...il.com>
To: axboe@...nel.dk
Cc: akpm@...ux-foundation.org,
	linux-block@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	I Hsin Cheng <richard120310@...il.com>
Subject: [PATCH] blk-wbt: Speed up integer square root in rwb_arm_timer

As the comments in rwb_arm_timer says, we should speed up the process of
integer square root with some variant versions. The implementation of
the variant integer square root "int_fast_sqrt()" is based on the
equation $lg(\sqrt{x}) = lg(x) / 2$ , where "lg" stands for logarithm
with base 2. After we take the first approximation by calculate
$2^{lg(x)/2}$ , we utilize Newton's method for three times in order to
enhance the precision.

To prove "int_fastsqrt" is indeed faster than the "int_sqrt", we take
some bench experiments to calculate the integer logarithm from 1 to 10^6
and use "perf stat --repeat 100" to measure the performance of each
function.

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.

The experiments runs on x86_64 GNU/Linux Architecture and the CPU is
Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz.

Signed-off-by: I Hsin Cheng <richard120310@...il.com>
---
 block/blk-wbt.c     |  2 +-
 lib/math/int_sqrt.c | 21 +++++++++++++++++++++
 2 files changed, 22 insertions(+), 1 deletion(-)

diff --git a/block/blk-wbt.c b/block/blk-wbt.c
index 0bb613139..8d25c0e55 100644
--- a/block/blk-wbt.c
+++ b/block/blk-wbt.c
@@ -407,7 +407,7 @@ static void rwb_arm_timer(struct rq_wb *rwb)
 		 * though.
 		 */
 		rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
-					int_sqrt((rqd->scale_step + 1) << 8));
+					int_fastsqrt((rqd->scale_step + 1) << 8));
 	} else {
 		/*
 		 * For step < 0, we don't want to increase/decrease the
diff --git a/lib/math/int_sqrt.c b/lib/math/int_sqrt.c
index a8170bb91..e25ba179e 100644
--- a/lib/math/int_sqrt.c
+++ b/lib/math/int_sqrt.c
@@ -40,6 +40,27 @@ unsigned long int_sqrt(unsigned long x)
 }
 EXPORT_SYMBOL(int_sqrt);

+
+/**
+ * int_fastsqrt - faster invariant of int_sqrt
+ * @x: integer of which to calculate the sqrt
+ *
+ * Computes: floor(sqrt(x))
+ */
+
+unsigned long int_fastsqrt(unsigned long x)
+{
+	unsigned long y = ((31 - __builtin_clz(x | 1)) >> 1);
+	unsigned long z = 1 << y;
+
+	z = (z + (x / z)) >> 1;
+	z = (z + (x / z)) >> 1;
+	z = (z + (x / z)) >> 1;
+
+	return z;
+}
+EXPORT_SYMBOL(int_fastsqrt);
+
 #if BITS_PER_LONG < 64
 /**
  * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input
-- 
2.34.1