Changes between Version 3 and Version 4 of FAQ/AlgorithmicComplexity


Ignore:
Timestamp:
Feb 3, 2006, 7:58:02 AM (14 years ago)
Author:
JoelSherrill
Comment:

/* Insertion of Message by Priority */ Added GAVL

Legend:

Unmodified
Added
Removed
Modified
  • FAQ/AlgorithmicComplexity

    v3 v4  
    1616
    1717When 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.
     18== GAVL===
     19
     20From Pavel Pisa as posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html).
     21
     22GAVL can solve this
     23
     24insert    = search O(log(n)),
     25            max one re-ballance O(1) with max O(log(n)) heights update.
     26
     27cut first = O(log(n)) find first and O(1) cut, zero re-balances
     28            O(log(n)) heights update
     29   First Last Enhanced Speed (FLES) alternative
     30            O(1) find first and O(1) cut, zero rebalance
     31            O(log(n)) heights update and next prepare
     32
     33premature delete = O(1) detach, O(log(n)) heights update
     34            and max O(log(n)) updates and re-balances,
     35            may be, it is possible to prove, that count of re-balances
     36            is lower or can be decreased. It is possible to omit
     37            re-balances at all, but AVL tree properties would be lost
     38            => height is not in range from
     39               log2(n+1)+1 to 1.44*log2(n+2)-0.328+1.
     40            The +1 one in GAVL is cost  for zero re-balanced
     41            cut first operation.
     42
     43More about this code is on my page: http://cmp.felk.cvut.cz/~pisa/#ulut
     44
     45There is no problem with RTEMS compatible license, in the fact uLUt is extensively used in our RTEMS based application for drivers and GUI code.
     46
     47Code is used in more components from OCERA project http://www.ocera.org
     48and proven to be extremely stable.
     49It is used even in http://ulan.sourceforge.net/ and SuiTk sources.
     50GAVL code doesnot need any dynamic memory allocations and it
     51significantly outperforms even heap-tree algorithm with preallocated
     52array for all elements (Heap tree is suggested solution
     53for priority queues in the classic theory texts).
     54
     55GAVL is result of my personal rethinking of AVL algorithm.
     56My C implementation can even ensure type safety, but macro magic
     57can be too much for you. Base of algorithm can be rewritten from
     58generic code to one purpose one. In the fact "gcc -E" does the work
     59and I have ported this way with some manual simplifications
     60some uLUt code even on 8051 based chips.
    1861= Message Broadcast =
    1962
     
    2871= Memory Allocation =
    2972
     73The list of free blocks is managed as an unsorted listed.  Allocating a memory block requires a linear search of a ==MS is composed of multiple software classes and is layered.  Each software class has its own execution characteristics.  Although every effort was made to ensure that after an instance of an object is created, that as many operations as possible execute in a fixed length of time.  In this light, the designers of RTEMS focused on the algorithms used and their algorithmic complexity.  Ideally, all algorithms in RTEMS would be O(constant) which is also know as stable.  However some algorithms have variations based upon what they are doing (e.g. blocking or non-blocking) or how many instances of an object are in the system.  If the algorithm varies in execution time based upon the number of instances of an object, it is said to be O(n) where n is the number of instances.
     74
     75This page attempts to capture information regarding the algorithmic complexity of the algorithms in RTEMS with a focus on those that are not O(constant).  We do not include operations that create or delete objects.  We will ignore variations due to a particular call blocking instead of a non-blocking since it is obvious blocking takes longer.  We will also ignore variations caused by an interrupt occuring during the execution of a call.
     76= SuperCore =
     77
     78
     79This section presents the non-constant order algorithms found in the SuperCore.  The SuperCore is used to implement all supported RTEMS APIs so they inherit these core hahaviors.
     80= Message Queue Handler =
     81=  ==Variable Length Messages===
     82
     83Longer messages take longer to copy.
     84
     85===Insertion of Message by Priority===
     86
     87When 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.
     88
     89====GAVL===
     90
     91From Pavel Pisa as posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html).
     92
     93GAVL can solve this
     94
     95insert    = search O(log(n)),
     96            max one re-ballance O(1) with max O(log(n)) heights update.
     97
     98cut first = O(log(n)) find first and O(1) cut, zero re-balances
     99            O(log(n)) heights update
     100   First Last Enhanced Speed (FLES) alternative
     101            O(1) find first and O(1) cut, zero rebalance
     102            O(log(n)) heights update and next prepare
     103
     104premature delete = O(1) detach, O(log(n)) heights update
     105            and max O(log(n)) updates and re-balances,
     106            may be, it is possible to prove, that count of re-balances
     107            is lower or can be decreased. It is possible to omit
     108            re-balances at all, but AVL tree properties would be lost
     109            => height is not in range from
     110               log2(n+1)+1 to 1.44*log2(n+2)-0.328+1.
     111            The +1 one in GAVL is cost  for zero re-balanced
     112            cut first operation.
     113
     114More about this code is on my page: http://cmp.felk.cvut.cz/~pisa/#ulut
     115
     116There is no problem with RTEMS compatible license, in the fact uLUt is extensively used in our RTEMS based application for drivers and GUI code.
     117
     118Code is used in more components from OCERA project http://www.ocera.org
     119and proven to be extremely stable.
     120It is used even in http://ulan.sourceforge.net/ and SuiTk sources.
     121GAVL code doesnot need any dynamic memory allocations and it
     122significantly outperforms even heap-tree algorithm with preallocated
     123array for all elements (Heap tree is suggested solution
     124for priority queues in the classic theory texts).
     125
     126GAVL is result of my personal rethinking of AVL algorithm.
     127My C implementation can even ensure type safety, but macro magic
     128can be too much for you. Base of algorithm can be rewritten from
     129generic code to one purpose one. In the fact "gcc -E" does the work
     130and I have ported this way with some manual simplifications
     131some uLUt code even on 8051 based chips.
     132
     133===Message Broadcast===
     134
     135Broadcasting a message results in every task currently blocking on a particular message queue waiting for a message to receive the same message.  The time required to execute this service is O(n) where n is the number of blocked tasks.
     136
     137==Watchdog Timer==
     138
     139===Insertion of a Timer===
     140
     141Timers are managed as a delta chain.  Insertion is O(n) where n is the number of timers on the chain (e.g. active).
     142
     143==Heap==
     144
     145The heap is used for variable memory allocation.
     146
     147===Memory Allocation===
     148
    30149The 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.
    31 = Classic API =
     150
     151=Classic API=
    32152
    33153
     
    38158 *  Timer insertion (timer manager, delays, and timeouts)
    39159 *  Memory Allocation
    40 = Region Manager =
    41 = Freeing Memory =
     160
     161==Region Manager==
     162
     163===Freeing Memory===
    42164
    43165Although freeing memory is O(constant), freeing a large block of memory may result in the outstanding requests of multiple blocked tasks being satisfied.
    44 = POSIX API =
     166
     167=POSIX API=
    45168
    46169The POSIX API inherits the following non-constant time algorithms from the SuperCode
     
    49172 *  Priority based message insertion
    50173 *  Timer insertion (timer manager, delays, and timeouts)
    51 = Message Queue Manager =
    52 = mq_open =
    53 
    54 There is a linear search for the message queue name.= mq_unlink =
     174
     175==Message Queue Manager==
     176
     177===mq_open===
    55178
    56179There is a linear search for the message queue name.
    57 = Semaphore Manager =
    58 = sem_open =
    59 
    60 There is a linear search for the semaphore name.= sem_unlink =
     180===mq_unlink===
     181
     182There is a linear search for the message queue name.
     183
     184==Semaphore Manager==
     185
     186===sem_open===
    61187
    62188There is a linear search for the semaphore name.
    63 = Timer Manager =
    64 = Timer Id Management =
     189===sem_unlink===
     190
     191There is a linear search for the semaphore name.
     192
     193==Timer Manager==
     194
     195===Timer Id Management===
    65196
    66197There is a linear search of slots in a timer array.