[PD] switch~ & cputime climbing

[Claude Heiland-Allen]

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
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: switch-vline-test.pd
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20070612/d6d02307/attachment.asc>