Best Circular Queue Implementation?

[rex1030]

Despite circular queues and buffers being a fundamental data structure in most programming langauges like c++ and java, labview doesn't seem to have any inherent circular queue functions.

Here is my situation. We are doing structural monitoring and I am using a crio device and I am acquiring data from 11 channels at 200Hz in on one loop and passing it to a record loop that is recording the data continuously. Now that we have recorded for long enough we have developed an algorithm to trigger recording based on events in the data. 

So I want to acquire data in one loop and write it to a queue. In the second loop I want to be writing pre-trigger data to a circular queue so that when an event is triggered, I would record the pretrigger data from this queue to file and then record data from the main queue to file until I have aquired enough post trigger data. It would then stop recording to file, fill up the pretrigger queue and continue writing to the circular queue. I also need to be analyzing the data on the fly as well to detect the trigger based on an amplitude change on any one of the channels (each with a different trigger value). 

So, I really feel like I am missing something fundamental here in LabView mechanics. I don't really want to re-invent the wheel here coming up with my own circular queue function, but I will if I have to.

I thought about writing to a second queue (the pretrigger queue) and dequeing enough elements to maintain the same queue size but this doesnt seem like the best way to do it. 

I like TST's example here: TST's Circular Queue

but I am not sure he is doing it in the most efficient way and quite frankly, I need the most efficient and resource-friendly way of doing this because I am working on an RT device (crio) with a decent data rate. So I need to minimize memory reallocations and cpu usage.

Can anyone offer any really good circular queue functions?

I swear Labview just needs to add circular queue functionality. You should be able to specify a queue size and queue type (circular or linear) when you execute the obtain queue function and it should operate like a circular queue, popping the oldest element when it pushes the newest. Isn't this low-level array index control, memory address control, that needs to be done by the language to avoid race conditions?

[RavensFan]

If you use the LabVIEW queue functions, the obtain queue function lets you set the max queue size.

For older labVIEW versions, what you could do is enqueue elements.  If you look at the stats of the queue and find it has reached its max size, then you can dequeue an element before enqueueing the next element.

Newer LabVIEW versions have the lossy enqueue function which will remove the element from the front of the queue automatically if it is filled when you want to enqueue the next element.

Whenever you want to actually view the elements in the queue without removing them from the queue, then use the preview queue function. 

Wouldn't that concept work for you?

[nathand]

