Benchmark for Insert Into Array vs Build Array

[AristosQueue (NI)]

This VI, saved in LV 2013, is a benchmark comparison between Insert Into Array vs Build Array when inserting elements randomly throughout an array. Insert Into Array wins by orders of magnitude.

[JÞB]

Nice to know.

I wonder though,  What the impact of this change would be

[crossrulz]

So what brought this up in the first place?  I know DarrinK made a comment about these nodes over in the Idea Exchance (http://forums.ni.com/t5/LabVIEW-Idea-Exchange/Highlight-Common-Performance-Issues/idc-p/2777240#M269...).  But he was referring to bulding an array with the Insert To Array (always appending) by leaving the index input unwired.

It only makes sense that adding to an array in the middle would be way faster with the Insert To Array.  That is what the node was made for after all.

[Darin.K]

Insert gives you a constant time cost, regardless of insertion point.  Build Array rocks for appending.  I will dig up the code, but I do have some old graphs.  I do not think that short strings in a short 1D array quite stresses the system enough to see the types of behaviors I encounter with larger data sets.  Here are a couple of plots where I show iteration-by-iteration times for two operations.  First I am appending rows of 512 I32s repeatedly.

Total time is the integral of the hair, it looks noisy, but it is very consistent and if you work back through the numbers you can infer the data allocation scheme.  The total time is the integral, but Build Array is much faster (like 50X).  Build Array seems to let the SR do its thing and double the buffer, Insert is doing work on every iteration, after about 6000 rows are added they both bang hard.  The doubling has stopped apparently in favor of fixed-size increases.  Examining the tail shows structure in the noise:

They both bang the memory manager regularly, but Insert is doing some work every iteration (copying elements), Build Array is doing basically nothing except when it needs to increase the buffer. 

Prepending does little to change insert (it always gives you the constant worst-case scenario), but Build Array is now much worse as we would expect.

tl;dr : I would like Insert to behave like Build Array when I explicitly tell it I am appending items (leaving the index unwired).  I could then use one function all the time and spend less time thinking.

[AristosQueue (NI)]

---

Darin.K wrote:

tl;dr : I would like Insert to behave like Build Array when I explicitly tell it I am appending items (leaving the index unwired).  I could then use one function all the time and spend less time thinking.

---

AH! I added the boldface. I posted this without linking to the other thread because I assumed you were seeing something real and I wasn't going to link back to the other until I figured out what it was. In the other thread, you opened with "Insert into Array.  This is a dog and should always be highlighted." You gave some specific examples, but I read those as instance cases, and still thought you meant that Insert Into Array should never be used for anything. I thought you had found a way to use Build Array for all use cases of Insert Into Array and get better performance.

I threw this VI up on the forums without expecting many people to jump on it, but I thought it might draw a comment from someone who said, "Oh, no... if you do XYZ, then Insert Into Array is faster..." Essentially, I was trying to avoid misconstruing your post again, Darin, by fishing for comments from others in a different forum. Didn't work the way I expected, but it did clarify the communication.

Back on the topic at hand:

No one has bothered to special case the code generation of Insert Array. It's on the list of possible optimizations to apply someday. The list of possible optimizations is huge, ranging from whole VI optimizations down to tuning of individual function special cases. We put priority behind the ones that show up regularly and/or have no workaround. This one doesn't show up regularly ... people tend to use Build Array when they are appending/prepending. Until today -- because your post made me go check -- I didn't even know that leaving the Index terminal unwired would insert at the end of the array. I assumed that it would take the default value (zero) and thus do a prepend. I suspect that most people would make the same assumption... it's unusual for a node to have a non-zero default value, and there's no documentation on this one. I am filing a documentation CAR to add a note about the default value to the documentation.

[Darin.K]

No one can accuse me of not RTFM.  It lures you right into using it to Append Arrays as if it would treat it as a special case.

Insert Into Array Function

Owning Palette: Array Functions

Requires: Base Package

...If you do not wire any index inputs, the function appends the new element or subarray to the end of the n-dim array....

What bugs me about this function is that it does too much work (except when prepending).  The memory management is suboptimal but probably still a bit of a holdover from the days of limited RAM.  Nonetheless, even if LV is a bit stingy when requesting buffer growth, there is still a linearly scaling amount of work being done every iteration.  It is consistent with moving every element every time.

Better than the alternative, but far, far from optimal.

[crossrulz]

---

@Darin.K wrote:

Prepending does little to change insert (it always gives you the constant worst-case scenario), but Build Array is now much worse as we would expect.

---

What happens if you reverse the array before and after adding the element to the array?  See this nugget:How to efficiently add items to the beginning of a 1D array

[Darin.K]

When they create the Reverse 2D array function I will test it. 🙂

I use prepending as a special case since it is the worst case just like I would delete the first element when benchmarking Delete From Array. (I think I aired my grievances with that function somewhere else). Prepending is expected to be potentially slow, appending not so much.