IT/모바일
저자: IT EXPERT, 리눅스 커널 프로그래밍 저자, 한동훈
이전기사 최적화 기법에 대해서는 많은 이야기들이 있습니다. 진실을 이야기하자면 대부분의 경우에 최적화에 대해서는 신경쓰지 않습니다. 네, 상용 프로그램을 만들때도 최적화를 하지 않습니다.
이 글을 등록하는 한빛미디어 사람들은 종종 다른 출판사의 책을 벤치마킹하기 위해 서점에 나가곤 합니다. 서재에서 책을 한 권 뽑으면 앞표지와 뒷표지의 레이아웃부터 살펴보고, 책의 휴대성을 살펴보고, 사용한 글꼴의 개수, 코드에 사용한 글꼴, 코드나 화면 편집 방법들에 대해서 살펴보는 나쁜(?) 버릇이 있습니다. 네, 저 같은 보통 사람들은 책의 제목과 내용을 먼저 살펴보는 데 말이죠. 때론, 전혀 상관없어 보이는 고시용 책이 출판사에 꽂혀있기도 합니다.
"누구 고시 공부하는 분 있어요?"
라고 물으면, 레이아웃과 편집 방식을 참고하기 위해 있는 책이라고 합니다.
저는 프로그래머이고, 최적화에는 관심이 없지만, 매우 느린 노트북을 사용하고 있습니다. 아직도 노트북이 P-III 800 Mhz이고, 여기서 모든 것을 다 합니다. VMware를 이용해서 리눅스 프로그래밍을 할 때도 있고, 원고를 쓸 때도 있습니다. 그래서, 최적화되지 않은 프로그램들이 상당히 많다는 것을 압니다. 네, 많은 상용 프로그램들은 최적화를 하지 않습니다. 특히, 웹 프로그램들은 심각한 수준으로 최적화를 하지 않습니다. 사람들이 이렇게 된 데에는 이유가 있습니다.
"최적화에 들이는 노력보다 하드웨어가 더 빠르게 발전하고 있다. 따라서 최적화는 무용. 느리면 서버 한 대 더 붙이면 되는 일이다"
"어셈블리를 쓰면서까지 최적화를 해도 컴파일러의 최적화를 앞서가지 못한다. 개발자는 CPU의 모든 특성을 알지 못하지만, 컴파일러 최적화는 CPU의 모든 특성을 이해하기 때문에 최적화에 맡기는 것이 낫다. 사람이 최적화를 하는 것은 필요없다"
라는 이야기를 듣습니다.
array의 0번째 item을 sentinel로 사용한 sequential scan에서도 알고리즘의 최적화에 대해 다루고 있지만 수작업 최적화보다 컴파일러 최적화가 더 최적화된 수행속도를 보여주는 것을 알 수 있습니다.
맞습니다. 오늘날에는 과거처럼 비트 단위까지 고려해가면서 최적화를 위해 각종 기교를 부릴 필요는 없어졌습니다. 각종 기교 때문에 이해하기 어려운 코드를 작성하는 것은 유지비용을 증가시키기 때문에 사라져야 합니다.
그런데, 딱 하나 남은 문제가 있습니다. 하드웨어가 아무리 빨라지고, 컴파일러 최적화 기능이 제 아무리 발전해도 애초에 설계가 잘못된 코드에 대해서는 최적화를 하지 못합니다.
최근에 어떤 제품의 라이브러리를 개발한 일이 있습니다. 모니터링 제품에 사용되는 것이기 때문에 라이브러리도 상당히 빠르게 동작해야 하고, UI 쪽에서도 상당히 빠르게 동작해야 합니다. 첫번째 버전은 동작 속도가 상당히 느렸습니다. 실시간으로 상태를 모니터링하지 못했습니다. 게다가, 메모리 사용량도 많았습니다. 때문에, 최적화 작업을 시작했습니다.
이 최적화에는 일반적으로 최적화 기법이라고 알려진 기교들을 전혀 사용하지 않았습니다. 예를 들어, 나눗셈을 곱셈 표현식으로 변환하는 최적화, 곱셈이나 덧셈을 비트 연산으로 변환하는 최적화, 모듈로(%) 연산을 비트 연산으로 변환하는 최적화 같은 것들은 전혀 사용하지 않았습니다. 사실, 이런 최적화 기법들은 현재 대부분의 컴파일러(VC++, gcc, Watcom C++, Borland C++ 등)들이 제공하고 있는 기능입니다.
문제에서 얘기한 것처럼 두 부분에서의 최적화를 진행했습니다. 라이브러리에서는 메모리 사용량을 줄이는 최적화를 했습니다. UI 쪽에서는 동작 속도를 개선하는 최적화를 했습니다.
메모리 사용량을 줄이는 최적화를 하기 위해 수행한 작업은 재설계(redesign)였습니다. 최적화를 위한 그 어떤 기교도 사용하지 않았고, 읽기 쉬운 코드를 작성하면서 시스템을 재설계한 것입니다. UI 쪽에서도 시스템을 재설계했습니다. 첫번째 버전을 만들면서 익히게 된 기술이 있고, UI 작업에도 익숙해진 만큼 개선점을 이해할 수 있고, 보다 나은 코드를 만들 수 있었습니다.
따라서, 요즘의 컴퓨팅 환경을 고려한다면 최선의 최적화는 점진적인 재설계입니다. 처음부터 완벽한 것을 만들려고 하는 것이 아니라 동작하는 최초의 코드를 만들고, 끊임없이 재설계하면서 코드를 개선해가는 것입니다. 이렇게 만든 코드들은 잘 동작하며, 끊임없이 개선되어가는 모습이 마치 살아있는 생명체와 같습니다. 오늘날 웹2.0 기업들이 너도나도 베타를 붙이는 것은 이런 의미입니다. 과거의 포탈들은 블로그 서비스를 만들었다고 한다면 3개월 동안 블로그 서비스를 개발하고, 블로그 서비스를 제공하는 것으로 끝입니다. 가끔 버그 수정 기간이 1개월 정도 있을 뿐이고, 그 기간이 끝나면 버그 수정조차 이뤄지지 않습니다. 또한, 자체 개발팀이 개발한 것이 아니라 외주 업체에 외주를 통해 개발했다면 그 소프트웨어는 프로젝트가 종료된 시점에 죽은 소프트웨어가 됩니다. 단순히 베타를 붙인 것이라면 죽은 말(dead horse)에게 베타를 붙인 것에 불과합니다.
이 글의 주제는 최적화입니다. 그런데, 지금까지 얘기한 내용들은 최적화를 위한 기교는 필요없으며, 최적화를 하려면 점진적인 재설계를 하는 것이 좋다라는 이야기를 하고 있습니다. 게다가, 모듈로, 나눗셈, 곱셈, 덧셈, 루프, 비교문에 대해서 대부분의 컴파일러들은 잘 알려진 최적화 기법을 모두 적용합니다. 심지어 함수 호출이 빠른가, 인라인 함수 호출이 빠른가를 판별해서 최적화해주는 기능까지 포함되어 있습니다. 단순히 컴파일만 하는 것이 아니죠! 굉장히 많은 일을 합니다!
네, 최적화를 하고 싶다면 기교를 찾는 것 보다는 성능을 최적화할 수 있도록 재설계하는 것이 가장 좋은 해결책입니다. 설계가 이미 충분히 최적화되어 있고, 알고리즘이 이미 충분히 잘 구성되어 있는데도 원하는 성능 목표에 도달하지 못했다면 최적화를 더 해야 합니다. 그럴때는 컴파일러가 해주지 않는 최적화에 대해 살펴봐야 합니다.
이제, 최적화에 대해 살펴보겠습니다.
문제제기
다음과 같은 버전의 연결 리스트 구현이 있습니다. 첫번째 버전 보다는 두번째 버전의 효율이 더 좋다고 알려져있습니다.
루프 최적화
루프 최적화에 대해 널리 알려진 방법은 루프 풀기입니다. 이 방법은 1983년 11월 Tom Duff씨가 루카스필름을 위한 프로그램을 개발하면서 발견한 것입니다. VAX 머신에서 분기 문이 많은 코드는 병목현상을 나타냈고, 이를 개선하기 위해 루프를 풀어내는 방법을 제안합니다. 다음은 병목현상이 발생하는 코드입니다.
그림. 병목현상이 있는 코드
VAX 머신에서 레지스터에 값을 넣으면 주소값이 자동으로 증가하기 때문에 *to = *from++과 같은 코드를 사용하는 것이 맞습니다. x86 환경에서 C 언어를 사용하고 있다면 *to++ = *from++과 같이 코드를 작성해야 정상적으로 동작합니다. 어쨌거나 이런 건 중요한 게 아닙니다. 다음은 루프를 풀어내는 방법으로 최적화를 수행한 것입니다.
그림. 루프 풀기로 최적화한 코드
이렇게 루프를 풀었을 때, 최적화가 되었다고 합니다. 뭐가 최적화된거죠?
VAX 머신이 8비트 시스템이었고, 오늘날에는 x86 32비트 시스템을 사용하고 있고, 64비트 시스템의 사용도 늘어나고 있습니다. 그런데, 이런 루프 풀기는 여전히 유효합니다. 대부분의 컴파일러는 루프 풀기 최적화를 하지 않습니다.
데이터 읽기가 최적화되나요? 알다시피, 이건 데이터를 빠르게 복사하는 코드를 최적화한 겁니다. 데이터는 한 번 읽고 쓰면 끝납니다. 캐싱해도 얻을 게 없고, 코드를 저렇게 바꿔도 별로 이득될게 없어보입니다. 대체, 뭐가 이득인거죠?
데이터 읽기가 최적화된 것도 아닙니다. 근데, 재미있는 건 루프 풀기가 읽기 최적화 기법으로 소개된다는 겁니다!
그러면, 실행되는 코드(제어구조나 변수)가 계속 반복적으로 접근되니까 코드 캐시가 최적화되는 걸까요? 두 루프간에 사용된 변수 차이도 거의 없습니다. 접근 횟수만 비교한다면 차이도 없습니다. 모듈로 연산까지하는 두번째 코드가 더 나쁩니다. 근데, 왜 최적화가 되고, 수행속도가 50%나 개선되었다는 이야기를 하게 된 걸까요? 위키 백과 사전을 보면 캐시 히트율(Cache hit rate)이 개선되었다는 이야기를 합니다. 데이터 캐시가 개선된 것? 코드 캐시가 개선된 것? 뭐죠? 뭐가 최적화 된거죠?
루프 풀기에 의한 50% 성능 개선에 대한 이유로 설명하는 것이 대부분 루프 반복 횟수가 줄어들었기 때문이라고 설명합니다. 진짜 루프 반복 횟수가 줄어든 게 그만큼의 성능이득일까요? 루프 안에 더 많은 코드를 넣게 되면 더 많은 데이터 공간을 사용하게 됩니다. 이는 성능상의 이득으로 연결되는 경우보단 저하로 연결되는 경우가 더 많습니다. 데이터 캐시 히트를 고려한다면 루프 안에 접근되는 코드들의 데이터 크기가 32바이트 이내로 꽉 짜여져 있어야 한다는 조건까지 붙어버립니다. 위의 예제는 간단한 루프이니 32바이트 조건 이내에 포함되지만, 대부분의 루프는 32바이트 이상의 데이터를 사용합니다. 게다가, 루프를 풀었거나 풀지 않았거나 CPU가 실행해야 하는 명령어의 총량은 둘 다 차이가 없습니다. 일반적인 루프로 작성된 코드에서 루프를 100번 수행하고, 그 안에서 5개의 명령어를 실행한다면 총 500개의 명령어를 실행합니다.
이 루프를 20번으로 줄이고, 안에서 5 * 5 = 25개의 명령어를 실행한다고 합시다. 이 경우에도 500개의 명령어를 실행합니다. 아니, 실제로는 루프를 풀기위해 모듈로 연산(%)을 사용하고, 딱 나누어 떨어지지 않는 수에 대해서는 추가적인 코드까지 작성해야 하기 때문에 루프 풀기를 했을 때 실행해야 하는 명령어의 수는 더 증가합니다. 전혀 최적화되지 않아야 정상입니다.
혹자는 이런 얘기를 합니다. 루프 비교 횟수가 100번에서 20번으로 줄어들었다. 따라서, 80번의 비교를 하지 않아도 된다라고 말합니다. 그런데, 이렇게 얻은 이점 정도는 루프 풀기를 위해 추가로 작성한 코드를 계산한다면 그 이득은 상쇄됩니다. 얻는 게 없는 것이죠.
이게 왜 최적화를 하는지 이해하려면 파이프라인에 대해 알아야 합니다.
현대 프로세서들은 모두 명령어를 빠르게 처리하기 위해 파이프라인을 사용합니다. 컴퓨터가 명령어를 수행하는 단계는 메모리를 읽는 단계, 명령을 해석하는 단계, 수행하는 단계로 나뉘어져있습니다. 실제로 ADD라는 간단한 명령을 수행하는데도 두 단계의 전처리가 필요한 겁니다. CPU는 한 사이클이면 명령을 실행할 수 있습니다. 이 때는 두 사이클을 대기하게 됩니다. 이는 비효율적이죠?
그래서, 도입된 게 파이프라인입니다. 어려운 게 아닙니다. 공장을 보면 컨베이어 벨트를 따라서 제품이 이동하는 동안에 사람들이 자동차 바퀴를 끼우고, 다음 위치에서는 볼트를 조이는 것과 같습니다. 자동차 공장에서 차를 1분에 한 대씩 생산한다고 해서 정말 차가 만들어지는 데 필요한 시간이 1분이 아닌 것과 같습니다. 때문에, 자동차 공장에서 정전이나 파업 같은 문제로 공장 가동을 중단하게 되면 단순히 차를 생산하지 못하는 것이 아니라 전체 라인을 재정비해야 하는 추가적인 비용이 들어가게 됩니다. 네, 경영자 입장에서 보면 막대한 손실입니다.
루프 안의 코드를 실행하는 것은 컨베이어 벨트를 타면서 이동하는 것과 같습니다. 즉, 순차적으로 모든 명령이 빠르게 수행됩니다. 그런데, 루프를 만나서 분기하게 되면 지금까지 해오던 작업을 모두 끝내야 합니다. 컨베이어 벨트 위에 있던 물건들을 몽땅 지우고, 첫단계부터 새로 작업을 시작해야 합니다. 자동차 공장에서 차를 1분에 한 대씩 생산하는 것은 맞지만, 컨베이어 벨트의 처음부터 끝까지 이동하는데 걸리는 시간은 일주일, 아니면 한 달이 걸리는 겁니다. 이렇게 긴 컨베이어 벨트 위의 과정을 모두 정리한다고 생각해 보세요. 끔찍한 일입니다.
파이프라인을 이용하는 현대 CPU에서 분기문은 파이프라인을 모두 정리하는 작업을 합니다. 따라서, 분기문을 자주 만날수록 코드의 실행은 느려집니다.
첫번째 루프 코드를 생각해보세요. 이 코드는 컨베이어 벨트의 직선 주기가 너무 짧습니다. 루프 안의 코드가 지나치게 짧다는 겁니다. 컨베이어 벨트를 너무 자주 정리하는 겁니다.
두번째 루프를 생각해보세요. 컨베이어 벨트가 길어졌습니다. 그리고, 컨베이어 벨트를 정리하는 횟수는 1/8로 줄여버렸습니다. 네, 여기서 수행속도의 향상이 발생합니다. 루프 풀기 기법은 파이프라인의 정리 횟수를 줄여주고, 결국 코드에 대한 캐시 히트율을 향상시킵니다.
일반적인 루프는 다음과 같습니다.
첫번째 코드와 같은 루프를 1:1 루프라고 합니다. 이때의 수행속도를 100%로 생각한다면, 두번째 1:2 루프 풀기는 66%의 수행속도가 나옵니다. 즉, 34% 정도가 개선된 셈입니다. 이는 CPU 아키텍처마다 다릅니다. 특히, AMD CPU들은 1:2 루프 풀기에서 수행 속도 향상이 10% 미만일 정도로 형편없습니다. 이는 CPU 아키텍처의 차이입니다. 그러나, 인텔이든 AMD이든 1:8 루프 풀기의 경우 50% 정도의 수행 속도 향상을 관찰할 수 있습니다. 32비트 환경에서 1:16, 1:32, 1:64 루프 풀기까지도 구현할 수 있지만 성능 향상의 차이가 5% 미만으로 매우 작습니다. P4 전용으로 컴파일한다면 버스트 사이클이 128 바이트이므로 1:32 루프 해제까지가 가장 이상적인 결과가 예상됩니다. 물론, 이는 이론적인 것입니다.
루프 풀기를 할 때의 문제점은 반드시 배수로 떨어지지 않는 다는 것입니다. 100번의 루프를 수행하는데 1:8 루프 해제를 한다면 96회까지는 배수이며, 나머지 4회는 루프 바깥에서 수행해야 합니다. 루프 풀기는 항상 이렇게 수행됩니다.
루프 풀기는 메모리 읽기에 대해서만 성능이 좋습니다. 메모리 쓰기에 대해서는 성능 개선이 거의 없습니다. 따라서, 루프 풀기 최적화를 적용하고 싶다면 읽기에 대해서만 적용해야 하며, 쓰기에 대해서는 적용하지 않아야 합니다.
루프 풀기는 만능이 아닙니다. CPU 아키텍처에 따라 다르지만 x86에서는 한번에 32바이트를 읽어올 수 있습니다. 따라서, 루프 안의 데이터도 32바이트 한도내에 있을 때에만 최적의 효율을 낼 수 있습니다.(VIA KT-133 칩셋에서 처음 시도했던 메모리 미리 읽기(Read-Ahead)에 대해서는 고려하지 않습니다)
만약, 코드를 해당 아키텍처에 최적화되게 컴파일했다면 버스트 사이클(Burst Cycle)의 길이가 달라집니다. 최근의 CPU들은 살펴보지 않아서 알 수 없지만, 애슬론(Athlon)은 64바이트이고, 펜티엄4는 128바이트입니다. 코어2 듀오 같은 최신 CPU의 버스트 사이클을 알지는 못하지만, 최소 128 바이트 이상일 것입니다. 이 말의 의미는 한 번에 128바이트를 읽어올 수 있다는 것을 의미합니다.
루프 풀기를 최적화하기 위해서 어셈블리를 사용할 수도 있습니다. 그런데, 저는 어셈블리를 거의 사용하지 않는 탓에 대부분의 어셈블리 언어를 잊어버렸습니다. 그래서 어셈블리를 사용한 루프 풀기는 하지 않을 겁니다. 네, 루프 풀기를 쉽게 할 수 있는 꽁수는 있습니다. gcc 컴파일러에서 gcc -s file.c 명령을 사용하면 file.s 파일이 생성됩니다. 어셈블리어 버전이 자동으로 생성되는데, 이렇게 생성된 코드를 가져다가 사용하는 방법도 있습니다.
루프 풀기를 자동화할 수 있는 여러가지 방법이 있는데, 저는 다음과 같은 방법이 가장 마음에 듭니다.
사실, 첫번째 이야기는 여기까지 끝이었는데, 다음은 다른 분들의 의견을 받아 읽을거리로 내용을 보강해봅니다.
VAX 머신과 파이프라인
VAX는 오래된 머신이고 사람들은 이 당시의 CPU에는 파이프라인이 적용되지 않았을 것이라고 얘기합니다. VAX 머신의 매뉴얼을 찾는데는 실패했으므로 파이프라인이 있다/없다라고 단정적으로 얘기하지 못해서 죄송합니다. 제 생각을 말하라면 VAX 머신에도 파이프라인이 적용되어 있었을 것이고, 아마도 당시에는 순차 파이프라인이 적용되어 있었기 때문에 루프문과 같은 분기문에 상당히 민감한 CPU였을 것이라 생각합니다.
파이프라인이 처음 적용된 것은 MOS-6502라는 프로세서로 1스텝 파이프라인이 적용되어 있었습니다. 이 8비트 프로세서는 1975년에 등장했습니다. VAX 머신은 그 보다 뒤인 1977년에 등장했고, Duff가 작업했던 당시는 1983년입니다. 최초로 등장했던 인텔의 8086 프로세서는 1976년도에 등장했습니다. 그러니까, MOS-7502 -> 8086 -> VAX의 순서로 등장했습니다. 8086은 16비트 프로세서였고, 6바이트의 프리페치 큐(prefetch queue)와 2 단계 파이프라인을 가졌습니다. 당시에 VAX는 서버용이었고, 파이프라인이 적용되었을거라 예상해봅니다. 오늘날에는 몇천원에 살 수 있는 8비트 AVR 프로세서도 5-6단계 파이프라인을 갖고 있습니다.(검색상에서는 VAX 파이프라인을 고려한 효율적인 프로그래밍에 대한 것은 찾았지만 정확히 몇 단계 파이프라인을 가졌는지는 찾지 못했습니다)
루프가 수행되는 횟수를 줄이는 것으로 성능 이득이 있었다고 알려진 것은 결국 잘못된 믿음이 되어 버린 것입니다. 정확하게는 루프 횟수의 감소가 분기의 감소를 의미하고, 분기의 감소는 파이프라인을 정리하는 횟수의 감소를 의미하기 때문에 성능이 증가하는 것입니다. 자동차 경주와 같습니다. 자동차는 직선 주로를 달릴 때는 빠르지만 코너를 돌 때는 속도를 늦춰야합니다. 자동차가 달려야 하는 총 거리는 500km인데 직선거리가 200km이고, 코너가 300km라면 경주시간은 길어지게 됩니다. 루프 풀기를 사용해서 직선거리를 400km로 늘려주고, 코너를 100km로 줄이면 경주시간은 짧아지게 됩니다. 결국, 어느쪽을 사용하든 달리는 거리는 같습니다. 프로그램에서야 루프 풀기를 하면 코드가 조금 더 복잡해지지만, 마지막에 소개한 매크로를 이용한 팁을 적용하면 루프 풀기를 할 때 부가적인 코드를 작성할 필요도 완전히 사라지게 됩니다. 네, 모듈로 연산을 완전히 제거할 수 있습니다.
참고. Duff"s Device가 처음 등장할 때는 루프(즉 분기문)의 횟수를 줄였더니 성능개선이 있었으니 루프를 줄이는 것이 목적이었습니다.
순차 파이프라인과 비순차 파이프라인
원문에서 설명한 파이프라인은 순차 파이프라인입니다. 순차 파이프라인에서는 분기문을 만나게 되면 반드시 파이프라인을 비우는 작업을 해야합니다. 현대 CPU는 비순차(Out-of-Order) 파이프라인을 사용합니다. 이런 파이프라인은 수십개 이상의 명령어를 미리 가져와서 병렬성을 찾아서 가능한 것들부터 미리 실행합니다. 즉, 코드에 있는 순서대로 실행되지 않습니다. OoO 머신에서는 분기 예측을 사용합니다. 코어2듀오와 같은 환경에서는 이러한 분기 예측이 보다 공격적으로 이뤄집니다. 커널 코드를 생성할 때 특정 코드로 이동할 때 왜 jmp 대신에 cmov를 사용하는가? 라는 질문이 올라온 적이 있습니다. 네, 조건을 판단해서 단순히 jmp 명령을 사용하는 것이 더 효율적인 것처럼 보입니다. cmov는 조건에 따라 이동하는 것이고, OoO 머신에서는 분기 예측까지 포함되기 때문에 더 느리게 동작할 것처럼 생각됩니다. 네, 상식적인 수준에서는 그렇습니다. 그러나, 실제로 분기 예측을 하는 CPU들은 매우 높은 분기 예측율을 달성하고 있고, 그런 머신에서는 jmp 문을 사용하는 것보다는 cmov를 사용하는 것이 분기 예측을 이용하기 때문에 더 높은 성능을 달성한다고 합니다.
따라서, 루프 풀기로 인해 성능이 극적으로 개선되는 것은 순차 파이프라인을 사용한 환경입니다. 아마도 8051, AVR 같은 임베디드 환경의 프로세서들이 그 대상이 되겠죠? 오늘날 PC에서 사용되는 대부분의 프로세서는 비순차 파이프라인입니다. 특히, 공격적인 분기 예측을 하는 것으로 잘 알려진 코어2듀오 같은 환경에서는 루프 풀기로 인한 성능 향상의 차이가 그렇게 크지는 않습니다. 코어2듀오 T7200 CPU에서 읽기에 대한 루프 풀기를 테스트하면 1:2 루프 풀기에서 20.3%의 성능 개선이 나타나고, 1:4 루프 풀기에서는 19.9%, 1:8 루프 풀기에서는 19.9%, 1:16 루프 풀기에서는 18.6%의 성능 개선이 나타납니다. 공격적인 분기 예측 때문에 루프 풀기를 하면 할수록 성능이 개선되기는커녕 떨어지는 것을 볼 수 있습니다. 코어2듀오 같은 환경이라면 1:2 루프 풀기가 가장 이상적이며 평균적으로 20%의 성능 향상을 얻는 것을 알 수 있습니다.
만약, 병목 현상이 있는 구간에 루프 풀기를 적용한다면 약 20%의 성능 개선을 얻을 수 있겠죠?
쓰기와 루프 풀기
쓰기의 경우에는 루프 풀기로 이득을 거의 볼 수 없습니다. P-III 800Mhz 환경에서 테스트하면 루프 풀기를 할 경우 2 ~ 10%의 성능 저하가 관찰됩니다. 코어2듀오 E7200 환경에서는 40 ~ 45%의 성능저하가 나타납니다. 따라서, 쓰기 성능에 대해서는 루프 풀기를 전혀 적용하지 않는 것이 좋습니다. 루프 풀기를 하는 경우 추가적인 코드 작성이 필요하고 이 부분이 성능 저하로 연결됩니다. 또한, 분기 예측 방법에 따라 성능 저하의 폭이 다르다는 것을 관찰할 수 있습니다. 만약, 다양한 환경을 갖추고 있다면 테스트 해볼 것을 권합니다.
쓰기에 대한 루프 풀기에 대한 예는 http://www.ddj.com/dept/cpp/184403799를 참고하기 바랍니다.
CPU 아키텍처에 따른 버스트 사이클
현대 PC에 사용되는 DRAM은 한 번 데이터를 읽을 때 정확히 해당 데이터만 읽어오지 않습니다. 정확히는 해당 데이터가 있는 열(Row) 전체를 읽어옵니다. x86 아키텍처에서 이 값은 오랫동안 32바이트입니다. 만약, AMD Athlon 전용으로 컴파일된 코드가 있다면 이 값은 64바이트입니다. 펜티엄4를 사용하고 있다면 이 값은 128바이트입니다. 다음과 같은 구조체가 있다고 생각해봅니다.
분기 예측은 완벽한가?
분기 예측은 완벽하지 않습니다. 가장 극단적인 예로 리눅스 커널에서 대부분의 코드는 잘 수행될 것이고, 올바른 값을 갖고 있을 것이라 생각하지만 데이터가 정확하게 들어왔는지 확인하기 위한 검사를 수행합니다. 이런 종류의 검사를 결벽증 환자가 깨끗한 손을 또 씻고 씻는 것과 비슷해서 그런지 몰라도 sanity check(온전성 검사)라 부릅니다. 대부분의 경우에 이런 if 문 안에 있는 내용들은 실행되지 않습니다. 이런 경우에 CPU 자체에 분기 예측을 맡기기 보다는 사람이 직접 컴파일러 힌트를 적어주는 방법을 사용해서 보다 효율적인 기계어를 생성하게 해줍니다. 커널 코드에서 가장 흔하게 볼 수 있는 likely(), unlikely() 매크로가 그런 역할을 수행합니다.
논의에 참여하신 분들 덕분에 애초 A4 6장 분량이었는데 11장으로 늘어났습니다. 역시, 참여자가 있으면 내용이 보다 알차지는 것 같습니다. 알찬 글을 꾸미는 데는 mkseo, object, 이원구님이 있었습니다.
내용이 길어졌습니다. 서두에 제기했던 문제에 대해서는 아직 시작도 못했는데 이야기가 너무 길어졌습니다. 다음엔 서두에 제시한 코드가 왜 더 빠르게 수행되는지 본격적으로 살펴보겠습니다.
참고자료
이전기사 최적화 기법에 대해서는 많은 이야기들이 있습니다. 진실을 이야기하자면 대부분의 경우에 최적화에 대해서는 신경쓰지 않습니다. 네, 상용 프로그램을 만들때도 최적화를 하지 않습니다.
이 글을 등록하는 한빛미디어 사람들은 종종 다른 출판사의 책을 벤치마킹하기 위해 서점에 나가곤 합니다. 서재에서 책을 한 권 뽑으면 앞표지와 뒷표지의 레이아웃부터 살펴보고, 책의 휴대성을 살펴보고, 사용한 글꼴의 개수, 코드에 사용한 글꼴, 코드나 화면 편집 방법들에 대해서 살펴보는 나쁜(?) 버릇이 있습니다. 네, 저 같은 보통 사람들은 책의 제목과 내용을 먼저 살펴보는 데 말이죠. 때론, 전혀 상관없어 보이는 고시용 책이 출판사에 꽂혀있기도 합니다.
"누구 고시 공부하는 분 있어요?"
라고 물으면, 레이아웃과 편집 방식을 참고하기 위해 있는 책이라고 합니다.
저는 프로그래머이고, 최적화에는 관심이 없지만, 매우 느린 노트북을 사용하고 있습니다. 아직도 노트북이 P-III 800 Mhz이고, 여기서 모든 것을 다 합니다. VMware를 이용해서 리눅스 프로그래밍을 할 때도 있고, 원고를 쓸 때도 있습니다. 그래서, 최적화되지 않은 프로그램들이 상당히 많다는 것을 압니다. 네, 많은 상용 프로그램들은 최적화를 하지 않습니다. 특히, 웹 프로그램들은 심각한 수준으로 최적화를 하지 않습니다. 사람들이 이렇게 된 데에는 이유가 있습니다.
"최적화에 들이는 노력보다 하드웨어가 더 빠르게 발전하고 있다. 따라서 최적화는 무용. 느리면 서버 한 대 더 붙이면 되는 일이다"
"어셈블리를 쓰면서까지 최적화를 해도 컴파일러의 최적화를 앞서가지 못한다. 개발자는 CPU의 모든 특성을 알지 못하지만, 컴파일러 최적화는 CPU의 모든 특성을 이해하기 때문에 최적화에 맡기는 것이 낫다. 사람이 최적화를 하는 것은 필요없다"
라는 이야기를 듣습니다.
array의 0번째 item을 sentinel로 사용한 sequential scan에서도 알고리즘의 최적화에 대해 다루고 있지만 수작업 최적화보다 컴파일러 최적화가 더 최적화된 수행속도를 보여주는 것을 알 수 있습니다.
맞습니다. 오늘날에는 과거처럼 비트 단위까지 고려해가면서 최적화를 위해 각종 기교를 부릴 필요는 없어졌습니다. 각종 기교 때문에 이해하기 어려운 코드를 작성하는 것은 유지비용을 증가시키기 때문에 사라져야 합니다.
그런데, 딱 하나 남은 문제가 있습니다. 하드웨어가 아무리 빨라지고, 컴파일러 최적화 기능이 제 아무리 발전해도 애초에 설계가 잘못된 코드에 대해서는 최적화를 하지 못합니다.
최근에 어떤 제품의 라이브러리를 개발한 일이 있습니다. 모니터링 제품에 사용되는 것이기 때문에 라이브러리도 상당히 빠르게 동작해야 하고, UI 쪽에서도 상당히 빠르게 동작해야 합니다. 첫번째 버전은 동작 속도가 상당히 느렸습니다. 실시간으로 상태를 모니터링하지 못했습니다. 게다가, 메모리 사용량도 많았습니다. 때문에, 최적화 작업을 시작했습니다.
이 최적화에는 일반적으로 최적화 기법이라고 알려진 기교들을 전혀 사용하지 않았습니다. 예를 들어, 나눗셈을 곱셈 표현식으로 변환하는 최적화, 곱셈이나 덧셈을 비트 연산으로 변환하는 최적화, 모듈로(%) 연산을 비트 연산으로 변환하는 최적화 같은 것들은 전혀 사용하지 않았습니다. 사실, 이런 최적화 기법들은 현재 대부분의 컴파일러(VC++, gcc, Watcom C++, Borland C++ 등)들이 제공하고 있는 기능입니다.
문제에서 얘기한 것처럼 두 부분에서의 최적화를 진행했습니다. 라이브러리에서는 메모리 사용량을 줄이는 최적화를 했습니다. UI 쪽에서는 동작 속도를 개선하는 최적화를 했습니다.
메모리 사용량을 줄이는 최적화를 하기 위해 수행한 작업은 재설계(redesign)였습니다. 최적화를 위한 그 어떤 기교도 사용하지 않았고, 읽기 쉬운 코드를 작성하면서 시스템을 재설계한 것입니다. UI 쪽에서도 시스템을 재설계했습니다. 첫번째 버전을 만들면서 익히게 된 기술이 있고, UI 작업에도 익숙해진 만큼 개선점을 이해할 수 있고, 보다 나은 코드를 만들 수 있었습니다.
따라서, 요즘의 컴퓨팅 환경을 고려한다면 최선의 최적화는 점진적인 재설계입니다. 처음부터 완벽한 것을 만들려고 하는 것이 아니라 동작하는 최초의 코드를 만들고, 끊임없이 재설계하면서 코드를 개선해가는 것입니다. 이렇게 만든 코드들은 잘 동작하며, 끊임없이 개선되어가는 모습이 마치 살아있는 생명체와 같습니다. 오늘날 웹2.0 기업들이 너도나도 베타를 붙이는 것은 이런 의미입니다. 과거의 포탈들은 블로그 서비스를 만들었다고 한다면 3개월 동안 블로그 서비스를 개발하고, 블로그 서비스를 제공하는 것으로 끝입니다. 가끔 버그 수정 기간이 1개월 정도 있을 뿐이고, 그 기간이 끝나면 버그 수정조차 이뤄지지 않습니다. 또한, 자체 개발팀이 개발한 것이 아니라 외주 업체에 외주를 통해 개발했다면 그 소프트웨어는 프로젝트가 종료된 시점에 죽은 소프트웨어가 됩니다. 단순히 베타를 붙인 것이라면 죽은 말(dead horse)에게 베타를 붙인 것에 불과합니다.
이 글의 주제는 최적화입니다. 그런데, 지금까지 얘기한 내용들은 최적화를 위한 기교는 필요없으며, 최적화를 하려면 점진적인 재설계를 하는 것이 좋다라는 이야기를 하고 있습니다. 게다가, 모듈로, 나눗셈, 곱셈, 덧셈, 루프, 비교문에 대해서 대부분의 컴파일러들은 잘 알려진 최적화 기법을 모두 적용합니다. 심지어 함수 호출이 빠른가, 인라인 함수 호출이 빠른가를 판별해서 최적화해주는 기능까지 포함되어 있습니다. 단순히 컴파일만 하는 것이 아니죠! 굉장히 많은 일을 합니다!
네, 최적화를 하고 싶다면 기교를 찾는 것 보다는 성능을 최적화할 수 있도록 재설계하는 것이 가장 좋은 해결책입니다. 설계가 이미 충분히 최적화되어 있고, 알고리즘이 이미 충분히 잘 구성되어 있는데도 원하는 성능 목표에 도달하지 못했다면 최적화를 더 해야 합니다. 그럴때는 컴파일러가 해주지 않는 최적화에 대해 살펴봐야 합니다.
이제, 최적화에 대해 살펴보겠습니다.
문제제기
다음과 같은 버전의 연결 리스트 구현이 있습니다. 첫번째 버전 보다는 두번째 버전의 효율이 더 좋다고 알려져있습니다.
struct linked
{
struct linked *next;
int data;
}
와
struct linked
{
struct linked *next;
int *data;
}
둘 간의 차이는 데이터 요소를 포인터로 선언해둔 것 뿐입니다. DRAM 메모리 특성 때문인데, 이에 대해서는 조금 더 자세히 살펴볼 필요가 있습니다. 특히, 두번째 구현과 같은 경우에 포인터를 해석하고 주소를 따라가서 값을 읽어와야 하기 때문에 더 느리지 않은가?라는 의문을 제기하게 됩니다. 자, 이 문제를 살펴보기 위해서 먼저 다음과 같은 배경지식을 살펴봅시다.
루프 최적화
루프 최적화에 대해 널리 알려진 방법은 루프 풀기입니다. 이 방법은 1983년 11월 Tom Duff씨가 루카스필름을 위한 프로그램을 개발하면서 발견한 것입니다. VAX 머신에서 분기 문이 많은 코드는 병목현상을 나타냈고, 이를 개선하기 위해 루프를 풀어내는 방법을 제안합니다. 다음은 병목현상이 발생하는 코드입니다.
그림. 병목현상이 있는 코드
VAX 머신에서 레지스터에 값을 넣으면 주소값이 자동으로 증가하기 때문에 *to = *from++과 같은 코드를 사용하는 것이 맞습니다. x86 환경에서 C 언어를 사용하고 있다면 *to++ = *from++과 같이 코드를 작성해야 정상적으로 동작합니다. 어쨌거나 이런 건 중요한 게 아닙니다. 다음은 루프를 풀어내는 방법으로 최적화를 수행한 것입니다.
그림. 루프 풀기로 최적화한 코드
이렇게 루프를 풀었을 때, 최적화가 되었다고 합니다. 뭐가 최적화된거죠?
VAX 머신이 8비트 시스템이었고, 오늘날에는 x86 32비트 시스템을 사용하고 있고, 64비트 시스템의 사용도 늘어나고 있습니다. 그런데, 이런 루프 풀기는 여전히 유효합니다. 대부분의 컴파일러는 루프 풀기 최적화를 하지 않습니다.
데이터 읽기가 최적화되나요? 알다시피, 이건 데이터를 빠르게 복사하는 코드를 최적화한 겁니다. 데이터는 한 번 읽고 쓰면 끝납니다. 캐싱해도 얻을 게 없고, 코드를 저렇게 바꿔도 별로 이득될게 없어보입니다. 대체, 뭐가 이득인거죠?
데이터 읽기가 최적화된 것도 아닙니다. 근데, 재미있는 건 루프 풀기가 읽기 최적화 기법으로 소개된다는 겁니다!
그러면, 실행되는 코드(제어구조나 변수)가 계속 반복적으로 접근되니까 코드 캐시가 최적화되는 걸까요? 두 루프간에 사용된 변수 차이도 거의 없습니다. 접근 횟수만 비교한다면 차이도 없습니다. 모듈로 연산까지하는 두번째 코드가 더 나쁩니다. 근데, 왜 최적화가 되고, 수행속도가 50%나 개선되었다는 이야기를 하게 된 걸까요? 위키 백과 사전을 보면 캐시 히트율(Cache hit rate)이 개선되었다는 이야기를 합니다. 데이터 캐시가 개선된 것? 코드 캐시가 개선된 것? 뭐죠? 뭐가 최적화 된거죠?
루프 풀기에 의한 50% 성능 개선에 대한 이유로 설명하는 것이 대부분 루프 반복 횟수가 줄어들었기 때문이라고 설명합니다. 진짜 루프 반복 횟수가 줄어든 게 그만큼의 성능이득일까요? 루프 안에 더 많은 코드를 넣게 되면 더 많은 데이터 공간을 사용하게 됩니다. 이는 성능상의 이득으로 연결되는 경우보단 저하로 연결되는 경우가 더 많습니다. 데이터 캐시 히트를 고려한다면 루프 안에 접근되는 코드들의 데이터 크기가 32바이트 이내로 꽉 짜여져 있어야 한다는 조건까지 붙어버립니다. 위의 예제는 간단한 루프이니 32바이트 조건 이내에 포함되지만, 대부분의 루프는 32바이트 이상의 데이터를 사용합니다. 게다가, 루프를 풀었거나 풀지 않았거나 CPU가 실행해야 하는 명령어의 총량은 둘 다 차이가 없습니다. 일반적인 루프로 작성된 코드에서 루프를 100번 수행하고, 그 안에서 5개의 명령어를 실행한다면 총 500개의 명령어를 실행합니다.
이 루프를 20번으로 줄이고, 안에서 5 * 5 = 25개의 명령어를 실행한다고 합시다. 이 경우에도 500개의 명령어를 실행합니다. 아니, 실제로는 루프를 풀기위해 모듈로 연산(%)을 사용하고, 딱 나누어 떨어지지 않는 수에 대해서는 추가적인 코드까지 작성해야 하기 때문에 루프 풀기를 했을 때 실행해야 하는 명령어의 수는 더 증가합니다. 전혀 최적화되지 않아야 정상입니다.
혹자는 이런 얘기를 합니다. 루프 비교 횟수가 100번에서 20번으로 줄어들었다. 따라서, 80번의 비교를 하지 않아도 된다라고 말합니다. 그런데, 이렇게 얻은 이점 정도는 루프 풀기를 위해 추가로 작성한 코드를 계산한다면 그 이득은 상쇄됩니다. 얻는 게 없는 것이죠.
이게 왜 최적화를 하는지 이해하려면 파이프라인에 대해 알아야 합니다.
현대 프로세서들은 모두 명령어를 빠르게 처리하기 위해 파이프라인을 사용합니다. 컴퓨터가 명령어를 수행하는 단계는 메모리를 읽는 단계, 명령을 해석하는 단계, 수행하는 단계로 나뉘어져있습니다. 실제로 ADD라는 간단한 명령을 수행하는데도 두 단계의 전처리가 필요한 겁니다. CPU는 한 사이클이면 명령을 실행할 수 있습니다. 이 때는 두 사이클을 대기하게 됩니다. 이는 비효율적이죠?
그래서, 도입된 게 파이프라인입니다. 어려운 게 아닙니다. 공장을 보면 컨베이어 벨트를 따라서 제품이 이동하는 동안에 사람들이 자동차 바퀴를 끼우고, 다음 위치에서는 볼트를 조이는 것과 같습니다. 자동차 공장에서 차를 1분에 한 대씩 생산한다고 해서 정말 차가 만들어지는 데 필요한 시간이 1분이 아닌 것과 같습니다. 때문에, 자동차 공장에서 정전이나 파업 같은 문제로 공장 가동을 중단하게 되면 단순히 차를 생산하지 못하는 것이 아니라 전체 라인을 재정비해야 하는 추가적인 비용이 들어가게 됩니다. 네, 경영자 입장에서 보면 막대한 손실입니다.
루프 안의 코드를 실행하는 것은 컨베이어 벨트를 타면서 이동하는 것과 같습니다. 즉, 순차적으로 모든 명령이 빠르게 수행됩니다. 그런데, 루프를 만나서 분기하게 되면 지금까지 해오던 작업을 모두 끝내야 합니다. 컨베이어 벨트 위에 있던 물건들을 몽땅 지우고, 첫단계부터 새로 작업을 시작해야 합니다. 자동차 공장에서 차를 1분에 한 대씩 생산하는 것은 맞지만, 컨베이어 벨트의 처음부터 끝까지 이동하는데 걸리는 시간은 일주일, 아니면 한 달이 걸리는 겁니다. 이렇게 긴 컨베이어 벨트 위의 과정을 모두 정리한다고 생각해 보세요. 끔찍한 일입니다.
파이프라인을 이용하는 현대 CPU에서 분기문은 파이프라인을 모두 정리하는 작업을 합니다. 따라서, 분기문을 자주 만날수록 코드의 실행은 느려집니다.
첫번째 루프 코드를 생각해보세요. 이 코드는 컨베이어 벨트의 직선 주기가 너무 짧습니다. 루프 안의 코드가 지나치게 짧다는 겁니다. 컨베이어 벨트를 너무 자주 정리하는 겁니다.
두번째 루프를 생각해보세요. 컨베이어 벨트가 길어졌습니다. 그리고, 컨베이어 벨트를 정리하는 횟수는 1/8로 줄여버렸습니다. 네, 여기서 수행속도의 향상이 발생합니다. 루프 풀기 기법은 파이프라인의 정리 횟수를 줄여주고, 결국 코드에 대한 캐시 히트율을 향상시킵니다.
Duff"s Device가 그 유래이며, 현재는 Loop Unrolling, Loop Unwinding이라는 용어를 사용하고 있습니다. 현재는 Loop Unwinding이라는 용어가 널리 쓰이고 있고, 오래된 책들은 Loop Unrolling이라는 표현을 사용합니다. 한국어로 표현하자면 "루프 풀기" 정도가 적당한 것 같습니다. 네, 제가 만들어본 한글 표현입니다. 한국어로 설명하면 개념을 전달하는 데 효과가 좋기 때문에 한글 표현을 선호합니다. 믿거나 말거나, 한국어로 설명해주면 이해는 잘 했다면서 바로 영어로 쓰는 것을 보곤 합니다. 정말 끔찍한 영어 사대주의랄까요!!!
일반적인 루프는 다음과 같습니다.
for( int i = 0; i < 100; ++i )
{
x += arr[ i ];
}
루프 풀기를 적용한 코드는 다음과 같습니다.
for( int i = 0; i < 100 / 2; ++i )
{
x += arr[ i ];
x += arr[ i + 1 ];
}
루프 반복 횟수를 절반으로 줄이고, 루프 안의 코드를 2배로 늘렸습니다. 이를 1:2 루프 풀기라고 부릅니다. 처음 소개한 Duff"s Device는 1:8 루프 풀기인 셈입니다. 32비트 시스템들은 모두 4바이트 단위이므로 1:8 루프 풀기까지가 일반적으로 가장 성능이 좋다는 것을 알 수 있습니다.
첫번째 코드와 같은 루프를 1:1 루프라고 합니다. 이때의 수행속도를 100%로 생각한다면, 두번째 1:2 루프 풀기는 66%의 수행속도가 나옵니다. 즉, 34% 정도가 개선된 셈입니다. 이는 CPU 아키텍처마다 다릅니다. 특히, AMD CPU들은 1:2 루프 풀기에서 수행 속도 향상이 10% 미만일 정도로 형편없습니다. 이는 CPU 아키텍처의 차이입니다. 그러나, 인텔이든 AMD이든 1:8 루프 풀기의 경우 50% 정도의 수행 속도 향상을 관찰할 수 있습니다. 32비트 환경에서 1:16, 1:32, 1:64 루프 풀기까지도 구현할 수 있지만 성능 향상의 차이가 5% 미만으로 매우 작습니다. P4 전용으로 컴파일한다면 버스트 사이클이 128 바이트이므로 1:32 루프 해제까지가 가장 이상적인 결과가 예상됩니다. 물론, 이는 이론적인 것입니다.
루프 풀기를 할 때의 문제점은 반드시 배수로 떨어지지 않는 다는 것입니다. 100번의 루프를 수행하는데 1:8 루프 해제를 한다면 96회까지는 배수이며, 나머지 4회는 루프 바깥에서 수행해야 합니다. 루프 풀기는 항상 이렇게 수행됩니다.
루프 풀기는 메모리 읽기에 대해서만 성능이 좋습니다. 메모리 쓰기에 대해서는 성능 개선이 거의 없습니다. 따라서, 루프 풀기 최적화를 적용하고 싶다면 읽기에 대해서만 적용해야 하며, 쓰기에 대해서는 적용하지 않아야 합니다.
루프 풀기는 만능이 아닙니다. CPU 아키텍처에 따라 다르지만 x86에서는 한번에 32바이트를 읽어올 수 있습니다. 따라서, 루프 안의 데이터도 32바이트 한도내에 있을 때에만 최적의 효율을 낼 수 있습니다.(VIA KT-133 칩셋에서 처음 시도했던 메모리 미리 읽기(Read-Ahead)에 대해서는 고려하지 않습니다)
만약, 코드를 해당 아키텍처에 최적화되게 컴파일했다면 버스트 사이클(Burst Cycle)의 길이가 달라집니다. 최근의 CPU들은 살펴보지 않아서 알 수 없지만, 애슬론(Athlon)은 64바이트이고, 펜티엄4는 128바이트입니다. 코어2 듀오 같은 최신 CPU의 버스트 사이클을 알지는 못하지만, 최소 128 바이트 이상일 것입니다. 이 말의 의미는 한 번에 128바이트를 읽어올 수 있다는 것을 의미합니다.
루프 풀기를 최적화하기 위해서 어셈블리를 사용할 수도 있습니다. 그런데, 저는 어셈블리를 거의 사용하지 않는 탓에 대부분의 어셈블리 언어를 잊어버렸습니다. 그래서 어셈블리를 사용한 루프 풀기는 하지 않을 겁니다. 네, 루프 풀기를 쉽게 할 수 있는 꽁수는 있습니다. gcc 컴파일러에서 gcc -s file.c 명령을 사용하면 file.s 파일이 생성됩니다. 어셈블리어 버전이 자동으로 생성되는데, 이렇게 생성된 코드를 가져다가 사용하는 방법도 있습니다.
루프 풀기를 자동화할 수 있는 여러가지 방법이 있는데, 저는 다음과 같은 방법이 가장 마음에 듭니다.
#define LOOP_UNROLL (x+=arr[i++];)
for( int i = 0; i < BLOCK_SIZE; )
{
LOOP_UNROLL; LOOP_UNROLL; LOOP_UNROLL; LOOP_UNROLL;
LOOP_UNROLL; LOOP_UNROLL; LOOP_UNROLL; LOOP_UNROLL;
}
이 방법을 사용하면 원하는 횟수만큼 자유롭게 루프 풀기를 할 수 있습니다.
사실, 첫번째 이야기는 여기까지 끝이었는데, 다음은 다른 분들의 의견을 받아 읽을거리로 내용을 보강해봅니다.
VAX 머신과 파이프라인
VAX는 오래된 머신이고 사람들은 이 당시의 CPU에는 파이프라인이 적용되지 않았을 것이라고 얘기합니다. VAX 머신의 매뉴얼을 찾는데는 실패했으므로 파이프라인이 있다/없다라고 단정적으로 얘기하지 못해서 죄송합니다. 제 생각을 말하라면 VAX 머신에도 파이프라인이 적용되어 있었을 것이고, 아마도 당시에는 순차 파이프라인이 적용되어 있었기 때문에 루프문과 같은 분기문에 상당히 민감한 CPU였을 것이라 생각합니다.
파이프라인이 처음 적용된 것은 MOS-6502라는 프로세서로 1스텝 파이프라인이 적용되어 있었습니다. 이 8비트 프로세서는 1975년에 등장했습니다. VAX 머신은 그 보다 뒤인 1977년에 등장했고, Duff가 작업했던 당시는 1983년입니다. 최초로 등장했던 인텔의 8086 프로세서는 1976년도에 등장했습니다. 그러니까, MOS-7502 -> 8086 -> VAX의 순서로 등장했습니다. 8086은 16비트 프로세서였고, 6바이트의 프리페치 큐(prefetch queue)와 2 단계 파이프라인을 가졌습니다. 당시에 VAX는 서버용이었고, 파이프라인이 적용되었을거라 예상해봅니다. 오늘날에는 몇천원에 살 수 있는 8비트 AVR 프로세서도 5-6단계 파이프라인을 갖고 있습니다.(검색상에서는 VAX 파이프라인을 고려한 효율적인 프로그래밍에 대한 것은 찾았지만 정확히 몇 단계 파이프라인을 가졌는지는 찾지 못했습니다)
루프가 수행되는 횟수를 줄이는 것으로 성능 이득이 있었다고 알려진 것은 결국 잘못된 믿음이 되어 버린 것입니다. 정확하게는 루프 횟수의 감소가 분기의 감소를 의미하고, 분기의 감소는 파이프라인을 정리하는 횟수의 감소를 의미하기 때문에 성능이 증가하는 것입니다. 자동차 경주와 같습니다. 자동차는 직선 주로를 달릴 때는 빠르지만 코너를 돌 때는 속도를 늦춰야합니다. 자동차가 달려야 하는 총 거리는 500km인데 직선거리가 200km이고, 코너가 300km라면 경주시간은 길어지게 됩니다. 루프 풀기를 사용해서 직선거리를 400km로 늘려주고, 코너를 100km로 줄이면 경주시간은 짧아지게 됩니다. 결국, 어느쪽을 사용하든 달리는 거리는 같습니다. 프로그램에서야 루프 풀기를 하면 코드가 조금 더 복잡해지지만, 마지막에 소개한 매크로를 이용한 팁을 적용하면 루프 풀기를 할 때 부가적인 코드를 작성할 필요도 완전히 사라지게 됩니다. 네, 모듈로 연산을 완전히 제거할 수 있습니다.
참고. Duff"s Device가 처음 등장할 때는 루프(즉 분기문)의 횟수를 줄였더니 성능개선이 있었으니 루프를 줄이는 것이 목적이었습니다.
순차 파이프라인과 비순차 파이프라인
원문에서 설명한 파이프라인은 순차 파이프라인입니다. 순차 파이프라인에서는 분기문을 만나게 되면 반드시 파이프라인을 비우는 작업을 해야합니다. 현대 CPU는 비순차(Out-of-Order) 파이프라인을 사용합니다. 이런 파이프라인은 수십개 이상의 명령어를 미리 가져와서 병렬성을 찾아서 가능한 것들부터 미리 실행합니다. 즉, 코드에 있는 순서대로 실행되지 않습니다. OoO 머신에서는 분기 예측을 사용합니다. 코어2듀오와 같은 환경에서는 이러한 분기 예측이 보다 공격적으로 이뤄집니다. 커널 코드를 생성할 때 특정 코드로 이동할 때 왜 jmp 대신에 cmov를 사용하는가? 라는 질문이 올라온 적이 있습니다. 네, 조건을 판단해서 단순히 jmp 명령을 사용하는 것이 더 효율적인 것처럼 보입니다. cmov는 조건에 따라 이동하는 것이고, OoO 머신에서는 분기 예측까지 포함되기 때문에 더 느리게 동작할 것처럼 생각됩니다. 네, 상식적인 수준에서는 그렇습니다. 그러나, 실제로 분기 예측을 하는 CPU들은 매우 높은 분기 예측율을 달성하고 있고, 그런 머신에서는 jmp 문을 사용하는 것보다는 cmov를 사용하는 것이 분기 예측을 이용하기 때문에 더 높은 성능을 달성한다고 합니다.
따라서, 루프 풀기로 인해 성능이 극적으로 개선되는 것은 순차 파이프라인을 사용한 환경입니다. 아마도 8051, AVR 같은 임베디드 환경의 프로세서들이 그 대상이 되겠죠? 오늘날 PC에서 사용되는 대부분의 프로세서는 비순차 파이프라인입니다. 특히, 공격적인 분기 예측을 하는 것으로 잘 알려진 코어2듀오 같은 환경에서는 루프 풀기로 인한 성능 향상의 차이가 그렇게 크지는 않습니다. 코어2듀오 T7200 CPU에서 읽기에 대한 루프 풀기를 테스트하면 1:2 루프 풀기에서 20.3%의 성능 개선이 나타나고, 1:4 루프 풀기에서는 19.9%, 1:8 루프 풀기에서는 19.9%, 1:16 루프 풀기에서는 18.6%의 성능 개선이 나타납니다. 공격적인 분기 예측 때문에 루프 풀기를 하면 할수록 성능이 개선되기는커녕 떨어지는 것을 볼 수 있습니다. 코어2듀오 같은 환경이라면 1:2 루프 풀기가 가장 이상적이며 평균적으로 20%의 성능 향상을 얻는 것을 알 수 있습니다.
만약, 병목 현상이 있는 구간에 루프 풀기를 적용한다면 약 20%의 성능 개선을 얻을 수 있겠죠?
쓰기와 루프 풀기
쓰기의 경우에는 루프 풀기로 이득을 거의 볼 수 없습니다. P-III 800Mhz 환경에서 테스트하면 루프 풀기를 할 경우 2 ~ 10%의 성능 저하가 관찰됩니다. 코어2듀오 E7200 환경에서는 40 ~ 45%의 성능저하가 나타납니다. 따라서, 쓰기 성능에 대해서는 루프 풀기를 전혀 적용하지 않는 것이 좋습니다. 루프 풀기를 하는 경우 추가적인 코드 작성이 필요하고 이 부분이 성능 저하로 연결됩니다. 또한, 분기 예측 방법에 따라 성능 저하의 폭이 다르다는 것을 관찰할 수 있습니다. 만약, 다양한 환경을 갖추고 있다면 테스트 해볼 것을 권합니다.
쓰기에 대한 루프 풀기에 대한 예는 http://www.ddj.com/dept/cpp/184403799를 참고하기 바랍니다.
CPU 아키텍처에 따른 버스트 사이클
현대 PC에 사용되는 DRAM은 한 번 데이터를 읽을 때 정확히 해당 데이터만 읽어오지 않습니다. 정확히는 해당 데이터가 있는 열(Row) 전체를 읽어옵니다. x86 아키텍처에서 이 값은 오랫동안 32바이트입니다. 만약, AMD Athlon 전용으로 컴파일된 코드가 있다면 이 값은 64바이트입니다. 펜티엄4를 사용하고 있다면 이 값은 128바이트입니다. 다음과 같은 구조체가 있다고 생각해봅니다.
struct data_structure {
unsigned long data0;
unsigned long data1;
unsigned long data2;
unsigned long data3;
unsigned long data4;
unsigned long data5;
unsigned long data6;
unsigned long data7;
unsigned long data8;
unsigned long data9;
…
}"
이 구조체의 멤버 data0에 접근하게 되면, 실제로는 data0에 대한 값만 메모리에서 읽어온 것이 아닙니다. 캐시에는 data0 ~ data7까지 총 32바이트의 데이터가 함께 캐시로 이동됩니다. 따라서, 그 이후에 data1 ~ data7까지 순차적으로 접근한다고 할 경우 메모리에 접근할 필요가 없습니다. 캐시에 접근하면 되기 때문에 성능이 향상됩니다. 펜티엄4 전용으로 커널을 컴파일한다면 보다 많은 멤버들이 캐시에 옮겨질 수 있기 때문에 성능의 향상을 볼 수 있습니다.
분기 예측은 완벽한가?
분기 예측은 완벽하지 않습니다. 가장 극단적인 예로 리눅스 커널에서 대부분의 코드는 잘 수행될 것이고, 올바른 값을 갖고 있을 것이라 생각하지만 데이터가 정확하게 들어왔는지 확인하기 위한 검사를 수행합니다. 이런 종류의 검사를 결벽증 환자가 깨끗한 손을 또 씻고 씻는 것과 비슷해서 그런지 몰라도 sanity check(온전성 검사)라 부릅니다. 대부분의 경우에 이런 if 문 안에 있는 내용들은 실행되지 않습니다. 이런 경우에 CPU 자체에 분기 예측을 맡기기 보다는 사람이 직접 컴파일러 힌트를 적어주는 방법을 사용해서 보다 효율적인 기계어를 생성하게 해줍니다. 커널 코드에서 가장 흔하게 볼 수 있는 likely(), unlikely() 매크로가 그런 역할을 수행합니다.
논의에 참여하신 분들 덕분에 애초 A4 6장 분량이었는데 11장으로 늘어났습니다. 역시, 참여자가 있으면 내용이 보다 알차지는 것 같습니다. 알찬 글을 꾸미는 데는 mkseo, object, 이원구님이 있었습니다.
내용이 길어졌습니다. 서두에 제기했던 문제에 대해서는 아직 시작도 못했는데 이야기가 너무 길어졌습니다. 다음엔 서두에 제시한 코드가 왜 더 빠르게 수행되는지 본격적으로 살펴보겠습니다.
참고자료
TAG :
이전 글 : 리눅스 커널 프로그래밍(1) - 메모리 모델
다음 글 : 고급 자바 컨텐츠 저장소 API - 1
최신 콘텐츠