Swap Array Elements Primitive

[Darin.K]

Is it immediately obvious to you what the following code does?

This rats nest simply swaps two elements in an array, a very common operation when trying to operate on a large array in-place.  The In Place Element Structure helps the looks a little, but I find the performance to lag when used in a tight loop, you know, the kind you encounter when you are trying to operate on large arrays.

I would like a simple primitive (sorry too lazy for a picture) which simply swaps two elements in an array.  It should be similar to the Replace Array Subset function, except for two sets of index inputs and no subset input.  If you want to really make my day be sure to allow disabled inputs to swap rows and columns in one shot for 2D arrays, or pages or volumes or whatever in higher dimensional arrays.

[GregSands]

Yes please!  I've noted also that the IPES is slower than the array primitives for this same usage, which is both surprising and disappointing.

[AristosQueue (NI)]

Sure, for int32s. Not for large strings or waveforms.

The overhead of the IPE is a check to make sure that the indicies are not the same index. In the case that you've posted, Darin, they are the same index, so in order for the IPE to operate, a new temporary must be created and copied into.

With the primitives, there's no such check, but there's also no prevention of copy, so even a mildly sized array quickly overruns the index comparison.

[Darin.K]

Well it is really simple then.  The primitive should skip the check and prevent the copy.  A common mistake while streamlining code is to put in a million comparisons to prevent a small number of harmless operations.

[AristosQueue (NI)]

It is logically impossible to skip both the check and the copy. One or the other is required or you end up with invalid code.

[Darin.K]

Wait. What? All I am asking is for a primitive to encompass the simple swap operation as shown in the first example, how does this lead to invalid code? Must be too early in the morning for me.

[Darin.K]

It seems we are talking about two different copies, I was referring to the array itself and you are talking about copying the elements themselves when required. Obviously that copy is always required for a swap. The IPES will simply ask a million times if a copy is required and the answer will always be yes. I am asking for a primitive to do this with no questions asked.

[AristosQueue (NI)]

When you said "The primitive should skip the check and prevent the copy", I took that as referring to the existing primitives, as if you were highlighting a bug in the existing behaviors. I didn't realize you were talking about your proposed new primitive. I think that's where the conversation skewed. The reason  I took that tack is that your original post implied that if the IPE had sufficient speed, you wouldn't be asking for a swap primitive, and I thought we were discussing the existing behaviors first before we got around to discussing whether a swap indices primitive was needed.

In the original idea Darin mentioned the performance problems of the IP, problems reiterated by GregS. As I said, that performance difference comes from a slight delay in comparing the indicies. That delay increases if those indicies are equal as the IPE will make a copy into a temporary location for the other copy.

To swap two elements does not require a data copy. Swapping can be done in memory without having to copy to a third memory location -- some systems give us assembly instructions to do that and the chip takes care of it, others have clever tricks involving XOR, both of which are faster than the copy-to-temp-location movement of data.

The check for "are these the same indices?" will still be needed on a swap indices primitive, although, yes, it would avoid the copy if they happened to be the same. Is the case where the two indices are identical really something you're that concerned about as a performance hit?

[Darin.K]

The IPE construction is more visually appealing than the primitive construction, and it is easier to see what is happening so I showed it in an attempt at full disclosure.  I could have completely mangled the primitive based swap to make it even uglier, but that is not really my point.

Bottom line:  The swap operation is fundamental to so many in-place algorithms that I believe it warrants a primitive.  It will make the right thing to do the best looking thing to do as well.  If it gets a tiny kick in performance in some chip sets, all the better. 

It is inevitable that the indices will sometimes be equal.  The temp-copy method is safe in this case (you are just doing a couple of unneccessary operations) so it is often best to just copy anyway instead of checking everytime to avoid a few repeated copies.  If the in-place swap fails in this case, then safe and speedy wins over fragile and slightly speedier.  Make it as safe and as speedy as possible.

The real time saving is not shaving a few flops here and there, it is saving development time by cutting down on wiring, and by encouraging in-place algorithms.  We all know the bucket brigade is more efficient than repeated calls to Delete from Array, I am trying to close the complexity gap so what works better looks better as well.

[AristosQueue (NI)]

Ok. Good arguments.

[crossrulz]

Darin.K - "It is inevitable that the indices will sometimes be equal.  The temp-copy method is safe in this case (you are just doing a couple of unneccessary operations) so it is often best to just copy anyway instead of checking everytime to avoid a few repeated copies."

I am refering to the new proposed primative here.  The fastest route would be if the indecies are the same to do nothing since there really isn't any swapping.