Re: [patch 00/13] Syslets, "Threadlets", generic AIO support, v3

[Davide Libenzi]

On Tue, 27 Feb 2007, Evgeniy Polyakov wrote:

> On Mon, Feb 26, 2007 at 06:18:51PM -0800, Davide Libenzi (davidel@xxxxxxxxxxxxxxx) 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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/