Changes between Version 14 and Version 15 of FAQ/AlgorithmicComplexity
- Timestamp:
- 11/23/14 06:42:26 (9 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
FAQ/AlgorithmicComplexity
v14 v15 6 6 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 occurring during the execution of a call. 7 7 8 = SuperCore =8 = !SuperCore = 9 9 10 10 11 This section presents the non-constant order algorithms found in the SuperCore. The SuperCoreis used to implement all supported RTEMS APIs so they inherit these core behaviours.11 This 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. 12 12 13 13 = Message Queue Handler = … … 19 19 20 20 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. 21 == Pavel Pisa's Sugestion == 21 22 == Pavel Pisa's Suggestion == 22 23 23 24 Posted to the RTEMS ML (http://lists.rtems.org/pipermail/users/2006-February/014021.html). … … 73 74 == Pavel Pisa's Suggestion == 74 75 75 http:// www.rtems.org/ml/rtems-users/2006/february/msg00099.html76 http://lists.rtems.org/pipermail/users/2006-February/014021.html 76 77 77 78 See GAVL and Htimer. Based on FLES GAVL variant, same timing. 78 79 79 Linux /Igno Molnar decided to go through RB-Tree for high resolution80 Linux Igno Molnar decided to go through RB-Tree for high resolution 80 81 timers, but it has not cut-first primitive and I believe, that GAVL 81 82 can outperform this in all aspects except premature timer delete. 82 83 AVL height is even lower than RB-tree there. 84 83 85 = Heap = 84 86 85 87 The heap is used for variable memory allocation. 88 86 89 = Memory Allocation = 87 90 88 91 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. 92 89 93 == Pavel Pisa's Suggestion == 90 94 91 Posted as http:// www.rtems.com/ml/rtems-users/2006/february/msg00099.html95 Posted as http://lists.rtems.org/pipermail/users/2006-February/014021.html 92 96 93 97 TLSF dynamic storage allocator … … 106 110 is possible. Idea is so clean, simple but unique that there 107 111 is no problem to re-implement it. 112 108 113 = Semaphores with Simple Priority Inheritance = 109 114 … … 119 124 When 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). 120 125 The 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 121 127 = Classic API = 122 128 … … 132 138 133 139 Although freeing memory is O(constant), freeing a large block of memory may result in the outstanding requests of multiple blocked tasks being satisfied. 140 134 141 = POSIX API = 135 142 … … 158 165 '''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. 159 166 160 '''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.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.