Skip to contentSkip to conversation

- Reduce overhead of calc_load

PATCH In review Jack Steiner 4 participants 10 messages Mar 17, 2006 – Mar 18, 2006 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 - Reduce overhead of calc_load

Currently, count_active_tasks() calls both nr_running() & nr_interruptible(). Each of these functions does a "for_each_cpu" & reads values from the runqueue of each cpu. Although this is not a lot of instructions, each runqueue may be located on different node. Depending on the architecture, a unique TLB entry may be required to access each runqueue.

Since there may be more runqueues than cpu TLB entries, a scan of all runqueues can trash the TLB. Each memory reference incurs a TLB miss & refill.

In addition, the runqueue cacheline that contains nr_running & nr_uninterruptible may be evicted from the cache between the two passes. This causes unnecessary cache misses.

Combining nr_running() & nr_interruptible() into a single function substantially reduces the TLB & cache misses on large systems. This should have no measureable effect on smaller systems.

On a 128p IA64 system running a memory stress workload, the new function reduced the overhead of calc_load() from 605 usec/call to 324 usec/call.

 include/linux/sched.h |    1 +
 kernel/sched.c        |   16 ++++++++++++++++
 kernel/timer.c        |    8 +++++++-
 3 files changed, 24 insertions(+), 1 deletion(-)
include/linux/sched.h +1 -0
Index: linux/include/linux/sched.h
===================================================================
@@ -98,6 +98,7 @@ extern int last_pid;
 DECLARE_PER_CPU(unsigned long, process_counts);
 extern int nr_processes(void);
 extern unsigned long nr_running(void);
+extern unsigned long nr_active(void);
 extern unsigned long nr_uninterruptible(void);
 extern unsigned long nr_iowait(void);
 
kernel/sched.c +16 -0
Index: linux/kernel/sched.c
===================================================================
@@ -1655,6 +1655,22 @@ unsigned long nr_iowait(void)
 	return sum;
 }
 
