[PATCH] sched.c

[PATCH] sched.c

[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.

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.orig Tue Aug 27 08:32:38 2002
+++ sched.c Tue Aug 27 08:32:38 2002
@@ -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);

Re: [PATCH] sched.c

[Willy Tarreau]

On Tue, Aug 27, 2002 at 09:15:03PM +0300, Lahti Oy wrote:
 
> - 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

Re: [PATCH] sched.c

[Andrew Morton]

Lahti Oy wrote:
> 
> 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.

Re: [PATCH] sched.c

[Daniel Phillips]

On Tuesday 27 August 2002 20:35, Andrew Morton wrote:
> Lahti Oy wrote:
> > - 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)

;-)

-- 
Daniel

Re: [PATCH] sched.c

[Andreas Dilger]

On Aug 28, 2002  02:13 +0200, Daniel Phillips wrote:
> On Tuesday 27 August 2002 20:35, Andrew Morton wrote:
> > Lahti Oy wrote:
> > > - 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)

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/

Re: [PATCH] sched.c

[Stephen C. Biggs]

Re: [PATCH] sched.c

[Daniel Phillips]

On Wednesday 28 August 2002 02:13, Daniel Phillips wrote:
> On Tuesday 27 August 2002 20:35, Andrew Morton wrote:
> > Lahti Oy wrote:
> > > - 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)

Err, i--

-- 
Daniel

Re: [PATCH] sched.c

[Daniel Phillips]

On Wednesday 28 August 2002 02:41, Andreas Dilger wrote:
> On Aug 28, 2002  02:13 +0200, Daniel Phillips wrote:
> > On Tuesday 27 August 2002 20:35, Andrew Morton wrote:
> > > Lahti Oy wrote:
> > > > - 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)
	       ^^^ 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) {
> 		...
> 	}

Hi Andreas,

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

Daniel

Re: [PATCH] sched.c

[Stephen C. Biggs]

[Empty post?]

On 28 Aug 2002 at 2:47, Daniel Phillips wrote:

> On Wednesday 28 August 2002 02:13, Daniel Phillips wrote:
> > On Tuesday 27 August 2002 20:35, Andrew Morton wrote:
> > > Lahti Oy wrote:
> > > > - 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)

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

unless i is unsigned...

Re: [PATCH] sched.c

[Rusty Russell]

On Tue, 27 Aug 2002 11:35:49 -0700
Andrew Morton <akpm@zip.com.au> 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.
-- 
   there are those who do and those who hang on and you don't see too
   many doers quoting their contemporaries.  -- Larry McVoy

Re: [PATCH] sched.c

[Thunder from the hill]

Hi,

On Tue, 27 Aug 2002, Stephen C. Biggs wrote:
> > > > 	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
-- 
--./../...-/. -.--/---/..-/.-./..././.-../..-. .---/..-/.../- .-
--/../-./..-/-/./--..-- ../.----./.-../.-.. --./../...-/. -.--/---/..-
.- -/---/--/---/.-./.-./---/.--/.-.-.-
--./.-/-.../.-./.././.-../.-.-.-