On Thu, Feb 21 2008, Peter Zijlstra wrote: > > On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote: > > > You use the empty pointer (missing right child), so why do we need a list. > > May > > be I am missing something. > > A fully threaded tree also has back-pointer to traverse backwards > through the ordered elements. > > That said, overloading the right child pointer might not be the best > thing for the linux kernel, as it will impact all the rb-tree lookups > which are open-coded and often performance critical (this is the reason > the colour isn't bit encoded in either of the child pointers either). > > But if you only want a uni directional thread, I guess we can stick it > in the unsigned long we use for the node colour. > > Still, perhaps it's worth it to grow rb_node to 4 words and do the fully > threaded thing as there are also a lot of rb_prev() users in the kernel. > Who knows.. > > Anyway, I agree that improving rb_next() is worth looking into for the > scheduler.
For the IO scheduler as well, it's used quite extensively! So speeding up rb_next() would definitely help, as it's typically invoked for every bio queued (attempting to back merge with the next request). CFQ and AS additionally does an rb_next() and rb_prev() when trying to decide which request to do next. -- Jens Axboe -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
