On Wed, 25 Feb 2009, Hans-Christoph Steiner wrote:

Sounds very cool. Just out of curiosty, how did you measure the speed difference? That would be a useful technic to know about for testing in general.

I use [t b a b] with [realtime], similar to enrique's, but i pass a float around for deciding of how many elements in the list. I made it automatically try several consecutive powers of two. I generated a large list using [#for] and [#to_list], but I included the generation of the list in the measurements I made. since then, I moved that part to above the [t b a b] so that it doesn't get measured. But that extra time is almost neglectible and taking it out would only result in a more insane speed ratio.

I also tried [usertime] but it is not really more accurate than [realtime] and its resolution is much worse. [usertime] and [systemtime] is in GridFlow and just uses the OS's corresponding functions, and in Linux, they sort of suck.

Finally I have just tried [tsctime], also from GridFlow, and this uses the CPU's built-in clock. When it does work, it's much more consistent than [realtime], but it can be fooled by the power-saving of the CPU, and it doesn't stop when switching to different processes, just like [realtime]. OTOH, [usertime] and [systemtime] do stop when switching processes, but they accumulate a lot of error.

Ideally, you'd put the equivalent of [tsctime] straight in the Linux kernel's scheduler, and it'd measure the time locally per process. If you also put it in the Linux kernel's system-call gate, you can also rewrite the usertime/systemtime system-call to use that and get a million times more precision than the existing functions.

Else, if you want an accurate measurement, you have to do it statistically. On average, making a test four times will get you twice more precision, so if you repeated the test 10 times and now you repeat it 1000 times, you will get one more trustable decimal in the average time.

_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec

On Thu, 26 Feb 2009, Martin Schied wrote:

I often used message boxes for list splitting in my current project because they were the fastest solution I could find using a benchmark of [t b b b] and [realtime].

I just made an alternate version of [list-drip-quick] that is faster than [list-drip-quicker] without even using [repeat], and the difference is that it uses a pile of messageboxes for anything smaller than 9 elements. I use [s] with two inlets to dispatch the message because any solution involving [spigot] would be much slower and cumbersome, and anything using [demux] would be using an external.

I made it after reading your mail but before looking at your patch, and it looks different from yours so I'm attaching it.

So, the score is (for a 32768-element list):

[list-drip] ~10000 ms [list-drip-quick] ~28.5 ms [list-drip-quicker] ~10.0 ms [list-drip-quick2] ~7.2 ms [list-drip-schied] ~6.0 ms [list-drip-schied2] ~5.1 ms [drip] ~1.1 ms

The [list-drip-schied2] is done by replacing the split32 by a single messagebox with commas in it.

_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec

On Wed, 25 Feb 2009, Enrique Erne wrote:

... and i thought my list-drip-custom would win :( could somebody explain how it exaclty works?

well, first, the right-inlet of [list] makes a copy of your list, so this makes it take a lot more time when cutting lists into pieces.

second, the left-inlet of [list] also makes a copy of your list, so this makes it take double the time that it just added, because [list] is a [list append], and it's appending a bang to a list, and a bang is an empty list, and it's not smart enough to skip the copy in that case.

this makes a regular list-drip make n*n atom copies, whereas when you cut in chunks of 64, it makes n*n/64 atom copies, and then it makes 64*64*(n/64) = 64*n atom copies with the rest, almost.

this also means that your recursion and [until] run at the same speed because they end up making the same copies, so you could achieve the same results with two levels of [until].

you can achieve more speed by adding extra levels of [until] and tuning the list chunk sizes for each level.

then also if you use a pair of [list split]s and a counter to iterate through it, you have to use a [list] to hold it, and then it takes n*n steps because it's an append, and if you try to use [textfile] or a settable messagebox, it also copies because it's doing comma-expansion, so it's no better (note that [textfile] is very much like an invisible messagebox, there's no real parsing involved unless you load from a real file)

so i figured out that I had to use [list split] with recursion without [list], so that it doesn't copy the sublists. but then, attempting to do it will output the elements in reverse order, so you have to use two [list split]s, which only copies n atoms (the absolute minimum).

then, doing it with one or two [list split]s gets you a stack overflow very soon, so by recursing over half-lists you can use up only log(n)/log(2) levels of recursion. this only copies n atoms, so it's the minimum possible.

when doing recursion, you have to be careful because pd's cold-inlets interfere with normal use of recursion... so, for example, I had to compute the half-list-size twice because I had two [list split]s.

