kernel <linux-2.6.11.10> kernel/sched.c

Given the frequency of schedule() calling, there is a margin to improve it. In step of recalculate task priority, it first dequeues from one priority queue, calls recalc_task_prio(), then enqueue the task into another priority queue. However, statistics shows only around 0.5% of recalculation changed task priority (see below). While rest of 99.5% of recalculation do not change priority, it is reasonably to use requeue_task() to avoid overhead of dequeue and enqueue on the same priority queue.

The patch is implemented with above idea. Note, a new help function, change_queue_task(), to combine dequeue() and enqueue() to reduce one function call overhead. Two statistics fields, sched_prio_changed and sched_prio_unchanged, are added to provide statistic data on priority recalculation.

Thanks,

chen
[email protected]

kernel/sched.c +12 -0

+static void change_queue_task(struct task_struct *p, prio_array_t *array, 
+							int old_prio)
+{
+	list_del(&p->run_list);
+	if (list_empty(array->queue + old_prio))
+		__clear_bit(old_prio, array->bitmap);
+	
+	sched_info_queued(p);
+	list_add_tail(&p->run_list, array->queue + p->prio);
+	__set_bit(p->prio, array->bitmap);
+	p->array = array;
+}

/*
* Put task to the end of the run list without the overhead of dequeue
* followed by enqueue.

kernel/sched.c +13 -3

@@ -2668,7 +2690,7 @@
 	struct list_head *queue;
 	unsigned long long now;
 	unsigned long run_time;
-	int cpu, idx;
+	int cpu, idx, prio;
 
 	/*
 	 * Test if we are atomic.  Since do_exit() needs to call into

@@ -2787,9 +2809,19 @@
 			delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
 
 		array = next->array;
-		dequeue_task(next, array);
+		prio = next->prio;
 		recalc_task_prio(next, next->timestamp + delta);
-		enqueue_task(next, array);
+		
+		if (unlikely(prio != next->prio))
+		{
+			change_queue_task(next, array, prio);
+			schedstat_inc(rq, sched_prio_changed);
+		}
+		else
+		{
+			requeue_task(next, array);
+			schedstat_inc(rq, sched_prio_unchanged);
+		}
 	}
 	next->activated = 0;

switch_tasks:
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Hi Chen,
With the added branch and the extra icache footprint, it isn't clear that this would be a win.

Also, you didn't say where your statistics came from (what workload).

So you really need to start by demonstrating some increase on some workload.

Also, minor comments on the patch: please work against mm kernels, please follow
kernel coding style, and don't change schedstat output format in the same patch
(makes it easier for those with schedstat parsing tools).

Quoted 6 lines

Hi Chen,
With the added branch and the extra icache footprint, it isn't clear that this would be a win.

Also, you didn't say where your statistics came from (what workload).

Quoted 8 lines

So you really need to start by demonstrating some increase on some workload.

Also, minor comments on the patch: please work against mm kernels, please follow
kernel coding style, and don't change schedstat output format in the same patch
(makes it easier for those with schedstat parsing tools).

Hi Nick,

Thank you very much for your comments. This is the first time of my kernel hacking. I will reduce the lines of changes as much as possible. As regard to the statistics, there are just count, ie, the total number of priority-recalculations vs. the number of priority changed from the former recalculation.

Quoted 6 lines

Hi Chen,
With the added branch and the extra icache footprint, it isn't clear that this would be a win.

Also, you didn't say where your statistics came from (what workload).

Quoted 9 lines

So you really need to start by demonstrating some increase on some workload.

Also, minor comments on the patch: please work against mm kernels, please follow
kernel coding style, and don't change schedstat output format in the same patch
(makes it easier for those with schedstat parsing tools).

Hi Nick,

Thank you very much for your comments. This is the first time of my kernel hacking. I will reduce the lines of changes as much as possible. As regard to the statistics, there are just count, ie, the total number of priority-recalculations vs. the number of priority changed from the former recalculation.

I minimized my patch and against to 2.6.12-rc4 this time, see below.

The new schedstat fields are for the test propose only, so I removed them completedly from patch. Theoritically, requeue_task() is always cheaper than dequeue_task() followed by enqueue_task(). So, if 99% of priority recalculation trigger requeue_task(), it will save.

In addition, my load is to build the kernel, which took around 30 minutes with around 30% CPU usage on 2x2 processors (duel processors with HT enable).
Here is the statistics:

CPU0: priority_changed (669 times), priority_unchanged(335,138 times)
CPU1: priority_changed (784 times), priority_unchanged(342,419 times)
CPU2: priority_changed (782 times), priority_unchanged(283,494 times)
CPU3: priority_changed (872 times), priority_unchanged(365,865 times)

Thanks,
-chen

/*=====Patch=====*/

kernel/sched.c +3 -2

@@ -2613,7 +2613,7 @@
 	struct list_head *queue;
 	unsigned long long now;
 	unsigned long run_time;
