__pick_last_entity() walks the entire tree on O(lgn) time to find the rightmost entry. This patch makes the routine more efficient by reducing the cost of the lookup
Description ----------- Cache the rightmost entry in the rb_tree in the same way that we cache the leftmost entry. __pick_last_entity now uses the cached value. A cautious reviewer might note that the rb_erase() in dequeue entity might cause the tree to be rebalanced and thus effect the cached value. In the case of the rightmost entity, we assign the value to the parent, which even if the tree is rebalanced will become the rightmost entity. NOTE: This depends on Peter Zijlstra's patch which checks for !rightmost. Check out http://lkml.org/lkml/2008/2/18/295. Peter that patch works for me, could you please push that as well. I've seen improvements with this patch. Specifically for the case reported by Yanmin (http://lkml.org/lkml/2008/2/13/128) Comments? Signed-off-by: Balbir Singh <[EMAIL PROTECTED]> --- kernel/sched.c | 7 +++++++ kernel/sched_fair.c | 30 +++++++++++++++++++----------- 2 files changed, 26 insertions(+), 11 deletions(-) diff -puN kernel/sched.c~make-sched-yield-fair-more-efficient kernel/sched.c --- linux-2.6.25-rc2/kernel/sched.c~make-sched-yield-fair-more-efficient 2008-02-21 08:49:06.000000000 +0530 +++ linux-2.6.25-rc2-balbir/kernel/sched.c 2008-02-21 09:50:13.000000000 +0530 @@ -537,7 +537,13 @@ struct cfs_rq { u64 min_vruntime; struct rb_root tasks_timeline; + + /* + * Cached data to help improve performance (avoid walking the + * tree) + */ struct rb_node *rb_leftmost; + struct rb_node *rb_rightmost; struct list_head tasks; struct list_head *balance_iterator; @@ -7332,6 +7338,7 @@ static void init_cfs_rq(struct cfs_rq *c cfs_rq->tasks_timeline = RB_ROOT; INIT_LIST_HEAD(&cfs_rq->tasks); cfs_rq->rb_leftmost = NULL; + cfs_rq->rb_rightmost = NULL; #ifdef CONFIG_FAIR_GROUP_SCHED cfs_rq->rq = rq; #endif diff -puN kernel/sched_fair.c~make-sched-yield-fair-more-efficient kernel/sched_fair.c --- linux-2.6.25-rc2/kernel/sched_fair.c~make-sched-yield-fair-more-efficient 2008-02-21 08:49:06.000000000 +0530 +++ linux-2.6.25-rc2-balbir/kernel/sched_fair.c 2008-02-21 10:26:06.000000000 +0530 @@ -233,6 +233,7 @@ static void __enqueue_entity(struct cfs_ struct sched_entity *entry; s64 key; int leftmost = 1; + int rightmost = 1; if (!entity_is_task(se)) return; @@ -256,6 +257,7 @@ static void __enqueue_entity(struct cfs_ */ if (key < entity_key(cfs_rq, entry)) { link = &parent->rb_left; + rightmost = 0; } else { link = &parent->rb_right; leftmost = 0; @@ -268,6 +270,8 @@ static void __enqueue_entity(struct cfs_ */ if (leftmost) cfs_rq->rb_leftmost = &se->run_node; + if (rightmost) + cfs_rq->rb_rightmost = &se->run_node; rb_link_node(&se->run_node, parent, link); rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline); @@ -286,6 +290,12 @@ static void __dequeue_entity(struct cfs_ if (cfs_rq->rb_leftmost == &se->run_node) cfs_rq->rb_leftmost = rb_next(&se->run_node); + /* + * The parent becomes the rightmost node + */ + if (cfs_rq->rb_rightmost == &se->run_node) + cfs_rq->rb_rightmost = rb_parent(&se->run_node); + rb_erase(&se->run_node, &cfs_rq->tasks_timeline); } @@ -294,6 +304,11 @@ static inline struct rb_node *first_fair return cfs_rq->rb_leftmost; } +static inline struct rb_node *last_fair(struct cfs_rq *cfs_rq) +{ + return cfs_rq->rb_rightmost; +} + static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) { return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node); @@ -301,17 +316,10 @@ static struct sched_entity *__pick_next_ static inline struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq) { - struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; - struct sched_entity *se = NULL; - struct rb_node *parent; - - while (*link) { - parent = *link; - se = rb_entry(parent, struct sched_entity, run_node); - link = &parent->rb_right; - } - - return se; + struct rb_node *rightmost = last_fair(cfs_rq); + if (!rightmost) + return NULL; + return rb_entry(rightmost, struct sched_entity, run_node); } /************************************************************** _ -- 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/
