[PD] switch~ & cputime climbing

[Kyle Klipowicz]

So just use this for now:

[X]              [inlet messages]
|                   |
[t f f]_____ |____
|                   |        |
[switch]   [spigot]
                    |
                 [vline~]


~Kyle

On 6/12/07, Claude Heiland-Allen <claudiusmaximus at goto10.org> wrote:
> Dafydd Hughes wrote:
> > I never figured out exactly why the climb was happening, but I found
> > that it happened when I turned off dsp in the abstraction, but left
> > the non-dsp elements running, ie continually trying to pass messages
> > to line~ and vd~ objects etc.  Switching off the mechanics when
> > switching off dsp solved it for me.
>
> Yes, sending many messages to a vline~ in a switch~'d off subpatch
> causes CPU usage to rise dramatically.  I nearly froze my box with Pd in
> RT mode when I set the metro period to 1ms and switch~'d the subpatch
> off, with the subpatch switch~'d on the cpu usage remains stable.  See
> attached test patch...
>
> Why this is happening:
>
> Sending a message to vline~ creates a t_vseg, which are stored in a
> sorted linear linked list, which means the time taken to add each new
> line segment would be O(n), where n is the number of existing line segments.
>
> If the subpatch containing vline~ is switch~'d off, the t_vseg's aren't
> removed by the dsp perform routine, which means that CPU usage rises
> quadratically if messages are sent to the vline~ at a constant rate (I
> think, it's been a while since I analyzed algorithmic time complexity).
>
> A solution:
>
> Use a better data structure than a linked list; a balanced tree would
> reduce time complexity to O(log n) instead of O(n) (if I remember
> correctly), admittedly at the cost of harder implementation.
>
> Workaround:
>
> Don't send messages to a switch~'d off vline~.
>
>
> Claude
> --
> http://claudiusmaximus.goto10.org
>
> #N canvas 0 0 450 300 10;
> #N canvas 0 0 450 300 \$0-subpatch 0;
> #X obj 28 17 inlet;
> #X obj 26 270 outlet~;
> #X obj 208 269 switch~;
> #X obj 208 19 inlet;
> #X obj 29 48 t b b;
> #X obj 59 74 random 100;
> #X obj 24 94 random 100;
> #X obj 23 121 pack f f;
> #X obj 24 164 vline~;
> #X connect 0 0 4 0;
> #X connect 3 0 2 0;
> #X connect 4 0 6 0;
> #X connect 4 1 5 0;
> #X connect 5 0 7 1;
> #X connect 6 0 7 0;
> #X connect 7 0 8 0;
> #X connect 8 0 1 0;
> #X restore 68 117 pd \$0-subpatch;
> #X obj 161 67 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0
> 1;
> #X obj 68 68 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0 1
> ;
> #X obj 197 67 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0
> 1;
> #X msg 197 90 \; pd dsp \$1;
> #X obj 302 88 metro 1000;
> #X obj 302 111 t b b;
> #X obj 302 133 cputime;
> #X obj 302 64 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0
> 1;
> #X floatatom 302 165 5 0 0 0 - - -;
> #X floatatom 119 67 5 0 0 0 - - -;
> #X obj 68 91 metro 10;
> #X text 14 205 cputime climbs when many messages are sent to a vline~
> in a switched off subpatch...;
> #X connect 1 0 0 1;
> #X connect 2 0 11 0;
> #X connect 3 0 4 0;
> #X connect 5 0 6 0;
> #X connect 6 0 7 0;
> #X connect 6 1 7 1;
> #X connect 7 0 9 0;
> #X connect 8 0 5 0;
> #X connect 10 0 11 1;
> #X connect 11 0 0 0;
>
> _______________________________________________
> PD-list at iem.at mailing list
> UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
>
>


-- 
-----
------------
    ----     -----
---- -------- - ------
http://perhapsidid.wordpress.com