Re: Make yield_task_fair more efficient

[Peter Zijlstra <a.p.zijlstra@chello.nl>]

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.