Il dispositivo Duff funziona in altre lingue?

Molti anni fa mentre si lavora su una grafica stretti I/problema O, Tom Duff srotolato un ciclo e ha creato il suo Duff's Device come segue: (. Nota questo utilizza i parametri di funzione vecchio stile - questo non è un errore)Il dispositivo Duff funziona in altre lingue?

dsend(to, from, count) 
char *to, *from; 
int 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); 
    } 
}

Questa codifica deriva direttamente dall'assembler e dalla codifica in C ed è dipendente dall'affermazione del case statement di C. Questo tipo di creatività nelle strutture di controllo interlacciare può funzionare in qualsiasi altro linguaggio?

fonte

2009-05-03 Shannon Nelson

cosa sono i "parametri di funzione vecchio stile"? –

Puoi farlo in qualsiasi linguaggio che supporti istruzioni GOTO computerizzata (Fortran, alcuni principi fondamentali, ecc)

fonte

2009-05-03 17:35:20 Dave

ma se non riesci a calcolare dinamicamente l'indirizzo che anche GOTO dovrebbe saltare, diventa così ingombrante che non ne vale davvero la pena. Quindi non penso che sarebbe una buona idea in linguaggi dinamici come PHP ... –

Funziona in C++.

Nota: il codice generato dipende dal compilatore. In particolare, quando ho compilato il dispositivo di Duff utilizzando le architetture ARM con targeting GCC, l'assembler ARM risultante era subottimale (credo che GCC l'abbia trasformato in una tabella di salto) a qualsiasi livello di ottimizzazione.

Ho finito per passare semplicemente la codifica dell'assemblatore.

fonte

2009-05-03 17:31:56 tpdi

Sì, era buono quando i compilatori non ottimizzavano molto (che è quando Duff l'ha inventato). Il problema è che ad ogni passo c'è sia il flusso drop-through che l'etichetta 'case', e ci vuole un ottimo compilatore per capire che non ha bisogno di svuotare i registri, ecc. E un compilatore così buono sarà probabilmente in grado comunque di srotolare il ciclo della realizzazione ingenua. Ancora, fa una buona domanda di intervista :) –

dispositivo di Duff è essenzialmente un calcolato goto che può essere fatto in molte altre lingue - assemblaggio (ovviamente) e FORTRAN è una coppia che li supporta direttamente.

fonte

2009-05-03 17:35:27

L'ho usato con successo in JavaScript per velocizzare l'elaborazione di array di grandi dimensioni. Vorrei poterlo usare in C#.

fonte

2009-05-03 17:35:36 Gary

Puoi. Non è necessario che il caso di cleanup sia uguale al loop. Fai il ciclo srotolato n/8 volte, quindi 7 passaggi condizionali alla fine. Dato che è per grandi matrici, ogni minima inefficienza negli ultimi 7 si perde nel rumore. –

Paul, se il caso di cleanup non è lo stesso del ciclo, allora non penso che possa essere giustamente chiamato dispositivo di Duff. Il dispositivo di Duff non riguarda solo lo srotolamento del loop. Si tratta di usare un'istruzione 'switch' per saltare nel mezzo di un loop srotolato. –

Anche se non può essere utilizzare in questo modo si può ancora avere due loop:

dsend(to, from, count) 
char *to, *from; 
int count; 
{ 
    int n; 
    for(n=0; n!=count/8; n+=8){ 
     *to = *from++; 
     *to = *from++; 
     *to = *from++; 
     *to = *from++; 
     *to = *from++; 
     *to = *from++; 
     *to = *from++; 
     *to = *from++; 
    } 
    for(; n!=count; n++) 
    { 
     *to = *from++; 
    } 
}

sicuro che questo sarà un po 'più lento con i più piccoli count ma è un po' più leggibile, un po 'più lingue in tutto portatili e produce molto Beneficio simile con grande count.

fonte

2017-01-05 19:34:26

Il dispositivo Duff funziona in altre lingue?

risposta

Problemi correlati