On Thu, Nov 6, 2014 at 1:53 AM, Sebastian Huber <sebastian.hu...@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.hu...@embedded-brains.de > PGP : Public key available on request. > > Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG. > _______________________________________________ > devel mailing list > devel@rtems.org > http://lists.rtems.org/mailman/listinfo/devel _______________________________________________ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
