나는 더프의 장치에서 Wikipedia 의 기사를 읽었으며 그것을 얻지 못했습니다. 정말 관심이 있지만 거기에 대한 설명을 몇 번 읽었지만 여전히 더프의 장치 작동 방식을 알 수 없습니다.
더 자세한 설명은 무엇입니까?
답변
다른 곳에서 좋은 설명이 있지만 시도해 보겠습니다. (이것은 화이트 보드에서 훨씬 쉽습니다!) 다음은 몇 가지 표기법이있는 Wikipedia 예입니다.
20 바이트를 복사한다고 가정 해 봅시다. 첫 번째 패스에 대한 프로그램의 흐름 제어는 다음과 같습니다.
int count; // Set to 20
{
int n = (count + 7) / 8; // n is now 3. (The "while" is going
// to be run three times.)
switch (count % 8) { // The remainder is 4 (20 modulo 8) so
// jump to the case 4
case 0: // [skipped]
do { // [skipped]
*to = *from++; // [skipped]
case 7: *to = *from++; // [skipped]
case 6: *to = *from++; // [skipped]
case 5: *to = *from++; // [skipped]
case 4: *to = *from++; // Start here. Copy 1 byte (total 1)
case 3: *to = *from++; // Copy 1 byte (total 2)
case 2: *to = *from++; // Copy 1 byte (total 3)
case 1: *to = *from++; // Copy 1 byte (total 4)
} while (--n > 0); // N = 3 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it is)
}이제 두 번째 패스를 시작하면 표시된 코드 만 실행합니다.
int count; //
{
int n = (count + 7) / 8; //
//
switch (count % 8) { //
//
case 0: //
do { // The while jumps to here.
*to = *from++; // Copy 1 byte (total 5)
case 7: *to = *from++; // Copy 1 byte (total 6)
case 6: *to = *from++; // Copy 1 byte (total 7)
case 5: *to = *from++; // Copy 1 byte (total 8)
case 4: *to = *from++; // Copy 1 byte (total 9)
case 3: *to = *from++; // Copy 1 byte (total 10)
case 2: *to = *from++; // Copy 1 byte (total 11)
case 1: *to = *from++; // Copy 1 byte (total 12)
} while (--n > 0); // N = 2 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it is)
}이제 세 번째 단계를 시작하십시오.
int count; //
{
int n = (count + 7) / 8; //
//
switch (count % 8) { //
//
case 0: //
do { // The while jumps to here.
*to = *from++; // Copy 1 byte (total 13)
case 7: *to = *from++; // Copy 1 byte (total 14)
case 6: *to = *from++; // Copy 1 byte (total 15)
case 5: *to = *from++; // Copy 1 byte (total 16)
case 4: *to = *from++; // Copy 1 byte (total 17)
case 3: *to = *from++; // Copy 1 byte (total 18)
case 2: *to = *from++; // Copy 1 byte (total 19)
case 1: *to = *from++; // Copy 1 byte (total 20)
} while (--n > 0); // N = 1 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it's not, so bail)
} // continue here...이제 20 바이트가 복사됩니다.
참고 : 원래의 더프 장치 (위 그림 참조)는 to주소 의 I / O 장치로 복사되었습니다 . 따라서 포인터를 증가시킬 필요가 없습니다 *to. 두 개의 메모리 버퍼 사이를 복사 할 때는을 사용해야 *to++합니다.
답변
Dr. Dobb ‘s Journal 의 설명은 이 주제에서 찾은 최고입니다.
이것은 나의 AHA 순간입니다.
for (i = 0; i < len; ++i) {
HAL_IO_PORT = *pSource++;
}된다 :
int n = len / 8;
for (i = 0; i < n; ++i) {
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
HAL_IO_PORT = *pSource++;
}
n = len % 8;
for (i = 0; i < n; ++i) {
HAL_IO_PORT = *pSource++;
}된다 :
int n = (len + 8 - 1) / 8;
switch (len % 8) {
case 0: do { HAL_IO_PORT = *pSource++;
case 7: HAL_IO_PORT = *pSource++;
case 6: HAL_IO_PORT = *pSource++;
case 5: HAL_IO_PORT = *pSource++;
case 4: HAL_IO_PORT = *pSource++;
case 3: HAL_IO_PORT = *pSource++;
case 2: HAL_IO_PORT = *pSource++;
case 1: HAL_IO_PORT = *pSource++;
} while (--n > 0);
}답변
더프의 장치에는 두 가지 중요한 사항이 있습니다. 첫째, 내가 이해하기 쉬운 부분이라고 생각되는 루프는 풀립니다. 이것은 루프의 완료 여부를 확인하고 루프의 맨 위로 점프하는 것과 관련된 오버 헤드를 피함으로써 더 큰 코드 크기를 더 빠른 속도로 교환합니다. CPU는 점프 대신 직선 코드를 실행할 때 더 빠르게 실행될 수 있습니다.
두 번째 측면은 switch 문입니다. 코드가 처음으로 루프의 중간 으로 이동합니다. 대부분의 사람들에게 놀라운 부분은 그러한 것이 허용된다는 것입니다. 글쎄요. 실행은 계산 된 사례 레이블에서 시작한 다음 다른 스위치 문과 마찬가지로 각 연속 할당 문으로 넘어갑니다 . 마지막 사례 레이블 이후에, 실행은 루프의 맨 아래에 도달하며,이 시점에서 다시 맨 위로 이동합니다. 루프의 상단은 switch 문 안에 있으므로 스위치는 더 이상 재평가되지 않습니다.
원래 루프는 8 번 풀리므로 반복 횟수는 8로 나뉩니다. 복사 할 바이트 수가 8의 배수가 아닌 경우 남은 바이트가 있습니다. 한 번에 바이트 블록을 복사하는 대부분의 알고리즘은 마지막에 나머지 바이트를 처리하지만 Duff의 장치는 처음에 처리합니다. 이 함수 count % 8는 switch 문을 계산 하여 나머지 내용을 파악하고 해당 바이트 수의 사례 레이블로 이동하여 복사합니다. 그런 다음 루프는 8 바이트 그룹을 계속 복사합니다.
답변
더프 장치의 요점은 엄격한 memcpy 구현에서 수행되는 비교 횟수를 줄이는 것입니다.
‘count’바이트를 a에서 b로 복사하려고한다고 가정하면 간단한 방법은 다음을 수행하는 것입니다.
do {
*a = *b++;
} while (--count > 0);카운트가 0보다 큰지 몇 번 비교해야합니까? ‘횟수’번.
이제 더프 장치는 의도하지 않은 스위치 케이스의 부작용을 사용하여 카운트 / 8에 필요한 비교 횟수를 줄일 수 있습니다.
이제 더프 장치를 사용하여 20 바이트를 복사한다고 가정하면 얼마나 많은 비교가 필요합니까? 4 개만 복사하는 마지막 첫 번째 바이트를 제외하고 한 번에 8 바이트를 복사하므로 3 개만 .
업데이트 : 8 개의 비교 / case-in-switch 문을 수행 할 필요는 없지만 기능 크기와 속도 사이의 균형은 합리적입니다.
답변
처음으로 읽을 때 자동 서식을 지정했습니다.
void dsend(char* to, char* from, count) {
int n = (count + 7) / 8;
switch (count % 8) {
case 0: do {
*to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
}무슨 일이 있었는지 전혀 몰랐습니다.
이 질문을 받았을 때가 아니라 지금 Wikipedia에 대한 설명이 아주 좋습니다.
이 장치는 C의 두 가지 속성으로 인해 유효하고 합법적입니다.
- 언어 정의에서 switch 문을 편안하게 지정합니다. 장치가 발명 될 당시 이것은 C 프로그래밍 언어의 첫 번째 판으로, 스위치의 제어 된 문장 만이 구문 상 유효한 (복합) 문장이어야하며,이 경우 레이블은 하위 문장 앞에 접두사로 나타날 수 있습니다. break 문이 없으면 제어 흐름이 하나의 케이스 레이블로 제어되는 명령문에서 다음 케이스로 제어되는 명령문으로 넘어 간다는 사실과 함께, 이는 코드가 다음에서 카운트 사본의 연속을 지정 함을 의미합니다. 메모리 소스 출력 포트에 순차적 인 소스 주소.
- C에서 루프 중간으로 합법적으로 점프하는 기능
답변
1 : 더프 장치는 루프 언 롤링의 특별한 의미입니다. 루프 언 롤링이란 무엇입니까?
루프에서 N 번 수행하는 작업이있는 경우 루프를 N / n 번 실행 한 다음 루프 코드에서 n 번 루프를 인라인 (언 롤링)하여 프로그램 크기를 속도로 교환 할 수 있습니다.
for (int i=0; i<N; i++) {
// [The loop code...]
}와
for (int i=0; i<N/n; i++) {
// [The loop code...]
// [The loop code...]
// [The loop code...]
...
// [The loop code...] // n times!
}N % n == 0 인 경우 더 잘 작동합니다-더프가 필요하지 않습니다! 그것이 사실이 아니라면 나머지를 처리해야합니다. 이것은 고통입니다.
2 : Duffs 장치는이 표준 루프 언 롤링과 어떻게 다릅니 까?
Duffs 장치는 N % n! = 0 일 때 나머지 루프 사이클을 처리하는 영리한 방법입니다. 전체 do / while은 표준 루프 언 롤링에 따라 N / n 횟수를 실행합니다 (0이 적용되므로). 루프를 통한 마지막 실행 ( ‘N / n + 1’시간)에서 케이스가 시작되고 N % n 케이스로 점프하여 루프 코드를 ‘remainder’횟수만큼 실행합니다.
답변
나는 당신이 요구하는 것을 100 % 확신하지 못하지만, 여기에갑니다 …
더프의 장치가 다루는 문제는 루프 풀기 중 하나입니다 (당신이 게시 한 위키 링크에서 의심 할 여지가 없습니다). 이것이 기본적으로 동일한 것은 메모리 풋 프린트에 대한 런타임 효율성의 최적화입니다. 더프의 장치는 오래된 문제가 아닌 직렬 복사를 다루지 만 루프에서 비교를 수행해야하는 횟수를 줄여 최적화를 수행하는 방법의 전형적인 예입니다.
이해하기 쉽도록 대체 예제로, 반복하려는 항목 배열이 있고 매번 1을 추가한다고 가정하십시오. 일반적으로 for 루프를 사용하고 약 100 번 반복 할 수 있습니다 . 이것은 상당히 논리적 인 것처럼 보이지만 …하지만 루프를 풀면 최적화 할 수 있습니다 (분명히 멀지 않습니다 … 또는 루프를 사용하지 않을 수도 있음).
따라서 규칙적인 for 루프는 다음과 같습니다.
for(int i = 0; i < 100; i++)
{
myArray[i] += 1;
}된다
for(int i = 0; i < 100; i+10)
{
myArray[i] += 1;
myArray[i+1] += 1;
myArray[i+2] += 1;
myArray[i+3] += 1;
myArray[i+4] += 1;
myArray[i+5] += 1;
myArray[i+6] += 1;
myArray[i+7] += 1;
myArray[i+8] += 1;
myArray[i+9] += 1;
}더프의 장치는 C 에서이 아이디어를 구현하지만 (위키에서 보았 듯이) 직렬 사본으로 구현합니다. 풀린 예제를 통해 위에서 본 것은 원본의 100과 비교 한 10 개의 비교입니다. 이는 사소하지만 중요한 최적화에 해당합니다.
