Queues: Possible and Useful?

[coderkearns]

While there seems to be a couple simple queue implementations in the libraries, I feel a built-in and robust version would be very useful when making more complex things in XOD.

C++ is not my strong suit, and after a number of tries I was only able to white out my screen and get lots of errors.

A couple things I think would be important:

1. Queue has its own type which is mutable (you don’t need to daisy chain each queue method into the next, all the queue methods only need a queue input)
2. Queues have enough safety that they could be used in multiple “simultaneous” loops.
3. Queues are generic, there isn’t a number-queue and a string-queue and a boolean-queue.
   3(b). This probably means there is a “New Queue” Node that takes in the generic it will be built from and creates a queue. Its output could be placed in a bus and used all over the place.

What do y’all think? Is it possible? Would it be useful enough to be a builtin?

[coderkearns]

Here’s a simple image of what it might look like:

[gweimer]

I’m not sure you can create an object like that & have generic pins in XOD…it won’t know when you create it what the sub-nodes (push/pop) are going to connect to, but it would be easy enough to have a queue-number, queue-string, etc.

Should it be a First-in-First-out or First-in-Last-out? Two implementations? Allow either (pop-top, pop-bottom)?

Are you going to define queue size when you create it, or use dynamic memory allocation? The latter could cause memory usage issues that are hard to track down when program just dies… This is even more of a problem for a queue of strings since each one can use quite a bit of memory.

“Pop waits if there is nothing in the queue”…That is going to be hard to implement unless you have a “done” pin on the pop node for flow control. As shown above, the program is going to assume output of pop has updated while it is “waiting”. It might be better to have an “undefined” value that gets returned if queue is empty, but that would be data-type dependent…

The fact that there are so many options for implementing queues is probably why there are so many libraries and no built-in implementation. Arduinos also tend to be memory-constrained, so implementing something that can quickly chew threw it is something many would hesitate to do.

Interesting…I’m surprised gweimer/utils is the only match for “queue” in Libraries — XOD… It falls well short of what you are asking for… It only has the one node to implement queue with generic pins, and I’ve had problems when it would get confused and not be able to cascade pin type correctly when chaining nodes together & fail to compile.

[coderkearns]

Wow, that was a super fast response and from the creator of the other queue themself!

I’ll preface this with saying I do a bit a LabVIEW (it’s how I discovered XOD) so the implementation I’m thinking of is very similar to theirs, which is very commonly used with one consumer loop and a bunch of producer loops.

I figured FIFO would be the goal, but it would probably be useful to have a common data structure and design patterns library with Queues, Stacks, etc.

I think dynamic memory allocation would be the way to go but my microcontroller knowledge is… limited at best.

The way I worded “pop waits if empty” might have been wrong. So far, its my understanding that if a C++ node has an execute function but doesn’t call emitValue, it won’t execute all the nodes that depend on that value. In the case of my screenshot above, the Watch wouldn’t even be called unless the pop used emitValue<output_OUT>(). If so, it would hopefully be trivial to add a:

if (queueInstance.empty()) {
    return
} else {
    // pop and emit here
}

EDIT: I was able to confirm this functionality is the case, so this would make an effective and simple wait so long as everything else works: test-eval-only-if-emit.xodball (5.1 KB)

The memory limitation is definitely a problem and probably makes this feature almost useless when compared with LabVIEW which usually has much more memory to use and spare. I can see it being used rarely at best so that might end the discussion right here… again, I’m not an expert on this stuff

It makes sense that generics wouldn’t work with custom nodes and types. Sad, but it makes sense. That also diminishes some of the value Queues would have, as in this case I envisioned a queue of “Command” records all being pushed in different places, and one consumer loop handling them as they come.

Thanks for the response!

[gweimer]

You can use generic pins for custom nodes, but the compiler needs to be able to determine from context what those pins should be. Generic pin means you can use the node for any data type, but compiler needs to be able to determine which type should be assigned to each node, it can’t change after compile-time. This means creating a queue “device” like your original example probably isn’t going to work. I’m not a XOD expert, so I could be wrong…

[peterli]

Will the response of the queue be faster?