Sorting 예제 및 array와 pointer비교

Procedure Swap

void swap(int v[],int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
v in $a0,k in $a1,temp in $t0

1    swap: sll $t1 $a1,2 #t1 = k*4 : v에서 k번 째 주소를 찾기 위함
2              add $t1,$a0,$t1 #t1 = v+(k*4) : v의 주소 + 4* k byte
3                lw $t0 ,0($t1) # temp = v[k] 
4              lw $t2 , 4($t1) # t2 - v[k+1]
5                sw $t2 0($t1) # v[k] = $t2 (v[k+1])
6              sw $t0 4($t1) #  v[k+1] = $t0 (temp)
7              jr $ra

• 1,2번 째 라인 : 우선 v의 k번 째 주소를 찾아야하는데 그 코드가 1,2번 째 라인이다
  • 찾은 주소값을 $t1에 저장한다
• 3,4번째 라인 : $t0 와 $t2에 v[k]와 v[k+1]의 값을 저장한다
• 5,6번째 라인 : 임시 저장값($t0와 $t2)를 v[k+1]와 v[k] 로 각각 옮긴다.

Non-leaf procedure

void sort(int v[],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i-1;ij>=0&&vpj]>v[j+1];j-=1)
{
swap(v,j)
}
}
}

v in $a0,k in $a1,i in $s0,j in $s1

Array vs Pointer

Array로 구현

• Multiplying by element size
• Adding to array base address

Pointer

• Can avoid indexing complexity

코드 비교

Array 구현시

clear(int array[],int size){
int i;
for(i=0;i<size;i+=1)
{array[i]=0}
}

move $t0,$zero #i=0
loop1 : sll $t1,$t0,2 #$t1 = i*4
              add $t2,$a0,$t1 # $t2 = &array[i]
            sw $zero 0($t2) #array[i] = 0
                add $t0,$t0,1 # i = i+1
                slt $t3,$t0,$a1 #$t3 = (i<size)
              bne $t2,$zero,loop1

Pointer로 구현시

clear(int *array,int size){
int *p;
for(p=&array[0];p<&array[size];p+=1)
{*p=0}
}

move $t0,$a0 # p=&array[0]
sll $t1,$a1,2 # $t1 = size*4
add $t2,$a0,$t1 # $ t2 = &array[size]
lopp1 : sw $zero,0($t0) #*p = 0
              addi $t0,$t0,4
              slt $t3,$t0,$t2 #t3 = p<&array[size]
              bne $t3,$zero,loop2

⇒ Array 구현시 loop가 2줄 더 길다. for문을 여러번 돌면, Pointer로 구현한 것과 차이가 커질 수 있다.

차이가나는 2줄은, array에서 인덱싱할 때,

1. i를 증가시키는 코드와
2. i를 해당 바이트 사이즈만큼 증가시켜
3. base array의 주소값에 i*4만큼 더해 구하기 때문이다..

즉, array 배열의 해당 구문이 pointer로 구현시에 한 줄로 줄어든다.

• array로 구현

sll $t1,$t0,2 #$t1 = i*4
add $t2,$a0,$t1 # $t2 = &array[i]
add $t0,$t0,1 # i = i+1

• pointer로 구현

addi $t0,$t0,4

⇒Pointer가 더 빠르지만 , Array가 이해하기 더 쉽고, 요즘은 Compiler 성능이 좋아져서 Array 사용해도 됨