Fix find busiest queue 2.6.0-test9

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

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.

Quoted 5 lines · Con Kolivas

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.

Quoted 11 lines · Andrew Morton

Quoted 6 lines · Con Kolivas

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.

Quoted 7 lines

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? ;-)

Quoted 3 lines

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.

Quoted 8 lines · Martin J. Bligh

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

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 ;-)

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.

Quoted 3 lines · 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.

Quoted 9 lines

Quoted 3 lines

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.

kernel/sched.c static inline unsigned int double_lock_b · line 911

Quoted 7 lines

kernel/sched.c +7 -0

+/* 
+ * 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])