Bagaimana cara kerja perangkat Duff?

Saya telah membaca artikel di Wikipedia pada perangkat Duff , dan saya tidak mengerti. Saya benar-benar tertarik, tetapi saya sudah membaca penjelasan di sana beberapa kali dan saya masih belum mengerti bagaimana perangkat Duff bekerja.

Apa penjelasan yang lebih rinci?

Ada beberapa penjelasan yang baik di tempat lain, tetapi izinkan saya mencobanya. (Ini jauh lebih mudah di papan tulis!) Inilah contoh Wikipedia dengan beberapa notasi.

Katakanlah Anda menyalin 20 byte. Kontrol aliran program untuk operan pertama adalah:

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)
}

Sekarang, mulai pass kedua, kita jalankan hanya kode yang ditunjukkan:

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)
}

Sekarang, mulailah pass ketiga:

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 byte sekarang disalin.

Catatan: Perangkat Duff asli (ditampilkan di atas) disalin ke perangkat I / O di toalamat. Jadi, itu tidak perlu untuk menambah pointer *to. Saat menyalin antara dua buffer memori yang perlu Anda gunakan *to++.

The penjelasan Dr. Dobb Journal adalah yang terbaik yang saya temukan pada topik.

Ini adalah momen AHA saya:

for (i = 0; i < len; ++i) {
    HAL_IO_PORT = *pSource++;
}

menjadi:

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++;
}

menjadi:

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);
}

Ada dua hal utama pada perangkat Duff. Pertama, yang saya curigai adalah bagian yang lebih mudah dipahami, loopnya tidak terbuka. Ini memperdagangkan ukuran kode yang lebih besar untuk kecepatan lebih dengan menghindari beberapa overhead yang terlibat dalam memeriksa apakah loop selesai dan melompat kembali ke atas loop. CPU dapat berjalan lebih cepat saat menjalankan kode garis lurus, bukan melompat.

Aspek kedua adalah pernyataan switch. Ini memungkinkan kode untuk melompat ke tengah - tengah loop pertama kali. Bagian yang mengejutkan bagi kebanyakan orang adalah hal seperti itu diperbolehkan. Yah, itu diizinkan. Eksekusi dimulai pada label kasus yang dihitung, dan kemudian jatuh ke setiap pernyataan penugasan berurutan, sama seperti pernyataan peralihan lainnya. Setelah label kasus terakhir, eksekusi mencapai bagian bawah loop, di mana titik itu melompat kembali ke atas. Bagian atas loop berada di dalam pernyataan switch, sehingga switch tidak dievaluasi kembali.

Loop asli dibatalkan delapan kali, sehingga jumlah iterasi dibagi delapan. Jika jumlah byte yang akan disalin bukan kelipatan delapan, maka ada beberapa byte yang tersisa. Sebagian besar algoritma yang menyalin blok byte pada suatu waktu akan menangani byte sisanya di akhir, tetapi perangkat Duff menanganinya di awal. Fungsi menghitung count % 8untuk pernyataan beralih untuk mencari tahu apa yang akan tersisa, melompat ke label kasus untuk banyak byte, dan menyalinnya. Kemudian loop terus menyalin grup delapan byte.

Tujuan perangkat duffs adalah untuk mengurangi jumlah perbandingan yang dilakukan dalam implementasi memcpy yang ketat.

Misalkan Anda ingin menyalin 'menghitung' byte dari a ke b, pendekatan lurus ke depan adalah dengan melakukan hal berikut:

  do {                      
      *a = *b++;            
  } while (--count > 0);

Berapa kali Anda perlu membandingkan jumlah untuk melihat apakah itu di atas 0? 'hitung' kali.

Sekarang, perangkat duff menggunakan efek samping yang tidak disengaja dari case switch yang memungkinkan Anda untuk mengurangi jumlah perbandingan yang diperlukan untuk menghitung / 8.

Sekarang anggaplah Anda ingin menyalin 20 byte menggunakan perangkat duffs, berapa banyak perbandingan yang Anda butuhkan? Hanya 3, karena Anda menyalin delapan byte pada suatu waktu kecuali terakhir pertama di mana Anda menyalin hanya 4.

DIPERBARUI: Anda tidak perlu melakukan 8 perbandingan / pernyataan case-in-switch, tetapi masuk akal trade-off antara ukuran fungsi dan kecepatan.

Ketika saya membacanya untuk pertama kalinya, saya melakukan autoformatt pada hal ini

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);
    }
}

dan aku tidak tahu apa yang sedang terjadi.

Mungkin tidak ketika pertanyaan ini diajukan, tetapi sekarang Wikipedia memiliki penjelasan yang sangat bagus

Perangkat ini valid, legal C berdasarkan dua atribut dalam C:

• Spesifikasi santai dari pernyataan sakelar dalam definisi bahasa. Pada saat penemuan perangkat, ini adalah edisi pertama dari Bahasa Pemrograman C yang hanya mensyaratkan bahwa pernyataan yang dikendalikan dari sakelar menjadi pernyataan (gabungan) yang valid secara sintaksis di mana label kasus dapat tampak mendahului setiap sub-pernyataan. Sehubungan dengan fakta bahwa, dengan tidak adanya pernyataan istirahat, aliran kontrol akan jatuh dari pernyataan yang dikendalikan oleh satu label kasus ke yang dikontrol oleh yang berikutnya, ini berarti bahwa kode tersebut menentukan suksesi jumlah salinan dari alamat sumber berurutan ke port output yang dipetakan memori.
• Kemampuan untuk melompat secara legal ke tengah lingkaran dalam C.

1: Perangkat Duffs adalah suatu pengutamaan khusus dari loop terbuka. Apa itu loop membuka gulungan?
Jika Anda memiliki operasi untuk melakukan N kali dalam satu loop, Anda dapat memperdagangkan ukuran program untuk kecepatan dengan mengeksekusi loop N / n kali dan kemudian dalam loop inlining (membuka gulungan) kode loop n kali misalnya mengganti:

for (int i=0; i<N; i++) {
    // [The loop code...] 
}

dengan

for (int i=0; i<N/n; i++) {
    // [The loop code...]
    // [The loop code...]
    // [The loop code...]
    ...
    // [The loop code...] // n times!
}

Yang bekerja sangat baik jika N% n == 0 - tidak perlu untuk Duff! Jika itu tidak benar maka Anda harus menangani sisanya - yang merupakan rasa sakit.

2: Apa perbedaan perangkat Duffs dengan loop standar ini?
Perangkat Duffs hanyalah cara yang cerdas untuk berurusan dengan siklus loop sisa ketika N% n! = 0. Seluruh do / while mengeksekusi N / n berapa kali per loop standar membuka gulungan (karena case 0 berlaku). Pada run terakhir melalui loop ('N / n + 1' kali) case menendang dan kita melompat ke case N% n dan menjalankan kode loop 'sisa' beberapa kali.

Meskipun saya tidak 100% yakin dengan apa yang Anda minta, ini dia ...

Masalah yang dialamatkan oleh perangkat Duff adalah masalah pengulangan (karena Anda pasti akan melihat tautan Wiki yang Anda pasang). Apa yang pada dasarnya disamakan dengan ini adalah optimalisasi efisiensi run-time, lebih dari jejak memori. Perangkat Duff berhubungan dengan penyalinan serial, dan bukan sembarang masalah lama, tetapi merupakan contoh klasik tentang bagaimana optimasi dapat dilakukan dengan mengurangi berapa kali perbandingan harus dilakukan dalam satu lingkaran.

Sebagai contoh alternatif, yang mungkin membuatnya lebih mudah untuk dipahami, bayangkan Anda memiliki berbagai item yang ingin Anda lewati, dan tambahkan 1 setiap kali ... biasanya, Anda dapat menggunakan perulangan for, dan perulangan sekitar 100 kali . Ini tampaknya cukup logis dan, bagaimanapun ... optimisasi dapat dilakukan dengan melepaskan loop (jelas tidak terlalu jauh ... atau Anda mungkin juga tidak menggunakan loop).

