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!

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.

@jancsika Fascinating.
It will take me some time to work through data science development since the 18th century.
gensym seems to be used extensively in externals.
60 keys is likely to be a maximum in any control patch I build, but any increased speed would be helpful.
The biggest so far had 64 in each of about 30 stores, where the patch looked up which store to search. Maybe a similar principle although of course no redundant slots.
David.

@whale-av I tend to be like you. The places I miss key/value pairs the most are the cases where there would typically be less than 10 keys. E.g.:

• doing math on some values. pitch * attenuation_level is way more readable than $f1 * $f2

• small collections of values, like what comes out the right outlet of soundfiler. It's a travesty that you cannot do [get - samplerate] on that output-- instead, you have to open up the help patch and manually map list positions to arguments. (And a reader of that patch must do the same if there happens to be an error somewhere.)

This is the problem of making even an elegant, performant, well-documented abstraction for a key/value store-- you cannot extend it to the other places in Pd where you need it.

@jancsika Just an undeveloped idea..... because I use a small lookup [slist] as part of [slist-master] throughout some patches....
.... a [value x] with a proper hash key "x" table behind it......created when the first [value x] is put, or separately... and so with global variable keys...... so that one could just send the key into its inlet to get the data.
You could add samplerate and other useful keys to it automatically of have a [value pd] that serves up internal parameters.

It "sort of" half exists for [expr].
You can do [expr pitch * attenuation_ level] if you first set [value pitch] and [value attenuation_level]....... but of course at the moment every [value] has one slot.
David.

@jancsika So I have changed [slist-master] so that it uses [value] to distribute globally.
Because I started with lists the second piece of data for foo is assigned to [value foo2] and so can be "got" from anywhere including in [expr]
slist-master.zip

Unfortunately [value] doesn't distribute messages across its inlets so its "name" cannot be changed on the fly without extra objects.
External with # please..... although maybe not for lists...... just key/value......?
David.

So here's what I'm thinking about. I'm not sure if this makes sense in Pd...

In SuperCollider, I can do:

s.boot;

(instrument: \something, midinote: 60, sustain: 2, amp: 0.7).play;

... and the sound comes from SC's own engine, based on a synth template named \something.

And I can also do:

MIDIClient.init;
m = MIDIOut(0).connect(0);

(type: \midi, midiout: m, midinote: 60, sustain: 2, amp: 0.7).play;

... and the same parameters midinote: 60, sustain: 2, amp: 0.7 are translated into MIDI noteon/noteoff messages, and performed by any MIDI software or hardware synth listening on that port.

A concrete benefit is: If I write some compositional algorithm and I want to decide later whether to play it within SC or using an external instrument, I don't have to change the composition logic at all. That part simply stuffs data into Event objects, and the event determines what finally happens.

In Pd, the data and the path the data take through the system are tightly coupled -- positional access to specific values is one way that this manifests, but more significantly, in a way, tight coupling is just the nature of dataflows.

So I'm wondering if this is a way to decouple: you could describe an action as a set of key-value pairs, forward the set to any event-player, and the event player would look up the data that it needs.

To some extent, you can already do this by discrete "key value" messages and [route]ing them into different parts of the player, but this isn't totally transparent: 1. If they are discrete messages, how do you know when the event is complete? Needs a sentinel. 2. [route] takes a little time to ignore irrelevant data (while a dictionary lookup would simply not look up irrelevant data). 3. If the pairs arrive out of order, math ops could be tricky, e.g. the following spits out a spurious 5 before the dog value comes through:

But with this hypothetical, you could control the order of access in the patch, instead of relying on well-behaved data:

This use case suggests that a dictionary should be lightweight, like a list, easy to pass around in the system (so, different from [text] or [array]). That matches up with jancsika's use cases (passing this type of dictionary into [expr] or getting it out of [soundfiler])... but it perhaps doesn't fit easily into the current message-passing scheme.

hjh

but it perhaps doesn't fit easily into the current message-passing scheme.

Funny enough, [get] takes a "gpointer" to a "scalar": essentially a bunch of typed key/value pairs stored in a byte array.

The problem there is too much boilerplate-- you can't just create an ad hoc datum and send it on its way. Instead you must first define the template for that data, then instantiate the data, then grab a reference to it by walking a linked list.

If that paragraph I just wrote could be superceded by a more sensible method for quickly defining and passing such data, that could be a solution. (There's also [set] for setting a key by name.)