: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
