Skip to contentSkip to conversation

Reduce overhead of menu governor

PATCH In review Mel Gorman 3 participants 7 messages Aug 6, 2014

Subsystems (2)
lore
Share & tools
lore

Mel Gorman

author reviewer
#0 lore raw

cover Reduce overhead of menu governor

The menu_select function is heavy and is very noticable in profiles for workloads that enter/leave idle state a lot. This primarily happens for scheduler microbenchmarks. The biggest contibution is the standard deviation calculations and comparisons but the excessive calls into the scheduler core do not help.

It would be nice to reduce the number of times nr_iowait is checked to once per 8 intervals but I was not sure how to measure what the general impact of such a change could be.

Similiarly I looked at different ways the standard deviation could be calculated but the standard equivalent calculations potentially overflow. It could be done as rolling average and rolling deviation but again it was unclear how that could be evaluated. Tips on how the goodness/badness of governor changes are evalated would be nice.

In the meantime, here are patches against some of the obvious stuff.

 drivers/cpuidle/governors/menu.c | 43 +++++++++++++++++++++-------------------
 include/linux/sched.h            |  3 +--
 kernel/sched/core.c              |  7 +++++++
 kernel/sched/proc.c              |  7 -------
 4 files changed, 31 insertions(+), 29 deletions(-)
Signature · 1 line
1.8.4.5
author reviewer
#1 lore raw

PATCH 1/4 cpuidle: menu: Use shifts when calculating averages where possible

We use do_div even though the divisor will usually be a power-of-two unless there are unusual outliers. Use shifts where possible

---
 drivers/cpuidle/governors/menu.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)
drivers/cpuidle/governors/menu.c +11 -3
index c4f80c1..801b2ee 100644
@@ -31,7 +31,8 @@
  * The default values do not overflow.
  */
 #define BUCKETS 12
-#define INTERVALS 8
+#define INTERVAL_SHIFT 3
+#define INTERVALS (1UL << INTERVAL_SHIFT)
 #define RESOLUTION 1024
 #define DECAY 8
 #define MAX_INTERESTING 50000
@@ -228,7 +229,10 @@ again:
 				max = value;
 		}
 	}
-	do_div(avg, divisor);
+	if (divisor == INTERVALS)
+		avg >>= INTERVAL_SHIFT;
+	else
+		do_div(avg, divisor);
 
 	/* Then try to determine standard deviation */
 	stddev = 0;
@@ -239,7 +243,11 @@ again:
 			stddev += diff * diff;
 		}
 	}
-	do_div(stddev, divisor);
+	if (divisor == INTERVALS)
+		stddev >>= INTERVAL_SHIFT;
+	else
+		do_div(stddev, divisor);
+
 	/*
 	 * The typical interval is obtained when standard deviation is small
 	 * or standard deviation is small compared to the average interval.
Signature · 1 line
1.8.4.5
author reviewer
#2 lore raw

PATCH 2/4 cpuidle: menu: Use ktime_to_us instead of reinventing the wheel

In reply to Mel Gorman

The ktime_to_us implementation is slightly better than the one implemented in menu.c. Use it

---
 drivers/cpuidle/governors/menu.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
drivers/cpuidle/governors/menu.c +1 -4
index 801b2ee..373278a 100644
@@ -297,7 +297,6 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	int latency_req = pm_qos_request(PM_QOS_CPU_DMA_LATENCY);
 	int i;
 	unsigned int interactivity_req;
-	struct timespec t;
 
 	if (data->needs_update) {
 		menu_update(drv, dev);
@@ -311,9 +310,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 		return 0;
 
 	/* determine the expected residency time, round up */
-	t = ktime_to_timespec(tick_nohz_get_sleep_length());
-	data->next_timer_us =
-		t.tv_sec * USEC_PER_SEC + t.tv_nsec / NSEC_PER_USEC;
+	data->next_timer_us = ktime_to_us(tick_nohz_get_sleep_length());
 
 
 	data->bucket = which_bucket(data->next_timer_us);
Signature · 1 line
1.8.4.5
Acked-by on v1 2/4
#3 lore raw

Re: [PATCH 2/4] cpuidle: menu: Use ktime_to_us instead of reinventing the wheel

Quoted 4 lines · Mel Gorman

The ktime_to_us implementation is slightly better than the one implemented in menu.c. Use it

Quoted 28 lines
---
  drivers/cpuidle/governors/menu.c | 5 +----
  1 file changed, 1 insertion(+), 4 deletions(-)
