cvs commit: src/sys/ddb db_ps.c src/sys/kern init_main.c kern_exit.c kern_fork.c kern_resource.c kern_sig.c sys_generic.c src/sys/platform/pc32/i386 pmap.c src/sys/platform/vkernel/platform pmap.c src/sys/sys proc.h tree.h src/sys/vm vm_vmspace.c

[Matthew Dillon]

:The problem is that sel*() is anyways O(nproc), because it only stores the PID and not the proc pointer.  So that is definitely an area for optimization.
:
:cheers
:  simon
:
:-- 
:Serve - BSD     +++  RENT this banner advert  +++    ASCII Ribbon   /"\

    pid lookups are nearly O(1).  They run through a fairly large hash
    table.  That isn't the problem with select.  If you are thinking of
    storing process and lwp pointers in selrecord(), its just not possible.
    The information in selrecord() can become stale very quickly, which is
    why it has to validate the pids/lwpids stored there to determine whether
    those processes and threads actually still exist.  Fortunately for
    selrecord() all those lookups can be shortcutted when the calling thread
    matches the one already recorded.

    The main problem with select is when it has to set the collision bit, 
    which occurs basically every time more then one thread selects on the 
    same descriptor.  At that point selrecord has to set SI_COLL and
    selwakeup will wake up all the threads blocked on the select instead
    of just one.

    So for example, if you are running apache configured to select on 
    accept (apache has options to get around it now but lets just say...),
    and you had 16 apache threads able to accept connections, then all
    16 threads would be woken up and return from the select() call
    for each incoming connection.

    There is also the problem of select() having to poll every single
    descriptor passed into it which can result in horrendous overhead,
    but there isn't much we can do about that.

    Nor is there a whole lot we can do about select() either.  If we 
    implement code to wake up only one select we risk racing so many
    other things that there's a good chance the program may miss the
    accept (or other I/O) event entirely.

					-Matt
					Matthew Dillon 
					<dillon at backplane.com>