Arrays and how LabVIEW handles memory

[Stagg54]

disclaimer: first of all this is related to the NI challenge problem. Not asking anyone to give away any solutions or anything, I just want a better understanding of how LabVIEW manages arrays. And hopefully I'm not giving too much away by my questions.

I have some questions about how LabVIEW handles arrays and memory management

My understanding (please correct me if I am wrong):

1. LabVIEW stores arrays in continuous blocks of memory, which it requests from Windows Memory manager in chunks. I believe LabVIEW just keeps a pointer to the first element. When you split the wire it makes another copy if necessary. The show buffer allocations should show you were this occurs.

2. Using build array inside a FOR or while loop is not optimal because it can cause LabVIEW to have to go to Windows memory manager to request more memory (I believe under the hood it is somewhat smart about this and often requests more than is needed).

3. When using the build array is much more efficient to add onto the end of an array because when adding to the beginning LabVIEW has to shift everything to make room for the new data at the beginning

So my questions:

1. deleting an element from the middle of an array - should require LabVIEW to move (shift) everything in the array after that point. Correct?

2. deleting an element from the end of the array - should not require LabVIEW to do any kind of shifting or anything (in theory i should just change the size of the array). Correct?

3. How does LabVIEW handle shifting? I assume that it it splits that array at the point where it is shifting (ie. what would become the new index 0)and then takes the first and second half and moves them to a temporary location and then appends the first half to the end of the second half. is that correct?

Some of these questions may already have been answered somewhere. If so, if you could point me in the right direction that would be great.

thanks,

Sam

[ned]

One thing that's important to remember here is that memory allocation, regardless of size, is almost always fast. COPYING data is slow and takes longer for more data.

Sorry I can't point you at documentation confirming my answers to your questions, they're all based on the accumulated reading of a lot of posts plus some knowledge of programming and compilers. First, responding to your initial comments:

1) basically true, although the comment about the pointer to the first element isn't completely correct (nor relevant). LabVIEW maintains all the array data in a continuous memory block. In a separate block of memory, it maintains a pointer to the array, the array length, and a stride. There might be other data, too. This makes certain operations, such as reverse array, array subset, and decimate, very efficient. For example, for reverse array, instead of copying the array data, LabVIEW simply allocates a new array information block with the same length, a stride of -1, and a pointer to the end of the array (which is now the beginning of the reversed array) - this is known as a sub-array, and will sometimes show up in the context help when you hover over an array wire. Of course, if some function wants to modify the reversed array while the original array is still needed, then LabVIEW must make a copy.

2) This is correct - each execution of build array could potentially force LabVIEW to go back to the operating system to request a larger block of memory, then copy the existing array into the new, larger location. LabVIEW may request a larger block than necessary and resize at the end of the loop, to minimize the number of allocations and copies.

3) Incorrect. There's no guarantee that there will be room to add to the end of the array; other data may already have been located there, in which case it's necessary to copy the entire array to a new, larger location regardless of whether you're adding data at the beginning or end.

As for your questions about deleting from arrays, I don't know the details and it may depend on which LabVIEW version as the compiler optimizations improve. 1 is most likely right. You should be able to delete from either end of an array efficiently, but there may also be differences between "delete from array" and "array subset" that makes one more efficient than the other.

When you say shifting, do you mean "rotate array"? Not that it really matters, I don't have any idea how that function is implemented and you probably should not be worrying about it at that level.

[GregR]

When talking about arrays, it is important to distinguish between copy(noun) and copy(verb). Copy(noun) refers to a memory buffer containing data. Copy(verb) refers to the act of reading memory from one location and writing those values to another location. If you are running out of memory, then you need to focus on the number of buffers allocated. If you want code to run fast, then your main focus should be the number of times you read from one and write to another. In many cases having more buffers means more read/write operations so reducing buffers tends to improve speed but the relationship is indirect. My discussion below refers to the operation of reading from one location and writing to another.

LabVIEW's memory manager handles resizes specifically. This means it can try to expand an allocation at its current location before resorting to allocating a new buffer. This also means that in the cases where a new buffer is required, it is the memory manager that copies the existing data to the new location and disposes the old buffer. So from an allocation standpoint, it doesn't matter if a new element is being added to the beginning, middle or end of an array. The chance of it causing a copy of every existing element is the same. After the allocation is done, then we can actually have enough space to add the new element. This is where the location matters. If you're adding to the beginning, we will copy every existing element to move it down. If you're adding to the end, we just have to set the new element.

Going back to the original build array scenario. This means that prepending an element with build array will copy the existing elements at least once and commonly twice. Appending an element with build array will either not copy or copy once. That makes appending always one less copy and that qualifies as "much more efficient" to me.

When LabVIEW shrinks an array, we do things in the opposite order but the same principles apply. Since we won't have enough room for all the data after resizing, we must move the data we want to the front before resizing. When deleting from the beginning, this means copying everything else. When deleting from the end, this requires nothing. We then call the memory manager. The odds are greater that the memory manager will keep the same buffer when shrinking, but there are still times when it won't so it must copy all the data to the new location.

Regarding delete from array vs array subset, delete from array is more expensive. Because delete from array has to handle cases where you delete from the middle, it doesn't produce a subarray. Array subset and split array always produce subarrays. This can reduce the overall number of copies, or it might just mean that the copy happens at the next node and the net result is no different.