[PD] array-abs

Matt Barber brbrofsvl at gmail.com
Mon Oct 5 04:17:41 CEST 2015 

>
> 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 <christof.ressi at gmx.at>
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" <brbrofsvl at gmail.com>
> *An:* "Miller Puckette" <msp at ucsd.edu>
> *Cc:* "Christof Ressi" <christof.ressi at gmx.at>, Pd-List <
> pd-list at lists.iem.at>
> *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 <brbrofsvl at gmail.com> 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 <msp at ucsd.edu> 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 <christof.ressi at gmx.at>
>>> > 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" <christof.ressi at gmx.at>
>>> > > *An:* "Matt Barber" <brbrofsvl at gmail.com>
>>> > >
>>> > > *Cc:* Pd-List <pd-list at lists.iem.at>
>>> > > *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" <brbrofsvl at gmail.com>
>>> > > *An:* "IOhannes m zmölnig" <zmoelnig at iem.at>
>>> > > *Cc:* Pd-List <pd-list at lists.iem.at>
>>> > > *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 <zmoelnig at iem.at>
>>> > > 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
>>> > >>
>>> > >>
>>> > >>
>>> > >> _______________________________________________
>>> > >> Pd-list at lists.iem.at mailing list
>>> > >> UNSUBSCRIBE and account-management ->
>>> > >> http://lists.puredata.info/listinfo/pd-list
>>> > >>
>>> > >
>>> > > _______________________________________________ Pd-list at lists.iem.at
>>> > > mailing list UNSUBSCRIBE and account-management ->
>>> > > http://lists.puredata.info/listinfo/pd-list
>>> > > _______________________________________________ Pd-list at lists.iem.at
>>> > > mailing list UNSUBSCRIBE and account-management ->
>>> > > http://lists.puredata.info/listinfo/pd-list
>>> > >
>>>
>>> > _______________________________________________
>>> > Pd-list at lists.iem.at mailing list
>>> > UNSUBSCRIBE and account-management ->
>>> http://lists.puredata.info/listinfo/pd-list
>>>
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20151004/db7c2a60/attachment-0001.html>

More information about the Pd-list mailing list