[PATCH] Fix find busiest queue 2.6.0-test9

[PATCH] Fix find busiest queue 2.6.0-test9

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 151 bytes --]

Hi

I believe this is a simple typo / variable name mixup between rq_src and 
this_rq. So far all testing shows positive (if minor) improvements.

Con

[-- Attachment #2: loadfix.patch --]
[-- Type: text/x-diff, Size: 674 bytes --]

--- linux-2.6.0-test9-base/kernel/sched.c	2003-10-26 07:52:58.000000000 +1100
+++ linux-2.6.0-test9/kernel/sched.c	2003-11-09 01:25:07.684769327 +1100
@@ -1073,11 +1073,11 @@ static inline runqueue_t *find_busiest_q
 			continue;
 
 		rq_src = cpu_rq(i);
-		if (idle || (rq_src->nr_running < this_rq->prev_cpu_load[i]))
+		if (idle || (rq_src->nr_running < rq_src->prev_cpu_load[i]))
 			load = rq_src->nr_running;
 		else
-			load = this_rq->prev_cpu_load[i];
-		this_rq->prev_cpu_load[i] = rq_src->nr_running;
+			load = rq_src->prev_cpu_load[i];
+		rq_src->prev_cpu_load[i] = rq_src->nr_running;
 
 		if ((load > max_load) && (rq_src != this_rq)) {
 			busiest = rq_src;

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Nick Piggin]

Con Kolivas wrote:

>Hi
>
>I believe this is a simple typo / variable name mixup between rq_src and 
>this_rq. So far all testing shows positive (if minor) improvements.
>

Hi Con,
It was correct (as Ingo intended) before the patch, I think.

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Andrew Morton]

Con Kolivas <kernel@kolivas.org> wrote:
>
> Hi
> 
> I believe this is a simple typo / variable name mixup between rq_src and 
> this_rq. So far all testing shows positive (if minor) improvements.
> 

Looks right to me.  I'll queue this up for the 2.6.1 deluge.

--- linux-2.6.0-test9-base/kernel/sched.c	2003-10-26 07:52:58.000000000 +1100
+++ linux-2.6.0-test9/kernel/sched.c	2003-11-09 01:25:07.684769327 +1100
@@ -1073,11 +1073,11 @@ static inline runqueue_t *find_busiest_q
 			continue;
 
 		rq_src = cpu_rq(i);
-		if (idle || (rq_src->nr_running < this_rq->prev_cpu_load[i]))
+		if (idle || (rq_src->nr_running < rq_src->prev_cpu_load[i]))
 			load = rq_src->nr_running;
 		else
-			load = this_rq->prev_cpu_load[i];
-		this_rq->prev_cpu_load[i] = rq_src->nr_running;
+			load = rq_src->prev_cpu_load[i];
+		rq_src->prev_cpu_load[i] = rq_src->nr_running;
 
 		if ((load > max_load) && (rq_src != this_rq)) {
 			busiest = rq_src;

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Nick Piggin]

Andrew Morton wrote:

>Con Kolivas <kernel@kolivas.org> wrote:
>
>>Hi
>>
>>I believe this is a simple typo / variable name mixup between rq_src and 
>>this_rq. So far all testing shows positive (if minor) improvements.
>>
>>
>
>Looks right to me.  I'll queue this up for the 2.6.1 deluge.
>

prev_cpu_load[i] is nr_running of cpu i last time this operation was
performed. Either it, or the current nr_running is taken, whichever
is lower.

I guess its done this way for cache benefits, but it was correct as
Ingo intended. For example, with Con's patch you can see
rq_src->prev_cpu_load[i] will only ever use the ith position in the array.

I wonder what improvements Con is seeing? If they are significant, change
prev_cpu_load to be an integer type and do a similar thing here.

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Davide Libenzi]

On Sun, 9 Nov 2003, Nick Piggin wrote:

> Andrew Morton wrote:
> 
> >Con Kolivas <kernel@kolivas.org> wrote:
> >
> >>Hi
> >>
> >>I believe this is a simple typo / variable name mixup between rq_src and 
> >>this_rq. So far all testing shows positive (if minor) improvements.
> >>
> >>
> >
> >Looks right to me.  I'll queue this up for the 2.6.1 deluge.
> >
> 
> prev_cpu_load[i] is nr_running of cpu i last time this operation was
> performed. Either it, or the current nr_running is taken, whichever
> is lower.
> 
> I guess its done this way for cache benefits, but it was correct as
> Ingo intended. For example, with Con's patch you can see
> rq_src->prev_cpu_load[i] will only ever use the ith position in the array.

