On Tue, Jan 15, 2008 at 10:47:33AM -0500, Chris Shoemaker <[EMAIL PROTECTED]>
wrote:
> It's O(N) in the number of child watchers, and runs only upon SIGCHLD.
Also, it just occured to me that this is totally misleading:
Your algorithm is O(c²) where c is the number of children in the number
of waitpid calls, where libev is O(c). If you take into account the number
of watchers, then your approach is O(w c²) where w is the number of
watchers, while libev's approach is O(w c) with a much smaller constant
factor due to the hashing.
As an example, with just 50 children, in the worst case, you require over
1200 waitpid calls where libev only requires 100, and each waitpid call,
if implemented correctly, would have to check all active watchers in your
case (leading to over 30000 iterations overall), and only the potentially
matching ones with libev (leading to roughly 150 iterations overall).
Performance quickly degrades from that point on.
It makes sense to implement it that way for you because you are required
to emulate a non-event-based API (waitpid) and there is little to do, but
punishing programs written in an event-based way makes no sense to me,
especially in an event-library: It is only natural that non-event-based
approaches might require less efficient algorithms.
Sure, 50 children is not typical, but it happens with some regularity,
just as 1000 or more file descriptors is not typical, but it happens with
some regularity.
> Is that really so bad? I'd love to know of a more efficient way, but
> efficiency is secondard to correctness,
libev *is* correct, it just isn't suitable for emulating waitpid, as it is a
generic event library. When talking about correctness, I'd say the correct
approach is to deliver data to the registered watchers, and not just some of
them.
(thinking about all this, I might be able to reduce the number of waitpid
calls further).
In any case, libev is commited to support event-based programing
efficiently, it is not meant to emulate the traditional UNIX api in a
different way: if you want waitpid, you know where to find it.
--
The choice of a Deliantra, the free code+content MORPG
-----==- _GNU_ http://www.deliantra.net
----==-- _ generation
---==---(_)__ __ ____ __ Marc Lehmann
--==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED]
-=====/_/_//_/\_,_/ /_/\_\
_______________________________________________
libev mailing list
libev@lists.schmorp.de
http://lists.schmorp.de/cgi-bin/mailman/listinfo/libev
