[CSAPP] 5.4 Eliminating Loop Inefficiencies(루프 비효율성 제거하기)

5.4 Eliminating Loop Inefficiencies(루프 비효율성 제거하기)

• 아래 combine 함수를 source code 레벨(프로그래머가 작성하는 코드)에서 최적화하는 과정 중 루프 비효율성을 제거하는 방법을 제시하겠다.

/* Implementation with maximum use of data abstraction */
	void combine1(vec_ptr v, data_t *dest)
{
	long i;

	*dest = IDENT;
	for (i = 0; i < vec_length(v); i++) {
		data_t val;
		get_vec_element(v, i, &val);
		*dest = *dest OP val;
	}
}

• 루프의 매 실행마다 test condition이 평가된다.
• 위 코드에서 test condition으로 vec_length를 계속하고 조건에 부합하는 지 비교하고 있다. 
• 이 반복되는 test를 줄이기 위해 vec_length를 한번 계산 후(변하지 않기 때문에), 계산된 값을 사용하면 불필요한 반복 과정을 줄일 수 있다.  
• 아래는 불필요한 반복을 없앤 방식의 코드이다. length 변수에 계산된 값을 저장 후 루프에 이용.

/* Move call to vec_length out of loop */
void combine2(vec_ptr v, data_t *dest)
{
	long i;
    long length = vec_length(v);

	*dest = IDENT;
	for (i = 0; i < length; i++) {
		data_t val;
		get_vec_element(v, i, &val);
		*dest = *dest OP val;
	}
}

불필요한 반복 연산을 줄인 결과

• 위와 같은 최적화는 code noiton 유형이다. 
  • code notion은 반복 계산되지만 변하지 않는 값을 코드 상단에 위치시켜 반복 평가되지 않도록 하는 것이다.
  • 해당 예시에서는 vec_length를 length 라는 변수에 저장시켜 loop가 실행되기 전인 loop 밖에 위치시켜 미리 계산을 해두었다.
• 컴파일러는 위와 같은 최적화를 시도하게 되는데 앞서 말한, 함수 호출이 부가 효과(Side efftect)를 가지는 지 알 수 없기 때문에 side effect를 가진다고 가정한다.
• vec_length() 함수가 side effect를 가지면 combine1과 combine2의 결과는 달라지기 때문에, 컴파일러가 최적화할 수 없다.
• 따라서 프로그래머가 컴파일러가 최적화를 수행할 수 있도록 code notion을 명시적으로 수행해줘야 한다. (vec_length()를 사전에 미리 계산 후 한번만 계산할 수 있도록 코드를 작성한다)

또 다른 루프 비효율성(loop inefficiency) 예시

 

• 위 lower 함수는 대문자를 소문자로 바꿔주는 작업을 한다.
• lower1은 루프문 내부에 strlen함수를 n번 반복 호출해서 연산하는 과정을 가지고 각 반복은 n번 수행된다.
• 따라서 lower1은 n^2 시간이 소요된다. 
• 아래는 lower1과 lower2의 비교 결과이다. 

• lower1은 string length(n)이 길어질 때마다 소요되는 시간이 크게 상승한다.
• lower2은 string length의 크기와 상관 없이 소요되는 시간이 유사하다.
• lower1은 code notion(사전 한번의 연산 후 이용)이 이루어지지 않았고 lower2는 code notion이 이루어졌다.
• 일반적으로 프로그램은 작은 데이터 세트에서 테스트되고 분석되기 때문에 , lower1의 성능이 적합하다고 생각해버릴 수 있다.
• 하지만 100만 이상의 문자열에 적용될 수 있기 때문에, 프로그래머는 이 점을 유의해야 한다.