Yes. The prev_cpu_load[] array takes a snapshot of the run queue lengths 
seen by the current rq (this_rq). The code is ok as is, and the reason is 
to avoid stealing tasks too fast from remote CPU (cache thing). Time ago I 
also tried to store an K-average (by varying K) rq length in 
prev_cpu_load[] instead of a simple min-of-two-values:

this_rq->prev_cpu_load[i] = (K * this_rq->prev_cpu_load[i] + rq_src->nr_running) / (K + 1);

I couldn't see any major improvements in my 2SMP (never tried on bigger SMP/NUMA).



- Davide

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Martin J. Bligh]

>> prev_cpu_load[i] is nr_running of cpu i last time this operation was
>> performed. Either it, or the current nr_running is taken, whichever
>> is lower.
>> 
>> I guess its done this way for cache benefits, but it was correct as
>> Ingo intended. For example, with Con's patch you can see
>> rq_src->prev_cpu_load[i] will only ever use the ith position in the array.
> 
> Yes. The prev_cpu_load[] array takes a snapshot of the run queue lengths 
> seen by the current rq (this_rq). The code is ok as is, and the reason is 
> to avoid stealing tasks too fast from remote CPU (cache thing). Time ago I 
> also tried to store an K-average (by varying K) rq length in 
> prev_cpu_load[] instead of a simple min-of-two-values:
> 
> this_rq->prev_cpu_load[i] = (K * this_rq->prev_cpu_load[i] + rq_src->nr_running) / (K + 1);
> 
> I couldn't see any major improvements in my 2SMP (never tried on bigger SMP/NUMA).

I ran it on the 16-way - no difference in performance. If the code is 
correct as was before (and I agree, it seems it was), perhaps it's just
in need of a big fat comment to explain the confusion? ;-)

M.

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Davide Libenzi]

On Sun, 9 Nov 2003, Martin J. Bligh wrote:

> I ran it on the 16-way - no difference in performance. If the code is 
> correct as was before (and I agree, it seems it was), perhaps it's just
> in need of a big fat comment to explain the confusion? ;-)

Ingo already dropped a fat comment ;) This is the relevant part:

 * We fend off statistical fluctuations in runqueue lengths by
 * saving the runqueue length during the previous load-balancing
 * operation and using the smaller one the current and saved lengths.
 


- Davide

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Martin J. Bligh]

>> I ran it on the 16-way - no difference in performance. If the code is 
>> correct as was before (and I agree, it seems it was), perhaps it's just
>> in need of a big fat comment to explain the confusion? ;-)
> 
> Ingo already dropped a fat comment ;) This is the relevant part:
> 
>  * We fend off statistical fluctuations in runqueue lengths by
>  * saving the runqueue length during the previous load-balancing
>  * operation and using the smaller one the current and saved lengths.

I think the confusing bit is this:

this_rq->prev_cpu_load[i] = rq_src->nr_running;

where "this_rq->prev_cpu_load[i]" doesn't intuitively look like what it
means ;-) Even just 's/i/cpu/' would help a bit, or something (like 
wrapping it in macros). Seems it is correct as was though - thanks for 
explaining it.

M.

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Davide Libenzi]

On Sun, 9 Nov 2003, Martin J. Bligh wrote:

> I think the confusing bit is this:
> 
> this_rq->prev_cpu_load[i] = rq_src->nr_running;
> 
> where "this_rq->prev_cpu_load[i]" doesn't intuitively look like what it
> means ;-) Even just 's/i/cpu/' would help a bit, or something (like 
> wrapping it in macros). Seems it is correct as was though - thanks for 
> explaining it.

Maybe something like:

 * We fend off statistical fluctuations in runqueue lengths by
 * saving the runqueue length (as seen by the balancing CPU) during the 
 * previous load-balancing operation and using the smaller one the current 
 * and saved lengths.


- Davide

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Con Kolivas]

On Mon, 10 Nov 2003 03:05, Davide Libenzi wrote:
> On Sun, 9 Nov 2003, Martin J. Bligh wrote:
> > I think the confusing bit is this:
> >
> > this_rq->prev_cpu_load[i] = rq_src->nr_running;
> >
> > where "this_rq->prev_cpu_load[i]" doesn't intuitively look like what it
> > means ;-) Even just 's/i/cpu/' would help a bit, or something (like
> > wrapping it in macros). Seems it is correct as was though - thanks for
> > explaining it.
>
> Maybe something like:
>
>  * We fend off statistical fluctuations in runqueue lengths by
>  * saving the runqueue length (as seen by the balancing CPU) during the
>  * previous load-balancing operation and using the smaller one the current

