Just noticed this in another thread:

As if on cue: A question popped up that falls outside of the streaming paradigm: https://forum.pdpatchrepo.info/topic/13269/splitting-variable-lists-based-on-symbol

IMO that user is just begging for a simple dictionary in Pd.

I've been working in HTML5 lately, so when I see this which is ad-hoc and annoying to parse in Pd:

ps 0 fft -1 -2 hip 5 0.4 9,3;
fft 0 1 hip 0 1 2;

I immediately see the desire for this kind of data structure:

{ps: 0, fft: [-1, -2], hip: [5, 0.4, 9,3]};
{fft: [0, 1], hip: [0, 1, 2]};

Immediately, you see that just throwing a Javascript object in there is way too rich for Pd-- even for this simple example I've got anonymous arrays and curly brackets. It would be quite a task to add JS objects or JSON objects as a primitive type in Pd.

So the question is-- what would Pd-style key/value pairs look like? What would it feel like to use them?

If someone has a good answer that gets me excited I'll write it as an idea for Purr Data GSoC this year. The only related area I can think of are data structures, but they tend to be too clunky and complicated for most users.

Edit: Even the puredata.info syntax highlighter is hinting at the hidden structure in that flat list!

@jancsika I once made [store] as a not to serious approach to key/value storage: https://forum.pdpatchrepo.info/topic/11171/store-a-multidimensional-array-with-key-value-storage-for-floats-symbols-and-lists

Edit: The find method does not exactly what the help file is implying though...

Thanks, I'll take a look at [store].

One possibility is to just replicate Pd's symbol hashing table in an abstraction and have an array of binbufs at each position. That could be achieved with data structures text fields and would be fast. I believe I implemented something like this at some point for floats and symbols and forgot about it.

I think there's a lot of potential for this to be implemented purely with abstractions.

@ingox Solving the users problem it seemed to me that Pd is seething with key/value pairs.
The headers/tags float, symbol etc. are used extensively as key/value for message routing.
[list] permits longer value strings.
The problem for the OP was only that a series of key/value pairs had been stored as a list and that needed splitting.... but it's not a common problem..... and luckily the key was not also a float.
The old [moonlib/slist] shared keys throughout a patch.
I used to use [slist] extensively as a dictionary, loading it from text files as necessary via [iem_pbank_csv].

I replaced them for vanilla like this...... pbank-slist.zip ... using [text] at the time......

Keys are already a fundamental part of message passing/parsing.
And the correct way to store them as a string in Pd would have been with comma separators.
(I think...!! ...??...... sorry.... my thinking is not at your level @jancsika)
David.

@whale-av said:

@ingox Solving the users problem it seemed to me that Pd is seething with key/value pairs.

To be clear, I'm talking about dictionaries which are collections of key/value pairs. You can use a list, a symbol or even a float as a single makeshift key/value pair, but that's different than a dictionary. (Also known as an associative array.)

The headers/tags float, symbol etc. are used extensively as key/value for message routing.

This is a flat list where the first atom of the list acts as a selector. That's definitely a powerful data structure but it isn't an associative array.

[list] permits longer value strings.

These are variable-length lists, not associative arrays.

The problem for the OP was only that a series of key/value pairs had been stored as a list and that needed splitting.... but it's not a common problem..... and luckily the key was not also a float.

The OP's problem is instructive:

1. If you need to send a single key/value(s) pair somewhere in Pd, a Pd message will suffice.
2. If you need to store a bunch of key/value(s) pairs as a group (like an associative array does), a [text] object will allow you to do that with semi-colon separated messages. The important thing here is that the semi-colon has a special syntactic meaning in Pd, so you don't have to manually parse atoms in order to fetch a "line" of text.
3. If you want to send a group of key/value(s) pairs downstream, or you want to keep a history of key/value(s) pair groups, you have to start building your own solution and manually parsing Pd messages, which is a pain.

After doing a lot of front end work with Javascript in Purr Data, I can say that associative arrays help not only with number 3 but also number 2. For example, you don't have to search a Javascript object for a key-- you just append the key name after a "." and it spits out the value.

It may be that number 3 isn't so common in Pd-- I'm not sure tbh. But the design of the OP's data storage thingy doesn't look unreasonable. It may just be that those of us used to Pd's limitations tend to work around this problem from the outset.

The old [moonlib/slist] shared keys throughout a patch.
I used to use [slist] extensively as a dictionary, loading it from text files as necessary.

