Skip to contentSkip to conversation

optimise wakeup order in xnsynch_flush

RFC PATCH In review Jan Kiszka 1 participant 2 messages Sep 7, 2006

lore
Share & tools
lore

Jan Kiszka

author
#0 lore raw

RFC PATCH 1/1 optimise wakeup order in xnsynch_flush

Hi,

this is so far a mind experiment combined with an untested patch:

[Assuming priority lists, the following is irrelevant for O(1) sched-queues]

Consider we have some bulk of threads with varying priorities waiting on a xnsynch object. Typically, they are queued in priority order, the highest prio thread at the head. When we wake them up all at once via xnsynch_flush, we iterate from high to low prio threads.

Waking up includes inserting those threads in the ready queue(s), again the highest prio thread first. On wake up of the first waiting thread we will only have to skip those threads in the ready queue that have higher priorities. For the second thread we already have to skip the first one as well on insert if it isn't of the same priority. One may continue this workflow...

Suggestion: Wouldn't it be more efficient to iterate the waiter queue in ascending order? Should come at no costs and save a few cycles once in a while.

Jan

nucleus/queue.h +18 -0
Index: include/nucleus/queue.h
===================================================================
@@ -242,6 +242,19 @@ static inline xnholder_t *popq (xnqueue_
     return nextholder;
 }
 
+static inline xnholder_t *lastq (xnqueue_t *qslot)
+{
+    xnholder_t *holder = qslot->head.last;
+    return holder == &qslot->head ? NULL : holder;
+}
+
+static inline xnholder_t *getlastq (xnqueue_t *qslot)
+{
+    xnholder_t *holder = lastq(qslot);
+    if (holder) removeq(qslot,holder);
+    return holder;
+}
+
 static inline int countq (xnqueue_t *qslot)
 {
     return qslot->elems;
@@ -437,6 +450,11 @@ static inline xnpholder_t *poppq (xnpque
     return (xnpholder_t *)popq(&pqslot->pqueue,&holder->plink);
 }
 
+static inline xnpholder_t *getlastpq (xnpqueue_t *pqslot)
+{
+    return (xnpholder_t *)getlastq(&pqslot->pqueue);
+}
+
 static inline int countpq (xnpqueue_t *pqslot)
 {
     return countq(&pqslot->pqueue);
nucleus/synch.c +1 -1
Index: ksrc/nucleus/synch.c
===================================================================
@@ -525,7 +525,7 @@ int xnsynch_flush(xnsynch_t *synch, xnfl
 
 	status = emptypq_p(&synch->pendq) ? XNSYNCH_DONE : XNSYNCH_RESCHED;
 
-	while ((holder = getpq(&synch->pendq)) != NULL) {
+	while ((holder = getlastpq(&synch->pendq)) != NULL) {
 		xnthread_t *sleeper = link2thread(holder, plink);
 		__setbits(sleeper->status, reason);
 		sleeper->wchan = NULL;
author
#1 lore raw
Quoted 11 lines · Jan Kiszka

Hi,

this is so far a mind experiment combined with an untested patch:

[Assuming priority lists, the following is irrelevant for O(1) sched-queues]

Consider we have some bulk of threads with varying priorities waiting on a xnsynch object. Typically, they are queued in priority order, the highest prio thread at the head. When we wake them up all at once via xnsynch_flush, we iterate from high to low prio threads.

Quoted 6 lines

Waking up includes inserting those threads in the ready queue(s), again the highest prio thread first. On wake up of the first waiting thread we will only have to skip those threads in the ready queue that have higher priorities. For the second thread we already have to skip the first one as well on insert if it isn't of the same priority. One may continue this workflow...

Forget about this, there was a sign mistake: ready-queue walk already takes place in the reverse order (from lower to higher prios), thus with minimal iterations for the sketched scenario. Time to go home...

Jan