섣부르지 않은 최적화 기법

들어가며

'The Art of Computer Programming' 의 저자로 유명한 컴퓨터과학의 거장 도널드 크누스는 '섣부른 최적화는 만악의 근원'이라는 말을 했다. 확실하지도 않은 성능상의 이익 때문에 아키텍처나 가독성을 해치는 개발을 하지 말라는 뜻이다. 컴파일러가 발전하면서 섣부른 최적화는 더욱 큰 악이 되었다. 반복문 횟수를 줄이려고 Loop unrolling을 한다던가, 곱셈이나 나눗셈을 비트 연산으로 대체한다던가 하는 식의 세밀한 최적화는 읽는 사람을 당황스럽게 하는 것 외에는 별 효과가 없게 되었다.

이 말이 너무나 유명해지면서 최적화라는 키워드에 시큰둥한 개발자들도 생겼다. 시간복잡도 자체를 낮추지 않는 최적화는 소용 없다는 식이다. 그러나 시간 복잡도가 동일하더라도 작성하기에 따라 실행 시간이 수십 배 이상 차이나는 경우가 흔하다. 또 이러한 최적화가 꼭 가독성을 크게 헤치는 것도 아니다.

이 글의 예상 독자는 컴퓨터공학과 학생이나 개발자 지망생이다. 이미 개발자로 일하고 있다면 너무나 당연한 내용일 수 있기 때문에 목차에 모르는 내용이 없다면 읽지 않아도 된다. 예시 코드는 모두 Python이나 Golang으로 작성하였으나 특정 언어에 한정되는 내용은 아니다. 많은 언어에서 사용할 수 있는 국밥 같은 팁만 엄선하였다.

동적 배열의 용량(capacity)을 짐작하고 있다면 미리 선언한다

많은 언어에서 동적 배열을 선언할 때 초기 용량을 같이 지정할 수 있다.

//빈 슬라이스 선언
arr1 := []string{}
//capacity를 1000으로 지정
arr2 := make([]string, 1000)

크기를 신경쓰지 않고 마음대로 덧붙일 수 있는 것이 동적 배열의 매력이기 때문에 왜 굳이 용량을 지정하는 스타일을 사용하는지 의문이 들 수 있다. 이는 동적 배열의 용량을 늘리는 연산이 꽤 비싸기 때문이다. 동적 배열을 확장할 때는 기존 배열을 새로운 배열로 복사하는 연산을 해야한다.

왜 복사를 하는지 이유를 알지 못하겠다면 배열의 정의를 다시 생각해보자. 배열이란 데이터를 메모리 상에 연속적으로 배치한 것이다. arr[0] 바로 옆에 arr[1]이, arr[1] 옆에 arr[2]가 줄서있다는 뜻이다. 연속된 공간에 있기 때문에 N번째 원소를 한 번에 가져올 수 있는 것이다. 예를 들어 32비트 정수를 저장하는 배열의 i번째 원소의 값을 알고 싶다면 (32bit * i) 만큼 떨어진 곳의 데이터를 읽으면 된다.

여기서 배열의 크기를 200으로 늘리려면 어떻게 해야 할까? arr[100]~arr[199]의 공간을 바로 사용할 수 있다면 좋겠지만, 운영체제가 해당 공간을 다른 응용 프로그램에게 주지 않고 비워뒀을거라는 보장이 없다. 결국 새로운 공간을 200칸 만큼 할당하고 arr[0]~arr[99]의 데이터를 복사해야 한다. 크기를 너무 작게 선언하였다가 확장을 반복한다면 이런 비싼 연산을 몇번이고 반복하게 된다.

성능을 비교해보고 싶다면 다음의 golang 코드로 테스트해보면 된다.

func BenchmarkSliceNoCap(b *testing.B) {
	arr := []int{}
	for i := 0; i < b.N; i++ {
		arr = append(arr, i)
	}
}

func BenchmarkSliceWithCap(b *testing.B) {
	arr := make([]int, (b.N))
	for i := 0; i < b.N; i++ {
		arr[i] = i
	}
}

BenchmarkSliceNoCap-8             	320632680	        18.31 ns/op
BenchmarkSliceWithCap-8           	431997141	         4.904 ns/op

동적 배열을 선언할 때 용량을 지정해준 것 만으로도 4배 이상의 성능 개선 효과가 있었다. 물론 초기 용량을 쓸데없이 크게 설정한다면 괜히 메모리만 낭비하게 되는 결과가 발생할수도 있다. '최소 이 정도 크기는 될 것이다.'라는 짐작이 명확할 때만 사용하는 것을 추천한다.

반복문 안에서의 파일 출력은 최대한 피한다

응용 프로그램이 파일 출력을 하려면, 운영체제의 허락을 받기 위해 시스템 콜(System call)이라는 행동을 해야 한다. 시스템 콜은 응용 프로그램 내부의 코드를 실행하는 것보다 훨씬 비싼 연산이다. 반복문 안에서 파일을 출력하면 반복문의 횟수만큼 시스템 콜을 해야 한다. 메모리가 충분하다면 출력할 내용을 일단 메모리에 저장해두었다가 한 번에 쓰는 방식으로 시간을 절약할 수 있다. (반대로 말하면 메모리가 파일의 내용을 모두 저장해둘만큼 충분하지 않다면 쓰면 안 되는 방법이다.)

