Optimize int_sqrt for small values for faster idle

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

I instrumented the function on my workstation and most values are 16bit only and most others 32bit (50% percentile is 122094, 75% is 3699533).

sqrt is implemented by starting with an initial estimation, and then iterating. int_sqrt currently only uses a fixed estimating which is good for 64bits worth of input.

This patch adds some checks at the beginning to start with a better estimate for values fitting in 8, 16bit and 32bit. This makes int_sqrt between 60+% faster for values in 16bit, and still somewhat faster (between 10 and 30%) for larger values upto 32bit. Full 64bit is slightly slower.

This optimizes the short idle calls and does not hurt the long sleep (which probably do not care) much.

An alternative would be a full table drive approach, or trying some inverted sqrt optimization, but this simple change already seems to have a good payoff.

This thread might be relevant:

https://lkml.org/lkml/2015/2/2/600

and perhaps using fls might still be a good approach.

Quoted 1 line

Quoted 1 line

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

I instrumented the function on my workstation and most values are 16bit only and most others 32bit (50% percentile is 122094, 75% is 3699533).

sqrt is implemented by starting with an initial estimation, and then iterating. int_sqrt currently only uses a fixed estimating which is good for 64bits worth of input.

This patch adds some checks at the beginning to start with a better estimate for values fitting in 8, 16bit and 32bit. This makes int_sqrt between 60+% faster for values in 16bit, and still somewhat faster (between 10 and 30%) for larger values upto 32bit. Full 64bit is slightly slower.

This optimizes the short idle calls and does not hurt the long sleep (which probably do not care) much.

An alternative would be a full table drive approach, or trying some inverted sqrt optimization, but this simple change already seems to have a good payoff.

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

I instrumented the function on my workstation and most values are 16bit only and most others 32bit (50% percentile is 122094, 75% is 3699533).

sqrt is implemented by starting with an initial estimation, and then iterating. int_sqrt currently only uses a fixed estimating which is good for 64bits worth of input.

This patch adds some checks at the beginning to start with a better estimate for values fitting in 8, 16bit and 32bit. This makes int_sqrt between 60+% faster for values in 16bit, and still somewhat faster (between 10 and 30%) for larger values upto 32bit. Full 64bit is slightly slower.

This optimizes the short idle calls and does not hurt the long sleep (which probably do not care) much.

An alternative would be a full table drive approach, or trying some inverted sqrt optimization, but this simple change already seems to have a good payoff.

Signed-off-by Andi Kleen <[email protected]>

---
 lib/int_sqrt.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

lib/int_sqrt.c +0 -0

index 1ef4cc3..2479ccf 100644

lib/int_sqrt.c +7 -0

