Reduce overhead of menu governor
Subsystems (2)
Mel Gorman
reviewercover 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
Mel Gorman
reviewerPATCH 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
@@ -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
Mel Gorman
reviewerPATCH 2/4 cpuidle: menu: Use ktime_to_us instead of reinventing the wheel
In reply to Mel GormanThe 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
@@ -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
Re: [PATCH 2/4] cpuidle: menu: Use ktime_to_us instead of reinventing the wheel
Quoted 4 lines · Mel Gorman
The
ktime_to_usimplementation is slightly better than the one implemented inmenu.c. Use itSigned-off-by Mel Gorman <[email protected]>
Quoted 28 lines
--- drivers/cpuidle/governors/menu.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)drivers/cpuidle/governors/menu.c +1
-4@@ -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
Mel Gorman
reviewerPATCH 3/4 cpuidle: menu: Call nr_iowait_cpu less times
In reply to Mel Gormanmenu_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
@@ -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
Mel Gorman
reviewerPATCH 4/4 cpuidle: menu: Lookup CPU runqueues less
In reply to Mel GormanThe 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
@@ -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
@@ -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
@@ -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
@@ -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
Quoted 10 lines · Mel Gorman
The
menu_selectfunction 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_iowaitis 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