Duff's device

Duff's device Q. template <typename T> void fill_array(T* begin, T* end, const T& data) { while (begin != end) { *begin = data; ++begin; } } 위의 코드와 같은 단순 루프를 더욱 최적화하려면 어떻게 해야 할까요? switch와 case문의 동작 원리에 대한 이해가 필요합니다. A. 먼저 문제의 코드를 검토해보도록 하겠습니다. template <typename T> void fill_array(T* begin, T* end, const T& data) { while (begin != end) { *begin = data; ++begin; } } 위의 코드를 최적화하기 위해 가장 먼저 떠오르는 방법은 mem-계열의 함수들입니다. 만약 T가 char형이라면 memset을, T가 char를 제외한 다른 built-in 타입이라면 memcpy를 적당한 방법으로 사용하면 될 듯 합니다. 하지만 문제는 위의 코드의 T는 사용자가 정의한 class타입이 될수도 있다는 사실입니다. 따라서 다른 방법을 검토해봐야 합니다. 코드는 세줄로 이루어져 있습니다. 그리고 그 중 밑의 두줄은 더 이상 어떻게 최적화할 수 있는 방법이 없어 보입니다. 따라서 "while (begin != end)" 부분을 최적화해야만 합니다. 즉 하나의 데이터를 대입하기 위해 한번의 비교를 하는것보다 한번의 비교에 여러개의 데이터를 대입하면 성능이 더욱 향상된다는 사실을 이용하는 것입니다. 먼저 비교 한번에 8개 정도의 데이터를 대입할 수 있는 코드를 작성해보면 아래와 같이 됩니다. int m = (end - begin) & 7; while (m--) { *begin = data; ++begin; } while (begin != end) { *begin = data; ++begin; *begin = data; ++begin; *begin = data; ++begin; *begin = data; ++begin; *begin = data; ++begin; *begin = data; ++begin; *begin = data; ++begin; *begin = data; ++begin; } 거의 다 해결된 것 같은데 남은 문제는 8의 나머지 수만큼은 역시 하나의 데이터 대입당 한번씩의 비교가 필요하게 됩니다. (코드의 윗부분입니다. 물론 end - begin이 매우 클 경우 무시될 수 있겠지만 이런 것을 그냥 보고만 있을 프로그래머들이 아니겠지요? ^_^) 그래서 나온 해결책이 switch, case문을 사용하는 Duff's device라는 것입니다. 예상하실 수 있듯이 Duff라는 사람이 만들었다고 합니다. (기본 duff's device는 http://www.lysator.liu.se/c/duffs-device.html에서 보실 수 있습니다.) Duff's device를 사용한 해결책은 아래와 같습니다. template <typename T> void fill_array(T* begin, T* end, const T& data) { switch ((end - begin) & 7) { case 0: while (begin != end) { *begin = data; ++begin; case 7: *begin = data; ++begin; case 6: *begin = data; ++begin; case 5: *begin = data; ++begin; case 4: *begin = data; ++begin; case 3: *begin = data; ++begin; case 2: *begin = data; ++begin; case 1: *begin = data; ++begin; } } } 합법적이며 portable한 C++/C코드입니다. 성능이 중요한 루틴에서 실제로 사용되고 있다고 합니다. 참고로 위와 같은 문법이 가능해지는 이유는 switch문에서의 case문은 goto문의 label과 같은 방법으로 사용되기 때문입니다. 예를 들면 아래와 같은 코드는 "default" 대신 "3"을 출력하게 됩니다. int c = 3; switch (c) { case 1: cout << "case 1\n"; { case 2: cout << "case 2\n"; { case 3: cout << "case 3\n"; break; } break; } break; default: cout << "default\n"; break; } Duff's device에 대한 실험 결과가 있어서 같이 올립니다. (아래 결과는 제가 직접 실험한 것이 아닙니다.) 사용한 방법은 COUNT 변수만큼의 double 배열을 REPEAT 변수만큼 반복하기를 반복 실험했다고 합니다. 실험 플랫폼은 P-III/750Mhz와 MSVC, MWCW, GNU g++ 2.95.2 컴파일러라고 합니다. (MWCW는 Metroworks CodeWarrior 6.9를 나타냅니다.) 먼저 Fill 알고리즘의 경우, 즉 배열을 어떤 값으로 채우는 경우. COUNT >= 100,000일 경우에는 일반 for-loop와 Duff's Device의 결과는 실용적으로 봤을때 거의 같다.   COUNT == 1,000일 경우에는 Duff's Device가 20% 향상이 있었다.   COUNT == 100일 경우 Duff's Device가 12%의 향상이 있었다.   (물론 위의 값들은 정확하지 않을 수 있으며 MSVC에서의 Duff's device에 관한 내용만 정리해본 것입니다.) COUNT 값이 매우 클 경우 왜 알고리즘에 따른 차이가 없는지는 다음 원인 때문이라고 추정하고 있습니다. 현재 CPU들은 대부분 L1, L2 cache들을 가지고 있다. 이러한 cache들은 main memory보다 수배에서 수십배 더 빠르게 동작한다. 여기서 data access시의 locality는 cache management에 매우 큰 영향을 미치게 된다. 하지만 위의 1번의 경우처럼 데이터의 양이 많은 경우는 cache hit 실패율이 매우 높아지기 때문에 루프의 성능은 알고리즘보다는 main memory의 bandwidth값에 수렴하게 된다. 즉 모두 비슷한 결과를 보이게 된다. 하지만 2, 3번과 같은 경우에는 성능에 알고리즘이 영향을 미치는 비율이 높아지며 따라서 알고리즘에 따라 조금씩 다른 결과를 보이게 된다. 위의 Fill 알고리즘외에 배열끼리의 Copy 알고리즘에 대해서도 쓰여 있는데 Duff's device가 역시 일반 루프보다는 나은 성능을 보여주고 있습니다. 얘기의 마무리를 하자면 Duff's device는 일반 루프보다 (거의 항상) 나은 성능을 나타내며 모든 타입에 대해서 사용 가능하고 100% portable한 코드가 됩니다. 참고로 이 실험과 관련된 원본 문서는 http://www.cuj.com/experts/1910/alexandr.htm에 있습니다.

---

2002.3.1.	잘못된 부분에 대해서는 저에게 메일 부탁드립니다.

---

출처