[RFC][PATCH]: sched/fair: search a task from the tail of the queue

[RFC][PATCH]: sched/fair: search a task from the tail of the queue

[Uladzislau Rezki (Sony)]

Hi,

while doing a load balancing (plus active) if we change a direction
of task search we may benefit when it comes to performance. See below
results of running hackbench with following parameters: 1000 samples 40 groups

[1] ftp://vps418301.ovh.net/incoming/hackbench_40_groups_1000_samples_default_patched_i5-3320M.png

Uladzislau Rezki (1):
  sched/fair: search a task from the tail of the queue

 kernel/sched/fair.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

-- 
2.11.0

[RFC][PATCH]: sched/fair: search a task from the tail of the queue

[Uladzislau Rezki (Sony)]

From: Uladzislau Rezki <urezki@gmail.com>

When a task is enqueued back from a physical CPU to the running
list it is placed in the beginning of the queue. Thus, the cfs_tasks
list is more or less sorted (except woken tasks) starting from recently
given CPU time tasks toward tasks with max wait time in a run-queue.

As part of the load balance operation, this approach starts
detach_tasks()/detach_one_task() from the tail of the queue
instead of the head, giving some advantages:

- tends to pick a task with highest wait time;
- tasks located in the tail are less likely cache-hot,
  therefore the can_migrate_task() decision is higher.

hackbench illustrates slightly better performance. For example
doing 1000 samples and 40 groups on i5-3320M CPU, it shows below
figures:

default: 0.672 avg / 0.674 median
patched: 0.665 avg / 0.667 median

Signed-off-by: Uladzislau Rezki (Sony) <urezki@gmail.com>
---
 kernel/sched/fair.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c77e4b1d51c0..028f5e8bc830 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6806,11 +6806,12 @@ static void detach_task(struct task_struct *p, struct lb_env *env)
  */
 static struct task_struct *detach_one_task(struct lb_env *env)
 {
-	struct task_struct *p, *n;
+	struct task_struct *p;
 
 	lockdep_assert_held(&env->src_rq->lock);
 
-	list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) {
+	list_for_each_entry_reverse(p,
+			&env->src_rq->cfs_tasks, se.group_node) {
 		if (!can_migrate_task(p, env))
 			continue;
 
@@ -6856,7 +6857,7 @@ static int detach_tasks(struct lb_env *env)
 		if (env->idle != CPU_NOT_IDLE && env->src_rq->nr_running <= 1)
 			break;
 
-		p = list_first_entry(tasks, struct task_struct, se.group_node);
+		p = list_last_entry(tasks, struct task_struct, se.group_node);
 
 		env->loop++;
 		/* We've more or less seen every task there is, call it quits */
@@ -6906,7 +6907,7 @@ static int detach_tasks(struct lb_env *env)
 
 		continue;
 next:
-		list_move_tail(&p->se.group_node, tasks);
+		list_move(&p->se.group_node, tasks);
 	}
 
 	/*
-- 
2.11.0

Re: [RFC][PATCH]: sched/fair: search a task from the tail of the queue

[Peter Zijlstra]

On Thu, Aug 24, 2017 at 12:44:45PM +0200, Uladzislau Rezki (Sony) wrote:
> From: Uladzislau Rezki <urezki@gmail.com>
> 
> When a task is enqueued back from a physical CPU to the running
> list it is placed in the beginning of the queue. Thus, the cfs_tasks
> list is more or less sorted (except woken tasks) starting from recently
> given CPU time tasks toward tasks with max wait time in a run-queue.

Hurm... that is only true for short running tasks, the moment you get
things like involuntary preemption that's completely off.

Imagine starting 3 busy-spinning tasks, lets call then A, B and C.

So our cfs_tasks list is ordered: C B A, since C is the last task we
started.

At this point, C might also be the leftmost task, since it has ran
least. But the moment we let A run its full quantum it will become the
rightmost and we'll pick C. Let C run its full quantum and that becomes
the rightmost.

So now we have, in our tree: B A C, while our list is still C B A. No
relation left what so ever.

How, hackbench will be very short running tasks, so the list tends to be
better ordered vs the tree.

That said, functionally it really doesn't matter what way around the
list we iterate for migration, so if this is a win for some, that's
nice. But it would be nice to get more benchmarks ran to see if there is
cases where it hurts.

Another thing you could play with is making pick_next_task_fair() move
the selected task to the front of the list. That way the list becomes a
MRU and picking from the tail always makes sense.

Re: [RFC][PATCH]: sched/fair: search a task from the tail of the queue

[Uladzislau Rezki]

On Thu, Aug 24, 2017 at 7:46 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Thu, Aug 24, 2017 at 12:44:45PM +0200, Uladzislau Rezki (Sony) wrote:
> > From: Uladzislau Rezki <urezki@gmail.com>
> >
> > When a task is enqueued back from a physical CPU to the running
> > list it is placed in the beginning of the queue. Thus, the cfs_tasks
> > list is more or less sorted (except woken tasks) starting from recently
> > given CPU time tasks toward tasks with max wait time in a run-queue.
>
> Hurm... that is only true for short running tasks, the moment you get
> things like involuntary preemption that's completely off.
>
> Imagine starting 3 busy-spinning tasks, lets call then A, B and C.
>
> So our cfs_tasks list is ordered: C B A, since C is the last task we
> started.
>
> At this point, C might also be the leftmost task, since it has ran
> least. But the moment we let A run its full quantum it will become the
> rightmost and we'll pick C. Let C run its full quantum and that becomes
> the rightmost.
>
> So now we have, in our tree: B A C, while our list is still C B A. No
> relation left what so ever.
>
I totally agree with your point and explanation.

> How, hackbench will be very short running tasks, so the list tends to be
> better ordered vs the tree.
>
> That said, functionally it really doesn't matter what way around the
> list we iterate for migration, so if this is a win for some, that's
> nice. But it would be nice to get more benchmarks ran to see if there is
> cases where it hurts.

>
> Another thing you could play with is making pick_next_task_fair() move
> the selected task to the front of the list. That way the list becomes a
> MRU and picking from the tail always makes sense.
>
Apparently, briefly looking at account_entity_enqueue function and not paying
much attention, i thought that the list is updated each time when a
task is moved
from/to rb tree, but that is not true. Thank you for your point!

I have uploaded a new patch set here: https://lkml.org/lkml/2017/8/24/860

--
Vlad Rezki