lkml.org 
[lkml]   [2007]   [Apr]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [Announce] [patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]
    On Mon, 16 Apr 2007, Pavel Pisa wrote:

    > I cannot help myself to not report results with GAVL
    > tree algorithm there as an another race competitor.
    > I believe, that it is better solution for large priority
    > queues than RB-tree and even heap trees. It could be
    > disputable if the scheduler needs such scalability on
    > the other hand. The AVL heritage guarantees lower height
    > which results in shorter search times which could
    > be profitable for other uses in kernel.
    >
    > GAVL algorithm is AVL tree based, so it does not suffer from
    > "infinite" priorities granularity there as TR does. It allows
    > use for generalized case where tree is not fully balanced.
    > This allows to cut the first item withour rebalancing.
    > This leads to the degradation of the tree by one more level
    > (than non degraded AVL gives) in maximum, which is still
    > considerably better than RB-trees maximum.
    >
    > http://cmp.felk.cvut.cz/~pisa/linux/smart-queue-v-gavl.c

    Here are the results on my Opteron 252:

    Testing N=1
    gavl_cfs = 187.20 cycles/loop
    CFS = 194.16 cycles/loop
    TR = 314.87 cycles/loop
    CFS = 194.15 cycles/loop
    gavl_cfs = 187.15 cycles/loop

    Testing N=2
    gavl_cfs = 268.94 cycles/loop
    CFS = 305.53 cycles/loop
    TR = 313.78 cycles/loop
    CFS = 289.58 cycles/loop
    gavl_cfs = 266.02 cycles/loop

    Testing N=4
    gavl_cfs = 452.13 cycles/loop
    CFS = 518.81 cycles/loop
    TR = 311.54 cycles/loop
    CFS = 516.23 cycles/loop
    gavl_cfs = 450.73 cycles/loop

    Testing N=8
    gavl_cfs = 609.29 cycles/loop
    CFS = 644.65 cycles/loop
    TR = 308.11 cycles/loop
    CFS = 667.01 cycles/loop
    gavl_cfs = 592.89 cycles/loop

    Testing N=16
    gavl_cfs = 686.30 cycles/loop
    CFS = 807.41 cycles/loop
    TR = 317.20 cycles/loop
    CFS = 810.24 cycles/loop
    gavl_cfs = 688.42 cycles/loop

    Testing N=32
    gavl_cfs = 756.57 cycles/loop
    CFS = 852.14 cycles/loop
    TR = 301.22 cycles/loop
    CFS = 876.12 cycles/loop
    gavl_cfs = 758.46 cycles/loop

    Testing N=64
    gavl_cfs = 831.97 cycles/loop
    CFS = 997.16 cycles/loop
    TR = 304.74 cycles/loop
    CFS = 1003.26 cycles/loop
    gavl_cfs = 832.83 cycles/loop

    Testing N=128
    gavl_cfs = 897.33 cycles/loop
    CFS = 1030.36 cycles/loop
    TR = 295.65 cycles/loop
    CFS = 1035.29 cycles/loop
    gavl_cfs = 892.51 cycles/loop

    Testing N=256
    gavl_cfs = 963.17 cycles/loop
    CFS = 1146.04 cycles/loop
    TR = 295.35 cycles/loop
    CFS = 1162.04 cycles/loop
    gavl_cfs = 966.31 cycles/loop

    Testing N=512
    gavl_cfs = 1029.82 cycles/loop
    CFS = 1218.34 cycles/loop
    TR = 288.78 cycles/loop
    CFS = 1257.97 cycles/loop
    gavl_cfs = 1029.83 cycles/loop

    Testing N=1024
    gavl_cfs = 1091.76 cycles/loop
    CFS = 1318.47 cycles/loop
    TR = 287.74 cycles/loop
    CFS = 1311.72 cycles/loop
    gavl_cfs = 1093.29 cycles/loop

    Testing N=2048
    gavl_cfs = 1153.03 cycles/loop
    CFS = 1398.84 cycles/loop
    TR = 286.75 cycles/loop
    CFS = 1438.68 cycles/loop
    gavl_cfs = 1149.97 cycles/loop


    There seem to be some difference from your numbers. This is with:

    gcc version 4.1.2

    and -O2. But then and Opteron can behave quite differentyl than a Duron on
    a bench like this ;)



    - Davide


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

    \
     
     \ /
      Last update: 2007-04-16 07:51    [W:4.089 / U:0.016 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site