[PD] [PD-dev] extremely fast pure pd [list-drip] (fwd)

[Mathieu Bouchard]

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