Changes between Version 14 and Version 15 of FAQ/AlgorithmicComplexity


Ignore:
Timestamp:
Nov 23, 2014, 6:42:26 AM (5 years ago)
Author:
Chris Johns
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • FAQ/AlgorithmicComplexity

    v14 v15  
    66This 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 occurring during the execution of a call.
    77
    8 = SuperCore =
     8= !SuperCore =
    99
    1010
    11 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 behaviours.
     11This section presents the non-constant order algorithms found in the [http://docs.rtems.org/doxygen/cpukit/html/ SuperCore].  The [http://docs.rtems.org/doxygen/cpukit/html/ SuperCore] is used to implement all supported RTEMS APIs so they inherit these core behaviours.
    1212
    1313= Message Queue Handler =
     
    1919
    2020When 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.
    21 == Pavel Pisa's Sugestion ==
     21
     22== Pavel Pisa's Suggestion ==
    2223
    2324Posted to the RTEMS ML (http://lists.rtems.org/pipermail/users/2006-February/014021.html).
     
    7374== Pavel Pisa's Suggestion ==
    7475
    75 http://www.rtems.org/ml/rtems-users/2006/february/msg00099.html
     76http://lists.rtems.org/pipermail/users/2006-February/014021.html
    7677
    7778See GAVL and Htimer.  Based on FLES GAVL variant, same timing.
    7879
    79 Linux/Igno Molnar decided to go through RB-Tree for high resolution
     80Linux  Igno Molnar decided to go through RB-Tree for high resolution
    8081timers, but it has not cut-first primitive and I believe, that GAVL
    8182can outperform this in all aspects except premature timer delete.
    8283AVL height is even lower than RB-tree there.
     84
    8385= Heap =
    8486
    8587The heap is used for variable memory allocation.
     88
    8689= Memory Allocation =
    8790
    8891The 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.
     92
    8993== Pavel Pisa's Suggestion ==
    9094
    91 Posted as http://www.rtems.com/ml/rtems-users/2006/february/msg00099.html
     95Posted as http://lists.rtems.org/pipermail/users/2006-February/014021.html
    9296
    9397TLSF dynamic storage allocator
     
    106110is possible. Idea is so clean, simple but unique that there
    107111is no problem to re-implement it.
     112
    108113= Semaphores with Simple Priority Inheritance =
    109114
     
    119124When a thread blocks when trying to obtain a semaphore, it places itself in the table of the holder thread. This way, when the holder thread releases the semaphore, it can easily search through the table the "second" highest priority thread (the "first" highest priority thread will, in principle - unless it is suspended - obtain the semaphore).
    120125The downside of this approach is the memory increase: needs a 4*256 = 1KiB increase in the TCB for each thread. Since the minimum size for the stack for each thread is about 4 KiB, this value may not be too significant.
     126
    121127= Classic API =
    122128
     
    132138
    133139Although freeing memory is O(constant), freeing a large block of memory may result in the outstanding requests of multiple blocked tasks being satisfied.
     140
    134141= POSIX API =
    135142
     
    158165'''FIX:''' This is a bad implementation which was originally submitted by a user who did not understand the standard  pattern of object management.  This pattern requires objects be preallocated at system initialization time and object creation only removes one from an inactive object list.  Normally, RTEMS object Id to pointer translation is constant order so, this manager is fixable.
    159166
    160 '''UPDATE:''' As of 1 Feb 2006, JoelSherrill is testing a new implementation of POSIX timers which will not have O(n) object Id management.
     167'''UPDATE:''' As of 1 Feb 2006, Joel Sherrill is testing a new implementation of POSIX timers which will not have O(n) object Id management.