[PD] long list-building time

[Roman Haefeli]

On Mit, 2013-03-13 at 12:28 -0700, Jonathan Wilkes wrote:
> ----- Original Message -----
> 
> > From: Roman Haefeli <reduzent at gmail.com>
> > To: pd-list at iem.at
> > Cc: 
> > Sent: Wednesday, March 13, 2013 1:49 PM
> > Subject: Re: [PD] long list-building time
> > 
> > On Mit, 2013-03-13 at 09:12 -0700, Jonathan Wilkes wrote:
> >>  Hi list,
> >>       See attached for difference between building a list
> >>  of symbols through [list append] and building an array
> >>  of symbols.
> >> 
> >> 
> >>  Now, I know the ds array resizing and setting is
> >>  more efficient than building out a list using [list append],
> >>  but I don't understand why the [list append] takes over
> >>  a minute to complete.  It can't be due to symbol table
> >>  stuff since I'm using the same symbol over and over.
> > 
> > [list append] is not particularly slow, but your algorithm of appending
> > is. You are passing 45000 + 44999 + 44998 + 44997 .... + 1 symbols
> > around, which is obviously very inefficient.
> 
> Yes it's slow, but the point is that a) it's not obvious why it would be as
> slow as it actually is until you get under the hood and look at the source
> and 

I don't get your point. Without having a look under the hood, I tried to
calculate the time it requires for passing around one single symbol
(please correct any mistakes):

list example:
1+2+3+4+5...+45000 = 45000*(45000+1)/2 = 1012522500 symbol copy ops
15000ms / 1012522500 = 0.000015703 ms per symbol copy operation

messagebox example:
9ms / 45000 = 0.0002 ms per symbol copy operation

According to this, the list approach even uses more than ten times less
time per symbol copy operation. To my surprise it is much faster than
what I would have expected. Why are you implying it is unexpectedly
slow? 


> b) it's the most obvious way to build up a list using the common
> list processing objects in Pd.

Agreed. As concatenating and serializing lists are such common and
really basic operations, they probably would deserve their own (and
fast!) sub-classes [list concatenate] and [list serialize].

>   Your misunderstanding that the patch is
> "passing" too many symbols is evidence of the non-obvious of the problem,

Can you elaborate this? What is the non-obvious of the problem and what
am I misunderstanding?

> and Frank's original implementation of [list-drip] is good evidence that accumulating
> atoms with another [list] object like I showed is the obvious approach for
> a whole class of list manipulations. 

Why are you referring to list-abs to prove what is obvious (are they
some form of authority?) and why should we focus on the obvious only?
It's kind of moot to argue about the obviousness of something and I
don't think it matters so much. Personally, I only rarely use the [list
append] loop for concatenating and I try to avoid the [list split 1]
loop for serializing whenever possible, just because they are so slow.
Mostly, I use the messagebox for concatenating and a [table] for
serializing lists of numbers. 

>  (Additionally, matju's newer [list-drip]
> approach using recursion is a great example of how difficult it is to get
> a handle on the eccentricities of list processing and get decent efficiency
> without resorting to externals.)
> 
> > 
> > I added another method to your patch that uses [add $1( to a message box
> > to append many symbols to a list. While the [list append] method takes
> > 15s on my machine, the messagebox method takes only 9 ms. 
> 
> I don't like solutions that blow up in the user's face when they do something as
> innocent as leaving a subpatch visible,

I somewhat see your point, but OTOH, the window - even if visible - does
not blow up. So this really doesn't do any harm.

Roman