Best Circular Queue Implementation?

[tst]

---

rex1030 wrote:

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). 

---

Or you could just use my original example. I looked at it now and it is perfectly efficient - you should note that ALL the resizing operations are only called if you change the size of the buffer. If you don't, there are only two operations performed on the array (in-place) and you don't have to do any tracking - the array is in chronological order.

If the size is constant, you can simply allocate it once and get rid of the dynamic resizing code.

[nathand]

---

tst wrote:

Or you could just use my original example. I looked at it now and it is perfectly efficient - you should note that ALL the resizing operations are only called if you change the size of the buffer. If you don't, there are only two operations performed on the array (in-place) and you don't have to do any tracking - the array is in chronological order.

---

I have to wonder here if rotate array does force a large memory move, even though it doesn't require a buffer allocation.  Any idea how efficient rotate array is?  If there's not a substantial penalty for it, I should rewrite my version that way - it's definitely easier to follow. 

[tst]

You're welcome to single step through the following code to verify that there is one 16 MB buffer allocated at the start and another at the end for the indicator and none in the middle.

Ah, sorry, I see you were asking about memory moves. I don't know about that. As far as I know, arrays are represented internally using a start pointer and a stride (which can be positive or negative, so reversing the array is simply a matter of changing the start address and negating the stride), but I don't know about the ability to start in the middle of the buffer. It's quite possible that rotate does have to move all the elements in memory, but I'm not sure how expensive that is. It's possible that keeping track of the current index is more efficient.

Message Edited by tst on 12.01.2010 03:53 PM

[nathand]

The slow part of a buffer allocation isn't actually the allocation, it's copying the data into it.  I just put together the snippet below as a quick benchmark and it's dramatically slower (by an order of 1000) to rotate an array each time versus doing a direct replacement at a different array index.  (The disabled case rotates the array by 1, then does replace array subset at index 0).

[tst]

You're right. I just ran a similar check on the code I posted above and it takes over a second to complete (which I didn't see initially because I was single stepping). I guess it's definitely a matter of deciding where your priority is. If timing is critical, you'd want to keep a running index. If convenience or fewer memory allocations when processing are, you'd probably want the rotation.

[rex1030]

Thank you very much! I had actually started writing a method using the rotate array function.1000 times slower is not what I need to be doing. You rock and your benchmark is priceless. Looks like I'll have to use the method of keep track of index locations. Maybe I'll have to write my own array class that handles all this efficiently based on keeping track of index, end, and size while adding elements with the addition of sort of a "lossy enqeue" type insert element where it will delete the oldest element and add a new element . I just thought labview would be able to handle that efficiently without me reinventing the wheel. I am a disappointed. 

Doesn't the difference found by your benchmark test indicate that labview is actually copying each element of the array to a new location in memory, or making an entirely new array with a different order and destroying the old one. Either way is fundamentally inefficient compared to having an array class that keeps track of index locations and handles adding/deleting elements and simple array reordering like some of the libraries in java.

[Ben]

Nathand,

Is that enable structure in there to force the code to execute? At first glance it looks like that code can be folded. I normally use a control to set the size so that structure folding does not get in the way.

Not questioning your code! Just want to learn.

Ben

[rex1030]

I thought he said that in the disable case of the disable diagram structure he was using the method of rotating the array and adding the element to the front of the array(or back), because thats the only difference in the code for the benchmark. But i could be wrong.

What do you think is going on under the hood with the rotate array function ben?

[nathand]

---

Ben wrote:

Is that enable structure in there to force the code to execute? At first glance it looks like that code can be folded. I normally use a control to set the size so that structure folding does not get in the way.

---

The enable structure is there because the disabled case has the rotate array code.  I agree that the loop theoretically could be folded, but it doesn't look to me like that's what's happening.  I get the same results if I change the array size to a control.  It's a good point, though - I never think about folding when I write a short timing sample like that.

[tst]

---

rex1030 wrote:

Doesn't the difference found by your benchmark test indicate that labview is actually copying each element of the array to a new location in memory, or making an entirely new array with a different order and destroying the old one.

---

No, my benchmark shows that there is no additional allocation. What's likely happening is that every single element in the array is moved, but the array itself stays in the same place in memory.