• Bug#265925: fillets-ng: Performance problems update (1/2)

    From Dylan Thurston@1:229/2 to All on Tue Aug 17 07:10:08 2004
    From: [email protected]

    This is a multi-part MIME message sent by reportbug.

    Package: fillets-ng
    Version: 0.5.0-1
    Followup-For: Bug #265925

    After some more playing, there is a problem on the level puzzle.lua.
    On my system, if I repeated load the attached save file, half of the
    time the reload happens at normal speed, and half the time it slows
    down dramatically at move 1424. On a freshly started game, this
    happens at the third reload. Oddly, the slowdown always happens at
    around this same move.

    This behaviour seems indicative of a bug.

    -- System Information:
    Debian Release: 3.1
    APT prefers unstable
    APT policy: (500, 'unstable')
    Architecture: i386 (i686)
    Kernel: Linux 2.6.7
    Locale: LANG=C, LC_CTYPE=zh_TW.UTF-8

    Versions of packages fillets-ng depends on:
    ii fillets-ng-data 0.5.0-1 docs, graphics, music and internat ii libc6 2.3.2.ds1-16 GNU C Library: Shared libraries an ii libgcc1 1:3.4.1-5 GCC support library
    ii liblua50 5.0.2-5 Main interpreter library for the L ii liblualib50 5.0.2-5 Extension library for the Lua 5.0 ii libsdl-image1.2 1.2.3-5 image loading library for Simple D ii libsdl-mixer1.2 1.2.5-8 mixer library for Simple DirectMed ii libsdl-ttf2.0-0 2.0.6-5 ttf library for Simple DirectMedia ii libsdl1.2debian 1.2.7-7 Simple DirectMedia Layer
    ii libstdc++5 1:3.3.4-7 The GNU Standard C++ Library v3
    ii libx11-6 4.3.0.dfsg.1-6 X Window System protocol client li ii xlibs 4.3.0.dfsg.1-6 X Window System client libraries m

    -- no debconf information

    saved_moves = 'dlluuRRRRRRRRRDDRDDDDDLLLLLLrrrrruullllUlLLUlllllrrrrrLrUUUllldddrrrrddddllulullrrrrrrLLLLLLLLLLLLLlllllllllllLLLLLLLLLDDDDDDDLLLLLLDDDDDDDDDDDDDDDRRRRRRRLLLLLLLDDDDDDDDDRRRURRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRrrrrr
    rrrrrrrrrdrrdrdldllluulllluluuuuDRRRDDDDLDLLLLLLLLrrrrruullllUUUlllllllRrrrrrrrrrrrdddddddrrrddddrrrddrrdddrdddllRrrulldluuuuluuullulrrullddlululuullllulUullllDrrrrrrddrrrrdrdrrdddddrddlluDDRRRRRRDDRRRDDDRDDDLLlUUuuuLllllUUuuLUuuLLLrrruruuuuuuuuuuuullllll
    lllllllllllllllllllllllllddldddddrrrllluuuuuuurrrrrrrrrrrrrrrrrrrrrrrrrrrdrrrddrdddrddddddddllllluUUUUuuuLllllRRRRRUUULLLLuuuLLUUULLLLLLLRRRRRRRRuuLLLLLddrrrrdddddrrddddlluuuuuuuuulrrdddllllluRRRRRuuRuuLLLLdddllllllllllLLLLLLLLLLLLLLLLLLLLLLDDDLDDDDLDDLLL
    LLDDDDDDDDDDDRRRRRRRLLLLLLLDDDDDDDDRRRRRRRLLUUUUUUUUURRUUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRrrrrrrrrrrrrrrrddddddrrrrrrddddrdddddllluuuuulululrrulllddluuuuulRRRuuuuuuRRRDDDDDLLLDLLLLLrrrrruuulllUdllUulLUulllDDLRRRRRRddddd
    ddrrrrrdddddddrrrddddllluuuuuuuuuRRRuululllllrrrrdddddrrrrrddddddrrrrrrrrrrrdddddddllddrrdDDDDDDDDDRRRRRRRRRRDDDDDDDDDDDLLUulllllllululuRRuuuululllluuuuuuuuuuulullllrrddddrrrdddddddrddrddddddlluuuuuuuuuuuuuuuululllllrrullllrrrrUUUUUddrrrddddddddddrrrrdrr
    drrrrrrrrrdddddddddddddlllllllllllluulluuuuuuuuuuuuuuuuuuuuuuulurrddddllllluuuuuuuLLLLLLLLUUUUUUUULLLUUUUUURRUUULUULLLLUULLLLLLLRRRRRRRRuLLluLLLLLLLLLLLLLLLLLLdlldllllllLLDDLLLLLDDDDDDDLLLLLLDDDDDDDRRRRRRRUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRDDDRRDDRRRDDRRR
    RRRRURRULLLLLDLLLLrrrrrrrddrrrdrdddddddddddrrrdrrddddrrrlDDDDDRRRRRDDDDRDDDRRRRRDRDDUULLLLLLLLLRllddllllRRdddddrrdrrddrrrrrrrrrrruuuuuullUUuldrruuuUUlllRrrrddlluulrrrddddlllrruuulllurRRRDDDLLlUulLLrdrddddlllddRRdluRRDDDDDDDDDDDLLLLLRRRUUURUULLullllrrrrrrr
    rrrrddrddllllllllllllRRUULUULULLLLLLLLLDDDDDRRDRDDDUuULULRURuuuLLlUuLlUUUUUUUUUUUUUUULRRRRRRRRDLLuuuuuuuuuuuuuuuuLLLLUUUUuuuLlluLLLdrrrrrdddddddrrrrrrdddrdrdddddddllulRRRDDDDRRRRDDDDDDRRRRRRRDDDDDDRDLLLLLdluldldrrdllrrrrrrrrr
    DDDLLRDRDDLDLRRULLddddlllllllllllluLUULLuRRRUuululuuuuuuuuuuUUUUUUUUUUUUUULULLUULDLUUULLLLRRRRRRUUuuuuuDLLLLLRRDDDLLULRRRRRRDRLULUUDDuUUUDDRDrrdDDRRRRRUUUURDDddddddddddddlluuuuuuuuuLLLLLLUUuuuuuuuuuuLUlulRRulllllllllllllllrrrrrrrrrrrrrrddddddlLLLLLLLLLLL
    LLLRRRRRRRRUUUDDDDLLUuuullllllllllllllllrrrrrrrrrrrrrrrrrrruuuurLllluulllllllllllllllllllllllldddrrrrllllddllRRRUUUULLLLLLLLLLLLLLLLLLLLLLDLDDRDRRRRRRLLLLLLLRRUUURRRRRRRRRRRRRRRRRRRRRDLLDDDLLLLLLLLUL'

    saved_models = {{
    [1]={2},
    [2]={3},
    [3]={4},
    [4]={5},
    [5]={6},
    [6]={7},
    [7]={8},
    [8]={9},
    [9]={10},
    [10]={11},
    [11]={12},
    [12]={13},
    [13]={14},
    [14]={15},
    [15]={16},
    [16]={17},
    [17]={18},
    [18]={19},
    [19]={20},
    [20]={21},
    [21]={22},
    [22]={23},
    [23]={24},
    [24]={25},
    [25]={26},
    [26]={27},
    [27]={28},
    [28]={29},
    [29]={30},
    [30]={31},
    [31]={32},
    [32]={33},
    [33]={34},
    [0]={35},
    },
    {
    ["index"]=1,
    ["dir"]=0,
    ["hotovo"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["faze"]=0,
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=6,
    ["anim_delay"]=0,
    ["YStart"]=24,
    ["XStart"]=37,
    ["Y"]=30,
    },
    {
    ["index"]=2,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=11,
    ["anim_delay"]=0,
    ["YStart"]=9,
    ["XStart"]=29,
    ["Y"]=30,
    },
    {
    ["index"]=3,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=15,
    ["anim_delay"]=0,
    ["YStart"]=7,
    ["XStart"]=19,
    ["Y"]=30,
    },
    {
    ["index"]=4,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=19,
    ["anim_delay"]=0,
    ["YStart"]=7,
    ["XStart"]=9,
    ["Y"]=30,
    },
    {
    ["index"]=5,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=6,
    ["anim_delay"]=0,
    ["YStart"]=24,
    ["XStart"]=29,
    ["Y"]=26,
    },
    {
    ["index"]=6,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=11,
    ["anim_delay"]=0,
    ["YStart"]=20,
    ["XStart"]=41,
    ["Y"]=26,
    },
    {
    ["index"]=7,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=15,
    ["anim_delay"]=0,
    ["YStart"]=7,
    ["XStart"]=24,
    ["Y"]=26,
    },
    {
    ["index"]=8,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,
    ["anim_pos"]=1,
    ["afaze"]=0,
    ["X"]=19,
    ["anim_delay"]=0,
    ["YStart"]=1,
    ["XStart"]=11,
    ["Y"]=26,
    },
    {
    ["index"]=9,
    ["dir"]=0,
    ["talk_phase"]=false,
    ["anim"]="",
    ["anim_label"]=1,

    [continued in next message]

    --- SoupGate-Win32 v1.05
    * Origin: you cannot sedate... all the things you hate (1:229/2)
  • From Ivo Danihelka@1:229/2 to Dylan Thurston on Tue Aug 17 23:30:13 2004
    From: [email protected]

    On Tue, 2004-08-17 at 06:46, Dylan Thurston wrote:
    After some more playing, there is a problem on the level puzzle.lua.
    On my system, if I repeated load the attached save file, half of the
    time the reload happens at normal speed, and half the time it slows
    down dramatically at move 1424. On a freshly started game, this
    happens at the third reload. Oddly, the slowdown always happens at
    around this same move.


    The code to compute object falling was not optimized for stacked
    objects. I have implemented faster algorithm to CVS.
    It was so obvious because during loading there must be 16=loadSpeed
    computing done in one time.

    --
    Ivo Danihelka



    --
    To UNSUBSCRIBE, email to [email protected]
    with a subject of "unsubscribe". Trouble? Contact [email protected]

    --- SoupGate-Win32 v1.05
    * Origin: you cannot sedate... all the things you hate (1:229/2)
  • From Dylan Thurston@1:229/2 to Ivo Danihelka on Wed Aug 18 00:20:06 2004
    From: [email protected]

    On Tue, Aug 17, 2004 at 11:11:43PM +0200, Ivo Danihelka wrote:
    On Tue, 2004-08-17 at 06:46, Dylan Thurston wrote:
    After some more playing, there is a problem on the level puzzle.lua.
    On my system, if I repeated load the attached save file, half of the
    time the reload happens at normal speed, and half the time it slows
    down dramatically at move 1424. On a freshly started game, this
    happens at the third reload. Oddly, the slowdown always happens at
    around this same move.


    The code to compute object falling was not optimized for stacked
    objects. I have implemented faster algorithm to CVS.
    It was so obvious because during loading there must be 16=loadSpeed
    computing done in one time.

    This would explain a one-time slowdown, but when I ran it the playback
    was slower all the time after that one loading moment.

    Peace,
    Dylan

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.2.5 (GNU/Linux)

    iD8DBQFBIn7bVeybfhaa3tcRAktCAJ0RMGqNxovGYRmqtpKkCYIyWVFwrwCfSPBf 22q4TBqOy1Hg2dOEjuMateQ=
    =S+Uv
    -----END PGP SIGNATURE-----

    --- SoupGate-Win32 v1.05
    * Origin: you cannot sedate... all the things you hate (1:229/2)
  • From Ivo Danihelka@1:229/2 to Dylan Thurston on Wed Aug 18 01:10:08 2004
    From: [email protected]

    On Tue, 2004-08-17 at 23:55, Dylan Thurston wrote:
    The code to compute object falling was not optimized for stacked
    objects. I have implemented faster algorithm to CVS.
    It was so obvious because during loading there must be 16=loadSpeed computing done in one time.

    This would explain a one-time slowdown, but when I ran it the playback
    was slower all the time after that one loading moment.


    That moment is when a big part of puzzle is composed together. Old
    algorithm objects ask objects below whether falling is possible. The old algorithm had time complexity O(n * s * m^s), where 'n' is number of
    objects, 's' is stack height and 'm' is average number of bottom
    neighbors. This is for the worst case when objects are in free space or
    inside tight "U".

    Piece in puzzle stands on ~3 other pieces and pieces are in steel "U".
    O(n * s * m^s) = (4*5) * 5 * 3^5 = 24300 is big enough.

    New algorithm has time complexity O(n * s) = (4*5) * 5 = 100
    NOTE: the speedup is noticeable only for stacked objects.

    --
    Ivo Danihelka



    --
    To UNSUBSCRIBE, email to [email protected]
    with a subject of "unsubscribe". Trouble? Contact [email protected]

    --- SoupGate-Win32 v1.05
    * Origin: you cannot sedate... all the things you hate (1:229/2)