4.11 Branching To Do

[Gedare Bloom]

On Thu, Nov 6, 2014 at 1:53 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> Hello,
>
> I have a new item for the list:
>
> Very desirable
> ==============
>
> + Since red-black trees are now used to implement the priority queues and
> they will play an important part in future SMP improvements I would like to
> do some performance measurements with alternative implementations.  I would
> like to compare
>
> 1. the RTEMS red-black tree implementation,
>
> 2. the RTEMS red-black tree implementation with the colour encoded in the
> parent pointer,
>
This is easy enough to implement, the tradeoff is size vs space. So
make sure to include that in your analysis.

> 3. the implementation from Eternally Confuzzled, see
> http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx,
>
I would avoid that implementation, I suspect it is theoretically flawed:
http://gedare-csphd.blogspot.com/2011/08/red-black-trees-bottom-up-or-top-down.html

That was a very simple test on x86_64 hardware, but I think the
results are likely to translate. Now, whether the scale difference
matters for RTEMS I am not so sure (how large are the trees going to
get?)

> 4. the BSD implementation <sys/tree.h>, and
>
This is probably the most compact code, but the macro-expansions cause
compiled-code bloat and must be used with some care. Be sure to
measure size effects.

> 5. the JFFS2 implementation (cpukit/libfs/src/jffs2/include/linux/rbtree.h),
> see http://lwn.net/Articles/184495/.
>
I have posted a modified version of RTEMS RBTree (long ago) in this
vein at PR 1891.

> I intend to use real hardware ARM, ColdFire, PowerPC and SPARC targets.
>
> Do we have other interesting red-black tree implementations?
>
Pavel posted about a generic tree framework:
http://permalink.gmane.org/gmane.os.rtems.devel/1327

I had some trouble getting inlining to work in the way that tree works
(in the short time I spent on it):
http://permalink.gmane.org/gmane.os.rtems.devel/1503

It is possible that working with the original author may be fruitful.
I don't know if this has had any movement in Linux.

There is also the option to use explicit left-right pointers instead
of the array we use. I did some experimenting, and gcc did not
optimize the direction array very well.
http://gedare-csphd.blogspot.com/2012/05/red-black-trees-redux-left-right.html

I can provide benchmark code given some time (of course funding can
make it appear faster).

-Gedare

> On 29/10/14 22:49, Joel Sherrill wrote:
>>
>> Hi
>>
>> Since we are long over due for a release.  I can count 4 new children
>> and a grandchild among the core developers since 4.10. :)
>>
>> Here is what I have off the top of my head:
>>
>> Mandatory
>> ==========
>> + Tool version selection
>>     - Likely gcc 4.9 on almost all targets.
>>     - binutils last release
>>     - newlib TBD
>>     - GDB could be new release
>>
>> + BeagleBoard BSP added
>>
>> + Run-Time Loader merged and tested
>>
>> + Visit the Getting Started manual. It is dated.
>>
>> + Push a bit more on warnings.
>>     - Three BSPs represent bulk of remaining warnings
>>
>> Very desirable
>> =============
>> + x86 context switch SMP handoff logic
>>
>> + Pi GSOC Code merged.
>>
>> Anything else?
>>
>
>
> --
> 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.
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel