topic Re: cluster array performance penalty in LabVIEW

cluster array performance penalty

shoneill — Thu, 22 Feb 2007 16:10:02 GMT

I'm creating this thread as an off-shoot from here.

Regarding the discussion which has gone on before regarding a big performance penalty when operating on otherwise in-place arrays within and without a cluster:

Ben correctly stated that arrays within a cluster carry a significant overhead and that handling non-clusteres arrays are faster. This has been verified.

I have trouble understanding WHY this is.

I've just repeated some of the tests mentioned in the original post, but in LabVIEW 6.1. Here I see that a clustered array with the cluster carried forward as in:
This is "Method 1" Unbundle 1
is just as fast as handling the naked arrays (a shift register for each array separately with unbundle / bundle OUTSIDE the loop) in LabVIEW 6.1 regardless whether the second array contains a load of data or not. In LabVIEW 8.20, it's significantly slower. Something changed between 6.1 and 8.20.

But when unbundling BOTH arrays as in:
This is "Method 1" Unbundle 2
, the clustered arrays are still an order of magnitude slower than naked arrays.

Referring to the version working directly with clustered arrays as "Method 1" and non-clustered arrays as "Method 2", here's a table of results I've just measured with the attached program:
"Small" and "Large" refer to the size of the second array element in the clusters being tested. This array is actually not altered during testing. Times are given in milliseconds.

I used the following settings for the "unbundle both" version and 1000 repeats for the "unbundle 1" option:

Final results were scaled to 1000 repeats to allow direct comparisons.

The plot thickens.

Shane.

Message Edited by shoneill on 02-22-2007 05:11 PM

Re: cluster array performance penalty

altenbach — Thu, 22 Feb 2007 16:43:04 GMT

Interesting. I never run across this because my sanity always prevented me from resizing arrays inside clusters. 😉

What is surprising is the fact that LabVIEW 8.20 claims that the entire inner loops are "folded" (see image).

Message Edited by altenbach on 02-22-2007 08:43 AM

Re: cluster array performance penalty

shoneill — Fri, 23 Feb 2007 07:45:09 GMT

My "Sanity" also prevented me from doing this up until recently.

I learned that variable length elements of a cluster are stored externally (out-sourced if you wish) meaning that a dimension change of one of these elements should require no copying of moving of the other cluster elements. They should be handled the same as a plain old unclustered element.

I then made a comment that this would be a good idea for state machines, whereupon Ben informed me (and showed me) that there is very much a performance penalty. I'm trying to find out why.

I think it would be really advantageous to be able to operate with clusters mixed with fixed- and variable-sized elements without having to worry about dramatic slowdown as is currently the case.

The fact that things have changed since LV 6.1 could be taken as an indicator that

The code to do this was unneccessarily complex and was dumped to reduce errors
The code was somehow "forgotten" or left out due to time constraints.

Either way, if we're going to suggest a new feature for handling "sometimes uninitialised shift registers" for state machines, I think making the clustered arrays behave as one would think after reading that the elements are not stored in contiguous memory would be the first step in the right direction. Then a single cluster wire for ALL elements passed through a state machine would clean up a lot of code.

Here's an example of mine for example which, although somewhat pretty, could do with some cleaning up.....

Shane.

Re: cluster array performance penalty

Ben — Fri, 23 Feb 2007 12:15:22 GMT

Hi Shane,

I spent about 2 hours looking at your example and could not figure it all out.

The differnce between 6.1 and latter I can not address since I no longer have 6.1 at home.

To get a proper understanding I will have to compare the performance with the "show buffer allocations" display and work up individual test were we can compare various methods and get some numbers on each variation.

I will try to return to this Q this week-end if my schedule permits.

This is what I can say now.

We are measuring to mant variables in your examples.

In the attached 7.1 VI I have moved the indicator updates to outside the time structure. I can not rule out LV attempting to update the GUI for test 1 while test 2 is running.

After doing that I get these two rather dramatic effects

The red circle note the beffer allocations

To continue I would alos like to to test the cluster performance using in-place operations. the build array and other non-in-place operators are forcing us to measure the amount of time required for LV to allocate larger buffers and this is blurring our ability to measure the cluster work alone. I don't even know if the inplaceness algorithm is even involved.

Those are my thought for now. I'll post more if I run across any other discoveries.

Just as perplexed as you are,

Ben

Message Edited by Ben on 02-23-2007 06:16 AM

Re: cluster array performance penalty

shoneill — Fri, 23 Feb 2007 14:47:31 GMT

Ben,

I'm at it two DAYS now and I still don't know what's going on.

I've taken your new suggestions to heart and made a new version. I've changed the "Append array" to "Replace array subset" and have moved the indicator update outside the timing structure. I also programatically generate the clusters involved and have put all relevant settings on the front panel.

In this VI I test 6 different methods.

Method 1 is the "Naked array" method shown below.

Method 2 is a Clustered array with one unbundle output wired and a cluster wire passthrough as shown below.

Method 3 is a clustered array with both unbundle outputs wired and a cluster wire passthrough as shown below.

Method 4 is a clustered array with both unbundle outputs wired and NO cluster wire passthrough as shown below.

Method 5 is a clustered array with one NAMED unbundle output wired and a cluster wire passtorugh (obligatory) as shown below.

Method 6 is a clustered array with both NAMED unbundle outputs wired and a cluster passthrough (obligatory) as shown below.

Running these with the VI attached (saved under 8.20 for LV 8.20) and the options shown on the diagram, I get following results:

NOTE: Columns for Method 3 and 4 are switched. The labelling is correct, "Cluster 2 no Thru" is for the clustered array with both unbundles wired and NO wire passthrough!

I thnk this is correct, but for the life of me, I can't explain why naked arrays are slower than clustered arrays in LV 6.1. I think I might need to move the "unbundle" and "bundle" for this case outside the timing structure. What do you think?

From my results in LV 8.20, it would seem that it makes no difference whether we are working with clustered arrays or bare arrays, just like the LV documentation says. I never thought of the indicator update issue you mentioned earlier. I was stuck in "data-flow" and I thought it would be finished updating before carrying on.

I appreciate your having a look at this.

VI Included (Version difference to the featured picture is because of the comments on the Block diagram).

Shane.

Message Edited by shoneill on 02-23-2007 03:48 PM

Re: cluster array performance penalty

Ben — Fri, 23 Feb 2007 17:14:54 GMT

Hi Shane,

For naked cluster try wiring the cluster around to the for loop to the bundle so the same buffer can be re-used.

I also think that if LV 8 sees a constant wired to the replaced, it may fold the code (see Christian observation) Replace the array elements with the index (just to defeat constant folding).

I am not going to be able to turn my attention to this riddle for quit a while.

My sister-in-law has gone on to meet the "Supreme Wire-Worker" yesterday so my attention will be demanded elsewhere.

Please share what you find,

Your brother in wire,

Ben

PS The answer is probably staring us in the face when we show buffer allocations.

Re: cluster array performance penalty

shoneill — Fri, 23 Feb 2007 18:16:28 GMT

Sorry to hear about your sister-in-law Ben.

I'll have another look, and I look forward to your input whenever you get around to it.

Shane.

PS I have much too little experience interpreting buffer allocations.......

Re: cluster array performance penalty

Ben — Sat, 24 Feb 2007 18:01:07 GMT

Hi Shane,

Attached is a revised version of your “Cluster pointers 8 6.1.vi” saved as 7.1.

The changes I made were;

1) The GUI updates could happen while other tests were running, move it to happen after all testing was done.

2) Add a default case so case “0” does not get special treatment.

3) Remember result (data) from each method so that the output buffer work is the same for all. Note: I believe LV will skip transferring data to an output tunnel data buffer of indexing is not enabled until the last iteration.

4) Used index value to as replace element to prevent constant folding clouding the measurements.

5) Wired the cluster around on method 1 to tell LV it was OK to re-use the input buffer as our output.

After a few runs I noticed my No-op was taking about as much time as my other best. This implied that the control logic ( selecting which method) and over-head (filling input and output buffers) was dominating the measurements. I tweaked the test parameters to invoke the control logic less often and beat the code we are trying to characterize harder. I saved my defaults (warning: Due to method 4 a test run takes forever).

This is how I read it.