+			m = 1UL << (8 - 2);
+		else
+			m = 1UL << (16 - 2);
+	} else if (x <= 0xffffffff)
+		m = 1UL << (32 - 2);
+	else
+		m = 1UL << (BITS_PER_LONG - 2);
 	while (m != 0) {
 		b = y + m;
 		y >>= 1;

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

I instrumented the function on my workstation and most values are 16bit only and most others 32bit (50% percentile is 122094, 75% is 3699533).

sqrt is implemented by starting with an initial estimation, and then iterating. int_sqrt currently only uses a fixed estimating which is good for 64bits worth of input.

This patch adds some checks at the beginning to start with a better estimate for values fitting in 8, 16bit and 32bit. This makes int_sqrt between 60+% faster for values in 16bit, and still somewhat faster (between 10 and 30%) for larger values upto 32bit. Full 64bit is slightly slower.

This optimizes the short idle calls and does not hurt the long sleep (which probably do not care) much.

An alternative would be a full table drive approach, or trying some inverted sqrt optimization, but this simple change already seems to have a good payoff.

lib/int_sqrt.c +2 -1

-	m = 1UL << (BITS_PER_LONG - 2);
+	if (x <= 0xffff) {
+		if (m <= 0xff)

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

Quoted 5 lines · Andi Kleen

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

Quoted 3 lines

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

If you want to optimize get_typical_interval(), why not just take the square root out of the equation (literally)?

Something like

Quoted 11 lines · Rasmus Villemoes

Quoted 8 lines · Andi Kleen

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

Quoted 4 lines

If you want to optimize get_typical_interval(), why not just take the square root out of the equation (literally)?

Something like

Looks good. Yes that's a better fix.

Quoted 15 lines · Andi Kleen

Quoted 14 lines · Rasmus Villemoes

Quoted 8 lines · Andi Kleen

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

If you want to optimize get_typical_interval(), why not just take the square root out of the equation (literally)?

Quoted 4 lines

Quoted 1 line

Something like

Looks good. Yes that's a better fix.

Thanks. (Is there a good way to tell gcc that avg*avg is actually a 32x32->64 multiplication?)

Thanks. (Is there a good way to tell gcc that avg*avg is actually a 32x32->64 multiplication?)

Quoted 2 lines · Rasmus Villemoes

Thanks. (Is there a good way to tell gcc that avg*avg is actually a 32x32->64 multiplication?)

If avg is 32bit, compiler does that for you.

u32 avg = ...

u64 result = (u64)avg * avg;

Quoted 10 lines · Eric Dumazet

Quoted 2 lines · Rasmus Villemoes

Thanks. (Is there a good way to tell gcc that avg*avg is actually a 32x32->64 multiplication?)

If avg is 32bit, compiler does that for you.

u32 avg = ...

u64 result = (u64)avg * avg;

Yeah, but in this case avg is u64 because it is used to temporarily contain the sum of a bunch of u32s, before being divided by #bunch. So I'd have to write that as (u64)(u32)avg * (u32)avg, which isn't very readable :-/

I just thought the scenario of a u64 known to be holding a value < 2^32 was common enough that some utility macros already existed.

Rasmus

Quoted 2 lines · Rasmus Villemoes

Thanks. (Is there a good way to tell gcc that avg*avg is actually a 32x32->64 multiplication?)

If avg is 32bit, compiler does that for you.

u32 avg = ...

u64 result = (u64)avg * avg;

Quoted 7 lines · Eric Dumazet

Quoted 2 lines · Rasmus Villemoes

Thanks. (Is there a good way to tell gcc that avg*avg is actually a 32x32->64 multiplication?)

If avg is 32bit, compiler does that for you.

Quoted 3 lines

u32 avg = ...

u64 result = (u64)avg * avg;

It does not in fact do that :/ See commit:

9e3d6223d209 ("math64, timers: Fix 32bit mul_u64_u32_shr() and friends")

Quoted 11 lines · Rasmus Villemoes

Quoted 8 lines · Andi Kleen

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

Quoted 4 lines

If you want to optimize get_typical_interval(), why not just take the square root out of the equation (literally)?

Something like

Looks good. Yes that's a better fix.

Quoted 15 lines · Andi Kleen

Quoted 14 lines · Rasmus Villemoes

Quoted 8 lines · Andi Kleen

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

If you want to optimize get_typical_interval(), why not just take the square root out of the equation (literally)?

Quoted 4 lines

Quoted 1 line

Something like

Looks good. Yes that's a better fix.

Andi, did you have a way to measure the impact, and if so, could I get you to run the numbers again with my patch?

Quoted 22 lines · Rasmus Villemoes

Quoted 19 lines · Andi Kleen

Quoted 7 lines · Rasmus Villemoes

Quoted 5 lines · Andi Kleen

From: Andi Kleen <[email protected]>

The menu cpuidle governor does at least two int_sqrt() each time we go into idle in get_typical_interval to compute stddev

Quoted 8 lines

Quoted 3 lines

int_sqrts take 100-120 cycles each. Short idle latency is important for many workloads.

If you want to optimize get_typical_interval(), why not just take the square root out of the equation (literally)?

Something like

Looks good. Yes that's a better fix.

Quoted 2 lines

Andi, did you have a way to measure the impact, and if so, could I get you to run the numbers again with my patch?

I got the numbers from the 0day runs (AIM7 gets faster) In theory if you post the patch that should happen automatically (checking with Fengguang)