Re: [PD] Efficient FIFO in Pd: How?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Ok, understood, i didn't see your attached patch from your first mail. ++ Jack Le 22/11/2015 17:15, Roman Haefeli a écrit : > 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 >>>> 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 th
Re: [PD] Efficient FIFO in Pd: How?
Hm, originally I was thinking this:[struct fifo float head float tail array a fifo-datum] [struct fifo-datum float flag float f symbol s] for a fifo of single-atom messages. But for a fifo of Pd messages I'm talking about this:[struct fifo float head float tail array a fifo-datum] [struct fifo-datum text t] -Jonathan On Sunday, November 22, 2015 1:35 PM, Matt Barber wrote: You'd store the number of elements in the list at the first index of a fifo entry and the number of elements in the symbol or float just before the data for each atom -- on read you'd accumulate the atoms of the list and stop. The next index would be the number of elements in the next fifo list entry. On Sun, Nov 22, 2015 at 12:46 PM, Jonathan Wilkes via Pd-list wrote: I might be reading it wrong, but Matt's description sounds like a way to queue atoms, not Pd messages. With the "text" field of data structures it might be possible to add Pd messages to that design-- that is, you could have a data structure array where each element is a text field. But Pd is still going to have to allocate memory for each text field as you add it to the queue. -Jonathan On Sunday, November 22, 2015 11:50 AM, Roman Haefeli wrote: On Sun, 2015-11-22 at 16:24 +, Jonathan Wilkes wrote: > Are you trying to add Pd messages to a queue of Pd messages, or create > a fifo > > for atoms? I was/am interested in a FIFO implementation for Pd messages of any size (containing symbols and/or floats). Why are you asking? Do you know a way to works well specifically for single atoms? 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
Re: [PD] Efficient FIFO in Pd: How?
You'd store the number of elements in the list at the first index of a fifo entry and the number of elements in the symbol or float just before the data for each atom -- on read you'd accumulate the atoms of the list and stop. The next index would be the number of elements in the next fifo list entry. On Sun, Nov 22, 2015 at 12:46 PM, Jonathan Wilkes via Pd-list < pd-list@lists.iem.at> wrote: > I might be reading it wrong, but Matt's description sounds like a way to > queue atoms, not Pd messages. > > With the "text" field of data structures it might be possible to add Pd > messages to that design-- > that is, you could have a data structure array where each element is a > text field. But > Pd is still going to have to allocate memory for each text field as you > add it to the queue. > > -Jonathan > > > > > > > On Sunday, November 22, 2015 11:50 AM, Roman Haefeli > wrote: > > > On Sun, 2015-11-22 at 16:24 +, Jonathan Wilkes wrote: > > Are you trying to add Pd messages to a queue of Pd messages, or create > > a fifo > > > > for atoms? > > I was/am interested in a FIFO implementation for Pd messages of any size > (containing symbols and/or floats). > > Why are you asking? Do you know a way to works well specifically for > single atoms? > > > 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
Re: [PD] Efficient FIFO in Pd: How?
I might be reading it wrong, but Matt's description sounds like a way to queue atoms, not Pd messages. With the "text" field of data structures it might be possible to add Pd messages to that design-- that is, you could have a data structure array where each element is a text field. But Pd is still going to have to allocate memory for each text field as you add it to the queue. -Jonathan On Sunday, November 22, 2015 11:50 AM, Roman Haefeli wrote: On Sun, 2015-11-22 at 16:24 +, Jonathan Wilkes wrote: > Are you trying to add Pd messages to a queue of Pd messages, or create > a fifo > > for atoms? I was/am interested in a FIFO implementation for Pd messages of any size (containing symbols and/or floats). Why are you asking? Do you know a way to works well specifically for single atoms? 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
Re: [PD] Efficient FIFO in Pd: How?
On Sun, 2015-11-22 at 16:24 +, Jonathan Wilkes wrote: > Are you trying to add Pd messages to a queue of Pd messages, or create > a fifo > > for atoms? I was/am interested in a FIFO implementation for Pd messages of any size (containing symbols and/or floats). Why are you asking? Do you know a way to works well specifically for single atoms? Roman signature.asc Description: This is a digitally signed message part ___ Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Re: [PD] Efficient FIFO in Pd: How?
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 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 > >> 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. Novem
Re: [PD] Efficient FIFO in Pd: How?
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 > >> 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" An: Pd-List > >>>> Betreff: [PD] Efficient FIFO in Pd: > >>>>
Re: [PD] Efficient FIFO in Pd: How?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Why you don't use [text] to build a fifo abs ? ++ Jack 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 >> 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" An: Pd-List >>>> 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 elemen
Re: [PD] Efficient FIFO in Pd: How?
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 > 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" > > > An: Pd-List > > > 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 > >
Re: [PD] Efficient FIFO in Pd: How?
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". 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 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. Matt On Sat, Nov 21, 2015 at 7:52 PM, Roman Haefeli 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" > > > An: Pd-List > > > 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
Re: [PD] Efficient FIFO in Pd: How?
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" > > An: Pd-List > > 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 > > signature.asc Description: This is a digitally signed message part ___ Pd-list@lists.iem.at mailing list UNSUBSCRIBE and account-management -> http://lists.puredata.info/listinfo/pd-list
Re: [PD] Efficient FIFO in Pd: How?
I was looking at the help patch for [pipe] the other day, and noticed that there has been a change. I think it was to allow symbols too. (Sorry, can't check on my phone now) On Sunday, November 22, 2015, Roman Haefeli wrote: > 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
Re: [PD] Efficient FIFO in Pd: How?
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. > Gesendet: Sonntag, 22. November 2015 um 00:24 Uhr > Von: "Roman Haefeli" > An: Pd-List > 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