there are several ways in which pd falls just short of allowing a simple way. For example, just a simple [repeat] with a counter would be several times less objects, cords and tricks, and can be somewhat speedier than [list-drip-quick] because you can avoid a lot of the other things that [list-drip-quick] has to do besides copying n atoms.

Actually, I just tried it with [repeat], and, the way I did it, it is consistently 2.9 times faster than [list-drip-quick].

But from the moment that you get it down to n atom copies, the speed differences don't tend to matter nearly as much, as the objects that receive the dripping will have to process n messages, and that is often taking more time than the splitting.

So, a pure C external version of [list-drip] may be still several times faster than the [repeat] version, but only as long as you don't send its output to any object at all! In real-life situations, the speed difference is much thinner than the benchmarks, when the objects being benchmarks are both quite fast.

Note that it's possible that adding to a messagebox cancels all speed improvements. Its running-time is either n copies or n*n/2 copies, because it's using a realloc, which may copy or not, depending on whether you're lucky.

what license do you publish your code when you post code on the pd-list? same as puredata?

yes, SIBSD license. well, it's on a case-by-case basis. there's no automatic license for anything, but let's say that [list-drip-quick] is SIBSD.

_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec

On Wed, 25 Feb 2009, Frank Barknecht wrote:

Anyway: Would it be okay to use it in [list]-abs which has Pd's BSD license?

Yes.

But now I'll have to digest the algorithm ...

Well, you don't _have_ to... you could first swallow the algorithm, and postpone the digestion to whenever you're ready.

Because, if it has the right license, the right output, no stack overflows, a higher speed and a lower memory usage, what's really wrong with just using it?

I think that its biggest practical downside might be that's it slower on very small lists, but that's all.

_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec

On Wed, 25 Feb 2009, Frank Barknecht wrote:

Nothing really, but I still want to understand it. I added some comments in the attached version that describe how far I got with understanding. Am I completely off?

Maybe. There is nothing that the code does on specifically the first two elements of the list.

The [list split 2] just checks whether the list has more than one element, and if it has only one element, output it. There were several ways to do it, but they were about as complicated as each other. the [bang]s with the [spigot] are for making a conditional about lists longer than 1 element. after that, the splitting occurs recursively in equal halves just as in a merge-sort or binary-search on an array.

Apart from that, I'd expect comments on an implementation to be at a higher level than the implementation. People can follow the wires and figure out what happens between two consecutive objects, but they most need to know what's the overall pattern of it and why things were done the way they were, because they couldn't learn that from anywhere else.

My big mail to Enrique contains a lot of useful information about the patch.

Other useful hints I could give are that the way the list is split, is like a balanced binary tree. It didn't have to be balanced, though, but that's sort of an ideal default, and it's really absolutely only to avoid stack overflow, though in other situations it does save a _lot_ of processing (merge-sort, binary-search...).

_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec

On Thu, 26 Feb 2009, Frank Barknecht wrote:

I took the version without the message box optimization

Well, I think that the switch from a O(n^2) abstraction to any of the O(n) abstractions is such a great improvement, that there is not so much need for more.

But basically, all further optimisations replace the right-hand part of the patch by a special-case dripper that only work on small list sizes.

for now to keep it a little bit compatible with older Pds that don't have settable sends - though I fear, a missing [list length] breaks it on older Pds anyway. I could have added [list-len] instead but that probably eats up all speed gains.

Well, what do you want to do without [list length]? I say kill all the old versions of Pd. If you don't know what to do or if life seems too easy, support old versions of Pd, back to 0.35. But there's a limit to self-inflicted torture.

Pd is already limited enough by what you can use in recursive patches... cold inlets unusable, so, have to use [list length] twice... can't reasonably pass a list and something else in the same message either, because it would requiring copying the said list. no nested lists of any kind.

Instead of always looking after Pd 0.39, Why not look after Pd 0.43 ? I think that the explanation for why [list-drip-quick] is the way it is, should serve as an example of things that could be changed in Vanilla or added to Vanilla... as long as you consider Vanilla to be the reference.

The message box version is in my 43 folders to be added sometime later. I added the EOL-outlet of the original list-drip and a bit more air around the objects so they don't overlap with font size 10.

I use font size 10 and they don't overlap and never have.

Additionally I added a [list-rdrip] for reverse serialization that uses the same approach, but with just one center-splitter. May come in handy sometimes.

Well, in any case where the highest speed is appreciated and order is not important, reverse dripping is faster than forward dripping, with today's pd.

_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec

On Wed, 25 Feb 2009, Mathieu Bouchard wrote:

I think that its biggest practical downside might be that's it slower on very small lists, but that's all.

That's not true. It's actually faster.

_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec