[PD] Efficient FIFO in Pd: How?

[Roman Haefeli]

On Sun, 2015-11-22 at 16:57 +0100, Jack wrote:
> Why you don't use [text] to build a fifo abs ?


One of the three examples I posted uses [text] as storage. While popping
is fast, adding messages to the buffer gets slower the more messages are
in the buffer. I was looking for an implementation that is fast with
pushing and popping.

Roman

> 
> Le 22/11/2015 09:47, Roman Haefeli a écrit :
> > 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
> >> 
> >> 
> >> 
> > 
> > 
> > 
> > _______________________________________________ 
> > 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/5a00171e/attachment.sig>