[PD] Efficient FIFO in Pd: How?

Jack jack at rybn.org
Sun Nov 22 16:57:58 CET 2015


-----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
>> <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
> 

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

iQEcBAEBAgAGBQJWUeYCAAoJEOuluecjw8GUVOIH/0iVuh0aimX7PEzrkPZGb9/s
oUB1l5gwE2ugZJnaJpErfhawq04Ee3mNk6CE1+sGz7YTr/jMmDmfRiqUZ649Meax
PoTiInByVQH4i+uDgF8ExLKSM1uDIzVdJy8yPVJbFfQqBqBKmQXf4yazh6zqu6Rd
QMC5tq69z+0DkliECyhhmJaPDPPo6FI0bNvO/niesDSqCMCkStKXMk/z7wlE35jG
b+/DXFbTMn3hlDLASC38q4eBO73ls7wswv+CqFaOK/hKhMpY48KRw1kLB1slXwUS
iW1M7S02gqXAbtxPEHPncCOgMsUmE5E+6NMTTdgyp28eZYDaY2U8y9m/9lPMtpA=
=T85G
-----END PGP SIGNATURE-----



More information about the Pd-list mailing list