optimise wakeup order in xnsynch_flush
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
@@ -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 (xnpquereturn (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
@@ -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 ;
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