I don't know about best, but here's a circular buffer I wrote a while back when I needed to do something similar (high-speed data acquisition with a pre-trigger).  It can handle an arbitrary number of channels and samples per channel.  Note that it's not a queue, it's just an array in a shift register (similar to TST's example), but it does demonstrate that you can handle all the array indexing just fine in LabVIEW.  With small modifications you could use it as a functional global.  If you do that,  it might be easier to make it a single queue for all your data, both post and pre-trigger.  After the trigger occurs, wait enough time to capture as much data as you need, then dump the entire buffer to a file at once.  You'll of course need to make sure that the buffer is big enough for one entire data collection period.

EDIT: added attachment

Message Edited by nathand on 01-06-2010 04:26 PM

[tst]

I can't look at the code I posted there at the moment, but assuming it's the same as I remember, it should be reasonably efficient (a single buffer which is rotated and replaced). That said, I haven't checked too carefully to see that it has no copies.

In 8.6 and later, the queue palette has a subpalette which allows doing a lossy enqueue, just like you want - if the queue is full, the oldest element will be replaced. I don't remember the details, but since the queue elements are probably saved using pointers, there should be no problems with reusing the memory there. One thing to look out for is that the queue doesn't allocate the memory when you obtain it, so you will probably want to fill it with dummy data before you start.

Another thing to look out for is that if you will preview the queue you will generate a copy. If you dequeue, the queue will obviously not be full. That's one of the advantages of the action engine I mentioned in the other post - if you do it right, you can have no data copies.

[rex1030]

Sounds like Lossy Enqueue is what i am looking for. Automatically dequeueing when it enques. You guys rock. I knew this was too simple to not have been solved already. Thanks gentlemen.

I'll probably try a few different methods and benchmark them to see what is the most efficient.

Message Edited by rex1030 on 01-06-2010 04:56 PM

[Ben]

---

rex1030 wrote:

Sounds like Lossy Enqueue is what i am looking for. Automatically dequeueing when it enques. You guys rock. I knew this was too simple to not have been solved already. Thanks gentlemen.

I'll probably try a few different methods and benchmark them to see what is the most efficient.

Message Edited by rex1030 on 01-06-2010 04:56 PM

---

I would be very interested in your results. Posting them would be a benefit to the community and may prompt some tweaks recomendations tht may help all of us.

Thank you,

Ben

[rex1030]

Well it appears that using a queue data structure is not practical. Each time a new data element is added to the queue I need to run an analysis on all the data in the queue to see whether an event has occured. If I used the queue structure I would have to dequeue every element in the queue into an array, then analyze the data points, then enqueue them back in a queue. This is way too much memory reallocating for how fast I need to be able to do this on the RT device and is obviously not the way to go about this.

So I need to use an array where I keep track of the index of the first and last elements (insert nightmares of data structures class here). 

My question now is what array functions do memory reallocating and which don't? From my understanding, the 'build array' does memory reallocating while the 'index array' does not. Is this correct? What else should I know about what I am trying to do? Can any of you labview pros drop an example?

Thanks

[nathand]

What sort of event are you expecting to occur?  I gather from your description that it's not something that can be detected from a single element in the queue, otherwise the queue solution would work for you.

The "Show Buffer Allocations" feature under Tools->Profile is helpful for determining where buffer allocations happen, although a buffer allocation does not necessarily mean that an entire new copy of the data is made at that point.  Searching this forum will turn up good information about memory optimization.  However, I highly recommend trying to get it working with a simple approach, and then only work on reducing memory use if necessary.  Don't start trying to write the most efficient code ever from the start.

Build array does not necessarily require memory reallocation; that's a problem mostly inside of a loop when build array constantly increases the size of the array.  If you are always building an array of the same size (you're not connecting the output and an input of build array to a shift register) then this is less of a problem.  If you do need to increase the size of an array inside a loop, preallocate an array outside the loop and then use replace array subset.

I think the example I posted earlier does a good job of memory management, take a look at it.

[rex1030]

Sinced you asked, the original data is 14 channels at 200Hz. The event will only need to be detected on channel 11. There will 1 second of 'pre-event' data and 0.5 seconds of 'post-event' data being analyzed to detect an event for a total of 300 data points. If the difference between the average of the pre-event data (first 200 points) and the average of the post-event data (last 100 points) is greater than 0.02 then an event has occured and all the data in that time period needs to be recorded. Otherwise, remove the oldest data from the queue and add the newest data and run the analysis again.

I must admit I found your previous example a little confusing.

[nathand]

---

rex1030 wrote:

I must admit I found your previous example a little confusing.

---

Sorry, it is lacking in comments.  Here's how it works:

At the start, allocate an array large enough to hold as much data as you need by setting the number of channels and points per channel.

There is also a shift register that tracks the current position in the array (the location where the next set of data will be written), initially set to 0.

Each time through the while loop, read all available data from the DAQ system.  Transpose that array (necessary to maintain ordering), then convert it to a 1-D array.  Write that new data to the current location in the buffer.  If the new data is too long to fit in the buffer, split it, then write the end of the new data to the beginning of the buffer.  Update the current location in the buffer. 

To get individual channel data out, decimate the buffer into the appropriate number of channels.  Decimation is an efficient operation (see here).  In your case, each time through the loop you would decimate into 14 channels, take only the data from channel 11, and do your analysis.  You would need to use the current index into the buffer to determine where the pre- and post-event data starts.

There might be a more efficient way to do this in your case by maintaining a running average of the single channel on which your event occurs, then pulling out the data for all channels when you detect the event.