I'll have to play around with that one-- I'm not entirely sure what it does yet.

Keys are already a fundamental part of message passing/parsing.
And the correct way to store them as a string in Pd would have been with comma separators.
(I think...!! ...??)

I tend to use [foo bar, bar 1 2 3, bee 1 2 3 4 5 6 7( as a substitute for an associative array. But again, there's a limitation because you stream each message separately. E.g., if you have a situation where you route your "foo... bar... bee" thingy to some other part of the chain based on some condition, it's way easier to do that with a single message. But again, perhaps we're used to these workarounds and plan our object chains to deal with it.

David.

@jancsika you made something in this thread: https://forum.pdpatchrepo.info/topic/8836/dictionary-object-in-pd-extended/26

@Jona Ah, thanks. It looks like I even leveraged the "text" field for arbitrary value storage.

It's interesting, though-- since the value itself is restricted to be a flat list, it doesn't solve the OP's problem.

It might make a good GSoC project to allow recursive storage of key/value(s), and converting cleanly to and from lists.

But perhaps this is already getting too obscure for such a project. It's hard to know because I've gotten so used to the limitations of Pd's data types.

If you need to store a bunch of key/value(s) pairs as a group (like an associative array does), a [text] object will allow you to do that with semi-colon separated messages.

Performance is abysmal, though -- I had guessed this would perform linearly = O(n), and a benchmark proves it.

• The array y range is 0 to 3000 (= 3 seconds). 10000 lookups per 'pd benchmark'.

• I had to abandon the test because, long before 100,000 elements, each iteration of the test was already taking 4-5 seconds.

• [* 1.2] -- in a search, failure is the worst-case. This is an arbitrary choice to generate 1/6 or about 16% failure cases.

I translated this from a quick benchmark in SuperCollider, using its associative collection IdentityDictionary.

(
f = { |n|
    var d = IdentityDictionary.new;
    n.do { |i| d[i] = i };
    d
};

t = Array.fill(200, { |i|
    var n = (i+1) * 1000;
    var d = f.value(n);
    var top = (n * 1.2).asInteger;  // 16% failure
    bench { 100000.do { d[top.rand] } };
});

t.plot;
)

• SC's implementation is a hash table, which should give logarithmic performance. The graph more or less follows that.

• SC is doing 10 times as many lookups per iteration, but:

  • In this graph, SC's worst performance between 46000 and 56000 elements is 17.4 ms.
  • If I look up in the Pd 'bench' array at 50 (51000 elements), I get 3082.
  • Extrapolating for SC's number of iterations, that's 30820 / 17 = 1771 times slower on average per lookup.
  • Since Pd is linear and SC is logarithmic, this ratio will get worse as n increases.

"This isn't fair, you're comparing apples to oranges" -- true, but that isn't my point at all. The point is that Pd doesn't have a properly optimized associative table implementation in vanilla. It has [text], but... wow, is it ever slow. Wow. Really not-OK slow.

So than people think, "Well, I've been using Pd for years and didn't need it"... but once it's there, then you start to use it and it expands the range of problems that become practical to approach in Pd... as jancsika said:

It's hard to know because I've gotten so used to the limitations of Pd's data types.

That shouldn't be considered acceptable, not really.

TL;DR I would love to see more robust and well-performing data structures in Pd.

hjh

If you're measuring search, last I looked it's just a simple linear search with [text] classes.

The point is that Pd doesn't have a properly optimized associative table implementation in vanilla.

Well, it does-- it is the global symbol table which t_symbol hooks into.

There are all these leaky parts between the language and the implementation-- I think it's what you are noticing when a solution gets produced from "on high." The user either has pentested potential workarounds enough to know which constructions are likely to be performant, or they've looked under the hood to see how things are implemented.

For example, when I said this in the other thread:

At least when I look at OP's problem, I see global receiver names followed by messages.

It's because I know that the global receiver names are a) created using a simple, effective hashing algo, and their associations are already cached by the time a symbol becomes part of a message. So the cost of forwarding a message to a receiver is just the cost of message evaluation plus the cost of invoking the relevant receiver's function in pd_typedmess. Since the user obviously knows how many arguments each receiver expects, they can skip iterating over the args in order to forward the next message. No lookups or data copying is needed.

TL;DR I would love to see more robust and well-performing data structures in Pd.

Yeah, I'd be curious to know after jumping into Pd if you have any opinions on what they could look like or at what level they could be implemented. IMO a decent associative array implementation ought to fill most niches. The demo solution I wrote that @jona found could be expanded to make things more expressive. (It just reimplements Pd's t_symbol hashing algo in a subpatch.) But of course it would be limited to that particular class/object-- you couldn't use it to pass around an associative array. (I guess gpointers could be used to do this, but that's not a great UX IMO.)

It's also possible to add something at the level of a native data type, at the cost of all the thinking about new syntax and compatibility that requires.

Edit: my letter b above got converted to a sunglasses-smily emoji. I like it.

maybe [pool] is slightly related
https://grrrr.org/research/software/pool/

@jancsika said:

The point is that Pd doesn't have a properly optimized associative table implementation in vanilla.

Well, it does-- it is the global symbol table which t_symbol hooks into.

That's good -- SC also has a global symbol table, so that symbols can be matched just by comparing the internal ID.

That would speed up the string matching in [text search], but [text]'s sequential storage means that the search can never be better than O(n).

SC's dictionary is fast because storage is by hash. A 100 item dictionary would be stored in a 256 item array (where even indices are for keys and odd indices are for values), and the position of a key is key.hash % (array size / 2) * 2. Hash collisions just push an item later in the array (and the array expands as needed, rearranging the items). If the hash is well designed, it may need to search only a few items to find the right one (and IdentityDictionary further optimizes by doing the whole hash search in C). SC's implementation expands to the next power of two, hence, logarithmic time.

There are all these leaky parts between the language and the implementation-- I think it's what you are noticing when a solution gets produced from "on high." The user either has pentested potential workarounds enough to know which constructions are likely to be performant, or they've looked under the hood to see how things are implemented.

This is also just part of fluency (when you've already made and discarded dozens of mistakes).

Yeah, I'd be curious to know after jumping into Pd if you have any opinions on what they could look like or at what level they could be implemented. IMO a decent associative array implementation ought to fill most niches.

Yes, a hash table is one that I miss. (Lua tables become available through Ofelia, but I've noticed some overhead in converting data between Lua and Pd.)

One usage of hash tables in SC is an Event, which is a bridge between arbitrary, named musical data and a concrete sounding result -- (degree: 0) represents a tonic quarter note; adding instrument: \synthdefname plays it using a specific synth, but you can also add type: \midi, midiout: aMIDIOutObject to play the same on an external MIDI device/program without rewriting logic. It's rich enough to support even strummed chords within one event, but lightweight enough to generate dozens of them per second ([text] doesn't fly there). Very powerful.

I'm hard-pressed to think of others. Multidimensional arrays perhaps (which you can already hack together, but re-engineering this wastes users' time).

hjh

That's good -- SC also has a global symbol table, so that symbols can be matched just by comparing the internal ID.

Pd actually allows to bind those symbols with objects (as well as a facility to have multiple objects bound to the same symbol). So it's not just that [;ps 1 2( doesn't have to look up "ps" to find it in the symbol table-- it also doesn't have to a search to find the object bound to "ps".

Yes, a hash table is one that I miss.

@Jona posted a link to a demo implementation I did awhile back. A similar abstraction could be used for a batteries-included hash-table

