Jens Axboe wrote: > On Thu, Feb 21 2008, Jens Axboe wrote: >> 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. > > One possible course of action to implement this without eating extra > space in the rb_node would be: > > - Add rb_right() and rb_set_right() (plus ditto _left variants) to > rbtree.h > - Convert all in-kernel users to use these. Quite extensive, as the > rbtree code search/insert functions are coded in situ and not in > rbtree.[ch] > - Now we can overload bit 0 of ->rb_right and ->rb_left to indicate > whether this is a node or thread pointer and modify rbtree.c to tag > and add the thread links when appropriate. >
Exactly along the lines I was thinking of.and discussing with David. > So we can definitely do this in a compatible fashion. Given that I have > a flight coming up in a few days time, I may give it a got if no one > beats me to it :-) > Feel free to do so, please do keep me on the cc. I am very interested in getting rb threaded trees done, but my bandwidth is a little limited this month. -- Warm Regards, Balbir Singh Linux Technology Center IBM, ISTL -- 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/