Sign in to follow this  

Swapping two arbitrary variables

This topic is 4859 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there a better way to implement this (in C#)?
    public class Utility<T>
    {
        private Utility() { }

        public static void Swap(ref T obj1, ref T obj2)
        {
            T temp = obj1;
            obj1 = obj2;
            obj2 = temp;
        }
    }


Share this post


Link to post
Share on other sites
Here is another way...it should work.


public static void swap(ref T obj1, ret T obj2){
obj1 = obj1 ^ obj2;
obj2 = obj1 ^ obj2;
obj1 = obj1 ^ obj2;
}


That way you dont have to create a temporary object. Then again, I dont know if it works for classes and objects.

Share this post


Link to post
Share on other sites
Quote:
Original post by visage
Here is another way...it should work.


public static void swap(ref T obj1, ret T obj2){
obj1 = obj1 ^ obj2;
obj2 = obj1 ^ obj2;
obj1 = obj1 ^ obj2;
}


That way you dont have to create a temporary object. Then again, I dont know if it works for classes and objects.


That will only work for classes for which the ^ operator is a bitwise XOR. You can't be sure that this is the case though (that I know of... though maybe you could do a compile time test... hmmm).

Dwiel

Share this post


Link to post
Share on other sites
Quote:
Original post by visage
Here is another way...it should work.


public static void swap(ref T obj1, ret T obj2){
obj1 = obj1 ^ obj2;
obj2 = obj1 ^ obj2;
obj1 = obj1 ^ obj2;
}


That way you dont have to create a temporary object. Then again, I dont know if it works for classes and objects.

Does C# allow you to cast without altering bits? In C/C++ you can, and that allows you to use the XOR trick for all data. Assuming your function is right, you'd want this:

*(int*)(&obj1) ^= *(int*)(&obj2);
*(int*)(&obj2) = *(int*)(&obj1) ^ *(int*)(&obj2);
*(int*)(&obj1) ^= *(int*)(&obj2);

If obj1 and obj2 are both 32-bits in size (which means 32-bit ints, 32-bit floats, or pointers) then that'll work. In C/C++. I don't think you can do this in Java, and I'm unclear on C#.

Share this post


Link to post
Share on other sites
Quote:
Original post by jperalta
Is there a better way to implement this (in C#)?

*** Source Snippet Removed ***


Seeing as how you use generics, it seems to me like you are using C# 2.0. So I think it would be better if you made the class static and removed the private constructor.

Share this post


Link to post
Share on other sites
Quote:
Original post by silvermace
on a prtial side note, the XOR swap _KILLS_ the pipe

Indeed. It'll be faster to create a tempoary. Trust me.
The XOR method is just a hack, its slow and ugly.

Share this post


Link to post
Share on other sites
Quote:
Original post by silvermace
on a prtial side note, the XOR swap _KILLS_ the pipe
I have read that several times but I don't understand what you mean with it, could you please explain?

Share this post


Link to post
Share on other sites
Quote:
Original post by visage

Here is another way...it should work.

XOR-trick

That way you dont have to create a temporary object. Then again, I dont know if it works for classes and objects.


Bad idea. It can only work with basic types of the same size. And if you ever make the mistake of calling swap(a,a) (which, with aliasing, may happen without you noticing), you're doomed.

Quote:
Original post by Eriond
I have read that several times but I don't understand what you mean with it, could you please explain?


Because you're hogging the ALU for something that doesn't need it.

Share this post


Link to post
Share on other sites
Here is really basic assembly for a normal swap, using two registers (found it by looking elsewhere on GameDev, posted by Prosper/LOADED):

inline void swap(int& a, int& b)
{
asm
{
mov eax, a
mov ebx, b

mov b, eax
mov a, ebx
};
}

You'll notice that the first two instructions are completely independent. This means that the processor can roughly do them at the same time. The second two instructions are also completely independent. They can be done at roughly the same time as well. The second two obviously have to wait for the first two to complete of course, but each pair can occur simultaneously. Modern processors have been doing this for quite a while, and they and compilers get better at it all the time.

The XOR method does not allow this. The second operation needs to wait for the first operation to complete before it can start. The third operation also needs to wait for the second operation to complete before it can start. All this waiting means that a lot of the CPU is sitting there unused.

Graphically, the first one would look like this:

[**** OPERATION 1 ****] [**** OPERATION 3 ****]
[**** OPERATION 2 ****] [**** OPERATION 4 ****]

The second one (XOR) would look more like this:

[**** OPERATION 1 ****][**** OPERATION 2 ****][**** OPERATION 3 ****]
So you can see how the XOR ends up taking longer, even though it has one less operation.

Share this post


Link to post
Share on other sites
Creating a temporary is actually faster than using XOR?! I thought bitwise operations were supposed to be really fast.

http://www.gamedev.net/reference/programming/features/bitwise/page4.asp
(ctrl + f "swapping variables")

^ Where I got my information from.

Share this post


Link to post
Share on other sites
Quote:
Original post by load_bitmap_file
Creating a temporary is actually faster than using XOR?! I thought bitwise operations were supposed to be really fast.

http://www.gamedev.net/reference/programming/features/bitwise/page4.asp
(ctrl + f "swapping variables")

^ Where I got my information from.
Well, they are, and movs are just as fast. So basically if you do something like this:

;; Swap eax and ebx
mov edx, eax ; u pipe \__ 1 clock!
mov ecx, ebx ; v pipe /
mov ebx, edx ; u pipe \__ 1 clock!
mov eax, ecx ; v pipe /
They're perfectly paired, no stalls.

;; Swap eax and ebx
xor eax, ebx ; u pipe --- 1 clock!
;; STALL, not paired, write after read (ebx)
xor ebx, eax ; u pipe --- 1 clock!
;; STALL, not paired, write after read (eax)
xor eax, ebx ; u pipe --- 1 clock!
Now, in the first method (temp swap) the C compiler will likely notice that you're swapping with a temp and replace it with xchg eax, ebx if it's relatively smart. A not-so-smart compiler might ignore the XOR-swap and just turn it into a bunch of XORs (ick).

;; Swap eax and ebx
xchg eax, ebx ----------- 1 clock!
Very nice.

Share this post


Link to post
Share on other sites
Also note that the hack shown by CGameProgrammer breaks when the size of the type you are passing in is different from sizeof(int) (note that aligment can also change the behavior of it).

i.e. calling the XOR swap with char could enp up modifying bits that you do not own.

It is interesting what was mentioned about performance, even though I do not think swap will show up on as a hotspot on a profile run.

My take on this (on the C++ side), use std::swap, use the temporary variable, and do not worry about its performance until you have profiled and found it to be something that is slowing down your application.

For C# there is no reliable way to do a swap that works across reference and value types.

Share this post


Link to post
Share on other sites
I'd advise everyone not to try and optimise something like this. Stick with the traditional way of creating a temporary variable. That's a method compilers can recognise, and they can do the optimisation for you. Chances are, they'll choose the best method for the situation. At any rate, it's not your job to worry about it, it's theirs.

Share this post


Link to post
Share on other sites

This topic is 4859 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this