… | |
… | |
2255 | |
2255 | |
2256 | In this section the complexities of (many of) the algorithms used inside |
2256 | In this section the complexities of (many of) the algorithms used inside |
2257 | libev will be explained. For complexity discussions about backends see the |
2257 | libev will be explained. For complexity discussions about backends see the |
2258 | documentation for C<ev_default_init>. |
2258 | documentation for C<ev_default_init>. |
2259 | |
2259 | |
|
|
2260 | All of the following are about amortised time: If an array needs to be |
|
|
2261 | extended, libev needs to realloc and move the whole array, but this |
|
|
2262 | happens asymptotically never with higher number of elements, so O(1) might |
|
|
2263 | mean it might do a lengthy realloc operation in rare cases, but on average |
|
|
2264 | it is much faster and asymptotically approaches constant time. |
|
|
2265 | |
2260 | =over 4 |
2266 | =over 4 |
2261 | |
2267 | |
2262 | =item Starting and stopping timer/periodic watchers: O(log skipped_other_timers) |
2268 | =item Starting and stopping timer/periodic watchers: O(log skipped_other_timers) |
2263 | |
2269 | |
2264 | This means that, when you have a watcher that triggers in one hour and |
2270 | This means that, when you have a watcher that triggers in one hour and |
… | |
… | |
2270 | That means that for changing a timer costs less than removing/adding them |
2276 | That means that for changing a timer costs less than removing/adding them |
2271 | as only the relative motion in the event queue has to be paid for. |
2277 | as only the relative motion in the event queue has to be paid for. |
2272 | |
2278 | |
2273 | =item Starting io/check/prepare/idle/signal/child watchers: O(1) |
2279 | =item Starting io/check/prepare/idle/signal/child watchers: O(1) |
2274 | |
2280 | |
2275 | These just add the watcher into an array or at the head of a list. If |
2281 | These just add the watcher into an array or at the head of a list. |
2276 | the array needs to be extended libev needs to realloc and move the whole |
|
|
2277 | array, but this happen asymptotically less and less with more watchers, |
|
|
2278 | thus amortised O(1). |
|
|
2279 | |
|
|
2280 | =item Stopping check/prepare/idle watchers: O(1) |
2282 | =item Stopping check/prepare/idle watchers: O(1) |
2281 | |
2283 | |
2282 | =item Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE)) |
2284 | =item Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE)) |
2283 | |
2285 | |
2284 | These watchers are stored in lists then need to be walked to find the |
2286 | These watchers are stored in lists then need to be walked to find the |