Tips and Tricks Build Array Ordering Description

[DAD]

In the January 10, 2012 NI News there is a link to "Tips and Tricks to Speed LabVIEW Performance"

Looking at that web page the last tip is (minus the picture):

6. Build Array Ordering

The operation of adding multiple values to the front of an array incurs the overhead of rearranging memory to accommodate each new element. You can avoid this overhead by flipping the array first using the Reverse 1D Array function, adding the new elements to the back, and then reversing the array again when complete. Adding elements to the end of the array is more efficient because LabVIEW has already allocated additional memory beyond the original size to accommodate appending values, and the reverse operation merely moves a pointer to the array from the beginning to the end.

While reversing an array and appending (then reversing again) is an efficient way to prepend data to an array, that last part of the description doesn't make sense (like it's been overly simplified).  How can this work if the reverse operation merely moves a pointer from one end of the array to the other?

[nathand]

I believe your question is answered further down in the thread.  There's no benefit to reversing the array and appending to the end.

[DAD]

The first item in the thread provides some elaboration by explaining that LabVIEW will use a negative offset after changing the start pointer to the end of the array.  But that doesn't explain how all these operations increase the efficiency when you want to prepend an element onto an array.  If reversing the array is just moving the pointer, then through what mechanism is there free memory before what was the beginning of the array to allow new elements to be appended without having to move the array?  Additional space is allocated when the array is created.  Is some of this space before the array or is all of it at the end?

Sorry if my original point got lost in the posting.  It seems to me the description is light on details and doesn't explain what's really going on.

[Ben]

---

@DAD wrote:

The first item in the thread provides some elaboration by explaining that LabVIEW will use a negative offset after changing the start pointer to the end of the array.  But that doesn't explain how all these operations increase the efficiency when you want to prepend an element onto an array.  If reversing the array is just moving the pointer, then through what mechanism is there free memory before what was the beginning of the array to allow new elements to be appended without having to move the array?  Additional space is allocated when the array is created.  Is some of this space before the array or is all of it at the end?

Sorry if my original point got lost in the posting.  It seems to me the description is light on details and doesn't explain what's really going on.

---

I am on the same page in thinking that some of the extra space has to be in the buffer prior to where the current index is.

TO be absolutely sure I would have to bench-mark it but, I'm lazy and nathad has never steered me wrong so I suspect his posting to be true and the extra space at the beginning is just not there.

If nayone proves this via a benchmark I'd like to see the code and your results.

Ben

[nathand]

It's light on details because it's WRONG (EDIT: slightly misleading).  Reversing an array and then adding to the end is no more efficient than adding to the beginning, as explained in the post to which I linked, further down the thread. (EDIT: OK, I understand now, thanks to Darin's post below.  It's more efficient in a LOOP, but not in a single instance.)

In some cases, LabVIEW can create a "sub-array."  This means that instead of copying an entire array to a new location, LabVIEW simply allocates a pointer to the first element and a "stride" - the distance between elements - which can be either positive or negative.  So, the output of reverse array will sometimes be a sub-array, with the pointer pointing at the last element of the input array, and a stride of -1.  Decimate array can produce a sub-array with a stride equal to the decimation factor.  However, when you modify the contents of the sub-array, it becomes necessary to do a full copy into a real array, and that's what happens in this reverse-then-append situation.  This, I think, is well-explained in the post in that thread by "Aristos Q."  For a bit more information on sub-arrays, see this discussion.

[Darin.K]

I believe your overall sense is correct, there is no free lunch here.  That tip shows you that in a very specific case, prepending multiple values, you are better off reversing an array, appending the values, then reversing again.  Everything you think has to happen, still has to happen.  A direct prepend will require all values to be moved on every iteration.  Reversing the array first will also require copying every value, but only at the beginning and end as opposed to each iteration.  Now you can see the math, if you are prepending a couple of times, the direct approach is ok.  If you are doing it many times in a row, you can limit the number of copies to 2, maybe 1 if you do not further modify the array.

[nathand]

Ah!  Thanks, Darin.  I'm sorry for my statement above about the original tip being wrong, and I've edited my post to reflect that.  I missed that the original tip was only suggesting that it is more efficient when operating in a loop, not for a single execution.  Now it makes more sense.

[Ben]

---

@nathand wrote:

Ah!  Thanks, Darin.  I'm sorry for my statement above about the original tip being wrong, and I've edited my post to reflect that.  ...

---

admitting an error is top notch. My faith is unshaken.

Ben