> Date: Wed, 05 Jun 2013 14:12:36 -0400 > From: Ted Unangst <[email protected]> > > On Wed, Jun 05, 2013 at 14:13, Alexandre Ratchov wrote: > > On Tue, Jun 04, 2013 at 11:33:12PM -0400, Ted Unangst wrote: > >> Instead of using a fixed size hash table for procs, use an rb tree. > >> > >> Makes thread/process lookup even more web scale. > >> > > > > any measurement? > > o ye of little faith... > > stock > 54.65 > 57.29 > 54.54 > > rbproc > 47.27 > 47.34 > 47.16 > > Benchmark code is below. Now you may well complain that I cooked the > test to give me the result I want. If you remove the pid colliding > code pertaining to 42, the results are different. > > stock > 37.16 > 37.52 > 37.07 > > rbproc > 47.20 > 46.84 > 46.51 > > Perhaps a more realistic test is called for, like building a kernel. > > stock > 1m24.51s real 4m6.24s user 0m43.34s system > 1m24.12s real 4m7.64s user 0m41.98s system > > rbproc > 1m24.02s real 4m6.90s user 0m43.65s system > 1m23.88s real 4m6.07s user 0m41.73s system > > rbproc wins by a hair, but I am happy to call it a draw. > > Conclusion? You'll never notice the difference. Personally I have a > slight preference for improving worst case behavior. The hash table > isn't *that* large today, but as we increase maxthreads it will get > bigger. I prefer dynamic structures to statically sized structures.
If it ain't broke, don't fix it? And I think there are some downsides you may be overlooking: * red-black trees tend to add a significant amount of code to the kernel * red-black trees are a PITA when debugging; it's difficult to find anything in them when you're in ddb/gdb Cheers, Mark
