<html><head></head><body><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" <brbrofsvl@gmail.com><br/>
<b>An:</b> "Miller Puckette" <msp@ucsd.edu><br/>
<b>Cc:</b> "Christof Ressi" <christof.ressi@gmx.at>, Pd-List <pd-list@lists.iem.at><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 class="HOEnZb">
<div class="h5">
<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></body></html>