New 1D data container: Circular Buffer

[Darin.K]

There is a construct I am quite fond of in pointer-friendly languages, using iterator math to implement circular buffers of arbitrary data types.  They are a little bit slower to use than straight arrays, but they provide a nice syntax for fixed sized buffers and are helpful in cases where you will be prepending and appending elements.

I am pretty certain that queues are implemented as circular buffers under the hood, so much of the infrastructure is already in place, this is mostly adding a new API.  Added bonus:  the explicit circular buffer can be synchronous, unlike the queue, so for example you can put them in subroutine VIs.

It should be easy to convert 1D arrays to/from circular buffers.  Array->CB is basically free, the elements are in order in memory.  CB->Array requires two block copies (most of the time).  This can be strategically mananged, much like Reverse or Transpose operations.

Use cases:

You can implement most of  the following two ideas naturally:

http://forums.ni.com/t5/LabVIEW-Idea-Exchange/Looping-Input-Tunnels/idi-p/2020406

http://forums.ni.com/t5/LabVIEW-Idea-Exchange/New-modes-on-auto-indexed-input-array-tunnels-in-loops...

Circular buffers would auto-index and cycle the elements and not participate in setting 'N'.

You can do 95+% of what I wanted to do with negative indexing:

http://forums.ni.com/t5/LabVIEW-Idea-Exchange/Negative-Values-in-Index-Array-or-Array-Subset/idi-p/9...

A lot of the classic divide and conquer algorithms become tractable in LV.  You can already use queues to implement your own stack and outperform native recursion.  A CB implementation of the stack would be amenable to subroutine priority and give a nice performance kick.  I have done it by hand for a few datatypes and the beauty and simplicity of  the recursive solution gets buried in the implementation of the stack.  A drop-in node or two would give you a cleaner look and high-octane performance.

Finally, perhaps the most practical reason yet:  simple XY Charts.

As for appearance I'd suggest a modified wire like the matrix data type.  Most if not all Array primitives should probably accept the CB.  A few new nodes are needed to get/set buffer size and number of elements and to do the conversions to/from 1D arrays. The control/indicator could have some superpowers:  set the first element, wraparound scrolling (the first element should be highlighted).

[altenbach]

I am wondering if you have and more specific ideas how all this should look like?

As a simplemost solution for some of this we could have a primitive that looks similar to a height=2 "build array", but would keep the upper array size fixed between input and output, prepending whatever is wired to the bottom terminal to the existing array and discarding old excess data as needed.

[Darin.K]

I am probably inclined to have Build Array (and its ilk) coerce the CB back to a 1D array.  You can reconvert to a CB (for very little cost) explicitly which I think puts the onus on the developer to set things like size.  If you join two CB or a CB and an array there is some ambiguity in setting the buffer size and any type of automatic behavior is bound to annoy someone.

Removing element(s) can be done with the Delete Primitive, reducing the size is fine.

Adding a single element (in any location) should probably use the Insert Function.  Special consideration should be given for appending and prepending.  (Also true for arrays).

Full support should be included in the In Place Element Structure.

I should also mention that this would make short work of the ubiqutous rolling average.

Outside of the bread-and-butter operations (append/prepend a new element) I am open to implementation ideas.  As usual I prefer intuitive behavior to alternatives that are marginally more useful.

[PhillipBrooks]

According to Aristos from 2006, queues are indeed implemented as circular buffers (LAVA).

NI seems to take the cautious path when adding features to primitives and tries to differentiate between true functionality and "syntactic sugar". Lossy queue functionality was (thankfully) added, but I wish that some of the other ideas in the LAVA thread could be added to the basic queue implementation.

Block data operations such as least-squares-fit, FFT or just UI charting are a common use case for queued data. 

A "# of Elements" input to "Dequeue Element" fuction could make 1 call to the underlying Queue and return an array, rather than 1024 dequeue calls while trying elseware to load the queue at a high rate. I can't help but think that this would be more efficient memory and processor wise than a simple LV loop; IMHO raising it above the level of "syntactic sugar".

[Aaron_KZ]

Darin,

I have made many different labview circular buffers that you can copy:

http://forums.ni.com/t5/LabVIEW-Idea-Exchange/Buffer-Function-as-efficient-as-the-Waveform-Chart-s/i... 

(see the attached project showing comparisons between them)

They are super-duper awesome...

[Yamaeda]

Isn't the fixed buffer size queue basically the same thing? With lossy enqueue the oldest gets removed and/or the Rotate 1d-array?

/Y

[Darin.K]

> Isn't the fixed buffer size queue basically the same thing? With lossy enqueue the oldest gets removed and/or the Rotate 1d-array?

A queue is a circular buffer, but not all circular buffers are queues.

Setting aside the not always necessary or desirable asynchronicity of the queue operations, simply consider the steps involved in incrementing the values.  Flush Queue + Increment + Enqueue Element N times in a loop.

[Yamaeda]

Good point Darin, then the Rotate array is a better solution as you can use the normal array functions.

/Y

[tst]

> ...Rotate array is a better solution as you can use the normal array functions

The main problem with Rotate Array is that it has to move every single element in the array in memory, which can be time consuming if you do often and on long arrays.

[Yamaeda]

Does it actually do that? Since an Array subset and build array would move an appropriate amount to the end/front of the list. If LV really moves all array elements they seriously need a smarter array function in this case. 🙂

That being said, a circular buffer is needed, if the rotate array doesn't solve the problem in a good way something better is well needed. 🙂

/Y

[tst]

>... If LV really moves all array elements they seriously need a smarter array function in this case.

The whole point of arrays is that they're efficient, and they do that by being very simple - there's a start address and a fixed sized for each element. LV knows how to find the location of each index by multiplying the two, which is very fast. A smarter array function for something like this would require changing all array functions (or at least the one which calculates the index) to know how to start from a specific address and then loop back around after it got to the end. It will also require the array to have more intelligence when it needs to resize the buffer.

These modifications might hurt the performance more than would be considered acceptable (at least when you consider that indexing is much more common than rotating).