[CSAPP] 5.6 Eliminating Unneeded Memory References(불필요한 메모리 참조 제거)

5.6 Eliminating Unneeded Memory References(불필요한 메모리 참조 제거)

• 아래 코드는 combine3 함수에서 *dest 연산 결과를 축적하는 과정을 어셈블리 코드로 변환한 결과이다.

data_t *get_vec_start(vec_ptr v)
{
	return v->data;
}

/* Direct access to vector data */
void combine3(vec_ptr v, data_t *dest)
{
	long i;	
   	long length = vec_length(v);
	data_t *data = get_vec_start(v);
	*dest = IDENT;
    
	for (i = 0; i < length; i++) {
		*dest = *dest OP data[i];
	}
}

//Inner loop of combine3. data_t = double, OP = *
//dest in %rbx, data+i in %rdx, data+length in %rax
1 .L17: loop:
2 vmovsd (%rbx), %xmm0 //Read product from dest
3 vmulsd (%rdx), %xmm0, //%xmm0 Multiply product by data[i]
4 vmovsd %xmm0, (%rbx) //Store product at dest
5 addq $8, %rdx //Increment data+i
6 cmpq %rax, %rdx //Compare to data+length
7 jne .L17 //If !=, goto loop

• 어셈블리 코드를 보면 %rbx(register)에 dest pointer 주소가 저장되어 있고 %rdx가 루프의 인덱스에 해당된다. 
• 한번의 루프가 돌고 %rdx에 8을 더해(double 형이기 때문에) 다음 인덱스를 가리키는 방식이다.
• %rax(data + length의 주소)와 %rdx를 비교함으로써 루프 조건을 확인한다.
• 위 코드는 불필요한 메모리 참조를 반복하고 있다. 
• 반복 시작 때 읽는 값은 *dest는 이전 반복문에서 끝난 값과 동일하기 때문에, 새롭게 메모리 읽기 쓰기를 하지 않아도 된다.
• 반복이 끝났을 때의 값을 저장해둔 후 다시 이용하는 방식을 이용하면 불필요한 메모리 참조를 줄일 수 있다.

/* Accumulate result in local variable */
void combine4(vec_ptr v, data_t *dest)
{
	long i;
	long length = vec_length(v);
	data_t *data = get_vec_start(v);
	data_t acc = IDENT;

	for (i = 0; i < length; i++) {
		acc = acc OP data[i];
	}
	*dest = acc;
}

//Inner loop of combine4. data_t = double, OP = *
//acc in %xmm0, data+i in %rdx, data+length in %rax
.L25: loop:
vmulsd (%rdx), %xmm0, %xmm0 //Multiply acc by data[i]
addq $8, %rdx //Increment data+i
cmpq %rax, %rdx //Compare to data+length
jne .L25 //If !=, goto loop

 

• acc라는 변수를 이용하여 이전 *dest 값을 이용할 수 있게 한다.
• 불필요한 메모리 읽기 쓰기를 제거할 수 있다.
• 어셈블리 코드의 경우 2번 읽고 1번 쓰는 코드에서 1번만 읽는 코드로 간소화 되었다.
• %xmm0은 acc 값을 저장하고 있다.
• 아래는 변환한 비교 결과이다.

• 약 2.2배에서 5.7배까지 성능이 향상되었음을 알 수 있다.

컴파일러가 위 과정을 자동으로 최적화할 수 있을까?

• 메모리 연결(Memory aliasing)으로 인해 combine4로 최적화 될 수 없다.

• vector인 v = [2,3,5]이고 IDENT는 1, OP는 *일 때를 가정하면
• 위의 경웨서 combine3는 *dest에 연산된 결과를 축적하고 있고 동일한 메모리를 반복하여 참조하고 있다. 

• 위와 같이 Memory aliasing으로 인해 다른 결과를 도출하기 때문에, 컴파일러는 최적화를 진행할 수 없다.
• 우리는 5.4~5.6 절의 과정을 통해 9~11 clock cycle에서 1.25~2.5 clock cycle만 이용할 수 있는 법을 배웠다.
• 이후에는 어떠한 것이 성능을 제한하고, 우리가 어떻게 더 성능을 향상시킬 수 있는 지에 대해 볼 것이다.