[PD] Efficient FIFO in Pd: How?

[Roman Haefeli]

On Sun, 2015-11-22 at 01:47 -0500, Matt Barber wrote:
> Your [fifo-list] is very much like [list-fifo] from list-abs, which
> suffers from the poor [list] performance. The message-box one also
> suffers from having to use lists to dequeue.
> 
> 
> I've thought of a way to do it using [list fromsymbol], [list
> tosymbol], and an elaborate array storage scheme which would store the
> length of each list at the beginning of the list like you do in the
> others, and then the length of each symbol before each symbol (or -1
> to store a float). Enqueueing would cost one [list-drip] plus the
> encoding and storing per list, but since the array is random-access,
> it should be O(n) over all with the size of the fifo.
> 
> 
> Retrieving would do it in reverse, which would cost one [list
> prepend]X[t a] loop plus reading and decoding per list, which should
> also be O(n) with the size of the fifo.
> 
> 
> You'd maintain a write and a read index into the array; [array size]
> the array to 2^24. What to do when you reach the end of the array is
> the tricky part. If you want to be able to do a ringbuffer kind of
> thing, you could just maintain another array to prewrite the list
> encoding into. By doing this, you'll know the entire length of what
> needs to be written, and if that exceeds what you have in your table,
> you could write an instruction (-100, say), to start at the beginning
> again, and then reset your write index to 0. You'd need to test to
> make sure that an incoming write doesn't allow your "write head" to
> lap your "read head".


Yeah, I thought about something similar, too. It'll basically look like
this:

[list-fromlist] <- converts any list to list of numbers
|
[nfifo] <- FIFO using a table as a ring-buffer
|
[list-tolist] converts back to lists with symbols

> If you needed REALLY arbitrary size, if you got to the end of one
> array, you'd dynamically allocate a new one, and write an instruction
> to move reading to the next array when your read index reaches it.

I guess if I would go for the route of converting everything to numbers
first, I'd use simply a [table] and it could be resized when necessary.

> I have no idea if this would work (it should), or what the constant
> time complexity factors are here; my guess is that it's slower than
> the others for short fifos. [array set] and [array get] are faster
> than you'd think, though, allowing you to write chunks at a time,
> unlike [tabwrite].

> If you make it I'll tweak it (for style) to include in my array-abs
> collection; otherwise I'll add it to my list and make it later.

Sounds interesting to do, but I'm not sure whether I'm going to invest
time in it. [fifop] works pretty well for my current use case.

Roman


> On Sat, Nov 21, 2015 at 7:52 PM, Roman Haefeli <reduzent at gmail.com>
> wrote:
>         On Sun, 2015-11-22 at 00:47 +0100, Christof Ressi wrote:
>         > Just in case you don't know: There's the [fifop] object in
>         zexy which works with lists and also lets you set the
>         priority. I'm sure it's also faster than anything one can do
>         with Pd objects.
>         
>         Thanks, somehow I forgot that zexy has that. It is indeed fast
>         (as in
>         linear fast). I'm going to use it.
>         
>         Just out of curiosity, I wonder if there is a O(n) vanilla
>         implementation, too.
>         
>         Roman
>         
>         
>         > > Gesendet: Sonntag, 22. November 2015 um 00:24 Uhr
>         > > Von: "Roman Haefeli" <reduzent at gmail.com>
>         > > An: Pd-List <pd-list at lists.iem.at>
>         > > Betreff: [PD] Efficient FIFO in Pd: How?
>         > >
>         > > Hi all
>         > >
>         > > I'm looking for a way to implement a FIFO buffer in Pd.
>         I'd like it to
>         > > be able enqueue messages with an arbitrary number of
>         elements in order
>         > > to retrieve them in the same order later. I came up with
>         three different
>         > > methods, but they are all either slow at enqueuing or at
>         dequeuing or
>         > > even both. It seems for a quick implementation you need
>         something like a
>         > > ring buffer, but I can't think of any method that would
>         work for
>         > > symbolic elements, too (as opposed to numbers).
>         > >
>         > > Attached patch comparison.pd compares the methods. Isn't
>         there really a
>         > > O(n) implementation as opposed to O(n^2)?
>         > >
>         > > Roman
>         > > _______________________________________________
>         > > 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 --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: This is a digitally signed message part
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20151122/eb6b7354/attachment.sig>