Changes between Version 4 and Version 5 of FAQ/AlgorithmicComplexity


Ignore:
Timestamp:
02/03/06 07:59:57 (18 years ago)
Author:
JoelSherrill
Comment:

/* Insertion of a Timer */ Add Pavel's notes on GAVL and Htimer.

Legend:

Unmodified
Added
Removed
Modified

  • FAQ/AlgorithmicComplexity

    v4 v5  
    6666
    6767Timers are managed as a delta chain.  Insertion is O(n) where n is the number of timers on the chain (e.g. active).
     68
     69 ==Pavel Pisa's Suggestion====
     70
     71http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html
     72
     73See GAVL and Htimer.  Based on FLES GAVL variant, same timing.
     74
     75Linux/Igno Molnar decided to go through RB-Tree for high resolution
     76timers, but it has not cut-first primitive and I believe, that GAVL
     77can outperform this in all aspects except premature timer delete.
     78AVL height is even lower than RB-tree there.
    6879= Heap =
    6980
    … …  
    7182= Memory Allocation =
    7283
    73 The 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 
    75 This 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 
    79 This 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 
    83 Longer messages take longer to copy.
    84 
    85 ===Insertion of Message by Priority===
    86 
    87 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.
    88 
    89 ====GAVL===
    90 
    91 From Pavel Pisa as posted to the RTEMS ML (http://www.rtems.com/ml/rtems-users/2006/february/msg00006.html).
    92 
    93 GAVL can solve this
    94 
    95 insert    = search O(log(n)),
    96             max one re-ballance O(1) with max O(log(n)) heights update.
    97 
    98 cut 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 
    104 premature 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 
    114 More about this code is on my page: http://cmp.felk.cvut.cz/~pisa/#ulut
    115 
    116 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.
    117 
    118 Code is used in more components from OCERA project http://www.ocera.org
    119 and proven to be extremely stable.
    120 It is used even in http://ulan.sourceforge.net/ and SuiTk sources.
    121 GAVL code doesnot need any dynamic memory allocations and it
    122 significantly outperforms even heap-tree algorithm with preallocated
    123 array for all elements (Heap tree is suggested solution
    124 for priority queues in the classic theory texts).
    125 
    126 GAVL is result of my personal rethinking of AVL algorithm.
    127 My C implementation can even ensure type safety, but macro magic
    128 can be too much for you. Base of algorithm can be rewritten from
    129 generic code to one purpose one. In the fact "gcc -E" does the work
    130 and I have ported this way with some manual simplifications
    131 some uLUt code even on 8051 based chips.
    132 
    133 ===Message Broadcast===
    134 
    135 Broadcasting 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 
    141 Timers 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 
    145 The heap is used for variable memory allocation.
    146 
    147 ===Memory Allocation===
    148 
    14984The 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.
    150 
    151 =Classic API=
     85= Classic API =
    15286
    15387
    … …  
    15892 *  Timer insertion (timer manager, delays, and timeouts)
    15993 *  Memory Allocation
    160 
    161 ==Region Manager==
    162 
    163 ===Freeing Memory===
     94= Region Manager =
     95= Freeing Memory =
    16496
    16597Although freeing memory is O(constant), freeing a large block of memory may result in the outstanding requests of multiple blocked tasks being satisfied.
    166 
    167 =POSIX API=
     98= POSIX API =
    16899
    169100The POSIX API inherits the following non-constant time algorithms from the SuperCode
    … …  
    172103 *  Priority based message insertion
    173104 *  Timer insertion (timer manager, delays, and timeouts)
     105= Message Queue Manager =
     106= mq_open =
    174107
    175 ==Message Queue Manager==
    176 
    177 ===mq_open===
     108There is a linear search for the message queue name.= mq_unlink =
    178109
    179110There is a linear search for the message queue name.
    180 ===mq_unlink===
     111= Semaphore Manager =
     112= sem_open =
    181113
    182 There is a linear search for the message queue name.
    183 
    184 ==Semaphore Manager==
    185 
    186 ===sem_open===
     114There is a linear search for the semaphore name.= sem_unlink =
    187115
    188116There is a linear search for the semaphore name.
    189 ===sem_unlink===
    190 
    191 There is a linear search for the semaphore name.
    192 
    193 ==Timer Manager==
    194 
    195 ===Timer Id Management===
     117= Timer Manager =
     118= Timer Id Management =
    196119
    197120There is a linear search of slots in a timer array.