"Priority" Channels

[KVR9]

One of the first things that pops out when you go from queues to channels is that there is no equivalent operation for channels to "enqueue at the opposite end". (And with very good reason, as outlined here and here).

But priority queues exist as a data structure.

So I was wondering whether anyone implemented a priority queue as a channel wire and if so, how that looked like.

Based on my (as yet) cursory understanding of channels, a messenger channel would be the best way to go about implementing such a priority channel?

(Note: I understand why such a channel can cause an indeterminate order of execution if more than two loops exist. But if there are just two loops, and only one channel, it is possible that such a channel can be useful.)

[altenbach]

You could probably implement an action engine that maintains value, priority, and age for each element, then implement decision algorithms of what to serve out based on priority and age (maybe internal priority should increase with age, else certain entries might never get out).

What is the datatype of the element? Might be difficult to implement a really flexible solution.

[IlluminatedG]

For the naive approach (where low priority items might be eternally stuck if not emptied quick enough) I could see implementing a custom channel wire that uses a map under the hood to store the sorted elements (maybe use a u32 as the map key = priority, 0 is the highest priority). It would not be the most efficient mechanism; little more than a map wrapped in a DVR with all the read/write checks added in.

I might have a go at that over the holidays. Bit busy right now finishing packing up my seattle apartment to move to the edge of the mojave desert.

If anyone else is feeling froggy (I'm the only person outside of NI that I know has made custom channel templates) you can find out info about channel implementations at https://forums.ni.com/t5/LabVIEW-Channel-Wires/Getting-Started-With-Channel-Wires/td-p/3505658?profi...

[IlluminatedG]

Would be little more than just using a map in a shift register behind the scenes to keep the priority list of values. Not sure how LabVIEW would handle all the potential memory allocations or keep re-using space. Would likely depend on the element type.

[KVR9]

@IlluminatedG: Why the for loop in there?

A few further refinements and ideas:

A single element per priority as shown above is lossy. If there is a next map element with priority 0 and value theta, theta will override beta. So it is better to use the Registeration Map palette instead. (That point is courtesy of @AristosQueue).

 But on thinking it over, the above syntax is not ideal either. As the set is sorted, if I had a third register node after the first two with priority 0 and element apex, The set would be apex followed by beta instead of the other way around.

So, with maps, the ideal way would probably be something along the lines of:

 (Of course, there will be additional blocks to remove a particular priority if the array becomes empty and such, but this is the barebones of it)

[KVR9]

Actually, thinking a bit more on it, there is already an implementation of a priority channel.

@jkodosky's MessengerM channels! (Are they available to download somewhere? I could not find it anywhere..)

He has spoken of them in a few places, and borrowing a screengrab from one of them:

The subchannel input can double as priority level, and if I understand the implementation right:

The reader can first chck for the number of elements in subchannel 0 (highest priority). If that is empty, check in the next subchannel, and so on. And when it gets to the the subchannel that has an element, read it out.

[IlluminatedG]

That was just the idea I through together in like 2 minutes 🙂

I would want to benchmark between grabbing the first element (becomes an iterator under the hood) or grabbing the min/max element (possibly traversing both "sides" of the tree) and see which has less overheard. Maybe since you'd only be looking at min or max it wouldn't be running the other traversal?

The actual data type of the element would need to be at least an array to hold the members of the same priority. Bit of array overhead and hence the remark about memory allocations and depending on the element type.

The iterative approach to the priority handling is explicitly what I was avoiding. How high do you count to find something? What's the max priority value allowed? Does it just spin over all priorities until something comes in? If you only have a handful of priorities it's likely the best setup to go with but the overhead goes up with the number of priority values that are allowed.

[KVR9]

---

@IlluminatedG wrote:
That was just the idea I through together in like 2 minutes🙂

🙂

@IlluminatedG wrote:
I would want to benchmark between grabbing the first element (becomes an iterator under the hood) or grabbing the min/max element (possibly traversing both "sides" of the tree) and see which has less overheard. Maybe since you'd only be looking at min or max it wouldn't be running the other traversal?

---

Same thing occurred to me too. I thought as it is a primitive, there may be some compiler optimizations under the hood that do just the one connected operation instead of two (like with malleable VIs). Worth exploring. (If we leave collections aside, and use the normal Max and Min or Array Max and Array Min, are such optimizations present, do you know?)

@IlluminatedG wrote:
The actual data type of the element would need to be at least an array to hold the members of the same priority. Bit of array overhead and hence the remark about memory allocations and depending on the element type.

I think this overhead can be mitigated if the channel has a fixed size for each priority. Do a replace element instead of add/delete. Maybe even a circular buffer with pointers.

@IlluminatedG wrote:
How high do you count to find something? What's the max priority value allowed?

I was thinking that depends on the user, and could be a configuration setting or something. If you are going with priority channels, you need atleast 2, obviously. 3 (like in AF) or maybe even 4 might be OK, but any more seems like overkill and a code smell. 🙂

@IlluminatedG wrote:
the overhead goes up with the number of priority values that are allowed.

---

What overhead would that be? The ones with arrays you alluded to above?

~ Vijayanth.