LabVIEW
Reversing array to Add element to the front of array performance
Solved!
Hi all,
I have read in a couple of places that reversing an array to add element to the front of it will yield better performance since no new allocation of memory is required.
I have 2 questions regarding this process:
1. "Reversing an array on requires pointers change."
Does this mean an array in Labview is like a linked list ? that has pointers that point to the next element.
So when this reverse array process happens, the head of the linked list will be at the last array element, and every links in the linked list will require a change.
Step 1: orignal array with extra space at the end
Step 2: Reverse array
Step 3: Add new element at the end of reversed array
Step 4: Reverse again.
2. The performance of reverse, add then reverse again is actually worse. Why is that ?
Your benchmarking code is meaningless, especaiiy after you disable debugging, because everything will be calcuated at compile time and turned into constants. Execution time will go to zero even for millions of iterations because there is nothing to do. Don't operate on diagram constants and always wire the outputs. Why is the "Numeric" U64 (And why don't you give the controls an intuitive name for better documenting the function)? As you can see from the coercion dots, the loops coerce it to I32 once it is wired to N. So leave it a I32.
What is the point of the upper for loop at the top, the output data is never used (besides, the right way would be to autoindex at the right loop boundary, not building the array in a shift register. That's just pure Rube Goldberg!).
Arrays are contiguous in memory, and reversing an array sometimes just sets a flag to index from the back, leaving the original data in place. Once you do further operations and size changes, often an actual reversal of the elements or even a new copy needs to be made.
can you point to the source of your misinformation?
- last edited on by
Content Cleaner
You are totally right, I was such a novice, I did not know that without indicators, Labview will think that the for loop has no purpose and will skip over it.
Here is an exerpt to the source that I read:
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.
"Overhead" here they meant "time" is that correct ? or "memory footprint" ?
PS: Actually, they seem to imply "time" per this FAQ
"Overhead" is the need for new buffer allocations, which indireclly affects execution time as well as memory.
Yes, often arrays have extra memory allocated past the end of the array to avoid resizing with every appending of an element..
Your quoted FAQ does not say anything about any reversal trick. For this to work, the array elements need to reversed in-place, then the element appended using the slack space (if it exists!), then the alements need again to ber reversed in-place. Seems like alot of work to do over and over. Yes, it might be slighty more efficient than having to allocate with every prepend operation but we don't really know what the compiler actually does. Maybe if slack is available, it would shift all elements up and insert the first element, making a new allocation only occasionally needed. Who knows? I have the highest respect for Darren, the author of the "source". Maybe he can clarify what he wrote.
Valid benchmarking of all this is quite difficult.
In any case, you often know the final size, so it can be allocated in one swoop and elements replaced with valid data as you go. That's always orders if magnutide more efficient that any other solution. If you need to grow an array one element at a time, append at the end, never at the begginning.
I would like to add that the "reverse array" trick that is supposedly to reduce memory footprint actually almost doubled it under Memory profiling.
The simple append front method actually showed much less memory use.
@zigbee1 wrote:
I would like to add that the "reverse array" trick that is supposedly to reduce memory footprint actually almost doubled it under Memory profiling.
As I said, false results are common without extremely careful benchmarking and profiling.
Unless such a statement comes directly from the LabVIEW compiler team, i will probably ignore it. 😉
Yes, adding to the beginning is always much worse than adding to the end. It possibly can be made slighly less worse by Darren's trick, but I am pretty sure adding to the end is still highly preferred.
If the "trick" is really worth that much, the compiler could silently substitute the reversal code even without the need to program it explicitly. It even could substitute an algorithm that is even more efficient. (The way i understand things, the reversals cannot be made by just setting a flag, else we would not get slack space on the correct end. Thus flipping, appending, flipping back required that every element of the array be touched several times.)
I hope Darren can provide some clarification. 😉 Maybe he has some benchmarking code....
@mikeporter wrote:
A random thought I had would be to append the element to the end and then rotate the array to make the last element the first.
Yup, I had something along those lines in mind. Basically reverse the insertee (or not, depending on the desired behavior), append at the end, then rotate by the size of the inserted array or scalar. Might be worth to do some valid benchmarking...
