On Tue, 27 Feb 2007, Evgeniy Polyakov wrote:
> On Mon, Feb 26, 2007 at 06:18:51PM -0800, Davide Libenzi
> (davidel@xmailserver.org) wrote:
> > On Mon, 26 Feb 2007, Evgeniy Polyakov wrote:
> >
> > > 2. its notifications do not go through the second loop, i.e. it is O(1),
> > > not O(ready_num), and notifications happens directly from internals of
> > > the appropriate subsystem, which does not require special wakeup
> > > (although it can be done too).
> >
> > Sorry if I do not read kevent code correctly, but in kevent_user_wait()
> > there is a:
> >
> > while (num < max_nr && ((k = kevent_dequeue_ready(u)) != NULL)) {
> > ...
> > }
> >
> > loop, that make it O(ready_num). From a mathematical standpoint, they're
> > both O(ready_num), but epoll is doing three passes over the ready set.
> > I always though that if the number of ready events is so big that the more
> > passes over the ready set becomes relevant, probably the "work" done by
> > userspace for each fetched event would make the extra cost irrelevant.
> > But that can be fixed by a patch that will follow on lkml ...
>
> No, kevent_dequeue_ready() copies data to userspace, that is it.
> So it looks roughly following:
In all the books where I studied, the algorithms below would be classified
as O(num_ready) ones:
[sys_kevent_wait]
+ for (i=0; i<num; ++i) {
+ k = kevent_dequeue_ready_ring(u);
+ if (!k)
+ break;
+ kevent_complete_ready(k);
+
+ if (k->event.ret_flags & KEVENT_RET_COPY_FAILED)
+ break;
+ kevent_stat_ring(u);
+ copied++;
+ }
[kevent_user_wait]
+ while (num < max_nr && ((k = kevent_dequeue_ready(u)) != NULL)) {
+ if (copy_to_user(buf + num*sizeof(struct ukevent),
+ &k->event, sizeof(struct ukevent))) {
+ if (num == 0)
+ num = -EFAULT;
+ break;
+ }
+ kevent_complete_ready(k);
+ ++num;
+ kevent_stat_wait(u);
+ }
It does not matter if inside the loop you invert a 20Kx20K matrix or you
copy a byte, they both are O(num_ready).
- Davide
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