반복문의 횟수가 $N$이고 모든 내용을 파일에 출력하는데 걸리는 시간이 $F$, 시스템 콜에 드는 시간이 $S$라 하자. 반복문 안에서 파일 출력을 할 때의 시간은 $F + NS$ 이다. 반면 메모리에 담아 두었다가 한 번에 출력할 경우 $F + S$ 만큼의 시간만 소모하면 된다. 데이터를 메모리에 저장할 때 드는 시간은 $F$나 $S$에 비하면 무시할만한 수준이다.

성능을 비교해보고 싶다면 다음 golang 코드를 실행해 보면 된다. 벤치마크 결과 메모리에 저장해두는 방법이 최소 수십 배 빠르다.

func BenchmarkWriteStringInLoop(b *testing.B) {
	f1, err := os.Create("loopIO.txt")
	if err != nil {
		panic(err)
	}
	for i := 0; i < b.N; i++ {
		f1.WriteString("Hello, World!\n")
	}
}

func BenchmarkWriteStringArrAtLast(b *testing.B) {
	toWrite := make([]string, b.N)
	for i := 0; i < b.N; i++ {
		toWrite[i] = "Hello, world!"
	}
	f1, err := os.Create("loopIO.txt")
	if err != nil {
		panic(err)
	}

	f1.WriteString(strings.Join(toWrite, "\n"))
}

BenchmarkWriteStringInLoop-8      	  672982	      1536 ns/op
BenchmarkWriteStringArrAtLast-8   	38086471	        37.41 ns/op

문자열이 불변(immutable) 객체일 경우 덧셈을 반복하지 않는다

Java, Python, Golang 등 많은 언어에서 문자열은 불변 객체이다. 한번 만들어지고 나서 내용을 변경할 수 없다는 뜻이다. Python에서 다음 코드를 실행하면 에러가 나는 것을 확인할 수 있다.

s="Hello, world!"
s[1]="h"

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

에러 메시지를 읽어보면 문자열 객체는 생성 후 변경이 불가능함을 확인할 수 있다. 그런데 Python에서는 덧셈 연산자를 통해 문자열을 덧붙이는 것을 허용한다. 문자열을 덧붙이는 것 역시 변경의 일종인데 어떻게 이런 일이 가능한 것일까? 동적 배열을 확장할 때와 같이 복사가 일어나기 때문이다. 기존 문자열을 s1, 덧붙이는 문자열을 s2라 하자. len(s1) + len(s2) 만큼의 공간을 할당하고 여기에 s1과 s2의 내용을 복사한다.

물론 문자열의 길이가 짧다면 복사에서 생기는 오버헤드는 무시할만한 수준이다. 직관적인 덧셈 기호를 사용할 수 있으므로 가독성도 좋다. 그러나 얼마나 길어질지 모르는 반복문에서 복사를 계속 수행한다면 성능에 영향을 미칠 수 있다. 다행히 문자열이 불변 객체일 경우 언어 차원에서 문자열을 빠르게 덧붙일 방법을 지원하는 경우가 많다. 대표적인 예로 Java의 StringBuilder 클래스, python의 join 메소드, golang의 strings.Builder 구조체 등이 있다. 문자열 덧셈을 반복해야 할 때는 이런 기능을 사용하는 것이 좋다.

성능을 비교해보려면 다음 golang 코드를 실행해보면 된다. 벤치마크 결과 약 3000배 차이가 난다.

func BenchmarkStringPlus(b *testing.B) {
	str := ""
	for i := 0; i < b.N; i++ {
		str += "Hello, world!\n"
	}
}

func BenchmarkStringBuilder(b *testing.B) {
	builder := strings.Builder{}
	for i := 0; i < b.N; i++ {
		builder.WriteString("Hello, world!\n")
	}
}

BenchmarkStringPlus-8             	  120865	     79937 ns/op
BenchmarkStringBuilder-8          	100000000	        24.68 ns/op

멀티 쓰레딩을 '적절히' 활용한다.

다음 예시는 반복문 안에서 2차원 배열을 할당하고 행렬 곱셈을 수행하는 예시이다. BenchmarkGoroutine 함수에서는 행렬 할당과 곱셈을 할 때마다 새로운 고루틴을 할당하고 있다. 벤치마크 결과 고루틴을 할당하면 싱글 쓰레드 처리시보다 실행 시간이 약 80퍼센트 감소한다.

func allocMat(size int) [][]int {
	mat := make([][]int, size)
	for i := range mat {
		mat[i] = make([]int, size)
	}

	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			mat[i][j] = i + j
		}
	}

	return mat
}

func MultiplyMat(mat1 [][]int, mat2 [][]int, size int) [][]int {
	result := make([][]int, size)
	for i := 0; i < size; i++ {
		result[i] = make([]int, size)
	}
	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			for k := 0; k < size; k++ {
				result[i][j] = mat1[i][k] * mat2[i][j]
			}
		}
	}

	return result
}

