lkml.org 
[lkml]   [2007]   [Feb]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [patch 00/13] Syslets, "Threadlets", generic AIO support, v3
    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 majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2007-02-27 17:03    [W:0.025 / U:0.248 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site