These two patches optimize the process of scanning the CPU by
adjusting the search order or breaking the loop.
Hao Jia (2):
sched/numa: Stop an exhastive search if an idle core is found
sched/core: Optimize the order of scanning CPU
kernel/sched/core.c | 2 +-
kernel/sched/fair.c | 12 ++++++------
2 files changed, 7 insertions(+), 7 deletions(-)
--
2.37.0
When select_idle_capacity() starts scanning for an idle CPU, it starts
with target CPU that has already been checked in select_idle_sibling().
So, we finally try the target CPU. Similarly for task_numa_assign(),
we have just checked numa_migrate_on of dst_cpu, so start from the
next CPU. This also works for steal_cookie_task(), the first scan
must fail and start directly from the next one.
Signed-off-by: Hao Jia <[email protected]>
---
kernel/sched/core.c | 2 +-
kernel/sched/fair.c | 4 ++--
2 files changed, 3 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 5800b0623ff3..f6ad68714546 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6154,7 +6154,7 @@ static bool steal_cookie_task(int cpu, struct sched_domain *sd)
{
int i;
- for_each_cpu_wrap(i, sched_domain_span(sd), cpu) {
+ for_each_cpu_wrap(i, sched_domain_span(sd), cpu + 1) {
if (i == cpu)
continue;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index b7cbec539c77..d95ee285734e 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1824,7 +1824,7 @@ static void task_numa_assign(struct task_numa_env *env,
int start = env->dst_cpu;
/* Find alternative idle CPU. */
- for_each_cpu_wrap(cpu, cpumask_of_node(env->dst_nid), start) {
+ for_each_cpu_wrap(cpu, cpumask_of_node(env->dst_nid), start + 1) {
if (cpu == env->best_cpu || !idle_cpu(cpu) ||
!cpumask_test_cpu(cpu, env->p->cpus_ptr)) {
continue;
@@ -6663,7 +6663,7 @@ select_idle_capacity(struct task_struct *p, struct sched_domain *sd, int target)
task_util = uclamp_task_util(p);
- for_each_cpu_wrap(cpu, cpus, target) {
+ for_each_cpu_wrap(cpu, cpus, target + 1) {
unsigned long cpu_cap = capacity_of(cpu);
if (!available_idle_cpu(cpu) && !sched_idle_cpu(cpu))
--
2.37.0
In update_numa_stats() we try to find an idle cpu on the NUMA node,
preferably an idle core. When we find an idle core,
we can stop searching.
Signed-off-by: Hao Jia <[email protected]>
---
kernel/sched/fair.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e4a0b8bd941c..b7cbec539c77 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env *env,
ns->nr_running += rq->cfs.h_nr_running;
ns->compute_capacity += capacity_of(cpu);
- if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
+ if (find_idle && idle_core < 0 && !rq->nr_running && idle_cpu(cpu)) {
if (READ_ONCE(rq->numa_migrate_on) ||
!cpumask_test_cpu(cpu, env->p->cpus_ptr))
continue;
@@ -1801,6 +1801,9 @@ static void update_numa_stats(struct task_numa_env *env,
ns->idle_cpu = cpu;
idle_core = numa_idle_core(idle_core, cpu);
+ /* If we find an idle core, stop searching. */
+ if (idle_core >= 0)
+ ns->idle_cpu = idle_core;
}
}
rcu_read_unlock();
@@ -1808,9 +1811,6 @@ static void update_numa_stats(struct task_numa_env *env,
ns->weight = cpumask_weight(cpumask_of_node(nid));
ns->node_type = numa_classify(env->imbalance_pct, ns);
-
- if (idle_core >= 0)
- ns->idle_cpu = idle_core;
}
static void task_numa_assign(struct task_numa_env *env,
--
2.37.0
On Fri, Oct 21, 2022 at 02:15:56PM +0800, Hao Jia wrote:
> These two patches optimize the process of scanning the CPU by
> adjusting the search order or breaking the loop.
Is it really optimization, as in it now runs measurably faster, or just
cleanups?
On 2022/10/24 Peter Zijlstra wrote:
> On Fri, Oct 21, 2022 at 02:15:56PM +0800, Hao Jia wrote:
>> These two patches optimize the process of scanning the CPU by
>> adjusting the search order or breaking the loop.
>
> Is it really optimization, as in it now runs measurably faster, or just
> cleanups?
I'm very sorry that my description confused you.
Yes, these two patches should just be cleanups.
Reduce the number of attempts by adjusting the scan order or breaking
the loop in time.
Just from code analysis, it will lead to a little optimization in most
cases.
But they won't bring significant performance gains. So, it's just cleanups.
Thanks,
Hao
On Fri, Oct 21, 2022 at 02:15:57PM +0800, Hao Jia wrote:
> In update_numa_stats() we try to find an idle cpu on the NUMA node,
> preferably an idle core. When we find an idle core,
> we can stop searching.
>
> Signed-off-by: Hao Jia <[email protected]>
> ---
> kernel/sched/fair.c | 8 ++++----
> 1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e4a0b8bd941c..b7cbec539c77 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env *env,
> ns->nr_running += rq->cfs.h_nr_running;
> ns->compute_capacity += capacity_of(cpu);
>
> - if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
> + if (find_idle && idle_core < 0 && !rq->nr_running && idle_cpu(cpu)) {
> if (READ_ONCE(rq->numa_migrate_on) ||
> !cpumask_test_cpu(cpu, env->p->cpus_ptr))
> continue;
> @@ -1801,6 +1801,9 @@ static void update_numa_stats(struct task_numa_env *env,
> ns->idle_cpu = cpu;
>
> idle_core = numa_idle_core(idle_core, cpu);
> + /* If we find an idle core, stop searching. */
> + if (idle_core >= 0)
> + ns->idle_cpu = idle_core;
> }
> }
> rcu_read_unlock();
> @@ -1808,9 +1811,6 @@ static void update_numa_stats(struct task_numa_env *env,
> ns->weight = cpumask_weight(cpumask_of_node(nid));
>
> ns->node_type = numa_classify(env->imbalance_pct, ns);
> -
> - if (idle_core >= 0)
> - ns->idle_cpu = idle_core;
> }
>
Remove the change in the first hunk and call break in the second hunk
after updating ns->idle_cpu.
--
Mel Gorman
SUSE Labs
On 2022/10/24 Peter Zijlstra wrote:
> On Fri, Oct 21, 2022 at 02:15:56PM +0800, Hao Jia wrote:
>> These two patches optimize the process of scanning the CPU by
>> adjusting the search order or breaking the loop.
>
> Is it really optimization, as in it now runs measurably faster, or just
> cleanups?
I'm very sorry that my description confused you.
Yes, these two patches should just be cleanups.
Reduce the number of attempts by adjusting the scan order or breaking
the loop in time.
IMHO, it will lead to a little optimization in most cases.
But they won't bring significant performance gains. So, it's just cleanups.
Thanks,
Hao
On 2022/10/24 Mel Gorman wrote:
> On Fri, Oct 21, 2022 at 02:15:57PM +0800, Hao Jia wrote:
>> In update_numa_stats() we try to find an idle cpu on the NUMA node,
>> preferably an idle core. When we find an idle core,
>> we can stop searching.
>>
>> Signed-off-by: Hao Jia <[email protected]>
>> ---
>> kernel/sched/fair.c | 8 ++++----
>> 1 file changed, 4 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index e4a0b8bd941c..b7cbec539c77 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env *env,
>> ns->nr_running += rq->cfs.h_nr_running;
>> ns->compute_capacity += capacity_of(cpu);
>>
>> - if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
>> + if (find_idle && idle_core < 0 && !rq->nr_running && idle_cpu(cpu)) {
>> if (READ_ONCE(rq->numa_migrate_on) ||
>> !cpumask_test_cpu(cpu, env->p->cpus_ptr))
>> continue;
>> @@ -1801,6 +1801,9 @@ static void update_numa_stats(struct task_numa_env *env,
>> ns->idle_cpu = cpu;
>>
>> idle_core = numa_idle_core(idle_core, cpu);
>> + /* If we find an idle core, stop searching. */
>> + if (idle_core >= 0)
>> + ns->idle_cpu = idle_core;
>> }
>> }
>> rcu_read_unlock();
>> @@ -1808,9 +1811,6 @@ static void update_numa_stats(struct task_numa_env *env,
>> ns->weight = cpumask_weight(cpumask_of_node(nid));
>>
>> ns->node_type = numa_classify(env->imbalance_pct, ns);
>> -
>> - if (idle_core >= 0)
>> - ns->idle_cpu = idle_core;
>> }
>>
>
> Remove the change in the first hunk and call break in the second hunk
> after updating ns->idle_cpu.
>
Yes, thanks for your review.
If I understand correctly, some things might look like this.
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e4a0b8bd941c..dfcb620bfe50 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env
*env,
ns->nr_running += rq->cfs.h_nr_running;
ns->compute_capacity += capacity_of(cpu);
- if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
+ if (find_idle && idle_core < 0 && !rq->nr_running &&
idle_cpu(cpu)) {
if (READ_ONCE(rq->numa_migrate_on) ||
!cpumask_test_cpu(cpu, env->p->cpus_ptr))
continue;
Thanks,
Hao
On Tue, Oct 25, 2022 at 11:16:29AM +0800, Hao Jia wrote:
> > Remove the change in the first hunk and call break in the second hunk
> > after updating ns->idle_cpu.
> >
>
> Yes, thanks for your review.
> If I understand correctly, some things might look like this.
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e4a0b8bd941c..dfcb620bfe50 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env
> *env,
> ns->nr_running += rq->cfs.h_nr_running;
> ns->compute_capacity += capacity_of(cpu);
>
> - if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
> + if (find_idle && idle_core < 0 && !rq->nr_running &&
> idle_cpu(cpu)) {
> if (READ_ONCE(rq->numa_migrate_on) ||
> !cpumask_test_cpu(cpu, env->p->cpus_ptr))
> continue;
>
I meant more like the below but today I wondered why did I not do this in
the first place? The answer is because it's wrong and broken in concept.
The full loop is needed to calculate approximate NUMA stats at a
point in time. For example, the src and dst nr_running is needed by
task_numa_find_cpu. The search for an idle CPU or core in update_numa_stats
is simply taking advantage of the fact we are scanning anyway to keep
track of an idle CPU or core to avoid a second search as per ff7db0bf24db
("sched/numa: Prefer using an idle CPU as a migration target instead of
comparing tasks")
The patch I had in mind is below but that said, for both your version and
my initial suggestion
Naked-by: Mel Gorman <[email protected]>
For the record, this is what I was suggesting initially because it's more
efficient but it's wrong, don't do it.
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e4a0b8bd941c..7f1f6a1736a5 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1800,7 +1800,12 @@ static void update_numa_stats(struct task_numa_env *env,
if (ns->idle_cpu == -1)
ns->idle_cpu = cpu;
+ /* If we find an idle core, stop searching. */
idle_core = numa_idle_core(idle_core, cpu);
+ if (idle_core >= 0) {
+ ns->idle_cpu = idle_core;
+ break;
+ }
}
}
rcu_read_unlock();
@@ -1808,9 +1813,6 @@ static void update_numa_stats(struct task_numa_env *env,
ns->weight = cpumask_weight(cpumask_of_node(nid));
ns->node_type = numa_classify(env->imbalance_pct, ns);
-
- if (idle_core >= 0)
- ns->idle_cpu = idle_core;
}
static void task_numa_assign(struct task_numa_env *env,
On 2022/10/25 Mel Gorman wrote:
> On Tue, Oct 25, 2022 at 11:16:29AM +0800, Hao Jia wrote:
>>> Remove the change in the first hunk and call break in the second hunk
>>> after updating ns->idle_cpu.
>>>
>>
>> Yes, thanks for your review.
>> If I understand correctly, some things might look like this.
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index e4a0b8bd941c..dfcb620bfe50 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env
>> *env,
>> ns->nr_running += rq->cfs.h_nr_running;
>> ns->compute_capacity += capacity_of(cpu);
>>
>> - if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
>> + if (find_idle && idle_core < 0 && !rq->nr_running &&
>> idle_cpu(cpu)) {
>> if (READ_ONCE(rq->numa_migrate_on) ||
>> !cpumask_test_cpu(cpu, env->p->cpus_ptr))
>> continue;
>>
>
> I meant more like the below but today I wondered why did I not do this in
> the first place? The answer is because it's wrong and broken in concept.
>
> The full loop is needed to calculate approximate NUMA stats at a
> point in time. For example, the src and dst nr_running is needed by
> task_numa_find_cpu. The search for an idle CPU or core in update_numa_stats
> is simply taking advantage of the fact we are scanning anyway to keep
> track of an idle CPU or core to avoid a second search as per ff7db0bf24db
> ("sched/numa: Prefer using an idle CPU as a migration target instead of
> comparing tasks")
>
> The patch I had in mind is below but that said, for both your version and
> my initial suggestion
>
> Naked-by: Mel Gorman <[email protected]>
>
> For the record, this is what I was suggesting initially because it's more
> efficient but it's wrong, don't do it.
>
Thanks for the detailed explanation, maybe my commit message misled you.
Yes, we can't stop the whole loop of scanning the CPU because we have a
lot of NUMA information to count.
But we can stop looking for the next idle core or idle cpu after finding
an idle core.
So, please review the previous code.
Thanks,
Hao
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e4a0b8bd941c..7f1f6a1736a5 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1800,7 +1800,12 @@ static void update_numa_stats(struct task_numa_env *env,
> if (ns->idle_cpu == -1)
> ns->idle_cpu = cpu;
>
> + /* If we find an idle core, stop searching. */
> idle_core = numa_idle_core(idle_core, cpu);
> + if (idle_core >= 0) {
> + ns->idle_cpu = idle_core;
> + break;
> + }
> }
> }
> rcu_read_unlock();
> @@ -1808,9 +1813,6 @@ static void update_numa_stats(struct task_numa_env *env,
> ns->weight = cpumask_weight(cpumask_of_node(nid));
>
> ns->node_type = numa_classify(env->imbalance_pct, ns);
> -
> - if (idle_core >= 0)
> - ns->idle_cpu = idle_core;
> }
>
> static void task_numa_assign(struct task_numa_env *env,
>
On Tue, Oct 25, 2022 at 07:10:22PM +0800, Hao Jia wrote:
> On 2022/10/25 Mel Gorman wrote:
> > On Tue, Oct 25, 2022 at 11:16:29AM +0800, Hao Jia wrote:
> > > > Remove the change in the first hunk and call break in the second hunk
> > > > after updating ns->idle_cpu.
> > > >
> > >
> > > Yes, thanks for your review.
> > > If I understand correctly, some things might look like this.
> > >
> > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > > index e4a0b8bd941c..dfcb620bfe50 100644
> > > --- a/kernel/sched/fair.c
> > > +++ b/kernel/sched/fair.c
> > > @@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env
> > > *env,
> > > ns->nr_running += rq->cfs.h_nr_running;
> > > ns->compute_capacity += capacity_of(cpu);
> > >
> > > - if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
> > > + if (find_idle && idle_core < 0 && !rq->nr_running &&
> > > idle_cpu(cpu)) {
> > > if (READ_ONCE(rq->numa_migrate_on) ||
> > > !cpumask_test_cpu(cpu, env->p->cpus_ptr))
> > > continue;
> > >
> >
> > I meant more like the below but today I wondered why did I not do this in
> > the first place? The answer is because it's wrong and broken in concept.
> >
> > The full loop is needed to calculate approximate NUMA stats at a
> > point in time. For example, the src and dst nr_running is needed by
> > task_numa_find_cpu. The search for an idle CPU or core in update_numa_stats
> > is simply taking advantage of the fact we are scanning anyway to keep
> > track of an idle CPU or core to avoid a second search as per ff7db0bf24db
> > ("sched/numa: Prefer using an idle CPU as a migration target instead of
> > comparing tasks")
> >
> > The patch I had in mind is below but that said, for both your version and
> > my initial suggestion
> >
> > Naked-by: Mel Gorman <[email protected]>
> >
> > For the record, this is what I was suggesting initially because it's more
> > efficient but it's wrong, don't do it.
> >
>
> Thanks for the detailed explanation, maybe my commit message misled you.
>
Yes, I did end up confusing myself. The title and changelog referred to
stopping a search which made me think of terms of "this whole loop can
terminate early" which it can't but it *can* stop checking for a new idle
core. If an idle core has been found, it follows that an idle CPU has also
been found. While numa_idle_core checks this explicitly, your patch avoids
an unnecessary cpumask_test_cpu so it has value.
> Yes, we can't stop the whole loop of scanning the CPU because we have a lot
> of NUMA information to count.
>
> But we can stop looking for the next idle core or idle cpu after finding an
> idle core.
>
> So, please review the previous code.
>
You're right and sorry for the noise.
Acked-by: Mel Gorman <[email protected]>
--
Mel Gorman
SUSE Labs
On 2022/10/25 Mel Gorman wrote:
> On Tue, Oct 25, 2022 at 07:10:22PM +0800, Hao Jia wrote:
>> On 2022/10/25 Mel Gorman wrote:
>>> On Tue, Oct 25, 2022 at 11:16:29AM +0800, Hao Jia wrote:
>>>>> Remove the change in the first hunk and call break in the second hunk
>>>>> after updating ns->idle_cpu.
>>>>>
>>>>
>>>> Yes, thanks for your review.
>>>> If I understand correctly, some things might look like this.
>>>>
>>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>>> index e4a0b8bd941c..dfcb620bfe50 100644
>>>> --- a/kernel/sched/fair.c
>>>> +++ b/kernel/sched/fair.c
>>>> @@ -1792,7 +1792,7 @@ static void update_numa_stats(struct task_numa_env
>>>> *env,
>>>> ns->nr_running += rq->cfs.h_nr_running;
>>>> ns->compute_capacity += capacity_of(cpu);
>>>>
>>>> - if (find_idle && !rq->nr_running && idle_cpu(cpu)) {
>>>> + if (find_idle && idle_core < 0 && !rq->nr_running &&
>>>> idle_cpu(cpu)) {
>>>> if (READ_ONCE(rq->numa_migrate_on) ||
>>>> !cpumask_test_cpu(cpu, env->p->cpus_ptr))
>>>> continue;
>>>>
>>>
>>> I meant more like the below but today I wondered why did I not do this in
>>> the first place? The answer is because it's wrong and broken in concept.
>>>
>>> The full loop is needed to calculate approximate NUMA stats at a
>>> point in time. For example, the src and dst nr_running is needed by
>>> task_numa_find_cpu. The search for an idle CPU or core in update_numa_stats
>>> is simply taking advantage of the fact we are scanning anyway to keep
>>> track of an idle CPU or core to avoid a second search as per ff7db0bf24db
>>> ("sched/numa: Prefer using an idle CPU as a migration target instead of
>>> comparing tasks")
>>>
>>> The patch I had in mind is below but that said, for both your version and
>>> my initial suggestion
>>>
>>> Naked-by: Mel Gorman <[email protected]>
>>>
>>> For the record, this is what I was suggesting initially because it's more
>>> efficient but it's wrong, don't do it.
>>>
>>
>> Thanks for the detailed explanation, maybe my commit message misled you.
>>
>
> Yes, I did end up confusing myself. The title and changelog referred to
> stopping a search which made me think of terms of "this whole loop can
> terminate early" which it can't but it *can* stop checking for a new idle
> core. If an idle core has been found, it follows that an idle CPU has also
> been found. While numa_idle_core checks this explicitly, your patch avoids
> an unnecessary cpumask_test_cpu so it has value.
>
Thank you for your review, I will change the commit message and send
patch v2.
>> Yes, we can't stop the whole loop of scanning the CPU because we have a lot
>> of NUMA information to count.
>>
>> But we can stop looking for the next idle core or idle cpu after finding an
>> idle core.
>>
>> So, please review the previous code.
>>
>
> You're right and sorry for the noise.
>
> Acked-by: Mel Gorman <[email protected]>
Thanks!
>
Thanks,
Hao