[CR] Circular Buffer

[hooovahh]

Name: Circular Buffer

Submitter: hooovahh

Submitted: 24 Sep 2014

Category: XNodes

LabVIEW Version: 2011

License Type: BSD (Most common)

Description

 

This package contains functions for maintaining a circular buffer.  

 

Create the Circular Buffer using the Initialize Circular Buffer function.  This makes a DVR, and the data type of the DVR changes based on the data type specified for the circular buffer.  The data type can be any type as long as it is not an array.  It must be a scalar.  The size of the buffer is specified on initialization but can be changed using the Change Circular Buffer Size function.

 

Add data to the circular buffer using the Write Circular Buffer function.  Scalar values can be added, or a 1D array of data can be added.  The data type of the values to be written is the data type defined in the initialize function.

 

Read the data back out of the circular buffer using the Read Circular Buffer function.  The data type of the read values will be the data type defined in the initialize function.

 

Cleanup the program by destroying the DVR on exit.  An example VI Circular Buffer Demo shows how a Circular Buffer can be used.

 

XNode Disclaimer

 

The Initialize, Read, Write, Get Status, and Change Size functions are implemented as XNodes.  NI does not provide support XNode development.

 

For an introduction to XNodes read Adam Rofer's "XNodes - A Crash Course" presentation (http://lavag.org/files/file/56-xnodes-a-crash-course-powerpoint).

 

Dependencies

 

LAVA Palette-1.0.0.1

 

How It Works

 

The source is all open and the template VIs for each XNode is what is executed when the XNode is generated.  This means you are welcome to try to further optimize these XNodes by editing the templates.  A new instance of the XNode will need to be placed which will force the new code to be used.  If anyone finds performance improvements for these functions please feel free to post in the support topic.  

 

Because the size of the buffer is practically unbounded, I wanted to avoid unnecessary data copies, which is why it is designed around DVRs.  There exists 3 things in the DVR, the buffer size, a pointer to the current write location in that buffer, and the array of scalar values, whos data type is defined during the initialization.

 

Click here to download this file

[Neil Pate]

Nice work. This is such a good use of XNodes adapting to type behaviour. 

 

Couple of questions though... 

 

In the Read, there is a Rotate 1 D array, is this not quite an expensive operation?

 

Could that could be removed if a Read Pointer was introduced?

[hooovahh]

Good questions and I'm up for changing.  At the moment the way this works is a pointer does exist which keeps track of the next write location.  This means that after a write is performed, the value at index 0 may not be the oldest value in the buffer.  

 

Lets say your buffer has 100 elements.  If you write 90 elements, then index 0 is the oldest, and index 89 is the newest.  Index 90 through 99 will be the default of that data type.  If you then write another 20 elements then the oldest data will be at index 10, the newest will be at index 9.  This makes the write relatively fast because it doesn't need to shift the array around.  I could do shifting after each write so index 0 is the oldest, and that would make reading easier because no shifting around would be needed.  I designed it thinking that writes take place more often then reads.  Without knowing the application this may or may not be true.

 

So because the write doesn't shift the array around, the read needs to.  I suppose one improvement is after the read does the shift around, it could write the array back, so that if you read again you won't need to shift it around again.

[ShaunR]

Could that could be removed if a Read Pointer was introduced?

 

Not so trivial in native labview since to read contiguous bytes using the array subset, you need to split and wrap the array by making copies and sewing them together again. You'll be lucky of it doesn't get a lot slower than a rotate.

 

There is one that uses direct calls to the LV memory manager though, but a rotate is much easier.

Edited September 24, 2014 by ShaunR

[Neil Pate]

Not so trivial in native labview since to read contiguous bytes using the array subset, you need to split and wrap the array by making copies and sewing them together again. You'll be lucky of it doesn't get a lot slower than a rotate.

 

There is one that uses direct calls to the LV memory manager though, but a rotate is much easier.

 

Yes, that's what I normally do (keeping track of whether we have wrapped around or not etc). I have never done any benchmarks, always just done it that way.

 

Quite often my circular buffers have a method to read n samples rather than the whole buffer, so I find I need to keep track of a separate read pointer.

[hooovahh]

Quite often my circular buffers have a method to read n samples rather than the whole buffer, so I find I need to keep track of a separate read pointer.

The first place I thought about using this was in a graph situation, where you have a circular buffer of XY pair data for N channels and each channel maybe updated at different rates.  In this case it made sense to read the whole buffer.  I can see a use where you may want a subset and you can do that now of course reading the whole thing then get a subset, but it could be more efficient.

[SDietrich]

Hi all,

 

one way to avoid rotating the buffer and still be able to use the Array Subset Node is the following:

• allocate a buffer twice the size the user requested
• apply writes to buffer also to buffer[usersize + i]
• use Array Subset Node to return any contiguous part of the buffer very efficiently as a contiguous subarray

