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@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@gmail.com *An:* "Miller Puckette" msp@ucsd.edu *Cc:* "Christof Ressi" christof.ressi@gmx.at, Pd-List < pd-list@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@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@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@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@gmx.at *An:* "Matt Barber" brbrofsvl@gmail.com
*Cc:* Pd-List pd-list@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@gmail.com *An:* "IOhannes m zmölnig" zmoelnig@iem.at *Cc:* Pd-List pd-list@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@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@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
_______________________________________________ Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list _______________________________________________ Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management ->
On 2015-10-05 13:25, Christof Ressi wrote:
I'm only dreaming, but maybe that could be a fantastic feature for a future pd vanilla release. :-)
i think it's so easy to implement as an abstraction that *i* think it should go into supporting libraries (like array-abs).
mgsdf IOhannes
You're right that it's easy to implement as an abstraction but I was rather thinking about execution speed. I guess a fictional object like [array drip] that would just iterate through the array using a C loop would be the fastest possible method. I don't see how you could even get close to that with abstractions, especially when using only vanilla objects.
Gesendet: Montag, 05. Oktober 2015 um 14:00 Uhr Von: "IOhannes m zmoelnig" zmoelnig@iem.at An: pd-list@lists.iem.at Betreff: Re: [PD] array-abs
On 2015-10-05 13:25, Christof Ressi wrote:
I'm only dreaming, but maybe that could be a fantastic feature for a future pd vanilla release. :-)
i think it's so easy to implement as an abstraction that *i* think it should go into supporting libraries (like array-abs).
mgsdf IOhannes
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Ah, gotcha. -Jonathan
On Monday, October 5, 2015 11:40 AM, Christof Ressi <christof.ressi@gmx.at> wrote:
You're right that it's easy to implement as an abstraction but I was rather thinking about execution speed. I guess a fictional object like [array drip] that would just iterate through the array using a C loop would be the fastest possible method. I don't see how you could even get close to that with abstractions, especially when using only vanilla objects.
Gesendet: Montag, 05. Oktober 2015 um 14:00 Uhr Von: "IOhannes m zmoelnig" zmoelnig@iem.at An: pd-list@lists.iem.at Betreff: Re: [PD] array-abs
On 2015-10-05 13:25, Christof Ressi wrote:
I'm only dreaming, but maybe that could be a fantastic feature for a future pd vanilla release. :-)
i think it's so easy to implement as an abstraction that *i* think it should go into supporting libraries (like array-abs).
mgsdf IOhannes
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
On 10/05/2015 05:39 PM, Christof Ressi wrote:
You're right that it's easy to implement as an abstraction but I was rather thinking about execution speed. I guess a fictional object like [array drip] that would just iterate through the array using a C loop would be the fastest possible method.
yes. well no: the fastest possible way would probably be hand-optimized assembler.
I don't see how you could even get close to that with abstractions, especially when using only vanilla objects.
i don't think that in practice this would matter though. an [array-drip]¹ implementation in Pd-vanilla should be O(n). an [array drip] implementation in C should be O(n).
sure, the abstraction implementation will perform worse by a (constant) factor but the complexity stays the same which is the important part.
i assume that the cases where you do need that extra speed boost are rather seldom, and do not warrant an extra built-in object.
gfamrds IOhannes
¹ it always causes me pain to see the name "drip" used so widely.
Agreed, "drip" is awful. I had one included and then removed it because I hated the name, and it's not that much to hook an iterator to a table reader (and you have the indices to work with in whatever way you need as well).
Speaking of which, on my machine [array get] is faster than plain [tabread]. It can get lists of about 30 from an array about as fast as [tabread] can get single floats. Weird, but cool.
M
On Mon, Oct 5, 2015 at 1:39 PM, IOhannes m zmölnig zmoelnig@iem.at wrote:
On 10/05/2015 05:39 PM, Christof Ressi wrote:
You're right that it's easy to implement as an abstraction but I was
rather thinking about execution speed.
I guess a fictional object like [array drip] that would just iterate
through the array using a C loop would be the fastest possible method.
yes. well no: the fastest possible way would probably be hand-optimized assembler.
I don't see how you could even get close to that with abstractions,
especially when using only vanilla objects.
i don't think that in practice this would matter though. an [array-drip]¹ implementation in Pd-vanilla should be O(n). an [array drip] implementation in C should be O(n).
sure, the abstraction implementation will perform worse by a (constant) factor but the complexity stays the same which is the important part.
i assume that the cases where you do need that extra speed boost are rather seldom, and do not warrant an extra built-in object.
gfamrds IOhannes
¹ it always causes me pain to see the name "drip" used so widely.
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
On 10/05/2015 07:57 PM, Matt Barber wrote:
Speaking of which, on my machine [array get] is faster than plain [tabread]. It can get lists of about 30 from an array about as fast as [tabread] can get single floats. Weird, but cool.
hmm, [array get] is indeed faster, but in my tests the difference is marginal (and someseldomtimes [tabread] is even a wee bit faster)
i did a quick implementation of [array drip] and compared it to [tabread] and [array get] implementations (both using an [until]/[i]/[+1] counter), and the pure C implementation performs about 10 times faster.
some stats:
values are average of 10 runs, itreating over an (uninitialized (zeroed out) table of 1e8 elements)
#1: ignoring the index completely: [array drip]..............: 562 [array get] implementation: 10624 [tabread] implementation..: 10390
#2: creating a value/index list with [pack]: [array drip]..............: 1613 [array get] implementation: 12984 [tabread] implementation..: 13049
so the performance of the patch using [array drip] drops significantly as soon as patch objects are introduced into the iteration; since this is the main use-case of [array drip], it makes a C-implementation even less interesting.
gmfsdr IOhannes
Thanks for the testing! That's very illustrative and I can confirm an analogous behaviour: When nothing is connected to the outlet of [array get]->[drip] resp. [until]->[tabread], [drip] will be about 10 times faster, no matter how many elements you're accessing. But as soon as you start adding math objects, the advantage of [drip] gets eaten up by and by. After adding 20 [exp] objects, they will both take about the same time - which is actually quite logical when I think of it...
So you totally have a point there! Although being 10x faster for light math objects might help in some live situations... The only thing [array drip] would provide for sure is some convenience, which could justify the expense of having another C object :-p.
A 'drip' (or call it 'iterate') method for [list] would probably be more important, since there's no practical vanilla solution at all, as we have seen (except for [list-drip] which uses only vanilla objects, but isn't really part of the Pd vanilla distributions).
Christof
Gesendet: Montag, 05. Oktober 2015 um 20:39 Uhr Von: "IOhannes m zmölnig" zmoelnig@iem.at An: pd-list@lists.iem.at Betreff: Re: [PD] array-abs
On 10/05/2015 07:57 PM, Matt Barber wrote:
Speaking of which, on my machine [array get] is faster than plain [tabread]. It can get lists of about 30 from an array about as fast as [tabread] can get single floats. Weird, but cool.
hmm, [array get] is indeed faster, but in my tests the difference is marginal (and someseldomtimes [tabread] is even a wee bit faster)
i did a quick implementation of [array drip] and compared it to [tabread] and [array get] implementations (both using an [until]/[i]/[+1] counter), and the pure C implementation performs about 10 times faster.
some stats:
values are average of 10 runs, itreating over an (uninitialized (zeroed out) table of 1e8 elements)
#1: ignoring the index completely: [array drip]..............: 562 [array get] implementation: 10624 [tabread] implementation..: 10390
#2: creating a value/index list with [pack]: [array drip]..............: 1613 [array get] implementation: 12984 [tabread] implementation..: 13049
so the performance of the patch using [array drip] drops significantly as soon as patch objects are introduced into the iteration; since this is the main use-case of [array drip], it makes a C-implementation even less interesting.
gmfsdr IOhannes
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Kind of off topic, but...If we're just talking about iterating through an array, how could hand-optimized assemblerpossibly beat a modern compiler? -Jonathan
On Monday, October 5, 2015 1:40 PM, IOhannes m zmölnig <zmoelnig@iem.at> wrote:
On 10/05/2015 05:39 PM, Christof Ressi wrote:
You're right that it's easy to implement as an abstraction but I was rather thinking about execution speed. I guess a fictional object like [array drip] that would just iterate through the array using a C loop would be the fastest possible method.
yes. well no: the fastest possible way would probably be hand-optimized assembler.
I don't see how you could even get close to that with abstractions, especially when using only vanilla objects.
i don't think that in practice this would matter though. an [array-drip]¹ implementation in Pd-vanilla should be O(n). an [array drip] implementation in C should be O(n).
sure, the abstraction implementation will perform worse by a (constant) factor but the complexity stays the same which is the important part.
i assume that the cases where you do need that extra speed boost are rather seldom, and do not warrant an extra built-in object.
gfamrds IOhannes
¹ it always causes me pain to see the name "drip" used so widely.
Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
-
Christof Ressi -
IOhannes m zmoelnig -
IOhannes m zmölnig
-
Jonathan Wilkes -
Matt Barber