Heapsort

[WG-]

Heapsort algorithm in LabVIEW.

Unfortunately not as fast as when you would right it in C, (not O(n*log(n)) time) because one clearly sees exponential behavoir in it when you benchmark it. Most likely caused by the algorithms labview uses for arrays.

[GriffinRU]

Why do that in LabVIEW, when you can do that in memory?

P.S.

Can you post your code in labview format not in rar?

[WG-]

What do you mean by "you can do that in memory"? You mean why not in C? Well anyway the answer is really simple... just because I can. So in others words there isn't really a reason why I made it

And I assume you have a problem with .rar because it is not an open format?

[GriffinRU]

You were benchmarking how labVIEW handles memory, and it is known fact that LabVIEW doesn't do that great - lots of reasons why good and bad...

So, if you would like to do something with large arrays you better do that with other means, i.e. programming in C,VB, .net and like over DLL calls, or utilize Intel primitive routines (if running on Intel platforms) and that would be the correct way of benchmarking agains, otherwise it is not fair to blame LabVIEW for the job it is not good for from the start.

In some cases simple in-place function can do the job.

I do not have a problem with "rar", but it is much more convenient if you can do previews with single click, i.e. png or vi works great.

-Artur

[dklipec]

This VI actually performs poorly because of the way it is designed, not because of LabVIEW or the way LabVIEW handles memory.  I've attached a fixed version, and I'll attempt to explain the reasons this has poor performance.

First, the algorithm doesn't stay true to the purpose of Heapsort.  You use Heapsort because you want to stay in-place.  Your VI creates two copies of the array and modifies them independently.

Second, you used sub-arrays, sub-arrays across VI boundaries, and into a recursive VI.  You have found a big corner case which LabVIEW's in-placer doesn't handle well.  This makes LabVIEW generate machine code that looks more like what would happen if you passed std::vector by reference, but then copied the result.

If you remove the recursion and operate in-place on the original array, this code performs quite well and tracks O(n*lg(n)).

[dklipec]

I looked at this a little more because there was a pretty big performance discrepancy between the LabVIEW primitive "Array Sort" and this.  It turns out you are also using an expression node to multiply by 2 instead of native G code in the left/right/parent which prevents those VIs from being inlined.

You also have to use the feedback loop to see this in the demo or the dead-code elimination step in LabVIEW's compiler causes it to skip the array primitive sort entirely which makes the performance comparison completely bunk.

I've attached another modified version which is now within a factor of 2 with the native sorting algorithm.  I actually don't know what LabVIEW uses under the hood for sorting arrays, but it isn't that unreasonable that the constant factor on that might be better than the algorithm for Heapsort.

[WG-]

Very interessting comments dklipec. Thanks for looking at the code and sharing your wisdom and results with us.