New Wiki Page -- RTEMS Algorithm Complexity

Thu Feb 2 12:20:55 UTC 2006

Pavel Pisa wrote:

>Hello Joel and others,
>
>I cannot hold myself to not reply to this document
>and offer some thoughts. I am totally out
>of time for this and next week, so I would not find probably
>time to answer questions now, but then I would be extremely happy
>to discuss more of these issues and some of my and my colleagues
>code and if you and some other core team people like
>some of my code and ideas I offer help to integrate
>them into RTEMS. I cannot do it myself solely, because
>I am not able to find time for that. I can try to find some
>students, but it is not probable, that there would be some
>big help from them.
>
>  
>

With you going out of town, I will hold off comments except to say that
RTEMS is VERY modular and that replacing a data structure in the
SuperCore should be fairly self-contained.  Also I would be happy to
see any O(n) algorithm replaced.

We need to up with come up with an acceptance plan for replacing these.
Nuno Costa got me thinking down this path.  He wrote a series of
POSIX API Timing tests which he graphed under different system
loads.  His tests should be part of the acceptable criteria as well.
Others like Till Straumann and Greg Menke have done inhouse
timing analysis and it would be good to get updates on those.

Looks promising.  I will try to read up on the algorithms while you
are out and update the Wiki with links and thoughts.

--joel

>>SuperCore
>>Insertion of Message by Priority
>>
>>When priority ordering of messages is used, the insertion is into
>>a simple list and is O(n) where n is the number of messages pending. 
>>    
>>
>
>GAVL can solve this
>
>insert    = search O(log(n)),
>            max one re-ballance O(1) with max O(log(n)) heights update.
>
>cut first = O(log(n)) find first and O(1) cut, zero re-balances
>            O(log(n)) heights update
>   First Last Enhanced Speed (FLES) alternative
>            O(1) find first and O(1) cut, zero rebalance
>            O(log(n)) heights update and next prepare
>
>premature delete = O(1) detach, O(log(n)) heights update
>            and max O(log(n)) updates and re-balances,
>            may be, it is possible to prove, that count of re-balances
>            is lower or can be decreased. It is possible to omit
>            re-balances at all, but AVL tree properties would be lost
>            => height is not in range from
>               log2(n+1)+1 to 1.44*log2(n+2)-0.328+1.
>            The +1 one in GAVL is cost  for zero re-balanced
>            cut first operation.
>
>More about this code is on my page
>
>  http://cmp.felk.cvut.cz/~pisa/#ulut
>
>There is no problem with RTEMS compatible license, in the fact uLUt
>is extensively used in our RTEMS based application for drivers and
>GUI code.
>
>Code is used in more components from OCERA project http://www.ocera.org
>and proven to be extremely stable.
>It is used even in http://ulan.sourceforge.net/ and SuiTk sources.
>GAVL code doesnot need any dynamic memory allocations and it
>significantly outperforms even heap-tree algorithm with preallocated
>array for all elements (Heap tree is suggested solution
>for priority queues in the classic theory texts).
>
>GAVL is result of my personal rethinking of AVL algorithm.
>My C implementation can even ensure type safety, but macro magic
>can be too much for you. Base of algorithm can be rewritten from
>generic code to one purpose one. In the fact "gcc -E" does the work
>and I have ported this way with some manual simplifications
>some uLUt code even on 8051 based chips.
>
>  
>
>>Watchdog Timer
>>Insertion of a Timer
>>
>>Timers are managed as a delta chain. Insertion is O(n) where n
>>is the number of timers on the chain (e.g. active). 
>>    
>>
>
>See GAVL and Htimer
>
>Based on FLES GAVL variant, same timing.
>
>Linux/Igno Molnar decided to go through RB-Tree for high resolution
>timers, but it has not cut-first primitive and I believe, that GAVL
>can outperform this in all aspects except premature timer delete.
>AVL height is even lower than RB-tree there.
>
>  
>
>>Heap
>>
>>The heap is used for variable memory allocation.
>>
>>Memory Allocation
>>
>>The list of free blocks is managed as an unsorted listed.
>>Allocating a memory block requires a linear search of all free
>>blocks until one large enough to satisfy the request is located.  
>>    
>>
>
>TLSF dynamic storage allocator
>
>http://rtportal.upv.es/rtmalloc/allocators/tlsf/index.shtml
>
>This is nice approach, O(1) allocate, O(1) delete. Needs to do
>find first bit set to compute log of size and then two find first
>bit set instructions and atomic double linked list delete for allocate.
>
>Only log computation and some set bit and list insert
>for free. Fragmentation is kept on reasonable level
>
>As for license, I know the people and I expect no problems.
>Even rewrite of the code onto RTEMS primitives from scratch
>is possible. Idea is so clean, simple but unique that there
>is no problem to reimplement it.
>
>As for my terrible endless fight with MX1 MMC/SD, I have got
>RTEMS driver port stable without DMA. There is still some
>minor, but fatal, issue with DMA which I desperately need to solve.
>My last version works stable in most cases, but sometimes
>it breaks in the commands around data write.
>Everybody liking to step into crusaders coalition against
>this enemy is invited.
>
>Best wishes
>
>                    Pavel Pisa
>        e-mail:     pisa at cmp.felk.cvut.cz
>        www:        http://cmp.felk.cvut.cz/~pisa
>        university: http://rtlab.felk.cvut.cz/
>        company:    http://www.pikron.com
>  
>