From: greg@sherrill.kiva.net (Gregory Travis)
Subject: Re: Thread creation/switch times on Linux and NT (was Re: Linux users working at Microsoft!)
Date: 8 Mar 1998 09:15:38 -0500

Here's some more data, using the latest version of my context switching
benchmark.  Test machine is a 64MB 200Mhz Pentium "classic".

Switch				Number of processes/Threads
Time			2	4	8	10	20	40
			----	----	----	----	----	----
Std. Procs		19us	13us	13us	14us	16us	27us
Std. Threads		16us	11us	10us	10us	15us	23us

Mingo Procs		 4us	 6us	11us	12us	15us	28us
Mingo Threads		 3us	 3us	 5us	 7us	12us	22us

NT Procs		10us	15us	15us	17us	16us	17us
NT Threads		 5us	 8us	 8us	 9us	10us	11us


Explanation:

The "Std." entries show the results of my yield_cpu() benchmark against
the standard Linux scheduler using either threads or processes.

The "Mingo" entries show the results of the same benchmark but after the
Linux yield_cpu() entry has been modified per Mingo's suggestion so that
it doesn't take the counter to zero.

The "NT" entries show the results of the benchmark under NT.

Each benchmark was run twice for each number (to promot accuracy).  Thus
the above is the result of 72 individual runs.

Analysis:

The dramatic drop in context switch time, between the "Std." and "Mingo"
runs shows how expensive the priority recalc can be - for short run
queues at least.  Note that it makes little or no difference as the
run queue length exceeds about 10 processes.  This is almost certainly
because the cost of the "goodness" function begins to dominate the picture.
For a given number of iterations, the goodness function is much more
expensive than the priority recalc function.  The goodness function must
be performed on each runnable process while the priority recalc must be
performed on all processes.  Thus with a small # of runnable processes,
the expensive goodness function is not called much while the "cheap"
priority recalc is called for each process, runnable or not.  As the run
queue grows, however, the goodness function is called more (while the
priority recalc function is essentially constant).  Around ~15 processes,
on my system, the cost of "goodness" washes out the noise from the priority
recalc.

Nevertheless, the context switch times shown in the "Mingo" series is
probably closest to the actual Linux context switch times.  Note how the
series dramatically illustrates how context switch overhead, on Linux,
grows as a function of the run queue length.

It appears that the context-switch overhead for Linux is better than NT for
shortish run queues and, especially, where process/process switch time is
compared.  With run queues longer than about 20 processes, though, NT's
scheduler starts to beat out the Linux scheduler.  Also note that NT's
scheduler appears more robust than the Linux scheduler - its degradation
as the run queue grows is nowhere as dramatic as Linux's.  NT's thread
switch times doubled between 2 and 40 threads while Linux's showed a
>sevenfold< slowdown.

Does it matter?  Quite probably not.  From my earlier posting, with data
from a heavily loaded webserver, I saw an average run queue length of
2.5 processes.  The run queue exceeded 10 processes only about 4% of the
time.

I've put my benchmarks, as well as the kernel changes to record
run queue length, on anonymous ftp at weasel.ciswired.com

greg