4.11 Branching To Do

[Sebastian Huber]

Hello Gedare,

On 06/11/14 14:57, Gedare Bloom wrote:
> 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.

yes, I already have a patch for this, but didn't run timing tests so far.

>
>> 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?)

Ok.

>
>> 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.

Yes, this big RB_GENERATE_INTERNAL() macro should be probably split up.

>
>> 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.

Ok, I have a look at this, once the bug tracker is up again.

>
>> 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.

Its also described here:

http://lwn.net/Articles/500355/

As far as I understand this it is just an addition of generic insert/search 
functions using a function pointer for comparison.

I have no numbers yet, but the Linux approach seems to be the best to me. 
Having the the global rb_insert_color() and rb_erase() functions for all trees 
is good for instruction cache efficiency and testing.  The custom insert/search 
gives you a lot of flexibility.  You can also add generic insert/search as 
described above.

>
> 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).

Yes, I a curious how this looks like on architectures other than x86.

>
> -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


-- 
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.