"during the previous load-balancing operation" is what made me interpret it 
differently.

Con

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Martin J. Bligh]

On the same vein ... this looks odd:

         * We fend off statistical fluctuations in runqueue lengths by
         * saving the runqueue length during the previous load-balancing
         * operation and using the smaller one the current and saved lengths.
         * If a runqueue is long enough for a longer amount of time then
         * we recognize it and pull tasks from it.
...
        if (idle || (this_rq->nr_running > this_rq->prev_cpu_load[this_cpu]))
                nr_running = this_rq->nr_running;
        else
                nr_running = this_rq->prev_cpu_load[this_cpu];

It says we uses the smaller of the two in the comment, but then it seems to
use the > of the two in the code? Unless I'm losing it, which is likely ;-)

Later, we do "*imbalance = (max_load - nr_running) / 2;" ... to "fend off 
statistical fluctuations", we want to reduce imbalance, which would mean
a larger nr_running .... so to my mind, it's the comment that's wrong?

M.

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Nick Piggin]

Martin J. Bligh wrote:

>On the same vein ... this looks odd:
>
>         * We fend off statistical fluctuations in runqueue lengths by
>         * saving the runqueue length during the previous load-balancing
>         * operation and using the smaller one the current and saved lengths.
>         * If a runqueue is long enough for a longer amount of time then
>         * we recognize it and pull tasks from it.
>...
>        if (idle || (this_rq->nr_running > this_rq->prev_cpu_load[this_cpu]))
>                nr_running = this_rq->nr_running;
>        else
>                nr_running = this_rq->prev_cpu_load[this_cpu];
>
>It says we uses the smaller of the two in the comment, but then it seems to
>use the > of the two in the code? Unless I'm losing it, which is likely ;-)
>

You want the larger of the two values to be taken for the destination
queue, and the smaller to be taken for the source queue. This way you
get a minimal imbalance.

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Ingo Molnar]

On Sun, 9 Nov 2003, Davide Libenzi wrote:

> Maybe something like:
> 
>  * We fend off statistical fluctuations in runqueue lengths by
>  * saving the runqueue length (as seen by the balancing CPU) during the 
>  * previous load-balancing operation and using the smaller one the current 
>  * and saved lengths.

yep, agreed - patch for 2.6.1 attached. (I also fixed a typo in the
original comment and reformatted the lines) Anything else?

	Ingo

--- kernel/sched.c.orig
+++ kernel/sched.c
@@ -1061,10 +1061,11 @@
 	 * the lock held.
 	 *
 	 * We fend off statistical fluctuations in runqueue lengths by
-	 * saving the runqueue length during the previous load-balancing
-	 * operation and using the smaller one the current and saved lengths.
-	 * If a runqueue is long enough for a longer amount of time then
-	 * we recognize it and pull tasks from it.
+	 * saving the runqueue length (as seen by the balancing CPU) during
+	 * the previous load-balancing operation and using the smaller one
+	 * of the current and saved lengths. If a runqueue is long enough
+	 * for a longer amount of time then we recognize it and pull tasks
+	 * from it.
 	 *
 	 * The 'current runqueue length' is a statistical maximum variable,
 	 * for that one we take the longer one - to avoid fluctuations in

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Con Kolivas]

On Mon, 10 Nov 2003 02:53, Davide Libenzi wrote:
> On Sun, 9 Nov 2003, Martin J. Bligh wrote:
> > I ran it on the 16-way - no difference in performance. If the code is
> > correct as was before (and I agree, it seems it was), perhaps it's just
> > in need of a big fat comment to explain the confusion? ;-)
>
> Ingo already dropped a fat comment ;) This is the relevant part:
>
>  * We fend off statistical fluctuations in runqueue lengths by
>  * saving the runqueue length during the previous load-balancing
>  * operation and using the smaller one the current and saved lengths.

Well that was the comment that led me to make that patch. 

After discussion with mbligh it seems the confusion coming from me seeing
->prev_cpu_load
as the load for that runqueue the last time we balanced; whereas it's actually 
the load of the last runqueue checked during the balancing. 

Anyway the performance differences are tiny on my testing and non existent on 
mblighs so forget it.

Con

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Martin J. Bligh]

