C의 루프 최적화 기법인 Duff's device와 관련되지만 독립적으로 고안된 Pigeon's device를 소개하고, 원래 구현과 함께 그 동작 방식을 설명합니다.
많은 사람들은 C에서 꽤 멋진 루프 최적화 기법인 Duff's device에 대해 들어봤을지도 모릅니다.
이 페이지는 Pigeon's device에 대한 세부 사항을 제공합니다. 이것은 관련은 있지만 독립적으로 고안된 기법입니다. Pigeon's device의 원래 구현은 인터넷이 있기 전 MS-DOS용으로 작성된 C 코드의 한 부분에 들어 있었기 때문에, 저는 Duff's device에 대해 들어본 적이 없었습니다. 나중에 그것을 알게 되었을 때 두 기법 사이의 유사성이 즉시 분명하게 보였습니다.
원래의 Pigeon's device는 원하는 정렬 순서에 따라 두 날짜/시간 레코드를 여러 방식으로 비교하는 함수 안에 있었습니다. FORWARD는 정방향 시간순, REVERSE는 역방향 시간순, REVDFWDT는 날짜는 역순이지만 각 날짜 안의 시간은 정방향으로 정렬하는 방식입니다. 원래 프로그램에만 있는 여러 typedef와 그런 잡다한 것들 때문에 원래 형태는 읽기에 꽤 난잡하지만, 기본 구조는 아주 단순합니다. 여기서는 함수로 표현해 보겠습니다.
int pigeons_device(int a, int b, int mode) { int result; /* Isn't C a wonderful language? */ switch (mode) { case 0: if (gloop(a, b)) { case 1: result = arfle(a, b); break; } else { case 2: result = barfle(a, b); break; } } return (result); }
다시 말해... mode == 1 이면 a와 b의 어떤 함수값을 반환합니다. mode == 2 이면 a와 b의 다른 함수값을 반환합니다. 하지만 mode == 0 이면 a와 b 사이의 어떤 다른 관계에 따라 어떤 함수값을 반환할지 결정합니다.
가능한 제어 흐름을 예쁜 색 화살표로 표시한 그림은 다음과 같습니다.
왜 누군가는 그렇게 하고 싶어 할까요? 간단한 대답은 "왜냐하면 사람은 비둘기이기 때문입니다"입니다. 더 복잡한 대답은... 음, 여기 원래 구현이 있으니 직접 보고 판단하실 수 있습니다.
int lfdcmp(const void *a, const void b) { static int mode; struct date d1, d2; struct time t; if (b==NULL) return(mode); if (a==NULL) { mode=(int )b; return(0); } / Isn't C a wonderful language? */ switch (mode) { case REVDFWDT: unixtodos(((lfdy *)a)->stamplog, &d1, &t); unixtodos(((lfdy *)b)->stamplog, &d2, &t); if ((d1.da_day==d2.da_day) && (d1.da_mon==d2.da_mon) \ && (d1.da_year==d2.da_year)) { case FORWARD : return(longsub(((lfdy *)a)->stamplog,((lfdy *)b)->stamplog)); break; } else { case REVERSE : return(longsub(((lfdy *)b)->stamplog,((lfdy *)a)->stamplog)); break; } default : pigeonerror(FATAL,"Bad lfdcmp mode: %d\n\r",mode); break; } return(0); }
이 함수는 비교 모드를 설정하고 읽어 오는 끔찍한 해킹으로 시작합니다. 이렇게 한 이유는 이 함수가 라이브러리 정렬 루틴에서 호출되는데, 그 루틴이 세 번째 "mode" 매개변수를 전달하도록 할 방법이 없었기 때문입니다. 모드를 함수 안으로 전달하는 다른 방법들도 여럿 있지만, 어차피 직접 모드를 설정하지 말고 대신 setsortmode()와 getsortmode() 함수를 사용해야 한다는 점을 명시하려는 의도도 있었기 때문에, 저는 그 함수들 내부의 숨겨진 동작이 이런 방식으로 하도록 만들었습니다. 그 편이 더 재미있었기 때문입니다.
그다음에 비로소 Pigeon's Device 자체로 넘어갑니다. FORWARD 정렬의 경우 이 함수는 두 날짜 레코드의 정방향 순서에 따라 부호가 달라지는 값을 그대로 반환합니다. longsub()는 long 형의 한 값을 다른 값에서 빼고, 그 결과를 int 형 값으로 반환하는 함수인데, 오버플로를 일으키는 대신 int 에 허용된 최대값과 최소값으로 제한합니다. 그런 값이면 추가 처리 없이도 라이브러리 정렬 함수의 요구를 만족합니다. REVERSE 정렬의 경우 두 레코드는 단순히 반대 방향으로 비교됩니다.
REVDFWDT 정렬, 즉 Reverse Date Forward Time의 경우 첫 번째 작업은 레코드에서 날짜 정보를 추출하는 것입니다. 레코드는 자정을 분명하게 드러내지 않는 UNIX 타임스탬프 형식으로 되어 있습니다. 그래서 날짜를 날짜와 시간이 분리된 DOS 형식으로 변환합니다. 그러고 나면 switch 문과 뒤얽힌 if 문에 도달합니다. 두 레코드가 같은 날짜에 해당하면 정방향으로 비교하고, 서로 다른 날짜에 해당하면 역방향으로 비교합니다. 그 결과 전체 목록은 날짜는 거꾸로 정렬되지만 각 날짜 안의 시간은 여전히 정방향으로 정렬됩니다.
default case는 "버그 포착기"입니다. 이 함수가 의도한 대로 setsortmode()를 호출해 모드를 설정한 상태로 사용된다면, 잘못된 값은 애초에 거기에 들어갈 수 없어야 합니다.
이상이 맥락 속에서 본 Pigeon's device입니다.
비둘기에게 친절하게 대해 주세요
