sched/fair: Reorder scheduling related structs to reduce cache misses
cover sched/fair: Reorder scheduling related structs to reduce cache misses
Reorder the fields within the struct cfs_rq and struct sched_entity to improve cache locality. This can reduce cache misses to improve performance in CFS scheduling-related operations, particularly for servers with hundreds of cores and ~1000 cgroups.
The reordering is based on the kernel data-type profiling
(https://lwn.net/Articles/955709/) indicating hot fields and fields that frequently accessed together.
This reordering aims to optimize cache utilization and improve the performance of scheduling-related functions, particularly tg_throttle_down, tg_unthrottle_up, and __update_load_avg_cfs_rq. The reordering mainly considers performance when CONFIG_FAIR_GROUP_SCHED is configured. When it is disabled, there is no CFS bandwidth control and only a single cfs_rq exists per CPU, thus its layout would not significantly impact performance.
We use a benchmark with multiple cgroup levels to simulate real server load. The benchmark constructs a tree structure hierarchy of cgroups, with “width” and “depth” parameters controlling the number of children per node and the depth of the tree. Each leaf cgroup runs a schbench workload and gets an 80% quota of the total CPU quota divided by number of leaf cgroups (in other words, the target CPU load is set to 80%) to exercise the throttling functions. Bandwidth control period is set to 10ms. We run the benchmark on Intel and AMD machines; each machine has hundreds of threads.
Kernel LLC load misses for 30 seconds. d3 w10 (wider tree) means a cgroup hierarchy of 3 levels, each level has 10 children, totaling 1000 leaf cgroups. d5 w4 represents a deeper tree with more hierarchies. Each benchmark is run 10 times, the table shows 95% confidence intervals of the kernel LLC misses in millions.
| Kernel LLC Misses | d3 w10 | d5 w4 | +-------------------+-------------------+-------------------+ | AMD-orig | [3025.5, 3344.1]M | [3382.4, 3607.8]M | | AMD-opt | [2410.7, 2556.9]M | [2565.4, 2931.2]M | | Change | -22.01% | -21.37% | | Intel-orig | [1157.2, 1249.0]M | [1343.7, 1630.7]M | | Intel-opt | [960.2, 1023.0]M | [1092.7, 1350.7]M | | Change | -17.59% | -17.86% |
Since the benchmark limits CPU quota, the RPS results reported by schbench did not show statistically significant improvement as it does not reflect the kernel overhead reduction.
Perf data shows the reduction of LLC misses percentage within the kernel for the depth 5, width 4 workload. The symbols are taken from the union of top 10 symbols in both original and optimized profiles.
| Symbol | Intel-orig | Intel-opt | +---------------------------------------+------------+-----------+ | worker_thread | 75.41% | 78.95% | | tg_unthrottle_up | 3.21% | 1.61% | | tg_throttle_down | 2.42% | 1.77% | | __update_load_avg_cfs_rq | 1.95% | 1.60% | | walk_tg_tree_from | 1.23% | 0.91% | | sched_balance_update_blocked_averages | 1.09% | 1.13% | | sched_balance_rq | 1.03% | 1.08% | | _raw_spin_lock | 1.01% | 1.23% | | task_mm_cid_work | 0.87% | 1.09% | | __update_load_avg_se | 0.78% | 0.48% |
| Symbol | AMD-orig | AMD-opt | +---------------------------------------+----------+---------+ | worker_thread | 53.97% | 61.49% | | sched_balance_update_blocked_averages | 3.94% | 2.48% | | __update_load_avg_cfs_rq | 3.52% | 2.62% | | update_load_avg | 2.66% | 2.19% | | tg_throttle_down | 1.99% | 1.57% | | tg_unthrottle_up | 1.98% | 1.34% | | __update_load_avg_se | 1.89% | 1.32% | | walk_tg_tree_from | 1.79% | 1.37% | | sched_clock_noinstr | 1.59% | 1.01% | | sched_balance_rq | 1.53% | 1.26% | | _raw_spin_lock | 1.47% | 1.41% | | task_mm_cid_work | 1.34% | 1.42% |
The percentage of the LLC misses in the system is reduced.
Zecheng Li (2):
sched/fair: Reorder struct cfs_rq
sched/fair: Reorder struct sched_entity
include/linux/sched.h | 37 +++++++++++--------- kernel/sched/core.c | 81 ++++++++++++++++++++++++++++++++++++++++++- kernel/sched/sched.h | 70 +++++++++++++++++++++++-------------- 3 files changed, 144 insertions(+), 44 deletions(-)
base-commit: 38fec10eb60d687e30c8c6b5420d86e8149f7557
Signature · 1 line
2.49.0
RFC PATCH 1/2 sched/fair: Reorder struct cfs_rq
Hot fields are moved to the first two cache lines. The first cache line is considered to be the hottest, and the second one is slightly cooler. With all related CONFIG enabled, it also moves fields originally located around the 4th and 5th cache line offsets to provide better locality when executing CFS bandwidth control functions. Due to the removal of holes in the struct, its size is observed to reduce by one cacheline in an x86 system.
The following changes are proposed:
- Move curr, rq, tg, throttle_count, and runtime_enabled to the first cache line as they are frequently accessed (and mostly read). They are pointers to the closely related structs (rq, tg) or checked as a condition (curr, throttle_count and runtime_enabled).
- propagate and idle, two frequently read fields, were placed in separate cache lines. Group them in cache line 2 with the remaining fields previously in cache line 1 to fill the hole.
- on_list is often accessed together with throttle_clock_* in tg_unthrottle_up and tg_throttle_down functions. Move runtime_remaining and throttled_pelt_idle, which are less frequently accessed, to the previous cache line to allow grouping on_list and throttle-related fields together.
- Use __cacheline_group_* macros to delineate logically grouped fields for cache alignment, with compile-time checks added in cfs_rq_struct_check.
--- kernel/sched/core.c | 61 +++++++++++++++++++++++++++++++++++++- kernel/sched/sched.h | 70 ++++++++++++++++++++++++++++---------------- 2 files changed, 104 insertions(+), 27 deletions(-)
kernel/sched/core.c +60 -1
@@ -8473,6 +8473,8 @@ LIST_HEAD(task_groups);static struct kmem_cache *task_group_cache__ro_after_init ;#endif +static void __init cfs_rq_struct_check (void ); +void __init sched_init (void ) {unsigned long ptr =0 ;
@@ -8489,7 +8491,7 @@ void __init sched_init(void)BUG_ON (!sched_class_above (&fair_sched_class, &ext_sched_class));BUG_ON (!sched_class_above (&ext_sched_class, &idle_sched_class));#endif - +cfs_rq_struct_check ();wait_bit_init ();#ifdef CONFIG_FAIR_GROUP_SCHED
@@ -10696,3 +10698,60 @@ void sched_enq_and_set_task(struct sched_enq_and_set_ctx *ctx)set_next_task (rq, ctx->p); }#endif /* CONFIG_SCHED_CLASS_EXT */ + +static void __init cfs_rq_struct_check (void ) +{ +/* +* The first two cache lines are hot and mostly read +* except load.inv_weight +*/ + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, load); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, nr_queued); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, h_nr_queued); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, h_nr_runnable); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, h_nr_idle); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, curr); + +#ifdef CONFIG_FAIR_GROUP_SCHED + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, rq); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, tg); + +#ifdef CONFIG_CFS_BANDWIDTH + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, throttle_count); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, runtime_enabled); +#endif + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, idle); + +#ifdef CONFIG_SMP + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, propagate); +#endif +#endif + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, avg_vruntime); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, avg_load); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, min_vruntime); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, tasks_timeline); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, hot, next); + +/* +* This cache line groups hot fields of the throttling functions. +* This group is enabled when CFS_BANDWIDTH is configured. +*/ +#ifdef CONFIG_CFS_BANDWIDTH +#ifdef CONFIG_FAIR_GROUP_SCHED + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, throttled); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, on_list); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, + leaf_cfs_rq_list); + + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, throttled_clock); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, + throttled_clock_pelt); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, + throttled_clock_pelt_time); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, + throttled_clock_self); + CACHELINE_ASSERT_GROUP_MEMBER(struct cfs_rq, throttle, + throttled_clock_self_time); +#endif +#endif +}
kernel/sched/sched.h +44 -26
118 lines not on this page · raw message
Signature · 1 line
2.49.0
RFC PATCH 2/2 sched/fair: Reorder struct sched_entity
In reply to Zecheng LiGroup the mostly read fields in struct sched_entity to the first cacheline when CONFIG_FAIR_GROUP_SCHED is set. This moves the additional fields from CONFIG_FAIR_GROUP_SCHED to the first cache line since they are mostly accessed and generally read most. Currently these fields related to cfs cgroup scheduling is placed on a separate cacheline from hot fields load, on_rq and vruntime. Although depth is not as hot as other fields, we keep it here to avoid breaking the #ifdef boundaries.
Also adds a compile time check when CONFIG_FAIR_GROUP_SCHED is set to check the placement of the hot fields.
--- include/linux/sched.h | 37 ++++++++++++++++++++----------------- kernel/sched/core.c | 20 ++++++++++++++++++++ 2 files changed, 40 insertions(+), 17 deletions(-)
include/linux/sched.h +20 -17
@@ -545,40 +545,43 @@ struct sched_statistics { }____cacheline_aligned ;struct sched_entity { +#ifdef CONFIG_FAIR_GROUP_SCHED +/* Group the read most hot fields in sched_entity in a cache line */ +__cacheline_group_begin_aligned (hot); +struct sched_entity *parent; +/* rq on which this entity is (to be) queued: */ +struct cfs_rq *cfs_rq; +/* rq "owned" by this entity/group: */ +struct cfs_rq *my_q; +/* cached value of my_q->h_nr_running */ +unsigned long runnable_weight; +int depth; +#endif +unsigned char on_rq; +unsigned char sched_delayed; +unsigned char rel_deadline; +unsigned char custom_slice;/* For load-balancing: */ struct load_weight load; +u64 vruntime; +#ifdef CONFIG_FAIR_GROUP_SCHED +__cacheline_group_end_aligned (hot); +#endif struct rb_node run_node;u64 deadline;u64 min_vruntime;u64 min_slice;struct list_head group_node; -unsigned char on_rq; -unsigned char sched_delayed; -unsigned char rel_deadline; -unsigned char custom_slice; -/* hole */ u64 exec_start;u64 sum_exec_runtime;u64 prev_sum_exec_runtime; -u64 vruntime;s64 vlag;u64 slice;u64 nr_migrations; -#ifdef CONFIG_FAIR_GROUP_SCHED -int depth; -struct sched_entity *parent; -/* rq on which this entity is (to be) queued: */ -struct cfs_rq *cfs_rq; -/* rq "owned" by this entity/group: */ -struct cfs_rq *my_q; -/* cached value of my_q->h_nr_running */ -unsigned long runnable_weight; -#endif -#ifdef CONFIG_SMP /* * Per entity load average tracking.
kernel/sched/core.c +20 -0
@@ -8474,6 +8474,7 @@ static struct kmem_cache *task_group_cache __ro_after_init;#endif static void __init cfs_rq_struct_check (void ); +static void __init sched_entity_struct_check (void );void __init sched_init (void ) {
@@ -8492,6 +8493,7 @@ void __init sched_init(void)BUG_ON (!sched_class_above (&ext_sched_class, &idle_sched_class));#endif cfs_rq_struct_check (); +sched_entity_struct_check ();wait_bit_init ();#ifdef CONFIG_FAIR_GROUP_SCHED
@@ -10755,3 +10757,21 @@ static void __init cfs_rq_struct_check(void)#endif #endif } + +static void __init sched_entity_struct_check (void ) +{ +/* +* The compile time check is only enabled with CONFIG_FAIR_GROUP_SCHED. +* We care about the placement of six hottest fields below. +*/ +#ifdef CONFIG_FAIR_GROUP_SCHED + CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, parent); + CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, cfs_rq); + CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, my_q); + CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, + runnable_weight); + CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, on_rq); + CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, load); + CACHELINE_ASSERT_GROUP_MEMBER(struct sched_entity, hot, vruntime); +#endif +}
Signature · 1 line
2.49.0
Hi Zecheng Li,
Quoted 8 lines · Zecheng Li
Reorder the fields within the
struct cfs_rqandstruct sched_entityto improve cache locality. This can reduce cache misses to improve performance in CFS scheduling-related operations, particularly for servers with hundreds of cores and ~1000 cgroups.The reordering is based on the kernel data-type profiling
(https://lwn.net/Articles/955709/) indicating hot fields and fields that frequently accessed together.
This patch is based on optimizations by reordering for 64 byte systems. In case of 128 byte L1 D-cache systems like Power10, this might or might not be beneficial. Moreover lot of space(almost half) would be wasted on the cache line due to APIs like __cacheline_group_begin_aligned and __cacheline_group_end_aligned that may restrict size to 64 bytes.
Since this is in generic code, any ideas on how to make sure that other architectures with different cache size don't suffer?
[..snip..]
Quoted 47 lines
| Kernel LLC Misses | d3 w10 | d5 w4 | +-------------------+-------------------+-------------------+ | AMD-orig | [3025.5, 3344.1]M | [3382.4, 3607.8]M | | AMD-opt | [2410.7, 2556.9]M | [2565.4, 2931.2]M | | Change | -22.01% | -21.37% | | Intel-orig | [1157.2, 1249.0]M | [1343.7, 1630.7]M | | Intel-opt | [960.2, 1023.0]M | [1092.7, 1350.7]M | | Change | -17.59% | -17.86% |Since the benchmark limits CPU quota, the RPS results reported by
schbenchdid not show statistically significant improvement as it does not reflect the kernel overhead reduction.Perf data shows the reduction of LLC misses percentage within the kernel for the depth 5, width 4 workload. The symbols are taken from the union of top 10 symbols in both original and optimized profiles.
| Symbol | Intel-orig | Intel-opt | +---------------------------------------+------------+-----------+ | worker_thread | 75.41% | 78.95% | | tg_unthrottle_up | 3.21% | 1.61% | | tg_throttle_down | 2.42% | 1.77% | | __update_load_avg_cfs_rq | 1.95% | 1.60% | | walk_tg_tree_from | 1.23% | 0.91% | | sched_balance_update_blocked_averages | 1.09% | 1.13% | | sched_balance_rq | 1.03% | 1.08% | | _raw_spin_lock | 1.01% | 1.23% | | task_mm_cid_work | 0.87% | 1.09% | | __update_load_avg_se | 0.78% | 0.48% || Symbol | AMD-orig | AMD-opt | +---------------------------------------+----------+---------+ | worker_thread | 53.97% | 61.49% | | sched_balance_update_blocked_averages | 3.94% | 2.48% | | __update_load_avg_cfs_rq | 3.52% | 2.62% | | update_load_avg | 2.66% | 2.19% | | tg_throttle_down | 1.99% | 1.57% | | tg_unthrottle_up | 1.98% | 1.34% | | __update_load_avg_se | 1.89% | 1.32% | | walk_tg_tree_from | 1.79% | 1.37% | | sched_clock_noinstr | 1.59% | 1.01% | | sched_balance_rq | 1.53% | 1.26% | | _raw_spin_lock | 1.47% | 1.41% | | task_mm_cid_work | 1.34% | 1.42% |
Quoted 1 line
The percentage of the LLC misses in the system is reduced.
Due to the reordering of the fields, there might be some workloads that could take a hit. May be try running workloads of different kinds(latency and throughput oriented) and make sure that regression is not high.
Thanks,
Madadi Vineeth Reddy
Quoted 12 lines
Zecheng Li (2):
sched/fair: Reorder structcfs_rq
sched/fair: Reorder structsched_entityinclude/linux/sched.h | 37 +++++++++++--------- kernel/sched/core.c | 81 ++++++++++++++++++++++++++++++++++++++++++- kernel/sched/sched.h | 70 +++++++++++++++++++++++-------------- 3 files changed, 144 insertions(+), 44 deletions(-)base-commit:
38fec10eb60d687e30c8c6b5420d86e8149f7557
Hi Madadi Vineeth Reddy,
Quoted 8 lines
This patch is based on optimizations by reordering for 64 byte systems. In case of 128 byte L1 D-cache systems like Power10, this might or might not be beneficial. Moreover lot of space(almost half) would be wasted on the cache line due to APIs like
__cacheline_group_begin_alignedand__cacheline_group_end_alignedthat may restrict size to 64 bytes.Since this is in generic code, any ideas on how to make sure that other architectures with different cache size don't suffer?
We propose to conditionally align to the cacheline boundary only when the cacheline size is 64 bytes, since this is the most common size.
For architectures with 128-byte cachelines (like PowerPC), this approach will still collocate the hot fields, providing some performance benefit from improved locality, but it will not enforce alignment to the larger 128-byte boundary. This avoids wasting cache space on those architectures due to padding introduced by the alignment, while still gaining benefits from collocating frequently accessed fields.
Quoted 4 lines
Due to the reordering of the fields, there might be some workloads that could take a hit. May be try running workloads of different kinds(latency and throughput oriented) and make sure that regression is not high.
For workloads running without a cgroup hierarchy, we expect a small performance impact. This is because there is only one cfs_rq per CPU in this scenario, which is likely in cache due to frequent access.
For workloads with the cgroup hierarchy, I have tested sysbench threads and hackbench --thread, there are no obvious regression.
Heavy load on 1024 instances of sysbench:
Latency (ms), after-patch, origial
avg avg: 2133.51, 2150.97
avg min: 21.9629, 20.9413
avg max: 5955.8, 5966.78
Avg runtime for 1024 instances of ./hackbench --thread -g 2 -l 1000 in a cgroup hierarchy:
After-patch: 34.9458s, Original: 36.8647s
We plan to include more benchmark results in the v2 patch. Do you have suggestions for other benchmarks you would like us to test?
Regards,
Zecheng
Quoted 11 lines · ZECHENG LI
Hi Madadi Vineeth Reddy,
Quoted 8 lines
This patch is based on optimizations by reordering for 64 byte systems. In case of 128 byte L1 D-cache systems like Power10, this might or might not be beneficial. Moreover lot of space(almost half) would be wasted on the cache line due to APIs like
__cacheline_group_begin_alignedand__cacheline_group_end_alignedthat may restrict size to 64 bytes.Since this is in generic code, any ideas on how to make sure that other architectures with different cache size don't suffer?
Quoted 7 lines
We propose to conditionally align to the cacheline boundary only when the cacheline size is 64 bytes, since this is the most common size.
For architectures with 128-byte cachelines (like PowerPC), this approach will still collocate the hot fields, providing some performance benefit from improved locality, but it will not enforce alignment to the larger 128-byte boundary. This avoids wasting cache
I don't see the check to enforce the alignment only for 64 bytes. IIUC, the macros seem to apply the alignment unconditionally based on arch specific cacheline size. I might be missing something, could you clarify this?
Quoted 22 lines
space on those architectures due to padding introduced by the alignment, while still gaining benefits from collocating frequently accessed fields.
Quoted 4 lines
Due to the reordering of the fields, there might be some workloads that could take a hit. May be try running workloads of different kinds(latency and throughput oriented) and make sure that regression is not high.
For workloads running without a cgroup hierarchy, we expect a small performance impact. This is because there is only one
cfs_rqper CPU in this scenario, which is likely in cache due to frequent access.For workloads with the cgroup hierarchy, I have tested sysbench threads and hackbench --thread, there are no obvious regression.
Heavy load on 1024 instances of sysbench:
Latency (ms), after-patch, origial
avg avg: 2133.51, 2150.97
avg min: 21.9629, 20.9413
avg max: 5955.8, 5966.78
Quoted 6 lines
Avg runtime for 1024 instances of ./hackbench --thread -g 2 -l 1000 in a cgroup hierarchy:
After-patch: 34.9458s, Original: 36.8647sWe plan to include more benchmark results in the v2 patch. Do you have suggestions for other benchmarks you would like us to test?
May be some throughput oriented workloads like ebizzy, sysbench and also some real life workloads would be good to include.
Thanks,
Madadi Vineeth Reddy
Quoted 3 lines
Regards,
Zecheng