Another interesting possibilty is to calculate certain figures like average or standard deviation directly when inserting/deleting elements instead of fetching the whole buffer everytime you need that figure.

 

Regards, Sebastian

[hooovahh]

Oh that is clever.  So the trade off would be that your data in memory will be twice the size it needs to be, but no shifting operation is needed, and the other down side is each write is two writes.  I'm not convinced it would be worth it, but it could be done.  Again I guess it comes down to the fact, will you expect to be reading more than you are writing?  Or writing more than you are reading?

[Gary Rubin]

one way to avoid rotating the buffer and still be able to use the Array Subset Node is the following:

• allocate a buffer twice the size the user requested
• apply writes to buffer also to buffer[usersize + i]
• use Array Subset Node to return any contiguous part of the buffer very efficiently as a contiguous subarray

 

 

I must be missing something - doesn't that only help you half the time?  What happens when i=2*usersize and both of your buffers have to roll over at the same time?  

If you knew your max resize, you could probably size them so that both the smaller and larger buffer aren't integer multiples in length and are unlikely to wrap-around within the same read block size.

[hooovahh]

I must be missing something - doesn't that only help you half the time?  What happens when i=2*usersize and both of your buffers have to roll over at the same time?  

If you knew your max resize, you could probably size them so that both the smaller and larger buffer aren't integer multiples in length and are unlikely to wrap-around within the same read block size.

Okay I typed up a big long explanation on how it worked and half way through I figured out it wouldn't work the way I was thinking.  Never mind I need to see an example first.

[mje]

Having not had the chance to download your code...

 

When I've done circular buffers I've only ever rotated the array if and when a subset is read and the rotation is required. It's expensive yes, but if all you're ever doing is reading a scalar, you can go the entire lifetime without ever rotating.

 

Note this is from the perspective of non RT. You may wish to conditionally force a rotation on each subset read to reduce jitter.

[hooovahh]

Having not had the chance to download your code...

You should it is awesome and I'm not biased at all...okay well I just wanted to explore more XNode stuff, and I think it could be useful.

 

When I've done circular buffers I've only ever rotated the array if and when a subset is read and the rotation is required. It's expensive yes, but if all you're ever doing is reading a scalar, you can go the entire lifetime without ever rotating.

 

Note this is from the perspective of non RT. You may wish to conditionally force a rotation on each subset read to reduce jitter.

Right now the read returns the whole buffer, I can see that reading a subset could be useful especially if a rotate is not always needed.

 

Also I'm getting the idea that if a rotate was required, that we could then write the newly rotated data back and set the pointer back to 0.  I think this would mean that you can no longer have a write and read happening in parallel, but right now I think you could, not that I would want to.  The benefit of this is that if you did two reads in a row before a write, the second read would never need a rotate.

 

All sound improvements team, I'll implement these changes soon.

[GregFreeman]

You should it is awesome and I'm not biased at all...okay well I just wanted to explore more XNode stuff, and I think it could be useful.

 

Right now the read returns the whole buffer, I can see that reading a subset could be useful especially if a rotate is not always needed.

 

Also I'm getting the idea that if a rotate was required, that we could then write the newly rotated data back and set the pointer back to 0.  I think this would mean that you can no longer have a write and read happening in parallel, but right now I think you could, not that I would want to.  The benefit of this is that if you did two reads in a row before a write, the second read would never need a rotate.

 

All sound improvements team, I'll implement these changes soon.

You're a week late. I just implemented one of these for a project (only for one data type). Would have preferred to use yours. The xnodes make this about a factor of 10 better than mine  . If it's any consolation, I rotate the array as well.

Edited September 26, 2014 by GregFreeman

[Gary Rubin]

I must be missing something - doesn't that only help you half the time?  What happens when i=2*usersize and both of your buffers have to roll over at the same time?  

If you knew your max resize, you could probably size them so that both the smaller and larger buffer aren't integer multiples in length and are unlikely to wrap-around within the same read block size.

Okay, I was missing something.  For some reason, I thought the idea proposed was 2 buffers so that one wraps around when the other doesn't.  I see that's not what SDietrich was suggesting, but I still don't see how his extra-long buffer keeps a wrap-around from happening.  I guess I'm still missing something.

[ShaunR]

Okay, I was missing something.  For some reason, I thought the idea proposed was 2 buffers so that one wraps around when the other doesn't.  I see that's not what SDietrich was suggesting, but I still don't see how his extra-long buffer keeps a wrap-around from happening.  I guess I'm still missing something.

 

It doesn't prevent wrap-around from happening. It means that you can read a contiguous array of data at any point in the buffer without having to chop and concatenate.

Edited September 26, 2014 by ShaunR

[hooovahh]

It doesn't prevent wrap-around from happening. It means that you can read a contiguous array of data at any point in the buffer without having to chop and concatenate.

Okay I think I get it but for this to work the dual write operations need to stop after every buffer location has been written to once correct? 

 

