ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libev/ev.html
(Generate patch)

Comparing libev/ev.html (file contents):
Revision 1.66 by root, Fri Dec 7 19:15:39 2007 UTC vs.
Revision 1.67 by root, Fri Dec 7 19:23:48 2007 UTC

… …
4<head> 4<head>
5 <title>libev</title> 5 <title>libev</title>
6 <meta name="description" content="Pod documentation for libev" /> 6 <meta name="description" content="Pod documentation for libev" />
7 <meta name="inputfile" content="&lt;standard input&gt;" /> 7 <meta name="inputfile" content="&lt;standard input&gt;" />
8 <meta name="outputfile" content="&lt;standard output&gt;" /> 8 <meta name="outputfile" content="&lt;standard output&gt;" />
9 <meta name="created" content="Fri Dec 7 20:07:44 2007" /> 9 <meta name="created" content="Fri Dec 7 20:23:46 2007" />
10 <meta name="generator" content="Pod::Xhtml 1.57" /> 10 <meta name="generator" content="Pod::Xhtml 1.57" />
11<link rel="stylesheet" href="http://res.tst.eu/pod.css"/></head> 11<link rel="stylesheet" href="http://res.tst.eu/pod.css"/></head>
12<body> 12<body>
13<div class="pod"> 13<div class="pod">
14<!-- INDEX START --> 14<!-- INDEX START -->
… …
2239<h1 id="COMPLEXITIES">COMPLEXITIES</h1> 2239<h1 id="COMPLEXITIES">COMPLEXITIES</h1>
2240<div id="COMPLEXITIES_CONTENT"> 2240<div id="COMPLEXITIES_CONTENT">
2241 <p>In this section the complexities of (many of) the algorithms used inside 2241 <p>In this section the complexities of (many of) the algorithms used inside
2242libev will be explained. For complexity discussions about backends see the 2242libev will be explained. For complexity discussions about backends see the
2243documentation for <code>ev_default_init</code>.</p> 2243documentation for <code>ev_default_init</code>.</p>
2244 <p>All of the following are about amortised time: If an array needs to be
2245extended, libev needs to realloc and move the whole array, but this
2246happens asymptotically never with higher number of elements, so O(1) might
2247mean it might do a lengthy realloc operation in rare cases, but on average
2248it is much faster and asymptotically approaches constant time.</p>
2244 <p> 2249 <p>
2245 <dl> 2250 <dl>
2246 <dt>Starting and stopping timer/periodic watchers: O(log skipped_other_timers)</dt> 2251 <dt>Starting and stopping timer/periodic watchers: O(log skipped_other_timers)</dt>
2247 <dd> 2252 <dd>
2248 <p>This means that, when you have a watcher that triggers in one hour and 2253 <p>This means that, when you have a watcher that triggers in one hour and
… …
2254 <p>That means that for changing a timer costs less than removing/adding them 2259 <p>That means that for changing a timer costs less than removing/adding them
2255as only the relative motion in the event queue has to be paid for.</p> 2260as only the relative motion in the event queue has to be paid for.</p>
2256 </dd> 2261 </dd>
2257 <dt>Starting io/check/prepare/idle/signal/child watchers: O(1)</dt> 2262 <dt>Starting io/check/prepare/idle/signal/child watchers: O(1)</dt>
2258 <dd> 2263 <dd>
2259 <p>These just add the watcher into an array or at the head of a list. If 2264 <p>These just add the watcher into an array or at the head of a list.
2260the array needs to be extended libev needs to realloc and move the whole
2261array, but this happen asymptotically less and less with more watchers,
2262thus amortised O(1).</p>
2263 </dd>
2264 <dt>Stopping check/prepare/idle watchers: O(1)</dt> 2265=item Stopping check/prepare/idle watchers: O(1)</p>
2266 </dd>
2265 <dt>Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE))</dt> 2267 <dt>Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE))</dt>
2266 <dd> 2268 <dd>
2267 <p>These watchers are stored in lists then need to be walked to find the 2269 <p>These watchers are stored in lists then need to be walked to find the
2268correct watcher to remove. The lists are usually short (you don't usually 2270correct watcher to remove. The lists are usually short (you don't usually
2269have many watchers waiting for the same fd or signal).</p> 2271have many watchers waiting for the same fd or signal).</p>

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines