ダフのデバイスでウィキペディアの記事を読みましたが、よくわかりません。とても興味がありますが、説明を何度か読みましたが、ダフのデバイスがどのように機能するのかまだわかりません。
より詳細な説明は何でしょうか？
36444 次
11 に答える
258
他にも良い説明がいくつかありますが、試してみましょう。（これはホワイトボードでははるかに簡単です！）これは、いくつかの表記法を使用した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)
}
次に、2番目のパスを開始し、指定されたコードだけを実行します。
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)
}
次に、3番目のパスを開始します。
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注：元のDuff's Device（上に表示）は、アドレスのI/Oデバイスにコピーされました。したがって、ポインタをインクリメントする必要はありませんでした*to。2つのメモリバッファ間でコピーする場合は、を使用する必要があります*to++。
于 2009-02-05T02:25:55.370 に答える
115
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);
}
于 2009-02-05T01:15:30.537 に答える
84
ダフのデバイスには 2 つの重要な要素があります。まず、これは理解しやすい部分だと思いますが、ループが展開されます。これは、ループが終了したかどうかを確認してループの先頭に戻ることに伴うオーバーヘッドの一部を回避することで、より大きなコード サイズと引き換えに速度を向上させます。CPU は、ジャンプする代わりに直線的なコードを実行すると、より高速に実行できます。
2 つ目の側面は、switch ステートメントです。これにより、コードが最初にループの途中にジャンプできるようになります。ほとんどの人にとって驚くべき部分は、そのようなことが許されているということです。まあ、それは許可されています。実行は、計算された case ラベルから開始され、他の switch ステートメントと同様に、連続する各代入ステートメントにフォールスルーします。最後の case ラベルの後、実行はループの最後に到達し、その時点で最初にジャンプして戻ります。ループの先頭はswitch ステートメント内にあるため、switch は再評価されません。
元のループは 8 回巻き戻されるため、反復回数は 8 で割られます。コピーするバイト数が 8 の倍数でない場合、いくつかのバイトが残っています。一度にバイトのブロックをコピーするほとんどのアルゴリズムは、残りのバイトを最後に処理しますが、Duff のデバイスはそれらを最初に処理します。この関数count % 8は、switch ステートメントを計算して余りがどうなるかを計算し、そのバイト数だけ case ラベルにジャンプしてコピーします。その後、ループは 8 バイトのグループをコピーし続けます。
于 2009-02-05T01:54:18.553 に答える
14
duffs デバイスのポイントは、タイトな memcpy 実装で行われる比較の数を減らすことです。
'count' バイトを a から b にコピーしたい場合、単純な方法は次のようにすることです。
do {
*a = *b++;
} while (--count > 0);
count が 0 より大きいかどうかを確認するには、count を何回比較する必要がありますか? 「カウント」回。
現在、duff デバイスは、count / 8 に必要な比較の数を減らすことができる switch ケースの厄介な意図しない副作用を使用しています。
duffs デバイスを使用して 20 バイトをコピーするとします。比較はいくつ必要ですか? 4 だけをコピーする最後の最初のバイトを除いて、一度に 8 バイトをコピーするため、3 だけです。
更新: 8 つの比較/case-in-switch ステートメントを実行する必要はありませんが、関数のサイズと速度のトレードオフとして妥当です。
于 2009-02-05T01:17:26.163 に答える
8
初めて読んだとき、これに自動フォーマットしました
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);
}
}
何が起こっているのかわかりませんでした。
この質問がされたときではないかもしれませんが、ウィキペディアには非常に良い説明があります
デバイスは、C の 2 つの属性によって有効で合法的な C です。
- 言語の定義における switch ステートメントの仕様の緩和。デバイスが発明された時点では、これは C プログラミング言語の初版であり、スイッチの被制御ステートメントが構文的に有効な (複合) ステートメントであることのみを要求し、サブステートメントの前に case ラベルを付けることができます。break ステートメントがない場合、制御の流れは、ある case ラベルによって制御されるステートメントから次のラベルによって制御されるステートメントにフォールスルーするという事実に関連して、これは、コードが一連のコピー数を指定することを意味します。シーケンシャル ソース アドレスをメモリ マップド出力ポートに送信します。
- C のループの途中に合法的にジャンプする機能。
于 2010-08-28T12:09:49.097 に答える
6
1: Duffs デバイスは、ループ展開の特定の実装です。ループ展開は、ループ内で 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 の場合、これはうまく機能します - Duff は必要ありません! そうでない場合は、残りを処理する必要があります。これは苦痛です。
2: Duffs デバイスは、この標準的なループ展開とどう違うのですか?
Duffs デバイスは、N % n != 0 の場合の残りのループ サイクルを処理する賢い方法です。do / while 全体は、標準のループ展開に従って N / n 回実行されます (ケース 0 が適用されるため)。ループの最後の最初の実行でケースが開始され、ループ コードを「残り」の回数実行します。残りのループは「通常どおり」実行されます。
于 2013-06-20T08:11:25.893 に答える
3
私はあなたが何を求めているのか100％確信が持てませんが、ここに行きます...
Duff のデバイス アドレスの問題は、ループの巻き戻しの 1 つです (投稿した Wiki リンクで見たことがあるはずです)。これが基本的に意味することは、メモリ フットプリントに対するランタイム効率の最適化です。Duff のデバイスは、単なる古い問題ではなくシリアル コピーを処理しますが、ループ内で比較を行う必要がある回数を減らすことで最適化を行う方法の典型的な例です。
理解しやすくなる別の例として、ループしたい項目の配列があり、そのたびに 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;
}
Duff のデバイスが行うことは、このアイデアを C で実装することですが、(Wiki で見たように) シリアル コピーを使用します。上記のアンワインドの例では、元の 100 回と比較して 10 回の比較が行われています。
于 2009-02-05T01:19:40.777 に答える
2
これは、ダフのデバイスの核心であると私が感じている詳細ではない説明です。
問題は、C は基本的にアセンブリ言語の優れたファサードであるということです (具体的には PDP-7 アセンブリです。それを調べれば、その類似点がどれほど驚くべきものであるかがわかります)。そして、アセンブリ言語では、実際にはループはありません。ラベルと条件分岐命令があります。したがって、ループは、ラベルとどこかに分岐がある命令の全体的なシーケンスの一部にすぎません。
instruction
label1: instruction
instruction
instruction
instruction
jump to label1 some condition
そして、switch 命令が分岐/ジャンプします。
evaluate expression into register r
compare r with first case value
branch to first case label if equal
compare r with second case value
branch to second case label if equal
etc....
first_case_label:
instruction
instruction
second_case_label:
instruction
instruction
etc...
アセンブリでは、これら 2 つの制御構造を組み合わせる方法は容易に想像できます。そのように考えると、C でのそれらの組み合わせはそれほど奇妙に思えなくなります。
于 2016-03-11T22:40:28.960 に答える
0
実験してみると、switchステートメントとループをインターリーブせずにうまくいく別doのバリアントが見つかりました。while
int n = (count + 1) / 8;
switch (count % 8)
{
LOOP:
case 0:
if(n-- == 0)
break;
putchar('.');
case 7:
putchar('.');
case 6:
putchar('.');
case 5:
putchar('.');
case 4:
putchar('.');
case 3:
putchar('.');
case 2:
putchar('.');
case 1:
putchar('.');
default:
goto LOOP;
}
技術的には、 はgotoまだループを実装していますが、このバリアントの方が少し読みやすいかもしれません。
于 2016-07-20T13:24:27.680 に答える