Messages in this thread | | | Date | Thu, 21 Feb 2008 21:55:45 +0100 | From | Jens Axboe <> | Subject | Re: Make yield_task_fair more efficient |
| |
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.
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 :-)
-- Jens Axboe
| |