[Xenomai-core] [RFC][PATCH] optimise wakeup order in xnsynch_flush

[Xenomai-core] [RFC][PATCH] optimise wakeup order in xnsynch_flush

[Jan Kiszka]

[-- Attachment #1.1: Type: text/plain, Size: 977 bytes --]

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

[-- Attachment #1.2: reverse-xnsynch_flush.patch --]
[-- Type: text/plain, Size: 1598 bytes --]

Index: include/nucleus/queue.h
===================================================================
--- include/nucleus/queue.h	(revision 1561)
+++ include/nucleus/queue.h	(working copy)
@@ -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);
Index: ksrc/nucleus/synch.c
===================================================================
--- ksrc/nucleus/synch.c	(revision 1561)
+++ ksrc/nucleus/synch.c	(working copy)
@@ -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;

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

[Xenomai-core] Re: [RFC][PATCH] optimise wakeup order in xnsynch_flush

[Jan Kiszka]

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

Jan Kiszka wrote:
> 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...

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]