<div dir="ltr"><blockquote style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex" class="gmail_quote"><span style="color:rgb(80,0,80);font-family:Verdana;font-size:12px">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.</span></blockquote><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">Oops, I wasn't quite clear. I said:</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><blockquote style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex" class="gmail_quote"><span style="font-size:12.8px">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.</span></blockquote><div class="gmail_default" style="font-family:verdana,sans-serif"><span style="font-size:12.8px"><br></span></div><div class="gmail_default" style="font-family:verdana,sans-serif"><span style="font-size:12.8px">In the first sentence I was referring to the [drip], which presumably iterates over the contents (of the list) in one go with a c loop. I'm curious about what that might mean in the long run for arrays built-ins. I could imagine a built-in enum where you fed it a range and it dripped the index and the value from outlets as though from an until loop, but faster; it could make a mapping function and reducing function quicker possibly, but without dripping the index it's not as useful.</span></div><div class="gmail_default" style="font-family:verdana,sans-serif"><span style="font-size:12.8px"><br></span></div><div class="gmail_default" style="font-family:verdana,sans-serif"><span style="font-size:12.8px"><br></span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Oct 4, 2015 at 4:25 PM, Christof Ressi <span dir="ltr"><<a href="mailto:christof.ressi@gmx.at" target="_blank">christof.ressi@gmx.at</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5"><div><div style="font-family:Verdana;font-size:12.0px"><div style="font-family:Verdana;font-size:12.0px">
<div>
<div>First of all, thanks to your great explanation regarding the stack overflow and the algorithm used in [list-split]!</div>
<div> </div>
<div>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.</div>
<div>You wrote:</div>
<div> </div>
<div><and lists in Pd are slower in general than<br>
<arrays, so an until loop and tabread over an array is going to be quicker.</div>
<div> </div>
<div>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 :-).</div>
<div> </div>
<div>I guess, having a dedicated interation method for [array] would be ideal, so everything could be done within a single object.</div>
<div>
<div style="margin:10.0px 5.0px 5.0px 10.0px;padding:10.0px 0 10.0px 10.0px;border-left:2.0px solid rgb(195,217,229)">
<div style="margin:0 0 10.0px 0"><b>Gesendet:</b> Sonntag, 04. Oktober 2015 um 21:43 Uhr<br>
<b>Von:</b> "Matt Barber" <<a href="mailto:brbrofsvl@gmail.com" target="_blank">brbrofsvl@gmail.com</a>><br>
<b>An:</b> "Miller Puckette" <<a href="mailto:msp@ucsd.edu" target="_blank">msp@ucsd.edu</a>><br>
<b>Cc:</b> "Christof Ressi" <<a href="mailto:christof.ressi@gmx.at" target="_blank">christof.ressi@gmx.at</a>>, Pd-List <<a href="mailto:pd-list@lists.iem.at" target="_blank">pd-list@lists.iem.at</a>><br>
<b>Betreff:</b> Re: [PD] array-abs</div>
<div>
<div>
<div class="gmail_default" style="font-family:verdana,sans-serif">It takes almost a full second to output a list of n=1,000,000 with a 100-cycle until on my computer.</div>
</div>
<div class="gmail_extra">
<div class="gmail_quote">On Sun, Oct 4, 2015 at 3:38 PM, Matt Barber <span><<a>brbrofsvl@gmail.com</a>></span> wrote:
<blockquote class="gmail_quote" style="margin:0 0 0 0.8ex;border-left:1.0px rgb(204,204,204) solid;padding-left:1.0ex">
<div>
<div class="gmail_default" style="font-family:verdana,sans-serif">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.</div>
</div>
<div>
<div>
<div class="gmail_extra">
<div class="gmail_quote">On Sun, Oct 4, 2015 at 2:48 PM, Miller Puckette <span><<a>msp@ucsd.edu</a>></span> wrote:
<blockquote class="gmail_quote" style="margin:0 0 0 0.8ex;border-left:1.0px rgb(204,204,204) solid;padding-left:1.0ex">Here's a way to serialize a list in (I believe) linear time:<br>
<br>
#N canvas 881 291 450 300 10;<br>
#X msg 136 14 list 3 . 1 4 1 5 9;<br>
#X obj 83 97 list length;<br>
#X obj 77 211 list split;<br>
#X obj 101 186 list;<br>
#X obj 139 55 t l b l;<br>
#X obj 83 119 until;<br>
#X obj 83 141 f;<br>
#X obj 114 142 + 1;<br>
#X msg 166 117 0;<br>
#X obj 83 163 t b f;<br>
#X obj 117 278 print;<br>
#X obj 116 250 list split 1;<br>
#X connect 0 0 4 0;<br>
#X connect 1 0 5 0;<br>
#X connect 2 1 11 0;<br>
#X connect 3 0 2 0;<br>
#X connect 4 0 1 0;<br>
#X connect 4 1 8 0;<br>
#X connect 4 2 3 1;<br>
#X connect 5 0 6 0;<br>
#X connect 6 0 7 0;<br>
#X connect 6 0 9 0;<br>
#X connect 7 0 6 1;<br>
#X connect 8 0 6 1;<br>
#X connect 9 0 3 0;<br>
#X connect 9 1 2 1;<br>
#X connect 11 0 10 0;<br>
<br>
cheers<br>
Miller
<div>
<div><br>
On Sun, Oct 04, 2015 at 02:27:37PM -0400, Matt Barber wrote:<br>
> Your [pd drip] does a lot of extra work. It's go basically linear stack<br>
> performance, and you're recopying the list every loop (an until loop would<br>
> solve this for a little extra cpu time). The secret of [list-drip] is that<br>
> it doesn't recopy the list using the [list] object, and it avoids stack<br>
> overflows by doing the recursion split at the midpoint of the list and only<br>
> outputting when it's done the binary split down to lists of size 1, which<br>
> are the elements, or size zero, which are bangs (and which are filtered<br>
> out).<br>
><br>
> Since it's binary recursion on the list, the stack only grows<br>
> proportionally to log_2(n), which is about 20 for n=1,000,000. It's still<br>
> going to be slower than an object written in C that can just iterate over<br>
> the contents in a single loop, and lists in Pd are slower in general than<br>
> arrays, so an until loop and tabread over an array is going to be quicker.<br>
> It is much slower for copying though -- an until loop with tabread and<br>
> tabwrite has way more overhead than an [array get]-[array set] pair.<br>
><br>
><br>
> On Sun, Oct 4, 2015 at 1:06 PM, Christof Ressi <<a>christof.ressi@gmx.at</a>><br>
> wrote:<br>
><br>
> > Please don't use the previous version of the multi-dimensional arrays!!!<br>
> > First, I forget to get rid of one [drip] object. Second, I discovered that<br>
> > [pd drip] will create a stack overflow if there are more than ca. 300<br>
> > elements! (Why???) So I replaced it with [list-drip] which works fine.<br>
> ><br>
> > So here's the corrected pure vanilla version + a zexy version using<br>
> > [drip]. I prefer to use the latter one because it's waaaaay faster than all<br>
> > the drip abstractions based on [list split].<br>
> ><br>
> > Vanilla: <a href="https://www.dropbox.com/s/wd0avxtaneqgdic/carray_vanilla.zip?dl=0" target="_blank">https://www.dropbox.com/s/wd0avxtaneqgdic/carray_vanilla.zip?dl=0</a><br>
> > Zexy: <a href="https://www.dropbox.com/s/ea8kihwbdqhcajr/carray_zexy.zip?dl=0" target="_blank">https://www.dropbox.com/s/ea8kihwbdqhcajr/carray_zexy.zip?dl=0</a><br>
> ><br>
> > Christof<br>
> ><br>
> > PS: I did a benchmark test of iterating through an array of 1 million<br>
> > elements, using [realtime], and here's what I found on my system:<br>
> ><br>
> > [array get] + [drip] --> ca. 6.5-9ms<br>
> > [until] + [tabread] --> ca. 120-200ms<br>
> > [array get] + [list-drip] --> ca. 340-400ms<br>
> ><br>
> > To me this result was a bit surprising...<br>
> ><br>
> > You can test yourself with the attached patch.</div>
</div>
> > *Gesendet:* Sonntag, 04. Oktober 2015 um 17:32 Uhr<br>
> > *Von:* "Christof Ressi" <<a>christof.ressi@gmx.at</a>><br>
> > *An:* "Matt Barber" <<a>brbrofsvl@gmail.com</a>><br>
> ><br>
> > *Cc:* Pd-List <<a>pd-list@lists.iem.at</a>><br>
> > *Betreff:* Re: [PD] array-abs<br>
<span>> > Wow, looks cool!<br>
> ><br>
> > Just a few days ago I reworked some of my personal table abstractions,<br>
> > which also make use of the [array] object. However, some of them depend on<br>
> > zexy externals (I hope I didn't miss any other dependencies). I haven't<br>
> > shared them yet so the documentation is quite poor (no help files, docs<br>
> > inside the abstraction) and they look a bit messy. But maybe you can get<br>
> > some inspiration for your library...<br>
> > <a href="https://www.dropbox.com/s/xvj031korqw8guf/ctab-abs.zip?dl=0" target="_blank">https://www.dropbox.com/s/xvj031korqw8guf/ctab-abs.zip?dl=0</a><br>
> ><br>
> > Additionally I've been working on three basic abstractions for creating,<br>
> > setting and reading multi-dimensional arrays of any number of dimensions.<br>
> > They are pure vanilla style and even come with a help file :-D. (a object<br>
> > for array resizing is yet to be done...)<br>
> > <a href="https://www.dropbox.com/s/6xfgdyt697138e6/carray.zip?dl=0" target="_blank">https://www.dropbox.com/s/6xfgdyt697138e6/carray.zip?dl=0</a><br>
> ><br>
> > Would be cool to hear your opinion on the multi-dimensional array stuff!<br>
> ><br>
> > Christof<br>
> ><br>
> ><br>
> ><br>
> ></span><br>
> > *Gesendet:* Samstag, 03. Oktober 2015 um 22:32 Uhr<br>
> > *Von:* "Matt Barber" <<a>brbrofsvl@gmail.com</a>><br>
> > *An:* "IOhannes m zmölnig" <<a>zmoelnig@iem.at</a>><br>
> > *Cc:* Pd-List <<a>pd-list@lists.iem.at</a>><br>
> > *Betreff:* Re: [PD] array-abs
<div>
<div>> > Thanks.<br>
> ><br>
> > Yes. Right now I'm just looking to see if these would be useful, if<br>
> > there's anything awful about the syntax, if they try to do too much or are<br>
> > too fussy, if anyone would want to contribute, etc. When I get them<br>
> > polished a bit I'll do a regular release on the normal channels (I can't<br>
> > remember if I have access to anything officially Pd related).<br>
> ><br>
> > Matt<br>
> ><br>
> > On Sat, Oct 3, 2015 at 4:22 PM, IOhannes m zmölnig <<a>zmoelnig@iem.at</a>><br>
> > wrote:<br>
> >><br>
> >> hi,<br>
> >><br>
> >> great!<br>
> >><br>
> >> On 10/03/2015 07:36 PM, Matt Barber wrote:<br>
> >> ><br>
> >> > <a href="https://www.dropbox.com/s/45tk62dpz0z2mqo/array-abs.zip?dl=0" target="_blank">https://www.dropbox.com/s/45tk62dpz0z2mqo/array-abs.zip?dl=0</a><br>
> >> ><br>
> >><br>
> >> db?<br>
> >><br>
> >> would you like to put those on a version control system of sorts, e.g.<br>
> >> the puredata svn or some publicly available git repository (e.g. github)?<br>
> >><br>
> >> (read as: please let us not go back to the dark ages, where code was<br>
> >> shared by sending files around by on floppy disks and you never new<br>
> >> which version was the current one)<br>
> >><br>
> >> fgmards<br>
> >> IOhannes<br>
> >><br>
> >><br>
> >><br>
> >> _______________________________________________<br>
> >> <a>Pd-list@lists.iem.at</a> mailing list<br>
> >> UNSUBSCRIBE and account-management -><br>
> >> <a href="http://lists.puredata.info/listinfo/pd-list" target="_blank">http://lists.puredata.info/listinfo/pd-list</a><br>
> >><br>
> ><br>
> > _______________________________________________ <a>Pd-list@lists.iem.at</a><br>
> > mailing list UNSUBSCRIBE and account-management -><br>
> > <a href="http://lists.puredata.info/listinfo/pd-list" target="_blank">http://lists.puredata.info/listinfo/pd-list</a><br>
> > _______________________________________________ <a>Pd-list@lists.iem.at</a><br>
> > mailing list UNSUBSCRIBE and account-management -><br>
> > <a href="http://lists.puredata.info/listinfo/pd-list" target="_blank">http://lists.puredata.info/listinfo/pd-list</a><br>
> ><br>
<br>
> _______________________________________________<br>
> <a>Pd-list@lists.iem.at</a> mailing list<br>
> UNSUBSCRIBE and account-management -> <a href="http://lists.puredata.info/listinfo/pd-list" target="_blank">http://lists.puredata.info/listinfo/pd-list</a><br>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
</div></div></div></div></div></blockquote></div><br></div>