… | |
… | |
2404 | .SH "COMPLEXITIES" |
2404 | .SH "COMPLEXITIES" |
2405 | .IX Header "COMPLEXITIES" |
2405 | .IX Header "COMPLEXITIES" |
2406 | In this section the complexities of (many of) the algorithms used inside |
2406 | In this section the complexities of (many of) the algorithms used inside |
2407 | libev will be explained. For complexity discussions about backends see the |
2407 | libev will be explained. For complexity discussions about backends see the |
2408 | documentation for \f(CW\*(C`ev_default_init\*(C'\fR. |
2408 | documentation for \f(CW\*(C`ev_default_init\*(C'\fR. |
|
|
2409 | .Sp |
|
|
2410 | All of the following are about amortised time: If an array needs to be |
|
|
2411 | extended, libev needs to realloc and move the whole array, but this |
|
|
2412 | happens asymptotically never with higher number of elements, so O(1) might |
|
|
2413 | mean it might do a lengthy realloc operation in rare cases, but on average |
|
|
2414 | it is much faster and asymptotically approaches constant time. |
2409 | .RS 4 |
2415 | .RS 4 |
2410 | .IP "Starting and stopping timer/periodic watchers: O(log skipped_other_timers)" 4 |
2416 | .IP "Starting and stopping timer/periodic watchers: O(log skipped_other_timers)" 4 |
2411 | .IX Item "Starting and stopping timer/periodic watchers: O(log skipped_other_timers)" |
2417 | .IX Item "Starting and stopping timer/periodic watchers: O(log skipped_other_timers)" |
2412 | This means that, when you have a watcher that triggers in one hour and |
2418 | This means that, when you have a watcher that triggers in one hour and |
2413 | there are 100 watchers that would trigger before that then inserting will |
2419 | there are 100 watchers that would trigger before that then inserting will |
… | |
… | |
2416 | .IX Item "Changing timer/periodic watchers (by autorepeat, again): O(log skipped_other_timers)" |
2422 | .IX Item "Changing timer/periodic watchers (by autorepeat, again): O(log skipped_other_timers)" |
2417 | That means that for changing a timer costs less than removing/adding them |
2423 | That means that for changing a timer costs less than removing/adding them |
2418 | as only the relative motion in the event queue has to be paid for. |
2424 | as only the relative motion in the event queue has to be paid for. |
2419 | .IP "Starting io/check/prepare/idle/signal/child watchers: O(1)" 4 |
2425 | .IP "Starting io/check/prepare/idle/signal/child watchers: O(1)" 4 |
2420 | .IX Item "Starting io/check/prepare/idle/signal/child watchers: O(1)" |
2426 | .IX Item "Starting io/check/prepare/idle/signal/child watchers: O(1)" |
2421 | These just add the watcher into an array or at the head of a list. If |
2427 | These just add the watcher into an array or at the head of a list. |
2422 | the array needs to be extended libev needs to realloc and move the whole |
|
|
2423 | array, but this happen asymptotically less and less with more watchers, |
|
|
2424 | thus amortised O(1). |
|
|
2425 | .IP "Stopping check/prepare/idle watchers: O(1)" 4 |
|
|
2426 | .IX Item "Stopping check/prepare/idle watchers: O(1)" |
2428 | =item Stopping check/prepare/idle watchers: O(1) |
2427 | .PD 0 |
|
|
2428 | .IP "Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % \s-1EV_PID_HASHSIZE\s0))" 4 |
2429 | .IP "Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % \s-1EV_PID_HASHSIZE\s0))" 4 |
2429 | .IX Item "Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE))" |
2430 | .IX Item "Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE))" |
2430 | .PD |
|
|
2431 | These watchers are stored in lists then need to be walked to find the |
2431 | These watchers are stored in lists then need to be walked to find the |
2432 | correct watcher to remove. The lists are usually short (you don't usually |
2432 | correct watcher to remove. The lists are usually short (you don't usually |
2433 | have many watchers waiting for the same fd or signal). |
2433 | have many watchers waiting for the same fd or signal). |
2434 | .IP "Finding the next timer per loop iteration: O(1)" 4 |
2434 | .IP "Finding the next timer per loop iteration: O(1)" 4 |
2435 | .IX Item "Finding the next timer per loop iteration: O(1)" |
2435 | .IX Item "Finding the next timer per loop iteration: O(1)" |