Are you trying to add Pd messages to a queue of Pd messages, or create a fifo for atoms? -Jonathan
On Sunday, November 22, 2015 11:17 AM, Roman Haefeli <reduz...@gmail.com> wrote: 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 > >> <reduz...@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" <reduz...@gmail.com> An: Pd-List > >>>> <pd-list@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@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 -> > 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