[announce] CFS-devel, performance improvements

Ingo Molnar
2007-09-11T20:14:44Z

fresh back from the Kernel Summit, Peter Zijlstra and me are pleased to
announce the latest iteration of the CFS scheduler development tree. Our
main focus has been on simplifications and performance - and as part of
that we've also picked up some ideas from Roman Zippel's 'Really Fair
Scheduler' patch as well and integrated them into CFS. We'd like to ask
people go give these patches a good workout, especially with an eye on
any interactivity regressions.

The combo patch against 2.6.23-rc6 can be picked up from:

http://people.redhat.com/mingo/cfs-scheduler/devel/

The sched-devel.git tree can be pulled from:

git://git.kernel.org/pub/scm/linux/kernel/git/mingo/linux-2.6-sched-devel.git

There are lots of small performance improvements in form of a
finegrained 29-patch series. We have removed a number of features and
metrics from CFS that might have been needed but ended up being
superfluous - while keeping the things that worked out fine, like
sleeper fairness. On 32-bit x86 there's a ~16% speedup (over -rc6) in
lmbench (lat_ctx -s 0 2) results:

(microseconds, lower is better)
------------------------------------------------------------
v2.6.22 2.6.23-rc6(CFS) v2.6.23-rc6-CFS-devel
----------------------------------------------------
0.70 0.75 0.65
0.62 0.66 0.63
0.60 0.72 0.69
0.62 0.74 0.61
0.69 0.73 0.53
0.66 0.73 0.63
0.63 0.69 0.61
0.63 0.70 0.64
0.61 0.76 0.61
0.69 0.74 0.63
----------------------------------------------------
avg: 0.64 0.72 (+12%) 0.62 (-3%)

there is a similar speedup on 64-bit x86 as well. We are now a bit
faster than the O(1) scheduler was under v2.6.22 - even on 32-bit. The
main speedup comes from the avoidance of divisions (or shifts) in the
wakeup and context-switch fastpaths.

there's also a visible reduction in code size:

text data bss dec hex filename
13369 228 2036 15633 3d11 sched.o.before (UP, nodebug)
11167 224 1988 13379 3443 sched.o.after (UP, nodebug)

which obviously helps embedded and is good for performance as well. Even
on 32-bit we are now within 1% of the size of v2.6.22's sched.o, which
was:

text data bss dec hex filename
9915 24 3344 13283 33e3 sched.o.v2.6.22

and on SMP the new scheduler is now substantially smaller:

text data bss dec hex filename
24972 4149 24 29145 71d9 sched.o-v2.6.22
24056 2594 16 26666 682a sched.o-CFS-devel

Changes: besides the many micro-optimizations, one of the changes is
that se->vruntime (virtual runtime) based scheduling has been introduced
gradually, step by step - while keeping the wait_runtime metric working
too. (so that the two methods are comparable side by side, in the same
scheduler)

The ->vruntime metric is similar to the ->time_norm metric used by
Roman's patch (and both are losely related to the already existing
sum_exec_runtime metric in CFS), it's in essence the sum of CPU time
executed by a task, in nanoseconds - weighted up or down by their nice
level (or kept the same on the default nice 0 level). Besides this basic
metric our implementation and math differs from RFS. The two approaches
should be conceptually more comparable from now on.

We have also picked up two cleanups from RFS (the cfs_rq->curr approach
and an uninlining optimization) and there's also a cleanup patch from
Matthias Kaehlcke. We welcome and encourage finegrained patches against
this patchset. As usual, bugreports, fixes and suggestions are welcome,

Ingo, Peter

------------------>
Matthias Kaehlcke (1):
sched: use list_for_each_entry_safe() in __wake_up_common()

Peter Zijlstra (5):
sched: simplify SCHED_FEAT_* code
sched: new task placement for vruntime
sched: simplify adaptive latency
sched: clean up new task placement
sched: add tree based averages

Ingo Molnar (23):
sched: fix new-task method
sched: small sched_debug cleanup
sched: debug: track maximum 'slice'
sched: uniform tunings
sched: use constants if !CONFIG_SCHED_DEBUG
sched: remove stat_gran
sched: remove precise CPU load
sched: remove precise CPU load calculations #2
sched: track cfs_rq->curr on !group-scheduling too
sched: cleanup: simplify cfs_rq_curr() methods
sched: uninline __enqueue_entity()/__dequeue_entity()
sched: speed up update_load_add/_sub()
sched: clean up calc_weighted()
sched: introduce se->vruntime
sched: move sched_feat() definitions
sched: optimize vruntime based scheduling
sched: simplify check_preempt() methods
sched: wakeup granularity fix
sched: add se->vruntime debugging
sched: debug: update exec_clock only when SCHED_DEBUG
sched: remove wait_runtime limit
sched: remove wait_runtime fields and features
sched: x86: allow single-depth wchan output

arch/i386/Kconfig | 11
include/linux/sched.h | 17 -
kernel/sched.c | 196 ++++-------------
kernel/sched_debug.c | 86 +++----
kernel/sched_fair.c | 557 +++++++++++++-------------------------------------
kernel/sysctl.c | 22 -
6 files changed, 243 insertions(+), 646 deletions(-)