Jump to content
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

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Similar Content

    • By hooovahh
      View File XNode Editor
      8 Years ago the first version of the XNode Manager was posted to the code repository in an attempt to allow the editing of XNodes.  Being a fan of XNodes, but knowing that the XNode Manager is pretty limiting because of its age, I set out to make a new version with similar functionality.
      The XNode Manager had a blank XNode, and blank Abilities that it just made copies of.  This is fine but then the abilities and XNode are quite old.  There were many new Abilities added since version 8.2 and you can't add them using the XNode Manager.  My XNode Editor reads your LabVIEW resource and populates the list of abilities to create from the ones that are possible to create.  Then VI server is used to create the XNode, State control, and Abilities.  This sets up the connector pane like it should and should work with all future versions of LabVIEW, until NI changes something that breaks it.  It also reads in the XNode Ability descriptions to help understand how to use the new ability VIs.
      In addition to being able to create and edit XNodes, you also can edit the XNode icon, and description, along with adding any new abilities.
      Be aware this uses several private functions, and several undocumented features that could be potentially bad.  I did a decent test to make sure memory leaks weren't a problem and I made several XNodes and Abilities and it seems stable.  But at the end of the day if it blows up and crashes, don't be surprised, you've been warned.  The original thread with discussion and progress on this tool was started here.

      Submitter hooovahh Submitted 03/15/2017 Category XNodes LabVIEW Version  
    • By Taylorh140
      After working on the set cluster element by name xnode, it made me realize i could use the same concept to convert a variant array to a cluster. The technique is actually pretty simple, the xnode generates a case structure for each element in a cluster in cluster order, wherein a bundle by name is used to set the value and an unbundle by name is used to get the type, a variant to data is used to convert the data. This has some benefits over some methods, you are not limited to 255 elements, although that is not usually the case some of us are paranoid that clusterosaurus giganticous will be larger than expected. It also has a draw back  that is that when converting from a variant array all the elements must have unique, non-blank names, and this is usually the case. 

      I think this technique (though very brute-force) might be useful for some other things let me know what you guys think.

      VariantArrayToCluster.zip
    • By Taylorh140
      This Xnode allows setting a cluster element by label string without using references. I pulled a great deal of inspiration from Hooovahhs Variant Array to cluster xnode, which i suppose this could be used for, another benefit is its not limited to 255 elements. Its mostly experimental because I haven't used it much. 
       
      SetClusterElement.zip

      SetClusterElementLV2013.zip
    • By UnlikelyNomad
      I've been working a lot lately with by-reference architectures that still cooperate completely with LabVIEW's implementation of OOP and polymorphism. I've also recently taken an interest in trying to speed up development with secondary providers (similar to GOOP) to enable automatic creation of accessor VIs hidden behind the DVR, automatic creation of the private data type and constructor/destructor, etc. within the project window. I'm generally not a fan of the extra stuff that goop adds in to classes, I'd prefer to keep the source code looking as close to a normal class as possible.
      That said, I've started on my first ever XNode and it's a cross between an unbundle by name node and the -> operator in C. It functions just like a normal UBN, however it was also pull items out of DVRs. Having to plop down a UBN to pull out the reference from the class, an in place node to dereference, and then another UBN to pull the data out gets tiresome after about the 100th property VI gets written.
      So far I've gotten the node drawing completed (except for data type coloring of the labels), the type inferencing from the input wire, and the popup menu for selecting an item. Next up will be the menu selection code so that the names will finally show up in the terminals! Then I get the daunting task of scripting up the GenerateCode ability >_>
      Anyone interested in something like this? Following this will be a match to the Bundle by Name node that serves the same purpose except to write the items.



    • By hooovahh
      8 Years ago the first version of the XNode Manager was posted to the code repository in an attempt to allow the editing of XNodes.  Being a fan of XNodes, but knowing that the XNode Manager is pretty limiting because of its age, I set out to make a new version with similar functionality.
      The XNode Manager had a blank XNode, and blank Abilities that it just made copies of.  This is fine but then the abilities and XNode are quite old.  There were many new Abilities added since version 8.2 and you can't add them using the XNode Manager.  My XNode Editor reads your LabVIEW resource and populates the list of abilities to create from the ones that are possible to create.  Then VI server is used to create the XNode, State control, and Abilities.  This sets up the connector pane like it should and should work with all future versions of LabVIEW, until NI changes something that breaks it.  It also reads in the XNode Ability descriptions to help understand how to use the new ability VIs.
      In addition to being able to create and edit XNodes, you also can edit the XNode icon, and description, along with adding any new abilities.
      Be aware this uses several private functions, and several undocumented features that could be potentially bad.  I did a decent test to make sure memory leaks weren't a problem and I made several XNodes and Abilities and it seems stable.  But at the end of the day if it blows up and crashes, don't be surprised, you've been warned.  The original thread with discussion and progress on this tool was started here.

×
×
  • Create New...

Important Information

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