[PD] Efficient FIFO in Pd: How?
Jack
jack at rybn.org
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-----
More information about the Pd-list
mailing list