modifying CFS failure - Kernel

This is a discussion on modifying CFS failure - Kernel ; We tried to replace RB-Trees in CFS by AVL trees to compare the performance benchmarks. For this we wrote a code for avl tree, and made changes in sched-cfs-v2.6.22.13-v24.patch by replacing each occurance of RB-tree function by corrosponding AVL tree ...

+ Reply to Thread
Results 1 to 4 of 4

Thread: modifying CFS failure

  1. modifying CFS failure

    We tried to replace RB-Trees in CFS by AVL trees to compare the
    performance benchmarks. For this we wrote a code for avl tree, and made
    changes in sched-cfs-v2.6.22.13-v24.patch by replacing each occurance of
    RB-tree function by corrosponding AVL tree function. We successfully
    applied the patch on the required kernel version and successfully compiled
    it. But we are not able to boot the kernel. Following are important
    portions from the boot error

    call trace

    enqueue_entity
    enqueue_task_fair
    enqueue_task
    activate_task
    wake_up_new_task
    do_fork
    kernel_init
    kernel_thread
    kernel_init
    kernel_thread_helper
    rest_init
    start_kernel
    unknown_boot option

    EIP[] insert_avl_node kernel panic attempting to kill the idle
    task!

    insert_avl_node is the function to insert a node in the avl tree.

    We have properly tested the avl tree code and its working fine. After
    trying to trace the error for a few days, we feel that we may be missing
    something (In addition to replacing all the occurances of RB by avl in the
    patch and including the avl tree code in kernel library)

    Attached with this mail are the avl tree codes, the modified patch. The
    patch is same as the file sched-cfs-v2.6.22.13-v24.patch, except all the
    occurances of RB tree have been replaced by corrosponding functions of avl
    tree.

    At present we are devoid of any ideas of proceeding forward with the task.
    We shall be thankful if someone can guide us to proceed further and
    rectifying the errors.

    Rohit Gupta
    NIT Allahabad India




  2. Re: modifying CFS failure

    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'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.

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  3. Re: 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

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  4. Re: modifying CFS failure

    > 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.
    >


    We haven't modified anything in CFS except replacing all the RB-Tree
    function calls by AVL tree function calls, so that only the implementation
    of the tree DS changes, and everything else remains same. We have retained
    the interface of tree DS and core scheduler as it is, so we assumed that
    everything must work fine.

    > 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.
    >

    Actually we wanted to replace RB with time ordered radix tree. But that
    seemed a tougher task, so we started with AVL trees first.

    > I'm glad people are working on CFS - its an interesting piece of the
    > kernel after all...
    >

    Thanks. This is really encouraging.


    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

+ Reply to Thread