New Wiki Page -- RTEMS Algorithm Complexity

[Pavel Pisa]

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.

> 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