Perhaps the best question is: what are the use cases that are currently cost prohibitive in Pd without a hash table? A long list of specific use-cases that are really clunky without one will help figure out the best interface. (Also keeping in mind the limitation inherent by Pd's ascetic choice of core atom types.)

I think getting a friendly interface to easily support the most likely use cases is the meat of the problem. One could design the most sophisticated, performant library. But if everyone uses it to dump out a flat list that they just [bang]--[until] into [tabwrite] then that wasn't a great design.

@lacuna Thanks, I can mention that as potential prior art in the project description.

Btw-- Google Summer of Code project descriptions are a bit of an art form. In the ones where we were too detailed we got back a lot of proposals that were just copy-pasta of the original description.

@jancsika said:

Perhaps the best question is: what are the use cases that are currently cost prohibitive in Pd without a hash table? A long list of specific use-cases that are really clunky without one will help figure out the best interface. (Also keeping in mind the limitation inherent by Pd's ascetic choice of core atom types.)

I'm pondering this. I don't have a lot to say about advanced Pd use cases though. There are some nice things we do with dictionaries in SuperCollider, which may or may not be compatible with Pd. Thinking about it.

One tricky thing about considering use cases first is: If you don't have it, you might go out of your way to avoid the need for it. So if someone says "where would this be useful?" you might say, "huh, dunno." But once you have it, then you may find other uses for it.

Anyway it's not much use for me if it doesn't make it into vanilla eventually (or... does/will Purr Data support Ofelia?).

hjh

does/will Purr Data support Ofelia

Got a user report that the main branch of Purr Data plays well with Ofelia, but I haven't made a release with those commits yet. (I'm in the weeds getting keyboard focus/interaction and automatic tab-indexing for iemguis.)

As far as shipping with Ofelia to all platforms-- I guess that depends on the level of support for that support.

I use a simple pdlua wrapper to a lua associative array: [lmap]. lua's arrays are ~supposed~ to be very optimised
https://github.com/sebshader/shadylib/blob/master/lmap.pd_lua

@seb-harmonik.ar Thanks, seb. It seems like pdlua is the most popular scripting lib in Pd. We ship it with Purr Data and try to keep up to date for that reason.

jancsika:

Got a user report that the main branch of Purr Data plays well with Ofelia

OK, that's good to know!

I switched to vanilla for courses because (a year ago when this course cycle was starting) Purr Data on Mac could not use GEM. And since then, I've gotten annoyed with GEM so I've put some effort into 60Hz's Ofelia abstractions. I wouldn't mind going back to Purr Data if I can be reasonably confident of it working with Ofelia in Mac and Windows. (I can try it in Windows but I don't have regular access to Mac.)

seb-:

I use a simple pdlua wrapper to a lua associative array: [lmap]. lua's arrays are ~supposed~ to be very optimised

I haven't used pdlua -- how is its performance when converting between Pd and Lua worlds?

As part of the work on shaders, I was testing whether it was faster to pass an "imageID xyz" message through one of these abstractions using [route] or using a function in the Ofelia script. Ofelia is slower, I think because it has to convert the Pd list into a Lua table, and then at the end convert the table back into a Pd list. I'm getting 17x slower with the bidirectional conversion (so Ofelia would be a bad choice if you need to go back and forth very often between Pd and Lua worlds -- may be fine if you just chuck a bunch of data into Ofelia, crunch it, and send results back to Pd less often).

hjh

@jancsika A little test for [text] without semi-colons...... slist.zip
Stepping could be done by line number if one needs that.
Long data sets should not slow it down as (I think?) they are not being searched.

I have no idea what method is used for a search (and that would be good to know), but it is fast enough for my purposes looking up control data by key..... (0.12ms on my machine for 5000th key.... 0.033ms for 3rd key).

Putting back the method for changing data by key..... which will suppress double entries....... makes it more useful but harder to test. There are no failures..... so not an associative array in the strict sense?.. or more likely because I have not tested for iteration?

Here it is in its useful form...... parameter storage and lookup.zip ...... a re-invention I am sure.

The key heads up the data on the right outlet for routing purposes.
Data sets can be saved and loaded from files by $1-float.txt
David.

0.12ms on my machine for 5000th key.... 0.033ms for 3rd key

That's an order of magnitude difference.

Imagine a table full of fortune cookies with 100 different people's names on them. You're asked to retrieve them for the people. In this case your only method is to search all of them. The person whose cookie is at the front of the table is lucky-- if they need to go in a hurry you'll find their cookie immediately. The person whose cookie is at the far end is unlucky-- you'll probably have to search through all the cookies before you find theirs.

Now hang 26 chains from the edge of the table, and label them with the letter A-Z. Store each cookie in a link of the chain that matches the first letter of that name.

Now on average you'll take a little more time to find the cookie that was previously sitting on the near edge of the table. But on average retrieving cookies will be 100 times faster.

However, in the worst possible case everybody's name begins with the letter "d" and you're back where you started. So you need a better rule than simple alphabetical order to try to get the worst case retrieval time closer to the average retrieval time. You'd prefer that "Dan" and "Dane" are in different slots, for example.

If you use the simple hashing algo in the gensym function that registers Pd symbols, it seems to do a decent job of spreading out symbols among all available slots in the table. So as long as the algo to map a name to a slot in the table is quick to run, this gets the worst case lookup time close to the average case lookup time, and that's good enough for a soft realtime system.

If the table has 1000 slots, and the time to turn a key into an index is negligible, then the only big expense is searching through the various items hanging from the chain at that index. In your example of 5000 items, the chain would likely only have five items to search. So the retrieval time on average is going to be a lot close to 0.033, and the worst case is unlikely to be much more than that.