: sched/fair: search a task from the tail of the queue

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

From: Uladzislau Rezki <[email protected]>

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

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

index c77e4b1d51c0..028f5e8bc830 100644
@@ -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

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.

I totally agree with your point and explanation.

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