Jump to content
News about the LabVIEW Wiki! Read more... ×
hooovahh

[CR] Circular Buffer

Recommended Posts

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

 

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?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 by ShaunR

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

  • Like 1

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 :worshippy: . If it's any consolation, I rotate the array as well.

Edited by GregFreeman

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 by ShaunR

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
  • 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 by ShaunR

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

  • Like 1

Share this post


Link to post
Share on other sites

Sweet, thanks for sharing.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 by LarryColvin

Share this post


Link to post
Share on other sites

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. 

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site, you agree to our Terms of Use.