Re: 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 <dillon@xxxxxxxxxxxxxxxxxxxx>]

:I think this an absolutely false move.  *Only* for select this is O(N), and select was O(N) before, so we didn't lose anything.  The RB-tree just makes everything more complicated.  The right thing to fix is the old, sucky select code.
:
:I think such changes should be discussed beforehand.  In this case I think the change should be backed out unless there is proof that it fixes a performance issue (other than the broken select).
:
:cheers
:  simon

    There are several places where iterations are replaced with a nearly
    direct lookups.  None of these places scaled well to a linear list,
    and almost all of them are in critical paths.  rtprio, direct LWP
    signaling (such as the vkernel uses to send an IPI to another cpu),
    selrecord(), selwakeup(), and TID selection for newly forked threads.

    selrecord() was O(nthread*nfd).  Now it is O(nfd) like it was originally.
    selwakeup() was O(ioreadyrate*nthread*(nthread again if collisions occur)).
    Now it is O(ioreadyrate*(nthread if collisions occur)).

    There is no real need for proof of any of this.  These were all
    in critical paths and CLEARLY would not scale well with a large threaded
    program.

    Now we could argue over which data structure is the best, and if you
    want to implement the final solution we come up with that's fine with
    me.  But we aren't going to back out these fixes.  A linear list is bad,
    period.

    Frankly, we aren't going to get much better then a red-black tree in
    terms of compactness, complexity, and efficiency.

						-Matt