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