All methods use an input Buffer “A” and an output buffer “B”. This includes the default method. The default method required about 300 ms on my machine to fill the input buffer and transfer it to the output buffer.

All methods that only required an input and output buffer ran about the same speed. I suspect under my default settings, the measurement time are indicative of the time required to fill input buffer and fill output buffer. To get a better measurement of the time require to execute each method I will have to tweak my measurement parameters again. Since method 4 is so inefficient I will stop using it my tests. Before I forget abou this method I will venture some guesses about why this si so bad.

The SR is realized by working in the input buffer. Each iteration copies the contents of all of the buffers in “A” to “C” and back to “A” again. No wonder this takes so long!

Now for a suprising issue.

Compare your method #2 and #5

And then #3 and #6

The differnces appear to be tht in the case of unbundled vs unbundled by name. In the case of the unbundled by name we pick-up an extra buffer copy to fill the buffer that is allocated for the SR.

Q : Why isn’t buffer “A” used to support the SR for the “by name” version?

Summary;

Building a cluster with large arrays (method 4) is costly.

Something weird is happening with unbundled/bundle by name.

Further study will be required to measure the performance of the buffeb A-B versions.

I’ll post more when I know more.

Ben

Message Edited by Ben on 02-24-2007 12:01 PM

Re: cluster array performance penalty

Ben — Sat, 24 Feb 2007 18:14:00 GMT

And if you deletemethod 4 and wire the cluster through you eliminate the need for the output buffer!

And of course the performance jumps due to less buffer copying.

Ben

Message Edited by Ben on 02-24-2007 12:14 PM

Re: cluster array performance penalty

shoneill — Sun, 25 Feb 2007 14:42:34 GMT

Ben,

Thanks for the analysis. I don't have access to LV 8.2 (or any other version for that matter) until I'm back at work on Monday.

I'll have a look at it then and see what I come up with.

I have to say, the problem (or at least the benchmarking program) has changed dramatically since the beginning of this discussion. As long as we get to a sensible answer at the end of it, it's all sweet.

I hadn't thought of a single operation dominating the results due to the loop-case structure. Good catch. I guess this explains the difference in best-case values between 6.1 and 8.20?

As I said, I'll have another look tomorrow.

Thanks again,

Shane.

Re: cluster array performance penalty

Ben — Sun, 25 Feb 2007 16:15:02 GMT

HI Shane,

I changed it even more to only allocate buffers before testing and then work from SR's.

You mention of LV 8.2 remended me to try that as well.

I think we have a bug in LV 8.2 (LV 8.2.1 Beta to be technically correct).

IN LV 7.1 all of the versions opperate in-place and it is a toss-up which verson is better. This is consistent with the KB article you quoted earlier.

Now in LV 8.2 method #2 (Cluster wired thru one bundle terminal wired) wants to create new buffers!

This screen shot illustrates.

Method #2 and #3 are identical with the exception of an un-wired input to the bundle function. In previous of versions of LV they are wire equivalent code.

Can I get some consensus on this being a bug ?

If this is not a bug, please help me understand the diffrences.

The LV 7.1 and LV 8.2 versions are attached.

Ben

Message Edited by Ben on 02-25-2007 10:18 AM

Re: cluster array performance penalty

Ben — Mon, 26 Feb 2007 12:43:58 GMT

Adding to the above...

With the exception of the bug, the in-placness algorithm is rather impresive, is it not?

Ben

Re: cluster array performance penalty

shoneill — Mon, 26 Feb 2007 13:10:24 GMT

'tis indeed Ben.

I see you've been quite busy with this trinket over the weekend. I needed a bit of time today before I could catch up.

So, am I right in summarizing:

1) Working on clustered arrays must not neccessarily be slower than working on "naked" arrays. The scope of this statement is the testing we've performed, and was limited up to now on uncomplicated clusters.
2) Working on arrays within a cluster is independent on the size of other data structures in the cluster (again only tested for small, uncomplicated clusters).
3) Some forms of clutered array manipulation seem to be buggy in the newest LV version. (Namely the "Cluster 2 no Passthrough" you have recently wisely removed from the test program).
4) The in-place algorithm rocks, when it's used.
5) I need to learn how to use the buffer allocation imformation in LV 8.20 😉

