DragonFly commits List (threaded) for 2007-08
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
: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).
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
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,
Frankly, we aren't going to get much better then a red-black tree in
terms of compactness, complexity, and efficiency.