const MultiplyMatCount = 10
const MatSize = 64

func BenchmarkSingleThread(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for j := 0; j < MultiplyMatCount; j++ {
			a := allocMat(MatSize)
			b := allocMat(MatSize)
			_ = MultiplyMat(a, b, MatSize)
		}
	}
}

func BenchmarkGoroutine(b *testing.B) {
	wg := sync.WaitGroup{}
	for i := 0; i < b.N; i++ {
		for j := 0; j < MultiplyMatCount; j++ {
			wg.Add(1)
			go func() {
				a := allocMat(MatSize)
				b := allocMat(MatSize)
				defer wg.Done()
				_ = MultiplyMat(a, b, MatSize)
			}()
		}
	}

	wg.Wait()
}

BenchmarkSingleThread-8           	     358	   3225632 ns/op
BenchmarkGoroutine-8              	    1516	    701193 ns/op

제목에 '적절히'라는 말을 강조한 것에는 두 가지 이유가 있다. 첫 번째 이유는 코드에 동시성을 도입한다고 무조건 빨라지는 것이 아니기 때문이다. 쓰레드를 할당하고 관리하는 작업 역시 성능에 영향을 끼친다. 예를 들어 쓰레드에 나눠준 작업의 실행 시간이 너무 짧다거나, 쓰레드를 너무 많이 만든다거나, 락을 잠그는 코드가 너무 많거나 하는 경우엔 쓰레드 할당의 오버헤드가 병렬 실행으로 인한 이득보다 클 수 있다. 멀티쓰레딩 도입시 성능 개선 여부를 논리적으로만 판단하기는 쉽지 않으므로 벤치마크를 통해 판단하는 것이 좋다. 두 번째 이유는 멀티쓰레딩이 코드의 복잡도를 크게 증가시킬 수 있기 때문이다. 특히 공유 자원이 많은 경우 코딩과 디버깅의 난이도가 급상승한다. 코드에 동시성을 도입하고 싶다면 코드의 복잡도를 줄이기 위한 고민을 충분히 해야 한다. 동시에 실행되는 코드를 함수형 스타일로 작성하는 것이 하나의 예이다.

생성에 오랜 시간이 걸리는 객체가 있다면 미리 만들어둔다

멀티쓰레딩에서 예시로 들었던 행렬 곱셈에선 매번 새로운 2차원 배열을 할당해야 했다. 2차원 배열을 미리 만들어두고 가져다 쓴다면 객체 할당 시간을 절약할 수 있다.

func BenchmarkSingleThreadWithPool(b *testing.B) {
	matrixPool := [][][]int{}
	for i := 0; i < MultiplyMatCount; i++ {
		matrixPool = append(matrixPool, allocMat(MatSize))
	}

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		for j := 0; j < MultiplyMatCount; j++ {
			a := matrixPool[j]
			b := matrixPool[j]
			_ = MultiplyMat(a, b, MatSize)
		}
	}
}

func BenchmarkGoroutineWithPool(b *testing.B) {
	matrixPool := [][][]int{}
	for i := 0; i < MultiplyMatCount; i++ {
		matrixPool = append(matrixPool, allocMat(MatSize))
	}

	b.ResetTimer()

	wg := sync.WaitGroup{}
	for i := 0; i < b.N; i++ {
		for j := 0; j < MultiplyMatCount; j++ {
			wg.Add(1)
			pool := j
			go func() {
				a := matrixPool[pool]
				b := matrixPool[pool]
				defer wg.Done()
				_ = MultiplyMat(a, b, MatSize)
			}()
		}
	}

	wg.Wait()
}

BenchmarkSingleThreadWithPool-8   	     432	   2678955 ns/op
BenchmarkGoroutineWithPool-8      	    2054	    601592 ns/op

매번 객체를 생성하던 방식 대비 실행 시간이 싱글 쓰레드 버전은 약 17퍼센트, 멀티 쓰레드 버전은 약 14퍼센트 감소한다. 이렇게 객체를 사전에 생성해둔 공간을 풀(Pool)이라고 한다. TCP 소켓이나 데이터베이스에 대한 연결을 매번 생성하지 않고 미리 만들어둔 것을 가져다 쓰는 커넥션 풀 방식이 실무에서 자주 쓰인다.

마치며

성능 최적화는 여전히 중요한 문제이다. 컴퓨팅 성능이 좋아진만큼 IT 서비스나 솔루션이 소화해야 할 연산의 양도 함께 증가했기 때문이다. 최적화 되지 않은 코드는 불필요한 인프라 비용을 발생시켜 사업의 마진을 해친다. 대용량 트래픽을 소화하고 싶다면 코드의 구조나 가독성을 해치지 않으면서 성능을 높일 방법을 계속 고민해야 한다. 섣부른 최적화를 하는 것도 좋지 않지만 일부러 느린 코드를 짤 필요도 없다.

참고 자료

Andrew Gerrand, Go Slices: usage and internals
stack overflow, How realloc work actually in the background?