An alliance with an insidious mistake
Having a problem understanding that when we want to go through the whole array and compare each value of the array with the number present in the array, say arr [0], then why is it recommended to initialize int with arr [0], just like int acomp = arr [0], and compare acomp with any integer present in the array, than compare any integer present in the array with arr [0]? For example, in the following union code, I was told that Code 2 is better than Code 1, but I'm not entirely sure why.
int unionarr(int p, int q){ //Code 1
for(int i=0;i<size;i++)
if(arr[i]==arr[p])
arr[i]=arr[q];}
int unionarr(int p, int q){ //Code 2
int pid=arr[p];
int qid=arr[q];
for(int i=0;i<size;i++)
if(arr[i]==pid)
arr[i]=qid;}
This is a correctness problem. An assignment within a loop for
can change the values ββof the array. You can change the very elements that are used in the comparison or on the right side of the assignment. This is why you must save them before entering the loop.
Making local copies of the pid and qid values ββthat would otherwise have to be re-searched in the array is a bit of a performance optimization.
However, I would be surprised if some modern compiler could not raise this value and do this optimization implicitly.
Using https://godbolt.org/ you can compare them. what you need is an instruction inside the loop.
With Clang 4.0 build:
-
Code 1
movsxd rax, dword ptr [rbp - 16] mov ecx, dword ptr [4*rax + arr] movsxd rax, dword ptr [rbp - 8] cmp ecx, dword ptr [4*rax + arr] jne .LBB0_4 movsxd rax, dword ptr [rbp - 12] mov ecx, dword ptr [4*rax + arr] movsxd rax, dword ptr [rbp - 16] mov dword ptr [4*rax + arr], ecx
-
Code 2
movsxd rax, dword ptr [rbp - 24] mov ecx, dword ptr [4*rax + arr] cmp ecx, dword ptr [rbp - 16] jne .LBB0_4 mov eax, dword ptr [rbp - 20] movsxd rcx, dword ptr [rbp - 24] mov dword ptr [4*rcx + arr], eax