drivers/cpuidle/governors/menu.c +1 -4
index 801b2ee..373278a 100644
@@ -297,7 +297,6 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
  	int latency_req = pm_qos_request(PM_QOS_CPU_DMA_LATENCY);
  	int i;
  	unsigned int interactivity_req;
-	struct timespec t;
 
  	if (data->needs_update) {
  		menu_update(drv, dev);
@@ -311,9 +310,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
  		return 0;
 
  	/* determine the expected residency time, round up */
-	t = ktime_to_timespec(tick_nohz_get_sleep_length());
-	data->next_timer_us =
-		t.tv_sec * USEC_PER_SEC + t.tv_nsec / NSEC_PER_USEC;
+	data->next_timer_us = ktime_to_us(tick_nohz_get_sleep_length());
 
 
  	data->bucket = which_bucket(data->next_timer_us);
Signature · 5 lines
 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
author reviewer
#4 lore raw

PATCH 3/4 cpuidle: menu: Call nr_iowait_cpu less times

In reply to Mel Gorman

menu_select() via inline functions calls nr_iowait_cpu() twice as much as necessary.

---
 drivers/cpuidle/governors/menu.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)
drivers/cpuidle/governors/menu.c +8 -7
index 373278a..90d8109 100644
@@ -143,7 +143,7 @@ static int get_loadavg(void)
 	return LOAD_INT(this) * 10 + LOAD_FRAC(this) / 10;
 }
 
