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

Evgeniy Polyakov
2007-02-27T10:19:05Z

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:

storage is ready: -> kevent_requee() - ends up in ading event to the end
of the queue (list add under spinlock)

kevent_wait() -> copy first, second, ...

Kevent poll (as long as epoll) model requires _additional_ check in
userspace context before it is copied, so we endup with checking the
full ready queue again - that what I pointed as O(ready_num), O() implies
price for copying to userspace, list_add and so on.

> - Davide
>

--
Evgeniy Polyakov