6437

Does swapping two variables without using a third improve performance? [closed]

Question:

I've seen a lot of techniques for swapping two variables without using a third.

<a href="https://stackoverflow.com/questions/804706/swap-two-variables-without-using-a-temp-variable" rel="nofollow">Swap two variables without using a temp variable</a><br /><a href="https://stackoverflow.com/questions/23514846/how-to-swap-two-numbers-without-using-third-variable" rel="nofollow">How to swap two numbers without using third variable? [duplicate]</a><br /><a href="https://stackoverflow.com/questions/24844487/swap-2-values-of-2-variables-without-using-a-third-variable-python" rel="nofollow">Swap 2 values of 2 variables without using a third variable; python</a><br /><a href="https://stackoverflow.com/questions/18356437/swap-two-variables-value-without-using-third-variable-in-php" rel="nofollow">Swap two variables value without using third variable in php [duplicate]</a><br /><a href="https://stackoverflow.com/questions/3647331/how-to-swap-two-numbers-without-using-temp-variables-or-arithmetic-operations" rel="nofollow">How to swap two numbers without using temp variables or arithmetic operations?</a>

Are any of these faster than using the third variable?

Answer1:

no even in computer archtecture point of view.

for example, if i use bit manipulation to swap two integer like following:

a ^= b; b ^= a; a ^= b;

what running in CPU is that:

mov reg1, &a mov reg2, &b xor reg1, reg2 xor reg2, reg1 xor reg1, reg2

what can tell easily is that reg1 and reg2 rely on each other.

modern CPUs use disorder execution of instruction stream. that is, execute more than one instructions if these instructions do not rely on the result of each other. therefore, it's normal for modern CPUs run multiple instructions at the same moment.

but what if you use a temp variable? dead easy. modern CPUs usually have instruction level support.

xchg reg1, reg2

done.

BTW, don't pay too much attention to the assembly. it varies in different architectures. just for demo.

Answer2:

No. At least in Java. Swapping two primitive integers using a third variable is the fastest (and easiest to understand).

I wrote this code to test it. It compares the two most common techniques I found in various answers: swapping using subtraction and swapping using bitwise xor.

package compareswapmethods; import java.util.Arrays; import java.util.Random; import java.util.Scanner; public class CompareSwapMethods { private static final Random rand = new Random(); private static final int ITERATIONS = 1000000; private static final int MIN_LENGTH = 2; private static final int MAX_LENGTH = 100; private static final int MIN_VAL = -100; private static final int MAX_VAL = 100; public static void main(String[] args) { System.out.println("press enter to start"); Scanner in = new Scanner(System.in); in.nextLine(); for(int i = 0; i < ITERATIONS; i++) { int[] sample1, sample2, sample3; sample1 = generateRandomArray(MIN_LENGTH, MAX_LENGTH, MIN_VAL, MAX_VAL); sample2 = Arrays.copyOf(sample1, sample1.length); sample3 = Arrays.copyOf(sample1, sample2.length); /*System.out.println(Arrays.toString(sample1)); System.out.println(Arrays.toString(sample2)); System.out.println(Arrays.toString(sample3));*/ int x = randomVal(0, sample1.length-1); int y = randomVal(0, sample1.length-1); thirdv(sample1, x, y); subtractive(sample2, x, y); bitwise(sample3, x, y); /*System.out.println(Arrays.toString(sample1)); System.out.println(Arrays.toString(sample2)); System.out.println(Arrays.toString(sample3)); System.out.println("-");*/ } System.out.println("done"); } /*swap elements in array using third variable*/ public static void thirdv(int[] arr, int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } /*swap elements in array using subtraction variable*/ public static void subtractive(int[] arr, int x, int y) { arr[x] = arr[x] + arr[y]; arr[y] = arr[x] - arr[y]; arr[x] = arr[x] - arr[y]; } /*swap elements in array using bitwise xor*/ public static void bitwise(int[] arr, int x, int y) { arr[x] ^= arr[y]; arr[y] ^= arr[x]; arr[x] ^= arr[y]; } /*returns random int between [min, max]*/ public static int randomVal(int min, int max) { return min + rand.nextInt(max - min + 1); } /*creates array of random length, between [min, max], and calls poppulateArray on it*/ public static int[] generateRandomArray(int minLength, int maxLength, int minVal, int maxVal) { int[] arr = new int[minLength+rand.nextInt((maxLength-minLength)+1)]; populateArray(arr, minVal, maxVal); return arr; } /*assigns random values, in the range of [min, max] (inclusive), to the elements in arr*/ public static void populateArray(int arr[], int min, int max) { Random r = new Random(); for(int i = 0; i < arr.length; i++) arr[i] = min+r.nextInt((max-min)+1); } }

I then used VisualVM to profile and here are the results:

<img alt="screenshot of results in VisualVM" class="b-lazy" data-src="https://i.stack.imgur.com/lm5rM.png" data-original="https://i.stack.imgur.com/lm5rM.png" src="https://etrip.eimg.top/images/2019/05/07/timg.gif" />

Results do very a bit between tests but I've always seen the thirdv method take the shortest amount of CPU time.

Recommend

  • What is the difference in logic and performance between LOCK XCHG and MOV+MFENCE? [duplicate]
  • Installing Flash Player on an Android Emulator
  • Making a panel persist despite click on page opened in browser
  • Regarding client side code generation from WSDL
  • Visual Studio not stopping on an exception being thrown
  • maven-dependency-plugin ignores outputDirectory configuration
  • Cannot convert a char value to money. The char value has incorrect syntax
  • Maven-Release-Plugin: Force to use specific version of scm provider
  • Is there a chance to get -splash: work for SWT applications that require -XstartOnFirstThread?
  • Spring Batch restart uncompleted jobs from the same execution and step
  • Where in the relevant specification is it documented that some comments in a SQL script are, in fact
  • How to package a jar and all dependencies within a new jar with maven
  • How do I configure Maven Cargo to use an embedded Tomcat server?
  • What is the equivalent of Android permissions in iOS development? [duplicate]
  • how to read a file in prolog?
  • Thread synchronization with syncwarp
  • include dlls in visual studio c++ 2008
  • R Split data.frame using a column that represents and on/off switch
  • Redshift Querying: error xx000 disk full redshift
  • Bash if statement with multiple conditions
  • Android changing fragment order inside FragmentPagerAdapter
  • SetWindowsHookEx does not react on media keys
  • Jquery popup on mouse over of calendar control
  • How to remove a SwiftyJSON element?
  • How do I get HTML corresponding to current DOM tree?
  • Swift: Switch statement fallthrough behavior
  • How to create a file in java without a extension
  • Repeat a vertical line on every page in Report Builder / SSRS
  • Android screen density dpi vs ppi
  • Bug in WPF DataGrid
  • Timeout for blocking function call, i.e., how to stop waiting for user input after X seconds?
  • jQuery tmpl and DataLink beta
  • SVN: Merging two branches together
  • Hibernate gives error error as “Access to DialectResolutionInfo cannot be null when 'hibernate.
  • Android Studio and gradle
  • How to include full .NET prerequisite for Wix Burn installer
  • How to CLICK on IE download dialog box i.e.(Open, Save, Save As…)
  • Can Visual Studio XAML designer handle font family names with spaces as a resource?
  • How to get NHibernate ISession to cache entity not retrieved by primary key
  • java string with new operator and a literal