-static inline int which_bucket(unsigned int duration)
+static inline int which_bucket(unsigned int duration, unsigned long nr_iowaiters)
 {
 	int bucket = 0;
 
@@ -153,7 +153,7 @@ static inline int which_bucket(unsigned int duration)
 	 * This allows us to calculate
 	 * E(duration)|iowait
 	 */
-	if (nr_iowait_cpu(smp_processor_id()))
+	if (nr_iowaiters)
 		bucket = BUCKETS/2;
 
 	if (duration < 10)
@@ -176,7 +176,7 @@ static inline int which_bucket(unsigned int duration)
  * to be, the higher this multiplier, and thus the higher
  * the barrier to go to an expensive C state.
  */
-static inline int performance_multiplier(void)
+static inline int performance_multiplier(unsigned long nr_iowaiters)
 {
 	int mult = 1;
 
@@ -185,7 +185,7 @@ static inline int performance_multiplier(void)
 	mult += 2 * get_loadavg();
 
 	/* for IO wait tasks (per cpu!) we add 5x each */
-	mult += 10 * nr_iowait_cpu(smp_processor_id());
+	mult += 10 * nr_iowaiters;
 
 	return mult;
 }
@@ -297,6 +297,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	int latency_req = pm_qos_request(PM_QOS_CPU_DMA_LATENCY);
 	int i;
 	unsigned int interactivity_req;
+	unsigned long nr_iowaiters;
 
 	if (data->needs_update) {
 		menu_update(drv, dev);
@@ -312,8 +313,8 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	/* determine the expected residency time, round up */
 	data->next_timer_us = ktime_to_us(tick_nohz_get_sleep_length());
 
-
-	data->bucket = which_bucket(data->next_timer_us);
+	nr_iowaiters = nr_iowait_cpu(smp_processor_id());
+	data->bucket = which_bucket(data->next_timer_us, nr_iowaiters);
 
 	/*
 	 * Force the result of multiplication to be 64 bits even if both
@@ -331,7 +332,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	 * duration / latency ratio. Adjust the latency limit if
 	 * necessary.
 	 */
-	interactivity_req = data->predicted_us / performance_multiplier();
+	interactivity_req = data->predicted_us / performance_multiplier(nr_iowaiters);
 	if (latency_req > interactivity_req)
 		latency_req = interactivity_req;
 
Signature · 1 line
1.8.4.5
author reviewer
#5 lore raw

PATCH 4/4 cpuidle: menu: Lookup CPU runqueues less

In reply to Mel Gorman

The menu governer makes separate lookups of the CPU runqueue to get load and number of IO waiters but it can be done with a single lookup.

---
 drivers/cpuidle/governors/menu.c | 17 +++++++----------
 include/linux/sched.h            |  3 +--
 kernel/sched/core.c              |  7 +++++++
 kernel/sched/proc.c              |  7 -------
 4 files changed, 15 insertions(+), 19 deletions(-)
drivers/cpuidle/governors/menu.c +7 -10
index 90d8109..fef0225 100644
@@ -135,12 +135,9 @@ struct menu_device {
 #define LOAD_INT(x) ((x) >> FSHIFT)
 #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
 
-static int get_loadavg(void)
+static inline int get_loadavg(unsigned long load)
 {
-	unsigned long this = this_cpu_load();
-
-
-	return LOAD_INT(this) * 10 + LOAD_FRAC(this) / 10;
+	return LOAD_INT(load) * 10 + LOAD_FRAC(load) / 10;
 }
 
 static inline int which_bucket(unsigned int duration, unsigned long nr_iowaiters)
@@ -176,13 +173,13 @@ static inline int which_bucket(unsigned int duration, unsigned long nr_iowaiters
  * to be, the higher this multiplier, and thus the higher
  * the barrier to go to an expensive C state.
  */
-static inline int performance_multiplier(unsigned long nr_iowaiters)
+static inline int performance_multiplier(unsigned long nr_iowaiters, unsigned long load)
 {
 	int mult = 1;
 
 	/* for higher loadavg, we are more reluctant */
 
-	mult += 2 * get_loadavg();
+	mult += 2 * get_loadavg(load);
 
 	/* for IO wait tasks (per cpu!) we add 5x each */
 	mult += 10 * nr_iowaiters;
@@ -297,7 +294,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	int latency_req = pm_qos_request(PM_QOS_CPU_DMA_LATENCY);
 	int i;
 	unsigned int interactivity_req;
-	unsigned long nr_iowaiters;
+	unsigned long nr_iowaiters, cpu_load;
 
 	if (data->needs_update) {
 		menu_update(drv, dev);
@@ -313,7 +310,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	/* determine the expected residency time, round up */
 	data->next_timer_us = ktime_to_us(tick_nohz_get_sleep_length());
 
-	nr_iowaiters = nr_iowait_cpu(smp_processor_id());
+	get_iowait_load(&nr_iowaiters, &cpu_load);
 	data->bucket = which_bucket(data->next_timer_us, nr_iowaiters);
 
 	/*
@@ -332,7 +329,7 @@ static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev)
 	 * duration / latency ratio. Adjust the latency limit if
 	 * necessary.
 	 */
-	interactivity_req = data->predicted_us / performance_multiplier(nr_iowaiters);
+	interactivity_req = data->predicted_us / performance_multiplier(nr_iowaiters, cpu_load);
 	if (latency_req > interactivity_req)
 		latency_req = interactivity_req;
 
include/linux/sched.h +1 -2
index 0376b05..a696d48 100644
@@ -168,8 +168,7 @@ extern int nr_processes(void);
 extern unsigned long nr_running(void);
 extern unsigned long nr_iowait(void);
 extern unsigned long nr_iowait_cpu(int cpu);
-extern unsigned long this_cpu_load(void);
-
+extern void get_iowait_load(unsigned long *nr_waiters, unsigned long *load);
 
 extern void calc_global_load(unsigned long ticks);
 extern void update_cpu_load_nohz(void);
kernel/sched/core.c +7 -0
index bc1638b..cfbbbf3 100644
@@ -2385,6 +2385,13 @@ unsigned long nr_iowait_cpu(int cpu)
 	return atomic_read(&this->nr_iowait);
 }
 
+void get_iowait_load(unsigned long *nr_waiters, unsigned long *load)
+{
+	struct rq *this = this_rq();
+	*nr_waiters = atomic_read(&this->nr_iowait);
+	*load = this->cpu_load[0];
+}
+
 #ifdef CONFIG_SMP
 
 /*
kernel/sched/proc.c +0 -7
index 16f5a30..8ecd552 100644
@@ -8,13 +8,6 @@
 
 #include "sched.h"
 
-unsigned long this_cpu_load(void)
-{
-	struct rq *this = this_rq();
-	return this->cpu_load[0];
-}
-
-
 /*
  * Global load-average calculations
  *
Signature · 1 line
1.8.4.5
#6 lore raw
In reply to Mel Gorman
Quoted 10 lines · Mel Gorman

The menu_select function is heavy and is very noticable in profiles for workloads that enter/leave idle state a lot. This primarily happens for scheduler microbenchmarks. The biggest contibution is the standard deviation calculations and comparisons but the excessive calls into the scheduler core do not help.

It would be nice to reduce the number of times nr_iowait is checked to once per 8 intervals but I was not sure how to measure what the general impact of such a change could be.

Quoted 7 lines

Similiarly I looked at different ways the standard deviation could be calculated but the standard equivalent calculations potentially overflow. It could be done as rolling average and rolling deviation but again it was unclear how that could be evaluated. Tips on how the goodness/badness of governor changes are evalated would be nice.

In the meantime, here are patches against some of the obvious stuff.

They look good, I'm going to apply them.

Rafael