lkml.org 
[lkml]   [2008]   [Apr]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: modifying CFS failure
On Sat, Apr 12, 2008 at 02:22:03PM +0200, Peter Zijlstra wrote:
> Please provide it as a series of patches against sched-devel/latest.
>
> Just plain AVL code and a huge modified CFS backport make it impossible
> to tell what changed and why.
>
> Which brings us to the question: _why_. That is, why are you trying to
> replace the rb-tree with an avl tree? Just because the worst case depth
> of the avl is slightly better than for an rb-tree, which can be offset
> by the slightl more expesive balance operations.

I would add that in the past, I too tried to replace the rbtree in order
to provide O(1) node deletion time. The tree was not balanced at all
(which provided faster operations). But the net result was very small
(maybe 1%, I don't remember exactly). The reason was that in practise,
the CFS rbtree does not change *that* often, and the pointer to the
first node already provides a great boost. I remember I had to play
in the area of millions of context-switches/s to see a difference, so
it was quite pointless (though the exercise itself was interesting).

> I'm glad people are working on CFS - its an interesting piece of the
> kernel after all, but provide it in a regular patch series, this is
> impossible to work with, sorry.

agreed.

Willy



\
 
 \ /
  Last update: 2008-04-12 15:31    [W:0.039 / U:0.096 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site