-	int cpu, idx;
+	int cpu, idx, prio;
 
 	/*
 	 * Test if we are atomic.  Since do_exit() needs to call into

@@ -2735,9 +2735,17 @@
 			delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
 
 		array = next->array;
-		dequeue_task(next, array);
+		prio = next->prio;
+		
 		recalc_task_prio(next, next->timestamp + delta);

Quoted 12 lines · chen Shang

I minimized my patch and against to 2.6.12-rc4 this time, see below.

The new schedstat fields are for the test propose only, so I removed them completedly from patch. Theoritically, requeue_task() is always cheaper than dequeue_task() followed by enqueue_task(). So, if 99% of priority recalculation trigger requeue_task(), it will save.

In addition, my load is to build the kernel, which took around 30 minutes with around 30% CPU usage on 2x2 processors (duel processors with HT enable).
Here is the statistics:

Quoted 4 lines

CPU0: priority_changed (669 times), priority_unchanged(335,138 times)
CPU1: priority_changed (784 times), priority_unchanged(342,419 times)
CPU2: priority_changed (782 times), priority_unchanged(283,494 times)
CPU3: priority_changed (872 times), priority_unchanged(365,865 times)

OK that gives you a good grounds to look at the patch, but _performance_ improvement is what is needed to get it included.

I minimized my patch and against to 2.6.12-rc4 this time, see below.

Quoted 1 line · chen Shang

I minimized my patch and against to 2.6.12-rc4 this time, see below.

looks good - i've done some small style/whitespace cleanups and renamed prio to old_prio, patch against -rc4 below.

Quoted 5 lines · Ingo Molnar

Quoted 1 line · chen Shang

I minimized my patch and against to 2.6.12-rc4 this time, see below.

looks good - i've done some small style/whitespace cleanups and renamed prio to old_prio, patch against -rc4 below.

We should inline requeue_task as well.

Quoted 13 lines · Nick Piggin

Quoted 12 lines · chen Shang

I minimized my patch and against to 2.6.12-rc4 this time, see below.

The new schedstat fields are for the test propose only, so I removed them completedly from patch. Theoritically, requeue_task() is always cheaper than dequeue_task() followed by enqueue_task(). So, if 99% of priority recalculation trigger requeue_task(), it will save.

In addition, my load is to build the kernel, which took around 30 minutes with around 30% CPU usage on 2x2 processors (duel processors with HT enable).
Here is the statistics:

Quoted 7 lines

Quoted 4 lines

CPU0: priority_changed (669 times), priority_unchanged(335,138 times)
CPU1: priority_changed (784 times), priority_unchanged(342,419 times)
CPU2: priority_changed (782 times), priority_unchanged(283,494 times)
CPU3: priority_changed (872 times), priority_unchanged(365,865 times)

OK that gives you a good grounds to look at the patch, but _performance_ improvement is what is needed to get it included.

If you end up using requeue_task() in the fast path and it is hit frequently with your code you'll need to modify requeue_task to be inline as well. Currently it is hit only via sched_yield and once every 10 scheduler ticks which is why it is not inline. The performance hit will be demonstrable if it is hit in every schedule()

Cheers,
Con

Quoted 8 lines · Con Kolivas

Quoted 5 lines · Ingo Molnar

Quoted 1 line · chen Shang

I minimized my patch and against to 2.6.12-rc4 this time, see below.

looks good - i've done some small style/whitespace cleanups and renamed prio to old_prio, patch against -rc4 below.

We should inline requeue_task as well.

yeah.

Acked-by Ingo Molnar <[email protected]>

Ingo

unforunately, dequeue_task does not accept the third parameter to make adjustment. Personally, I feel it's good to add extra function as my first version of patch to combine dequeue and enqueue together. Reasons as following:
1) adding the third parameter to dequeue_task() would cause other places' code change;
2) for schedule functions, performance is the first consideration. Notice both dequeue_task() and enqueue_task() are NOT inline. Combining those two in one saves one function call overhead;

the real problem comes from recalc_task_prio() having a side-effect, which makes requeueing of tasks harder. The solution is to return the prio from recalc_task_prio() - see the tested patch below. Agreed?

Ingo

--

micro-optimize task requeueing in schedule() & clean up recalc_task_prio().

kernel/sched.c renamed from kernel/sched.c.orig +12 -7

@@ -675,7 +675,7 @@ static inline void __activate_idle_task(
        rq->nr_running++;
 }
 
-static void recalc_task_prio(task_t *p, unsigned long long now)
+static int recalc_task_prio(task_t *p, unsigned long long now)
 {
        /* Caller must always ensure 'now >= p->timestamp' */
        unsigned long long __sleep_time = now - p->timestamp;

@@ -734,7 +734,7 @@ static void recalc_task_prio(task_t *p,
                }
        }
 
-       p->prio = effective_prio(p);
+       return effective_prio(p);
 }
 
 /*

@@ -757,7 +757,7 @@ static void activate_task(task_t *p, run
        }
 #endif
 
-       recalc_task_prio(p, now);
+       p->prio = recalc_task_prio(p, now);
 
        /*
         * This checks to make sure it's not an uninterruptible task

@@ -2751,7 +2751,7 @@ asmlinkage void __sched schedule(void)
        struct list_head *queue;
        unsigned long long now;
        unsigned long run_time;
-       int cpu, idx;
+       int cpu, idx, new_prio;
 
        /*
         * Test if we are atomic.  Since do_exit() needs to call into

@@ -2873,9 +2873,14 @@ go_idle:
                        delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
 
                array = next->array;
-               dequeue_task(next, array);
-               recalc_task_prio(next, next->timestamp + delta);
-               enqueue_task(next, array);
+               new_prio = recalc_task_prio(next, next->timestamp + delta);
+
+               if (unlikely(next->prio != new_prio)) {
+                       dequeue_task(next, array);
+                       next->prio = new_prio;
+                       enqueue_task(next, array);
+               } else
+                       requeue_task(next, array);
        }
        next->activated = 0;
 switch_tasks: