Duff's Device: sløjfe ruller for fortolket sprog - 💡 Fix My Ideas

Duff's Device: sløjfe ruller for fortolket sprog

Duff's Device: sløjfe ruller for fortolket sprog


Forfatter: Ethan Holmes, 2019

I 1983 opfandt Tom Duff en rigtig mærkelig måde at bruge C-sprogets omskifter og casestudier til in-code "unrolling" optimering af store sløjfer. Som et eksempel beskrev han en enkel loop, der kopierer en matrix til et outputregister:

send (til, fra, tælle) registrere kort * til, * fra; register tæller; {do * til = * fra ++; mens (- count> 0); }

Ved hver iteration af sløjfen, ud over den kopi, der udføres, reduceres tællervariablen, og en sammenligning foretages mod 0. Duffs Enhed giver dig mulighed for at opnå det samme resultat, men med kun en 8. overhead:

send (til, fra, tælle) registrere kort * til, * fra; register tæller; {register n = (count + 7) / 8; switch (tæller% 8) {case 0: gør {* til = * fra ++; sag 7: * til = * fra ++; tilfælde 6: * til = * fra ++; tilfælde 5: * til = * fra ++; tilfælde 4: * til = * fra ++; tilfælde 3: * til = * fra ++; tilfælde 2: * til = * fra ++; sag 1: * til = * fra ++; } While (- n> 0); }}

Hvad der sker er, at løkken rulles ud 8 gange, så hver iteration af løkken løber den interne kode 8 gange uden sammenligningen. Genius af Duff's Device er, at det udnytter den måde, C-switch / case-strukturen fungerer på. Første gang igennem, hvis iterationerne ikke deles jævnt med 8, udføres loopkoden nok gange til at svare til resten af ​​iterationer / 8.Det er lidt bizart, fordi "gør" erklæringen forekommer inden for switchen, men der er "tilfælde" udsagn inden for "do". Ikke desto mindre er det gyldigt C.

Før nogen græder fejl, skal du huske, at dette kun er virkelig egnet til at fremskynde ydelsen af ​​indre sløjfer, når der ikke findes nogen passende, bedre algoritme. Hvis du kodes C, er de fleste moderne kompilatorer kloge nok til automatisk at optimere din kode og rulle løkker for dig.

For fortolket sprog som PHP eller Javascript, skal du undertiden selv lave en lille optimering, hvis du vil presse lidt ekstra ydeevne ud. Heldigvis har begge sprog en c-style switch statement.

Andy King skrev om en lidt ændret version af denne loop unrolling-algoritme, som slår afbryder sætningen og bryder den normale Duff's Device i to separate sløjfer, en for resten og en til udrullingen. I Javascript udfører den en simpel additionssløjfe i kun en tredjedel af tiden for en normal for sløjfe (testVal ++ er normal sløjfeets indvendige):

funktion duffFasterLoop8 (iterationer) {var testVal = 0; var n = iterationer% 8; hvis (n> 0) {do {testVal ++; } mens (--n); // n skal være større end 0 her} n = parseInt (iterationer / 8); gør {testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; } mens (--n); }

Det er ikke så syntaktisk smart som Duff's Device, men det er en god måde at manuelt afrulle en indre sløjfe og få den bedste ydeevne for din ekstra indsats.

Duff's Device Andy King optimerer JavaScript til udførelseshastighed



Du Kan Være Interesseret

Top 10: Cykelreparation

Top 10: Cykelreparation


Hej farvel

Hej farvel


Har du foråret rengjort dine online profiler?

Har du foråret rengjort dine online profiler?


Boganmeldelse + Projektuddrag: World of Geekcraft, af Susan Beal

Boganmeldelse + Projektuddrag: World of Geekcraft, af Susan Beal






Seneste Indlæg