Skip to contentSkip to conversation

CFS-devel, performance improvements

announce dimm 2 participants 2 messages Sep 13, 2007 – Sep 14, 2007 Scheduler

lore
Share & tools
lore

dimm

author
#0 lore raw

and here's something a bit more intrusive.

The initial idea was to completely get rid of 'se->fair_key'. It's always equal to 'se->vruntime' for all runnable tasks but the 'current'. The exact key within the tree for the 'current' has to be known in order for __enqueue_entity() to work properly (if we just use 'vruntime', we may go a wrong way down the tree while looking for the correct position for a new element).
Sure, it's possible to cache the current's key in the 'cfs_rq' and add a few additional checks, but that's not very nice... so what if we don't keep the 'current' within the tree? :-)

The illustration is below. Some bits can be missed so far but a patched kernel boots/works (haven't done real regression tests yet... can say that the mail client is still working at this very moment :-).

There are 2 benefits:

(1) no more 'fair_key' ;
(2) entity_tick() is simpler/more effective : 'update_curr()' now vs. 'dequeue_entity() + enqueue_entity()' before.

anyway, consider it as mainly an illustration of idea so far.

---

include/linux/sched.h +0 -1
diff -upr linux-2.6.23-rc6/include/linux/sched.h linux-2.6.23-rc6-my/include/linux/sched.h
@@ -890,7 +890,6 @@ struct load_weight {
  *     6 se->load.weight
  */
 struct sched_entity {
-	s64			fair_key;
 	struct load_weight	load;		/* for load-balancing */
 	struct rb_node		run_node;
 	unsigned int		on_rq;
kernel/sched.c +0 -1
diff -upr linux-2.6.23-rc6/kernel/sched.c linux-2.6.23-rc6-my/kernel/sched.c
@@ -6534,7 +6534,6 @@ void normalize_rt_tasks(void)
 
 	read_lock_irq(&tasklist_lock);
 	do_each_thread(g, p) {
-		p->se.fair_key			= 0;
 		p->se.exec_start		= 0;
 #ifdef CONFIG_SCHEDSTATS
 		p->se.wait_start		= 0;
kernel/sched_debug.c +1 -1
diff -upr linux-2.6.23-rc6/kernel/sched_debug.c linux-2.6.23-rc6-my/kernel/sched_debug.c
@@ -38,7 +38,7 @@ print_task(struct seq_file *m, struct rq
 
 	SEQ_printf(m, "%15s %5d %15Ld %13Ld %5d ",
 		p->comm, p->pid,
-		(long long)p->se.fair_key,
+		(long long)p->se.vruntime,
 		(long long)(p->nvcsw + p->nivcsw),
 		p->prio);
 #ifdef CONFIG_SCHEDSTATS
kernel/sched_fair.c +33 -18

119 lines not on this page · raw message

---

#1 lore raw
Quoted 16 lines · dimm

and here's something a bit more intrusive.

The initial idea was to completely get rid of 'se->fair_key'. It's always equal to 'se->vruntime' for all runnable tasks but the 'current'. The exact key within the tree for the 'current' has to be known in order for __enqueue_entity() to work properly (if we just use 'vruntime', we may go a wrong way down the tree while looking for the correct position for a new element). Sure, it's possible to cache the current's key in the 'cfs_rq' and add a few additional checks, but that's not very nice... so what if we don't keep the 'current' within the tree? :-)

The illustration is below. Some bits can be missed so far but a patched kernel boots/works (haven't done real regression tests yet... can say that the mail client is still working at this very moment :-).

Quoted 5 lines

There are 2 benefits:

(1) no more 'fair_key' ;
(2) entity_tick() is simpler/more effective : 'update_curr()' now vs. 'dequeue_entity() + enqueue_entity()' before.

cool patch - i like it! It removes some code as well, besides shrinking struct task_struct with another 64-bit variable - so it's a nice speedup:

   text    data     bss     dec     hex filename
  34467    3466      24   37957    9445 sched.o.before
  34414    3466      24   37904    9410 sched.o.after

i've applied it to the end of the queue - it depends on whether ->vruntime works out well.

Ingo