First of all, thanks to your great explanation regarding the stack overflow and the algorithm used in [list-split]!
I had similar results when testing Miller's example patch! The time needed for the calculation seems to grow exponentially. For a list of n=100,000 I had to wait nearly a minute :-D. At least Pd didn't crash.
You wrote:
<and lists in Pd are slower in general than
<arrays, so an until loop and tabread over an array is going to be quicker.
<arrays, so an until loop and tabread over an array is going to be quicker.
I thought that too! But after some testing it turned out that [array get] -> [drip] is clearly the winner, with [until] -> [tabread] being only a little bit better than [array get] -> [list-split]. All three of them seem to be more or less linear concerning computation time. Have a look at my patch and make you own test :-).
I guess, having a dedicated interation method for [array] would be ideal, so everything could be done within a single object.
Gesendet: Sonntag, 04. Oktober 2015 um 21:43 Uhr
Von: "Matt Barber" <[email protected]>
An: "Miller Puckette" <[email protected]>
Cc: "Christof Ressi" <[email protected]>, Pd-List <[email protected]>
Betreff: Re: [PD] array-abs
Von: "Matt Barber" <[email protected]>
An: "Miller Puckette" <[email protected]>
Cc: "Christof Ressi" <[email protected]>, Pd-List <[email protected]>
Betreff: Re: [PD] array-abs
It takes almost a full second to output a list of n=1,000,000 with a 100-cycle until on my computer.
On Sun, Oct 4, 2015 at 3:38 PM, Matt Barber <[email protected]> wrote:
This is still much slower than [list-drip], and it freezes Pd for me when I get up to lists of n=100,000 or so. I think it's because Pd has to copy the list to an output every cycle of [until], so when n=10, you're only outputting something of size 10 10 times, but that grows by n^2 so when it's n=10,000 times 10,000 outputs, it's a lot. 1,000,000 seems impossible unless the list decreases in size each cycle, which it does in [list-drip], recursively.On Sun, Oct 4, 2015 at 2:48 PM, Miller Puckette <[email protected]> wrote:Here's a way to serialize a list in (I believe) linear time:
#N canvas 881 291 450 300 10;
#X msg 136 14 list 3 . 1 4 1 5 9;
#X obj 83 97 list length;
#X obj 77 211 list split;
#X obj 101 186 list;
#X obj 139 55 t l b l;
#X obj 83 119 until;
#X obj 83 141 f;
#X obj 114 142 + 1;
#X msg 166 117 0;
#X obj 83 163 t b f;
#X obj 117 278 print;
#X obj 116 250 list split 1;
#X connect 0 0 4 0;
#X connect 1 0 5 0;
#X connect 2 1 11 0;
#X connect 3 0 2 0;
#X connect 4 0 1 0;
#X connect 4 1 8 0;
#X connect 4 2 3 1;
#X connect 5 0 6 0;
#X connect 6 0 7 0;
#X connect 6 0 9 0;
#X connect 7 0 6 1;
#X connect 8 0 6 1;
#X connect 9 0 3 0;
#X connect 9 1 2 1;
#X connect 11 0 10 0;
cheers
Miller> > *Gesendet:* Sonntag, 04. Oktober 2015 um 17:32 Uhr
On Sun, Oct 04, 2015 at 02:27:37PM -0400, Matt Barber wrote:
> Your [pd drip] does a lot of extra work. It's go basically linear stack
> performance, and you're recopying the list every loop (an until loop would
> solve this for a little extra cpu time). The secret of [list-drip] is that
> it doesn't recopy the list using the [list] object, and it avoids stack
> overflows by doing the recursion split at the midpoint of the list and only
> outputting when it's done the binary split down to lists of size 1, which
> are the elements, or size zero, which are bangs (and which are filtered
> out).
>
> Since it's binary recursion on the list, the stack only grows
> proportionally to log_2(n), which is about 20 for n=1,000,000. It's still
> going to be slower than an object written in C that can just iterate over
> the contents in a single loop, and lists in Pd are slower in general than
> arrays, so an until loop and tabread over an array is going to be quicker.
> It is much slower for copying though -- an until loop with tabread and
> tabwrite has way more overhead than an [array get]-[array set] pair.
>
>
> On Sun, Oct 4, 2015 at 1:06 PM, Christof Ressi <[email protected]>
> wrote:
>
> > Please don't use the previous version of the multi-dimensional arrays!!!
> > First, I forget to get rid of one [drip] object. Second, I discovered that
> > [pd drip] will create a stack overflow if there are more than ca. 300
> > elements! (Why???) So I replaced it with [list-drip] which works fine.
> >
> > So here's the corrected pure vanilla version + a zexy version using
> > [drip]. I prefer to use the latter one because it's waaaaay faster than all
> > the drip abstractions based on [list split].
> >
> > Vanilla: https://www.dropbox.com/s/wd0avxtaneqgdic/carray_vanilla.zip?dl=0
> > Zexy: https://www.dropbox.com/s/ea8kihwbdqhcajr/carray_zexy.zip?dl=0
> >
> > Christof
> >
> > PS: I did a benchmark test of iterating through an array of 1 million
> > elements, using [realtime], and here's what I found on my system:
> >
> > [array get] + [drip] --> ca. 6.5-9ms
> > [until] + [tabread] --> ca. 120-200ms
> > [array get] + [list-drip] --> ca. 340-400ms
> >
> > To me this result was a bit surprising...
> >
> > You can test yourself with the attached patch.
> > *Von:* "Christof Ressi" <[email protected]>
> > *An:* "Matt Barber" <[email protected]>
> >
> > *Cc:* Pd-List <[email protected]>
> > *Betreff:* Re: [PD] array-abs
> > Wow, looks cool!
> >
> > Just a few days ago I reworked some of my personal table abstractions,
> > which also make use of the [array] object. However, some of them depend on
> > zexy externals (I hope I didn't miss any other dependencies). I haven't
> > shared them yet so the documentation is quite poor (no help files, docs
> > inside the abstraction) and they look a bit messy. But maybe you can get
> > some inspiration for your library...
> > https://www.dropbox.com/s/xvj031korqw8guf/ctab-abs.zip?dl=0
> >
> > Additionally I've been working on three basic abstractions for creating,
> > setting and reading multi-dimensional arrays of any number of dimensions.
> > They are pure vanilla style and even come with a help file :-D. (a object
> > for array resizing is yet to be done...)
> > https://www.dropbox.com/s/6xfgdyt697138e6/carray.zip?dl=0
> >
> > Would be cool to hear your opinion on the multi-dimensional array stuff!
> >
> > Christof
> >
> >
> >
> >
> > *Gesendet:* Samstag, 03. Oktober 2015 um 22:32 Uhr
> > *Von:* "Matt Barber" <[email protected]>
> > *An:* "IOhannes m zmölnig" <[email protected]>
> > *Cc:* Pd-List <[email protected]>
> > *Betreff:* Re: [PD] array-abs> > Thanks.
> >
> > Yes. Right now I'm just looking to see if these would be useful, if
> > there's anything awful about the syntax, if they try to do too much or are
> > too fussy, if anyone would want to contribute, etc. When I get them
> > polished a bit I'll do a regular release on the normal channels (I can't
> > remember if I have access to anything officially Pd related).
> >
> > Matt
> >
> > On Sat, Oct 3, 2015 at 4:22 PM, IOhannes m zmölnig <[email protected]>
> > wrote:
> >>
> >> hi,
> >>
> >> great!
> >>
> >> On 10/03/2015 07:36 PM, Matt Barber wrote:
> >> >
> >> > https://www.dropbox.com/s/45tk62dpz0z2mqo/array-abs.zip?dl=0
> >> >
> >>
> >> db?
> >>
> >> would you like to put those on a version control system of sorts, e.g.
> >> the puredata svn or some publicly available git repository (e.g. github)?
> >>
> >> (read as: please let us not go back to the dark ages, where code was
> >> shared by sending files around by on floppy disks and you never new
> >> which version was the current one)
> >>
> >> fgmards
> >> IOhannes
> >>
> >>
> >>
> >> _______________________________________________
> >> [email protected] mailing list
> >> UNSUBSCRIBE and account-management ->
> >> http://lists.puredata.info/listinfo/pd-list
> >>
> >
> > _______________________________________________ [email protected]
> > mailing list UNSUBSCRIBE and account-management ->
> > http://lists.puredata.info/listinfo/pd-list
> > _______________________________________________ [email protected]
> > mailing list UNSUBSCRIBE and account-management ->
> > http://lists.puredata.info/listinfo/pd-list
> >
> _______________________________________________
> [email protected] mailing list
> UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
#N canvas 410 360 896 442 10; #X obj 39 98 array get test; #X obj 37 74 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 30 208 realtime; #X obj 39 150 t b a b; #X floatatom 21 241 6 0 0 0 - - -, f 6; #X obj 75 240 drip; #X obj 390 185 until; #X obj 370 57 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 372 84 array size test; #X obj 391 231 f; #X obj 435 237 + 1; #X msg 415 209 0; #X floatatom 313 266 6 0 0 0 - - -, f 6; #X obj 371 138 t b f b; #X obj 389 260 tabread test; #X obj 313 244 realtime; #X obj 191 98 array get test; #X obj 191 72 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 180 208 realtime; #X obj 194 159 t b a b; #X floatatom 174 247 6 0 0 0 - - -, f 6; #X obj 226 247 list-drip; #N canvas 0 50 450 337 drip1 0; #X obj 83 97 list length; #X obj 77 211 list split; #X obj 101 186 list; #X obj 139 55 t l b l; #X obj 83 119 until; #X obj 83 141 f; #X obj 114 142 + 1; #X msg 131 120 0; #X obj 83 163 t b f; #X obj 116 250 list split 1; #X obj 115 284 outlet; #X obj 136 27 inlet; #X connect 0 0 4 0; #X connect 1 1 9 0; #X connect 2 0 1 0; #X connect 3 0 0 0; #X connect 3 1 7 0; #X connect 3 2 2 1; #X connect 4 0 5 0; #X connect 5 0 6 0; #X connect 5 0 8 0; #X connect 6 0 5 1; #X connect 7 0 5 1; #X connect 8 0 2 0; #X connect 8 1 1 1; #X connect 9 0 10 0; #X connect 11 0 3 0; #X restore 576 249 pd drip1; #X obj 542 92 array get test; #X obj 542 66 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 533 209 realtime; #X obj 547 160 t b a b; #X floatatom 522 250 6 0 0 0 - - -, f 6; #X obj 546 125 list split; #X obj 40 124 list split; #X obj 193 130 list split; #X obj -22 71 s \$0-n; #X obj 453 110 r \$0-n; #X obj 630 124 r \$0-n; #X obj 273 130 r \$0-n; #X obj 122 123 r \$0-n; #X obj -22 43 nbx 8 14 -1e+037 1e+037 0 0 empty empty empty 0 -8 0 10 -262144 -1 -1 1e+006 256; #X obj -25 -7 loadbang; #X obj 694 93 array get test; #X obj 694 67 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1 -1; #X obj 685 210 realtime; #X obj 699 161 t b a b; #X floatatom 679 249 6 0 0 0 - - -, f 6; #X obj 698 126 list split; #X obj 782 125 r \$0-n; #X text 541 39 beware!; #X text 692 40 beware!!!; #N canvas 0 50 450 337 drip2 0; #X obj 159 151 outlet; #X obj 143 40 inlet; #X obj 146 75 list split 1; #X obj 177 115 list; #X obj 128 113 t b f; #X connect 1 0 2 0; #X connect 2 0 4 0; #X connect 2 1 3 1; #X connect 3 0 2 0; #X connect 4 0 3 0; #X connect 4 1 0 0; #X restore 728 249 pd drip2; #X obj 371 111 min; #X obj 50 13 table test 1e+007; #X text 61 41 change size; #X msg -22 18 1000; #X connect 0 0 29 0; #X connect 1 0 0 0; #X connect 2 0 4 0; #X connect 3 0 2 1; #X connect 3 1 5 0; #X connect 3 2 2 0; #X connect 6 0 9 0; #X connect 7 0 8 0; #X connect 8 0 48 0; #X connect 9 0 10 0; #X connect 9 0 14 0; #X connect 10 0 9 1; #X connect 11 0 9 1; #X connect 13 0 15 1; #X connect 13 1 6 0; #X connect 13 2 11 0; #X connect 13 2 15 0; #X connect 15 0 12 0; #X connect 16 0 30 0; #X connect 17 0 16 0; #X connect 18 0 20 0; #X connect 19 0 18 1; #X connect 19 1 21 0; #X connect 19 2 18 0; #X connect 23 0 28 0; #X connect 24 0 23 0; #X connect 25 0 27 0; #X connect 26 0 25 1; #X connect 26 1 22 0; #X connect 26 2 25 0; #X connect 28 0 26 0; #X connect 29 0 3 0; #X connect 30 0 19 0; #X connect 32 0 48 1; #X connect 33 0 28 1; #X connect 34 0 30 1; #X connect 35 0 29 1; #X connect 36 0 31 0; #X connect 37 0 51 0; #X connect 38 0 43 0; #X connect 39 0 38 0; #X connect 40 0 42 0; #X connect 41 0 40 1; #X connect 41 1 47 0; #X connect 41 2 40 0; #X connect 43 0 41 0; #X connect 44 0 43 1; #X connect 48 0 13 0; #X connect 51 0 36 0;
_______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
