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.
I know tcl lappend works fairly fast. Is there a way to speed up [list] stuff in Pd?
-Jonathan
Hi all -
I don't think there's any way to implement [list append] that doesn't require copying the list (tcl can do the append in place so doesn't have to do that). So building a list of length n requires a compute time on the order of n^2 - which gets to be problematic when n gets big.
Another alternative to arrays might be textfiles - however, there aren't yet very good methods for getting the data back out of them :)
Miller
On Wed, Mar 13, 2013 at 09:12:51AM -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.
I know tcl lappend works fairly fast. Is there a way to speed up [list] stuff in Pd?
-Jonathan
#N struct wa array a word; #N struct word symbol s; #N canvas 588 135 450 506 10; #N canvas 0 0 450 300 word 0; #X obj 108 40 struct word symbol s; #X restore 332 25 pd word; #N canvas 0 0 450 300 wa 0; #X obj 40 40 struct wa array a word; #X restore 330 71 pd wa; #X scalar wa ; foo ; ;; #X obj 174 217 pointer; #X obj 134 300 setsize wa a; #X obj 89 335 element wa a; #X msg 62 305 symbol foo; #X obj 62 201 until; #X obj 62 161 t a b; #X msg 111 184 0; #X obj 62 235 f; #X obj 107 235 + 1; #X obj 107 257 t a a; #X obj 62 273 t b a; #X obj 62 366 set -symbol word s; #X obj 192 15 bng 33 250 50 0 empty empty do_it. 41 16 0 10 -262144 -1 -1; #X msg 174 140 traverse pd-dsresizing.pd , next; #X obj 311 312 until; #X obj 311 282 t a b; #X msg 371 313 bang; #X obj 311 334 list append; #X obj 311 356 list append foo; #X msg 311 260 45000; #X obj 247 261 realtime; #X obj 292 165 bng 33 250 50 0 empty empty do_it. 41 16 0 10 -262144 -1 -1; #X obj 292 203 t b b b; #X floatatom 247 283 8 0 0 0 - - -; #X obj 231 88 realtime; #X floatatom 231 110 8 0 0 0 - - -; #X obj 192 53 t b b b b; #X msg 62 139 45000; #X connect 3 0 4 1; #X connect 3 0 5 1; #X connect 5 0 14 1; #X connect 6 0 14 0; #X connect 7 0 10 0; #X connect 8 0 7 0; #X connect 8 1 9 0; #X connect 9 0 10 1; #X connect 10 0 11 0; #X connect 10 0 13 0; #X connect 11 0 12 0; #X connect 12 0 10 1; #X connect 12 1 4 0; #X connect 13 0 6 0; #X connect 13 1 5 0; #X connect 15 0 29 0; #X connect 16 0 3 0; #X connect 17 0 20 0; #X connect 18 0 17 0; #X connect 18 1 19 0; #X connect 19 0 20 1; #X connect 20 0 21 0; #X connect 21 0 20 1; #X connect 22 0 18 0; #X connect 23 0 26 0; #X connect 24 0 25 0; #X connect 25 0 23 1; #X connect 25 1 22 0; #X connect 25 2 23 0; #X connect 27 0 28 0; #X connect 29 0 27 1; #X connect 29 1 30 0; #X connect 29 2 16 0; #X connect 29 3 27 0; #X connect 30 0 8 0;
Pd-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
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.
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.
Roman
----- Original Message -----
From: Roman Haefeli reduzent@gmail.com To: pd-list@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 b) it's the most obvious way to build up a list using the common list processing objects in Pd. Your misunderstanding that the patch is "passing" too many symbols is evidence of the non-obvious of the problem, 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. (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, but I do agree that's the fastest way to build up a list.
Btw-- is there a list-abs object to do the appending in place? I scanned through the objects but didn't see one.
-Jonathan
Roman
Pd-list@iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
On Mit, 2013-03-13 at 12:28 -0700, Jonathan Wilkes wrote:
----- Original Message -----
From: Roman Haefeli reduzent@gmail.com To: pd-list@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
-
Jonathan Wilkes -
Miller Puckette -
Roman Haefeli