>> > I ran it on the 16-way - no difference in performance. If the code is
>> > correct as was before (and I agree, it seems it was), perhaps it's just
>> > in need of a big fat comment to explain the confusion? ;-)
>> 
>> Ingo already dropped a fat comment ;) This is the relevant part:
>> 
>>  * We fend off statistical fluctuations in runqueue lengths by
>>  * saving the runqueue length during the previous load-balancing
>>  * operation and using the smaller one the current and saved lengths.
> 
> Well that was the comment that led me to make that patch. 
> 
> After discussion with mbligh it seems the confusion coming from me seeing
> ->prev_cpu_load
> as the load for that runqueue the last time we balanced; whereas it's actually 
> the load of the last runqueue checked during the balancing. 

Personally, I think the following makes the code more readable - if
several of us can't easily see what the code is doing, I think it's
a problem. I'm sure it makes me the very personification of Evil to 
suggest such a thing, but I don't care ;-) 

diff -urpN -X /home/fletch/.diff.exclude virgin/kernel/sched.c fbq_readable/kernel/sched.c
--- virgin/kernel/sched.c	Tue Sep  2 09:55:57 2003
+++ fbq_readable/kernel/sched.c	Sun Nov  9 08:44:39 2003
@@ -902,6 +902,14 @@ static inline unsigned int double_lock_b
 	return nr_running;
 }
 
+/* 
+ * macro to make the code more readable - this_rq->prev_cpu_load[i]
+ * is our local cached value of i's prev cpu_load. However, putting
+ * this_rq->prev_cpu_load into the code makes it read like it's the
+ * prev_cpu_load of this_cpu, which makes it confusing to read
+ */
+#define prev_cpu_load_cache(cpu) (this_rq->prev_cpu_load[cpu])
+
 /*
  * find_busiest_queue - find the busiest runqueue among the cpus in cpumask.
  */
@@ -932,10 +940,10 @@ static inline runqueue_t *find_busiest_q
 	 * that case we are less picky about moving a task across CPUs and
 	 * take what can be taken.
 	 */
-	if (idle || (this_rq->nr_running > this_rq->prev_cpu_load[this_cpu]))
+	if (idle || (this_rq->nr_running > prev_cpu_load_cache(this_cpu)))
 		nr_running = this_rq->nr_running;
 	else
-		nr_running = this_rq->prev_cpu_load[this_cpu];
+		nr_running = prev_cpu_load_cache(this_cpu);
 
 	busiest = NULL;
 	max_load = 1;
@@ -944,11 +952,11 @@ static inline runqueue_t *find_busiest_q
 			continue;
 
 		rq_src = cpu_rq(i);
-		if (idle || (rq_src->nr_running < this_rq->prev_cpu_load[i]))
+		if (idle || (rq_src->nr_running < prev_cpu_load_cache(i)))
 			load = rq_src->nr_running;
 		else
-			load = this_rq->prev_cpu_load[i];
-		this_rq->prev_cpu_load[i] = rq_src->nr_running;
+			load = prev_cpu_load_cache(i);
+		prev_cpu_load_cache(i) = rq_src->nr_running;
 
 		if ((load > max_load) && (rq_src != this_rq)) {
 			busiest = rq_src;

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Davide Libenzi]

On Sun, 9 Nov 2003, Martin J. Bligh wrote:

> +/* 
> + * macro to make the code more readable - this_rq->prev_cpu_load[i]
> + * is our local cached value of i's prev cpu_load. However, putting
> + * this_rq->prev_cpu_load into the code makes it read like it's the
> + * prev_cpu_load of this_cpu, which makes it confusing to read
> + */
> +#define prev_cpu_load_cache(cpu) (this_rq->prev_cpu_load[cpu])

Ouch, the implicit "this_rq" is really evil ;) Eventually:

#define prev_cpu_load_cache(rq, cpu) (rq->prev_cpu_load[cpu])



- Davide

Re: [PATCH] Fix find busiest queue 2.6.0-test9

[Martin J. Bligh]

>> +/* 
>> + * macro to make the code more readable - this_rq->prev_cpu_load[i]
>> + * is our local cached value of i's prev cpu_load. However, putting
>> + * this_rq->prev_cpu_load into the code makes it read like it's the
>> + * prev_cpu_load of this_cpu, which makes it confusing to read
>> + */
>> +#define prev_cpu_load_cache(cpu) (this_rq->prev_cpu_load[cpu])
> 
> Ouch, the implicit "this_rq" is really evil ;) Eventually:

Yeah, I know, but ...
 
># define prev_cpu_load_cache(rq, cpu) (rq->prev_cpu_load[cpu])

I think the implicit version is clearer to read. Oh well, maybe a good
balance between readability and sheer evil ;-)

M.