Jadi biasa untuk loop:

for(int i = 0; i < 100; i++)
{
    myArray[i] += 1;
}

menjadi

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;
}

Apa yang dilakukan perangkat Duff adalah mengimplementasikan ide ini, dalam C, tetapi (seperti yang Anda lihat di Wiki) dengan salinan serial. Apa yang Anda lihat di atas, dengan contoh yang tidak dilonggarkan, adalah 10 perbandingan dibandingkan dengan 100 pada aslinya - ini berarti sedikit, tetapi mungkin signifikan, optimasi.

Berikut adalah penjelasan yang tidak terperinci yang menurut saya adalah inti dari perangkat Duff:

Masalahnya, C pada dasarnya adalah fasad yang bagus untuk bahasa rakitan (rakitan PDP-7 lebih spesifik; jika Anda mempelajari bahwa Anda akan melihat seberapa mencolok persamaannya). Dan, dalam bahasa assembly, Anda tidak benar-benar memiliki loop - Anda memiliki label dan instruksi cabang bersyarat. Jadi loop hanyalah sebagian dari keseluruhan urutan instruksi dengan label dan cabang di suatu tempat:

        instruction
label1: instruction
        instruction
        instruction
        instruction
        jump to label1  some condition

dan instruksi sakelar bercabang / melompat agak ke depan:

        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...

Dalam perakitan, mudah untuk menggabungkan dua struktur kontrol ini, dan ketika Anda memikirkannya, kombinasi mereka dalam C tampaknya tidak begitu aneh lagi.

Ini adalah jawaban yang saya poskan ke pertanyaan lain tentang Perangkat Duff yang mendapatkan beberapa upvaotes sebelum pertanyaan ditutup sebagai duplikat. Saya pikir ini memberikan sedikit konteks yang berharga di sini tentang mengapa Anda harus menghindari konstruksi ini.

"Ini adalah Perangkat Duff . Ini adalah metode membuka gulungan loop yang menghindari harus menambahkan loop fix-up sekunder untuk menangani saat-saat ketika jumlah putaran loop tidak diketahui sebagai kelipatan tepat dari faktor membuka gulungan.

Karena sebagian besar jawaban di sini tampaknya secara umum positif tentang hal itu, saya akan menyoroti kelemahannya.

Dengan kode ini kompiler akan berjuang untuk menerapkan optimasi apa pun ke loop body. Jika Anda hanya menulis kode sebagai loop sederhana kompiler modern harus dapat menangani membuka gulungan untuk Anda. Dengan cara ini Anda mempertahankan keterbacaan dan kinerja dan memiliki beberapa harapan optimasi lain yang diterapkan ke loop body.

Artikel Wikipedia yang dirujuk oleh orang lain bahkan mengatakan kapan 'pola' ini dihapus dari kinerja kode sumber Xfree86 yang benar-benar membaik.

Hasil ini adalah khas dari tangan membabi buta mengoptimalkan kode apa pun yang Anda pikir mungkin membutuhkannya. Ini mencegah kompiler melakukan tugasnya dengan benar, membuat kode Anda lebih mudah dibaca dan lebih rentan terhadap bug dan biasanya memperlambatnya. Jika Anda melakukan hal-hal dengan cara yang benar di tempat pertama, yaitu menulis kode sederhana, kemudian membuat profil untuk kemacetan, kemudian mengoptimalkan, Anda bahkan tidak akan pernah berpikir untuk menggunakan sesuatu seperti ini. Tidak dengan CPU dan kompiler modern pula.

Tidak apa-apa untuk memahaminya, tetapi saya akan terkejut jika Anda benar-benar menggunakannya. "

Hanya bereksperimen, menemukan varian lain yang akrab tanpa interleaving switch dan loop:

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;
}