Skip to contentSkip to conversation

sched.c

PATCH In review Lahti Oy 8 participants 11 messages Aug 27, 2002 – Aug 28, 2002

lore
Share & tools
lore

Lahti Oy

author
#0 lore raw

PATCH 1/1 sched.c

Small patch that makes NR_CPUS loops decrement from 31 to 0 in sched.c to squeeze out some cycles (of course only on SMP machines). Also deprecated a macro that was only used once in the code and changed one if-conditional to else if.

If everyone agrees, do I need to post the patch to someone or will it be picked from the list?

Furthermore, there are probably many other juicy spots in the kernel where decrementing loops could be applied. Is there a reason for not doing so at the moment?

sched.c Tue Aug 27 08:32:38 2002 renamed from sched.c.orig Tue Aug 27 08:32:38 2002 +7 -8
@@ -161,7 +161,6 @@
 #define cpu_rq(cpu)  (runqueues + (cpu))
 #define this_rq()  cpu_rq(smp_processor_id())
 #define task_rq(p)  cpu_rq(task_cpu(p))
-#define cpu_curr(cpu)  (cpu_rq(cpu)->curr)
 #define rt_task(p)  ((p)->prio < MAX_RT_PRIO)
 
 /*

@@ -543,7 +542,7 @@
 {
  unsigned long i, sum = 0;
 
- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
   sum += cpu_rq(i)->nr_running;
 
  return sum;

@@ -553,7 +552,7 @@
 {
  unsigned long i, sum = 0;
 
- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
   sum += cpu_rq(i)->nr_uninterruptible;
 
  return sum;

@@ -563,7 +562,7 @@
 {
  unsigned long i, sum = 0;
 
- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
   sum += cpu_rq(i)->nr_switches;
 
  return sum;

@@ -667,7 +666,7 @@
 
  busiest = NULL;
  max_load = 1;
- for (i = 0; i < NR_CPUS; i++) {
+ for (i = NR_CPUS; i; i--) {
   if (!cpu_online(i))
    continue;
 

@@ -1297,7 +1296,7 @@
   if (increment < -40)
    increment = -40;
  }
- if (increment > 40)
+ else if (increment > 40)
   increment = 40;
 
  nice = PRIO_TO_NICE(current->static_prio) + increment;

@@ -1344,7 +1343,7 @@
  */
 int idle_cpu(int cpu)
 {
- return cpu_curr(cpu) == cpu_rq(cpu)->idle;
+ return cpu_rq(cpu)->curr == cpu_rq(cpu)->idle;
 }
 
 /**

@@ -2081,7 +2080,7 @@
  runqueue_t *rq;
  int i, j, k;
 
- for (i = 0; i < NR_CPUS; i++) {
+ for (i = NR_CPUS; i; i--) {
   prio_array_t *array;
 
   rq = cpu_rq(i);
#1 lore raw
Quoted 3 lines · Lahti Oy

- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
sum += cpu_rq(i)->nr_running;

you change isn't equivalent : previously, we called cpu_rq() for 0..NR_CPUS-1, and now you call it for 1..NR_CPUS.

You should have written :
+ for (i = NR_CPUS - 1; i>=0; i--)
which might still be a win towards the former version. But of course, this is only valid if i is SIGNED, and it isn't here. Another valid form which would work with unsigned int is :
+ for (i = NR_CPUS; i--; )

but I'm not sure it will save some cycles because increments/decrements within conditions are not always well optimizable.

Same comments for other locations.

Cheers,
Willy

#2 lore raw
In reply to Lahti Oy
Quoted 11 lines · Lahti Oy

Small patch that makes NR_CPUS loops decrement from 31 to 0 in sched.c to squeeze out some cycles (of course only on SMP machines). Also deprecated a macro that was only used once in the code and changed one if-conditional to else if.

...

- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
sum += cpu_rq(i)->nr_running;

Off-by-one there. You'd want

	for (i = NR_CPUS; --i >= 0; )

or something similarly foul ;)

But these are not performance-critical functions. And by far the most inefficient part of them is that they're reading data for
CPUs which cannot exist. That can be fixed with a `cpu_possible(i)'
test in there, but Rusty was going to give us a `for_each_cpu' macro. We haven't seen that yet.

#3 lore raw
Quoted 10 lines · Andrew Morton
Quoted 3 lines · Lahti Oy

- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
sum += cpu_rq(i)->nr_running;

Off-by-one there. You'd want

	for (i = NR_CPUS; --i >= 0; )

or something similarly foul ;)

	int i = NR_CPUS;

	while (--i)

;-)

Signature · 1 line
Daniel
#4 lore raw
Quoted 8 lines · Daniel Phillips
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Lahti Oy

- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
sum += cpu_rq(i)->nr_running;

Off-by-one there. You'd want

Quoted 7 lines
Quoted 3 lines
	for (i = NR_CPUS; --i >= 0; )

or something similarly foul ;)

	int i = NR_CPUS;

	while (--i)

Actually, I prefer the following to avoid wrap-around conditions in strange circumstances (i.e. if 'i' is manipulated between setting and the while loop):

	while (i-- > 0) {
		...
	}

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/

#5 lore raw
Quoted 9 lines · Andreas Dilger
Quoted 8 lines · Daniel Phillips
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Lahti Oy

- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
sum += cpu_rq(i)->nr_running;

Off-by-one there. You'd want

Quoted 7 lines
Quoted 7 lines
Quoted 3 lines
	for (i = NR_CPUS; --i >= 0; )

or something similarly foul ;)

	int i = NR_CPUS;

	while (--i)
	       ^^^ i--
Quoted 8 lines

Actually, I prefer the following to avoid wrap-around conditions in strange circumstances (i.e. if 'i' is manipulated between setting and the while loop):

	while (i-- > 0) {
		...
	}

Hi Andreas,

If this counter goes negative you have other, much bigger problems and you better not try to cover them up.

Daniel

#7 lore raw
In reply to Daniel Phillips
Quoted 8 lines · Daniel Phillips
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Lahti Oy

- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
sum += cpu_rq(i)->nr_running;

Off-by-one there. You'd want

Quoted 7 lines
Quoted 3 lines
	for (i = NR_CPUS; --i >= 0; )

or something similarly foul ;)

	int i = NR_CPUS;

	while (--i)

Err, i--

Signature · 1 line
Daniel
#8 lore raw

[Empty post?]

Quoted 9 lines · Daniel Phillips
Quoted 8 lines · Daniel Phillips
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Lahti Oy

- for (i = 0; i < NR_CPUS; i++)
+ for (i = NR_CPUS; i; i--)
sum += cpu_rq(i)->nr_running;

Off-by-one there. You'd want

Quoted 7 lines
Quoted 7 lines
Quoted 3 lines
	for (i = NR_CPUS; --i >= 0; )

or something similarly foul ;)

	int i = NR_CPUS;

	while (--i)

for (i = NR_CPUS - 1; i >= 0; i--)

unless i is unsigned...

#9 lore raw

Hi,

Quoted 9 lines · Stephen C. Biggs
Quoted 5 lines
Quoted 5 lines
Quoted 1 line
	for (i = NR_CPUS; --i >= 0; )
	int i = NR_CPUS;

	while (--i)

for (i = NR_CPUS - 1; i >= 0; i--)

unless i is unsigned...

That was exactly the point, yours was the current code, and i is indeed unsigned.

Thunder

Signature · 4 lines
--./../...-/. -.--/---/..-/.-./..././.-../..-. .---/..-/.../- .-
--/../-./..-/-/./--..-- ../.----./.-../.-.. --./../...-/. -.--/---/..-
.- -/---/--/---/.-./.-./---/.--/.-.-.-
--./.-/-.../.-./.././.-../.-.-.-
#10 lore raw
In reply to Andrew Morton
Quoted 5 lines · On Tue, 27 Aug 2002 11:35:49 -0700 Andrew Morton <[email protected]> wrote:

But these are not performance-critical functions. And by far the most inefficient part of them is that they're reading data for
CPUs which cannot exist. That can be fixed with a `cpu_possible(i)'
test in there, but Rusty was going to give us a `for_each_cpu' macro. We haven't seen that yet.

I have it, but Linus isn't taking the prerequeisite, which changes cpu masks to generic bitmaps.

Due to be retransmitted in the next couple of days, Rusty.

Signature · 2 lines
   there are those who do and those who hang on and you don't see too
   many doers quoting their contemporaries.  -- Larry McVoy