> > 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.
Oops, I wasn't quite clear. I said: 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. 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. On Sun, Oct 4, 2015 at 4:25 PM, Christof Ressi <[email protected]> wrote: > 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. > > 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 > 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 >>> >>> 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. >>> > > *Gesendet:* Sonntag, 04. Oktober 2015 um 17:32 Uhr >>> > > *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 >>> >>> >>
_______________________________________________ [email protected] mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
