Misc on RBTree Thread Queue Priority Discipline Changes

Sebastian Huber sebastian.huber at embedded-brains.de
Thu Jul 10 07:41:55 UTC 2014

Hello Joel,

I think it is good approach to use a RB tree for the priority queues.  Reducing 
the size of non-thread objects is always beneficial, since you usually have a 
lot of them.  The new network stack uses for example more than 2000 semaphores, 
but only a hand full of tasks.

It might be interesting to compare the performance of the two priority queue 
implementations (existing and RB tree based).

The RB tree implementation itself has room for improvement.  You can for 
example store the color in the lower bits of one of the pointers.  This is how 
other RB tree implementations do this (its a size reduction of 25%).  Also the 
RB tree control is pretty huge.  The compare function and is unique indicator 
can easily be converted to function parameters (its a size reduction of 33%). 
The max pointer may be avoided also.  We can do something like this

struct RBTree_Control:
   RBTree_Root             Root
   RBTree_Compare_function compare_function
   bool                    is_unique

   base_op(ctrl.Root, ctrl.compare_function, ctrl.is_unique)

Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber at embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

More information about the devel mailing list