OK, 4 and 5 are perhaps less critical....

I think I need to whip up an example with significantly more complex clusters, just in case.

Shane.

Re: cluster array performance penalty

altenbach — Mon, 26 Feb 2007 18:54:36 GMT

@shoneill wrote:
3) Some forms of clutered array manipulation seem to be buggy ...

I'm sure you meant to say cluttered. 😄

Re: cluster array performance penalty

Ben — Tue, 27 Feb 2007 14:23:53 GMT

The bug invloving the Bundle function in LV 8.2 was reported to NI Support unde SR 934633.

I will update this thread if I learn more.

Ben

Re: cluster array performance penalty

Ben — Wed, 28 Feb 2007 18:06:32 GMT

A CAR has been filed for this issue;

the title is

"Cluster Array Performance Penalty," and the ID is 46QG7LJG.

Ben

Re: cluster array performance penalty

Travis_M. — Tue, 13 Mar 2007 20:43:44 GMT

Hello,

The screenshots on the font panel of your 8.2 attachment - were those taken from 8.2?

To address these issues as I see them:
A) No buffer allocation should occur at a tunnel (not auto indexed) going into any structure or coming out of any loop (I could see a case for an allocation for a tunnel coming out of a case structure since the compiler doesn't know which case is going to be executed until the program runs). I think this is what you are pointing out in your picture labeled as "A" and "B". I don't see these allocations occurring with LabVIEW 8.20

B) Why does the "wiring through" of the array in method 3 alter the inplaceness of the operation? I do think I can answer this question, and it is not a bug (though it could probably be improved. I believe that the algorithm to detect if an operation can occur in place looks for a 'well known pattern'. A well known pattern is an unbundle, operation, rebundle with the same wire (such as done in "method 3"), I believe that if you don't connect all the terminals the pattern is not recognized as something that can occur in place and therefore a buffer allocation is performed (as in method 2).

Please let me know if you have any comments. Have a great afternoon-

Re: cluster array performance penalty

shoneill — Wed, 14 Mar 2007 08:38:57 GMT

Travis,

Thanks for your input on this one. It's nice to get an idea as to where these issues are coming from.

Regarding the optimisations of the inplaceness detection, can this be taken seriously please? Should I post a product suggection form (or whatever it's called). It's pretty hard for a user to know when a cluster's going to be re-used and when not. Since the variable length cluster elements are strored in separate memory areas, can't this simply be done for each variable length element individually. This would pretty much simplify the "pattern" detection, no? My guess would be that the algorithms for detecting inplaceness should ideally be quite similar (if not the same) to those used for the variable-length elements on their own (not clustered). With NI advocating the use of state machines, wiring lots of parameters through multiple states is pretty much becoming a requirement. If we can rest assured that the in-placeness is working properly, then it makes performance predictions a bit easier. This was actually the origin of this thread: a discussion on the requirement for a new feature to make handling state machine data easier. Perconally, I think clusters are the best, but they need some more tweaking I think.

One of the most worrying aspects is the difference in performance between LV versions. I no longer have the values fresh in memory, but I recall LV 6.1 having less problems with this inplaceness than LV 8.20.

My 2c.

Shane.

Re: cluster array performance penalty

Ben — Wed, 14 Mar 2007 12:24:10 GMT

Hi Travis,

Please look again.

LV 7.1 handles the bundle efficiently.

LV 8.2 (8.2.1 Beta) does not.

Applications that use that construct and run fine in LV 7.1 will suffer badly if used in LV 8.2.

So please run the benchmarks yourself in both version and please post back.

Thank you,

Ben

Re: cluster array performance penalty

Travis_M. — Thu, 15 Mar 2007 17:11:31 GMT

Hello folks,

First, I assure you that we do take the issues seriously and we will look into it. I am submitting the following 2 files with the bug report which really highlight the issue at hand. I tried them on both 7.1 and 8.2 (I don't know about 8.2.1, I don't think we made any announcements about anything called 8.2.1), and like we saw before 8.2 is much slower (and, yes, I do agree that this is a problem).

Does anyone have any other comments related to this issue that I can add to the bug report?

Thanks for everyone's contributions, have a good afternoon-