+unsigned long nr_active(void)
+{
+	unsigned long i, running = 0, uninterruptible = 0;
+
+	for_each_online_cpu(i) {
+		running += cpu_rq(i)->nr_running;
+		uninterruptible += cpu_rq(i)->nr_uninterruptible;
+	}
+
+	if (unlikely((long)uninterruptible < 0))
+		uninterruptible = 0;
+
+	return running + uninterruptible;
+}
+
+
 #ifdef CONFIG_SMP
 
 /*
kernel/timer.c +1 -1
Index: linux/kernel/timer.c
===================================================================
@@ -849,7 +849,7 @@ void update_process_times(int user_tick)
  */
 static unsigned long count_active_tasks(void)
 {
-	return (nr_running() + nr_uninterruptible()) * FIXED_1;
+	return nr_active() * FIXED_1;
 }
 
 /*
Acked-by on v1 1/1
#1 lore raw
Quoted 1 line · Jack Steiner
Quoted 5 lines

extern int nr_processes(void);
extern unsigned long nr_running(void);
+extern unsigned long nr_active(void);
extern unsigned long nr_uninterruptible(void);
extern unsigned long nr_iowait(void);

ob'nit, i'd make it:

Quoted 5 lines

extern int nr_processes(void);
extern unsigned long nr_running(void);
extern unsigned long nr_uninterruptible(void);
+extern unsigned long nr_active(void);
extern unsigned long nr_iowait(void);

just to keep the logical order.

Ingo

author Acked-by Ingo Molnar
#2 lore raw

Currently, count_active_tasks() calls both nr_running() & nr_interruptible(). Each of these functions does a "for_each_cpu" & reads values from the runqueue of each cpu. Although this is not a lot of instructions, each runqueue may be located on different node. Depending on the architecture, a unique TLB entry may be required to access each runqueue.

Since there may be more runqueues than cpu TLB entries, a scan of all runqueues can trash the TLB. Each memory reference incurs a TLB miss & refill.

In addition, the runqueue cacheline that contains nr_running & nr_uninterruptible may be evicted from the cache between the two passes. This causes unnecessary cache misses.

Combining nr_running() & nr_interruptible() into a single function substantially reduces the TLB & cache misses on large systems. This should have no measureable effect on smaller systems.

On a 128p IA64 system running a memory stress workload, the new function reduced the overhead of calc_load() from 605 usec/call to 324 usec/call.

(Same as previous patch except reorder extern as requested by Ingo)

 include/linux/sched.h |    1 +
 kernel/sched.c        |   16 ++++++++++++++++
 kernel/timer.c        |    8 +++++++-
 3 files changed, 24 insertions(+), 1 deletion(-)
include/linux/sched.h +1 -0
Index: linux/include/linux/sched.h
===================================================================
@@ -99,6 +99,7 @@ DECLARE_PER_CPU(unsigned long, process_c
 extern int nr_processes(void);
 extern unsigned long nr_running(void);
 extern unsigned long nr_uninterruptible(void);
+extern unsigned long nr_active(void);
 extern unsigned long nr_iowait(void);
 
 #include <linux/time.h>
kernel/sched.c +16 -0
Index: linux/kernel/sched.c
===================================================================
@@ -1655,6 +1655,22 @@ unsigned long nr_iowait(void)
 	return sum;
 }
 
+unsigned long nr_active(void)
+{
+	unsigned long i, running = 0, uninterruptible = 0;
+
+	for_each_online_cpu(i) {
+		running += cpu_rq(i)->nr_running;
+		uninterruptible += cpu_rq(i)->nr_uninterruptible;
+	}
+
+	if (unlikely((long)uninterruptible < 0))
+		uninterruptible = 0;
+
+	return running + uninterruptible;
+}
+
+
 #ifdef CONFIG_SMP
 
 /*
kernel/timer.c +1 -1
Index: linux/kernel/timer.c
===================================================================
@@ -849,7 +849,7 @@ void update_process_times(int user_tick)
  */
 static unsigned long count_active_tasks(void)
 {
-	return (nr_running() + nr_uninterruptible()) * FIXED_1;
+	return nr_active() * FIXED_1;
 }
 
 /*
#3 lore raw
Quoted 5 lines · Jack Steiner
kernel/sched.c +4 -0
+unsigned long nr_active(void)
+{
+	unsigned long i, running = 0, uninterruptible = 0;
+

kernel/sched.c unsigned long nr_iowait(void) · line 1671

Quoted 10 lines
kernel/sched.c +10 -0
+	for_each_online_cpu(i) {
+		running += cpu_rq(i)->nr_running;
+		uninterruptible += cpu_rq(i)->nr_uninterruptible;
+	}
+
+	if (unlikely((long)uninterruptible < 0))
+		uninterruptible = 0;
+
+	return running + uninterruptible;
+}

Is that check for (uninterruptible < 0) (copied from nr_uninterruptible) really needed? Can rq->nr_uninterruptible actually go negative?

Perhaps nr_context_switches() and nr_iowait() should also go into this function, then we rename it all to

	struct sched_stuff {
		unsigned nr_uninterruptible;
		unsigned nr_running;
		unsigned nr_active;
		unsigned long nr_context_switches;
	};

	void get_sched_stuff(struct sched_stuff *);

and then convert all those random little counter-upper-callers we have.

And then give get_sched_stuff() a hotplug handler (probably unneeded) and then scratch our heads over why nr_uninterruptible() iterates across all possible CPUs while this new nr_active() iterates over all online CPUs like nr_running() and unlike nr_context_switches().

IOW: this code's an inefficient mess and needs some caring for.

#4 lore raw
Quoted 12 lines · Andrew Morton
Quoted 10 lines · Jack Steiner
kernel/sched.c +10 -0
+unsigned long nr_active(void)
+{
+	unsigned long i, running = 0, uninterruptible = 0;
+
+	for_each_online_cpu(i) {
+		running += cpu_rq(i)->nr_running;
+		uninterruptible += cpu_rq(i)->nr_uninterruptible;
+	}
+
+	if (unlikely((long)uninterruptible < 0))
Quoted 9 lines

kernel/sched.c unsigned long nr_iowait(void) · line 1671

Quoted 4 lines
kernel/sched.c +4 -0
+		uninterruptible = 0;
+
+	return running + uninterruptible;
+}

Is that check for (uninterruptible < 0) (copied from nr_uninterruptible) really needed? Can rq->nr_uninterruptible actually go negative?

The sum cannot if there are no concurrent updates, however when there are concurrent updates then it can go negative.

rq->nr_uninterruptible itself is meaningless because it can be incremented on one rq and decremented on another.

Quoted 12 lines

Perhaps nr_context_switches() and nr_iowait() should also go into this function, then we rename it all to

	struct sched_stuff {
		unsigned nr_uninterruptible;
		unsigned nr_running;
		unsigned nr_active;
		unsigned long nr_context_switches;
	};

	void get_sched_stuff(struct sched_stuff *);
Quoted 2 lines

and then convert all those random little counter-upper-callers we have.

Is there a need? Do they (except calc_load) use multiple values at the same time?

Quoted 1 line

And then give get_sched_stuff() a hotplug handler (probably unneeded) and

What would the hotplug handler do?

Quoted 4 lines

then scratch our heads over why nr_uninterruptible() iterates across all possible CPUs while this new nr_active() iterates over all online CPUs like nr_running() and unlike nr_context_switches().

I think it need only iterate over possible CPUs.

Quoted 2 lines

IOW: this code's an inefficient mess and needs some caring for.

What are the performance critical places that call the nr_blah() functions?

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#5 lore raw
Quoted 11 lines · Nick Piggin
Quoted 11 lines

Perhaps nr_context_switches() and nr_iowait() should also go into this function, then we rename it all to

	struct sched_stuff {
		unsigned nr_uninterruptible;
		unsigned nr_running;
		unsigned nr_active;
		unsigned long nr_context_switches;
	};
Quoted 7 lines
Quoted 4 lines
	void get_sched_stuff(struct sched_stuff *);

and then convert all those random little counter-upper-callers we have.

Is there a need? Do they (except calc_load) use multiple values at the same time?

Don't know. It might happen in the future. And the additional cost is practically zero.

Quoted 3 lines
Quoted 1 line

And then give get_sched_stuff() a hotplug handler (probably unneeded) and

What would the hotplug handler do?

Move the stats from the going-away CPU into the current CPU's runqueue.

Quoted 6 lines
Quoted 4 lines

then scratch our heads over why nr_uninterruptible() iterates across all possible CPUs while this new nr_active() iterates over all online CPUs like nr_running() and unlike nr_context_switches().

I think it need only iterate over possible CPUs.

Someone who has four online CPUs, sixteen present CPUs and 128 possible CPUs would be justifiably disappointed, no?

Quoted 5 lines
Quoted 2 lines

IOW: this code's an inefficient mess and needs some caring for.

What are the performance critical places that call the nr_blah() functions?

That depends upon the frequency with which userspace reads /proc/loadavg, /proc/stat or /proc/future-stuff.

#6 lore raw
Quoted 9 lines · Andrew Morton
Quoted 2 lines · Nick Piggin

Is there a need? Do they (except calc_load) use multiple values at the same time?

Don't know. It might happen in the future. And the additional cost is practically zero.

Unless it happens to hit another cacheline (cachelines for all other CPUs but our own will most likely be invalid on this cpu). In which case the cost could double quite easily.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

And then give get_sched_stuff() a hotplug handler (probably unneeded) and

What would the hotplug handler do?

Move the stats from the going-away CPU into the current CPU's runqueue.

Oh, that. Yeah that is handled already for nr_uninterruptible (although, ironically, it isn't needed because of the for_each_cpu loop there!)

Quoted 6 lines
Quoted 1 line

I think it need only iterate over possible CPUs.

Someone who has four online CPUs, sixteen present CPUs and 128 possible CPUs would be justifiably disappointed, no?

Yes. Ingo? This can be changed, right?

Quoted 11 lines
Quoted 5 lines
Quoted 2 lines

IOW: this code's an inefficient mess and needs some caring for.

What are the performance critical places that call the nr_blah() functions?

That depends upon the frequency with which userspace reads /proc/loadavg, /proc/stat or /proc/future-stuff.

I think it might be better to leave it for the moment. If something comes up we can always take a look at it then (it isn't particularly tricky code).

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#7 lore raw
Quoted 8 lines · Nick Piggin
Quoted 6 lines · Andrew Morton
Quoted 2 lines · Nick Piggin

Is there a need? Do they (except calc_load) use multiple values at the same time?

Quoted 8 lines
Quoted 3 lines

Don't know. It might happen in the future. And the additional cost is practically zero.

Unless it happens to hit another cacheline (cachelines for all other CPUs but our own will most likely be invalid on this cpu). In which case the cost could double quite easily.

That would be an inefficient implementation. Let's not implement it inefficiently.

Quoted 2 lines

I think it might be better to leave it for the moment. If something comes up we can always take a look at it then (it isn't particularly tricky code).

What we're seeing here is a proliferation of little functions, all of which do the same thing, some of them in different ways.

Take a look at (for example) nr_iowait. We forget to spill the count out of the departing CPU's runqueue and hence we have to sum it across all possible CPUs and we don't bother accounting for the possibility of the sum going negative because we happen to dink with the runqueue of a now-possibly-downed CPU. It's inefficient and it's inconsistent and some of it is, or will become incorrect. The other counters there probably have various combinations of these problems but I can't be bothered checking them all because they're all implemented differently.

Better to do them all in the one place and do them all the same way. I'd suggest a cacheline-aligned struct of local_t's which can be queried into a struct of ulongs.

That query should only look at online CPUs, which becomes rather necessary if we're to allocate runqueues only for online CPUs (desirable - the thing is huge).

#8 lore raw
Quoted 14 lines · Andrew Morton
Quoted 12 lines · Nick Piggin
Quoted 9 lines · Andrew Morton
Quoted 2 lines · Nick Piggin

Is there a need? Do they (except calc_load) use multiple values at the same time?

Don't know. It might happen in the future. And the additional cost is practically zero.

Quoted 9 lines
Quoted 4 lines

Unless it happens to hit another cacheline (cachelines for all other CPUs but our own will most likely be invalid on this cpu). In which case the cost could double quite easily.

That would be an inefficient implementation. Let's not implement it inefficiently.

Unconditionally adding up n fields in the runqueue versus 1 field? It is inevitable that they will cross cacheline boundaries on some CPU architectures and with some per-cpu implementations isn't it?

Quoted 8 lines
Quoted 3 lines

I think it might be better to leave it for the moment. If something comes up we can always take a look at it then (it isn't particularly tricky code).

What we're seeing here is a proliferation of little functions, all of which do the same thing, some of them in different ways.

Of course they should be made consistent where it makes sense.

Quoted 2 lines

Take a look at (for example) nr_iowait. We forget to spill the count out of the departing CPU's runqueue and hence we have to sum it across all

I don't think a departing runqueue should have any iowaiters on it, should it?

Quoted 7 lines

possible CPUs and we don't bother accounting for the possibility of the sum going negative because we happen to dink with the runqueue of a now-possibly-downed CPU. It's inefficient and it's inconsistent and some of it is, or will become incorrect. The other counters there probably have various combinations of these problems but I can't be bothered checking them all because they're all implemented differently.

Maybe (they're also used in different ways, and with different races to be careful of so in some respects that is inevitable). But that doesn't mean we should introduce this new get_sched_stats thing.

Quoted 4 lines

Better to do them all in the one place and do them all the same way. I'd suggest a cacheline-aligned struct of local_t's which can be queried into a struct of ulongs.

Now common scheduler operations have to access the runqueue cacheilnes and this disjoint "stats" structure cacheline, so basic operations will get slower. Not to mention that all but one are protected by the runqueue lock, so local_t isn't needed for the rest of them.

Quoted 4 lines

That query should only look at online CPUs, which becomes rather necessary if we're to allocate runqueues only for online CPUs (desirable - the thing is huge).

Sure, those consistency and efficiency changes should be made now, with the current structure.

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#9 lore raw
Quoted 8 lines · Nick Piggin
Quoted 2 lines · Andrew Morton

Take a look at (for example) nr_iowait. We forget to spill the count out of the departing CPU's runqueue and hence we have to sum it across all

I don't think a departing runqueue should have any iowaiters on it, should it?

No I'm wrong there. Instead of doing all these migrations and having the ugly nr_iowait and nr_uninterruptible things I would much prefer just to migrate the stat when the actual task is migrated. This should take care of cpu hotplug, and also can make everything consistent.

I'll try doing a patch for that sometime.

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com