[PD] Efficient FIFO in Pd: How?

Sun Nov 22 20:28:55 CET 2015

-----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 
>>>> <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
> 
> 
> 
> _______________________________________________ 
> Pd-list at lists.iem.at mailing list UNSUBSCRIBE and 
> account-management -> http://lists.puredata.info/listinfo/pd-list
> 

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJWUhdyAAoJEOuluecjw8GUNf0H/1ewLE6AyP82MFZxFv8uRqxR
OugcPrTN2KGtXsfZ/yopneoyymyzdMIoWa6re2vNG0AIbs0EQlssS2YPiggOaQIO
qRP9eKcK9REnuatxJILRw1Ypn9fRW+24eGseHbqX6+ElNGfmWLAdP6TI94JACJkk
ac9N805L65lHNlr+NG+t9jlLbmutHnG5F460e+UkrNWfoG6aFOjDMkni6Fc9amVl
mPEI95hJnGD6cgKYk5uwQ4SUhnZ2Qy0us7JuwkUmsvWk0iLIY3MxUUTsdcKSMQJA
jNI5VL2dnyB4cthebmRz0BKBMWWH5AAs5KpnG/Xh4llMe+2p9dtlOb1mdRZMSr4=
=fNKU
-----END PGP SIGNATURE-----