• allocate a buffer twice the size the user requested
• apply writes to buffer also to buffer[usersize + i]
• Once the buffer has every point written to, continue writing at buffer[usersize+1] wrapping back around to buffer[0] after buffer[usersize+usersize] is written 
• use Array Subset Node to return any contiguous part of the buffer very efficiently as a contiguous subarray

[ShaunR]

• Once the buffer has every point written to, continue writing at buffer[usersize+1] wrapping back around to buffer[0] after buffer[usersize+usersize] is written 

Nearly..

 

After i=usersize, you wrap around to buffer[0] all the while writing to buffer and buffer[i+usersize]. Then, if you read at index i for a length usersize, you will get what you need.

Edited September 26, 2014 by ShaunR

[hooovahh]

Okay so I didn't get around to doing the double the buffer size technique.  I'm not convinced it would be for the best due to the extra memory needed, and the fact that two writes need to take place for each write.  But attached is a non-XNode version of the circular buffer which is implemented with strings.  I wanted to share this improved version with offset and length for reading subsets of data, and not performing a shift 1D array if it isn't needed.  Also if a shift was needed for the read, then write the shifted data back.

 

There were also some bugs with what happens if the buffer wasn't filled once.  There is also a mild bug with doing a read when the offset is greater than 0, and the length is greater than the size it will wrap around.  I didn't get to figuring out a way to fix that.

 

If anyone gets a chance take a look at the read and see if they can come up with a better way, or give the thumbs up to the way it was done.

Non XNode Circular Buffer.zip

[gb119]

One of the things I wanted to be able to do was to read from both ends of the buffer - so to have a way to get to the most recent n items for n less than or equal to the size of the buffer. So I tweaked the read buffer XNode template to handle a negative offset meaning to read from the current buffer position backwards (i.e.  Python style). This, of course breaks LabVIEW array indexing semantics, but for this particular situation it makes some degree of intuitive sense to me. The attached is my hacked template.

XNode Template.vi

[hooovahh]

Sweet, thanks for sharing.

[Rolf Kalbermatter]

On 25-9-2014 at 5:51 PM, hooovahh said:

Oh that is clever.  So the trade off would be that your data in memory will be twice the size it needs to be, but no shifting operation is needed, and the other down side is each write is two writes.  I'm not convinced it would be worth it, but it could be done.  Again I guess it comes down to the fact, will you expect to be reading more than you are writing?  Or writing more than you are reading?

I don't think you need to write the data twice each time. You need to shift the data once whenever you wrap around the end of the buffer on write, but that is all. The one drawback I see with this is that it could make the write operation pretty erratic in execution time and therefore unsuited to be called directly in a time critical or realtime loop.

[hooovahh]

Again I never got around to implementing it, but I assumed the reason for having the double buffer size, was because you would then never need to perform a shift, which is where I thought the more intensive operation would be.  By having a double buffer size I can perform a read and just have it read the subset of N samples that I want continuously, but of course to to do this a single write has to write to both halves of the buffer, but again no shift is needed.  

The method you described is close to what is currently implemented (in the non-xnode version posted), where there is one buffer, but it won't shift data, it will write it, and then if it gets to the end of the buffer, write again at point starting at 0.  This means no shifting and no double writing unless you reach the end of the buffer.  The trade off is that when you do a read you need to shift the data, if the subset you are trying to read wraps around the buffer, if it doesn't no shift takes place.  Since the shifting was taking place anyway on some reads, I had the read function write the shifted data back, so the next write starts at pointer 0 again.

These are the 3 implementations I've thought about with minor details changing how it is done under the hood, causing different performance.  As I mentioned before the current implementation is probably better than most if you are writing more often then you are reading, which was my case when I was needing this.  I never did any bench marking between these three.

[LarryColvin]

When I want to implement a circular buffer I generally use Lossy Queues. This allows "Get Queue Status" and "Flush Queue" to be used to peek/extract data from the circular buffer. The nice thing about this is it requires no work on your part to perform the shifting when the buffer wraps around. I'm not sure what the performance of this would be though compared to DVRs. Also a nicely created VIM (VI Macro) which does the unpacking of variant data allows the buffer to accept any data type.

Edited May 22, 2017 by LarryColvin

[mje]

Queue vs DVR shouldn't make much difference if all other implementation details are equivalent since both use the same underlying synchronization method. That said the synchronization will prevent either method from being as peformant as a native array implementation if access speed is a concern. 

[smithd]

3 hours ago, mje said:

Queue vs DVR shouldn't make much difference if all other implementation details are equivalent since both use the same underlying synchronization method. That said the synchronization will prevent either method from being as peformant as a native array implementation if access speed is a concern. 

Is the labview queue not based on a linked list? If its an array then sure they should be similar, but if it has to walk a 1000-element linked list of individually wrapped doubles then thats obviously going to be terrible.