[PD] long list-building time

[Jonathan Wilkes]

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

Re: [PD] long list-building time

[Miller Puckette]

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


___
Pd-list@iem.at mailing list
UNSUBSCRIBE and account-management - 
http://lists.puredata.info/listinfo/pd-list

Re: [PD] long list-building time

[Roman Haefeli]

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 
#N struct wa array a word;
#N struct word symbol s;
#N canvas 588 135 717 482 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;
#N canvas 1013 564 306 141 big_message 0;
#X obj 67 25 inlet;
#X msg 67 47;
#X obj 67 69 outlet;
#X connect 0 0 1 0;
#X connect 1 0 2 0;
#X restore 487 358 pd big_message;
#X msg 487 337 add2 foo;
#X obj 487 310 until;
#X msg 487 286 45000;
#X obj 423 251 realtime;
#X obj 468 155 bng 33 250 50 0 empty empty do_it. 41 16 0 10 -262144
-1 -1;
#X obj 468 193 t b b b;
#X floatatom 423 273 8 0 0 0 - - -;
#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;
#X connect 32 0 31 0;
#X connect 33 0 32 0;
#X connect 34 0 33 0;
#X connect 35 0 38 0;
#X connect 36 0 37 0;
#X connect 37 0 35 1;
#X connect 37 1 34 0;
#X connect 37 2 35 0;
___
Pd-list@iem.at mailing list
UNSUBSCRIBE and account-management - 
http://lists.puredata.info/listinfo/pd-list

Re: [PD] long list-building time

[Jonathan Wilkes]

- Original Message -

 From: Roman Haefeli reduz...@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
 

___
Pd-list@iem.at mailing list
UNSUBSCRIBE and account-management - 
http://lists.puredata.info/listinfo/pd-list

Re: [PD] long list-building time

[Roman Haefeli]

On Mit, 2013-03-13 at 12:28 -0700, Jonathan Wilkes wrote:
 - Original Message -
 
  From: Roman Haefeli reduz...@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.15703 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





___
Pd-list@iem.at mailing list
UNSUBSCRIBE and account-management - 
http://lists.puredata.info/listinfo/pd-list