[PD] poor performance when saving an abstraction when many copies are loaded in a patch

[Mathieu Bouchard]

On Thu, 10 Jan 2008, Thomas Grill wrote:

> this is because PD maintains it's internal structures using linked lists
> which gives a very bad behavior with many structure items.

I don't think that the use of linked lists so far has caused any 
significant problem. The problem lies more in things like recompiling the 
DSP many times in a row without any use for it, and such.

Linked list problems can appear if you try to use a few hundred inlets in 
the same object, or a few thousands objects (or maybe less). Creating N 
[inlet]s dynamically takes O(n^3) time... it's as much a question of 
algorithms and reducing the number of updates, as it is a matter of linked 
lists. In that case you can reduce to O(n^2 log n) by using a better sort 
algorithm, but you can reduce to O(n^2) if you just sort less often, O(n 
log n) if you do both, and O(1) if Pd wasn't relying on the x-position of 
[inlet] objects in the first place.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal QC Canada