Η συσκευή του Duff: ξετυλίξτε το βρόχο για τις ερμηνευμένες γλώσσες - 💡 Fix My Ideas

Η συσκευή του Duff: ξετυλίξτε το βρόχο για τις ερμηνευμένες γλώσσες

Η συσκευή του Duff: ξετυλίξτε το βρόχο για τις ερμηνευμένες γλώσσες


Συγγραφέας: Ethan Holmes, 2019

Το 1983, ο Tom Duff εφευρέθηκε έναν πραγματικά παράξενο τρόπο να χρησιμοποιήσει τις μεταβολές της γλώσσας C και τις δηλώσεις περίπτωσης για τον κώδικα "unrolling" βελτιστοποίηση μεγάλων βρόχων. Για παράδειγμα, περιέγραψε έναν απλό βρόχο που αντιγράφει έναν πίνακα σε ένα μητρώο εξόδου:

αποστολή (προς, από, καταμέτρηση) εγγραφή σύντομη * σε, * από; καταμέτρηση μητρώου · {do * to = * από ++. ενώ (- count> 0). }}

Σε κάθε επανάληψη του βρόχου, εκτός από το αντίγραφο που εκτελείται, η μεταβλητή μέτρησης μειώνεται και μια σύγκριση γίνεται έναντι 0. Η συσκευή του Duff σας επιτρέπει να επιτύχετε το ίδιο αποτέλεσμα, αλλά μόνο με ένα 8ο από τα γενικά έξοδα:

αποστολή (προς, από, καταμέτρηση) εγγραφή σύντομη * σε, * από; καταμέτρηση μητρώου · {μητρώο n = (αριθμός + 7) / 8; διακόπτης (count% 8) {case 0: do {* to = * από ++; περίπτωση 7: * σε = * από ++; περίπτωση 6: * έως = * από ++. περίπτωση 5: * έως = * από ++. περίπτωση 4: * έως = * από ++. περίπτωση 3: * έως = * από ++; περίπτωση 2: * σε = * από ++; περίπτωση 1: * σε = * από ++; } ενώ (- n> 0). }}

Αυτό που συμβαίνει είναι ότι ο βρόχος ξετυλίγεται 8 φορές, οπότε κάθε επανάληψη του βρόχου τρέχει τον εσωτερικό κωδικό 8 φορές χωρίς τη σύγκριση. Η ιδιοφυΐα της συσκευής του Duff είναι ότι εκμεταλλεύεται τον τρόπο λειτουργίας του διακόπτη C / δομής περιβλήματος. Την πρώτη φορά, αν οι επαναλήψεις δεν διαιρούνται ομοιόμορφα κατά 8, ο κώδικας βρόχου εκτελείται αρκετές φορές για να ισούται με το υπόλοιπο των επαναλήψεων / 8.Είναι λίγο περίεργο, επειδή η εντολή "do" εμφανίζεται μέσα στο διακόπτη, αλλά υπάρχουν δηλώσεις "case" μέσα στο "do". Παρ 'όλα αυτά, είναι έγκυρο C.

Πριν κάποιος φωνάξει φάουλ, θυμηθείτε ότι αυτό είναι μόνο κατάλληλο για την επιτάχυνση της απόδοσης των εσωτερικών βρόχων όταν δεν υπάρχει κατάλληλος, καλύτερος αλγόριθμος. Αν κωδικοποιείτε το C, οι περισσότεροι σύγχρονοι μεταγλωττιστές είναι αρκετά έξυπνοι ώστε να βελτιστοποιούν αυτόματα τον κώδικα σας και να ξετυλίξουν τους βρόχους για σας.

Για ερμηνευμένες γλώσσες, όπως PHP ή Javascript, ωστόσο, κάποιες φορές χρειάζεται να κάνετε λίγη βελτιστοποίηση μόνοι σας εάν θέλετε να αποφύγετε κάποια επιπλέον απόδοση. Ευτυχώς, και οι δύο γλώσσες έχουν δήλωση διακόπτη τύπου c.

Ο Andy King έγραψε μια ελαφρώς αλλοιωμένη έκδοση αυτού του αλγορίθμου ξετυλίγματος βρόχου, ο οποίος σπάζει τη δήλωση του διακόπτη και σπάζει την κανονική συσκευή του Duff σε δύο ξεχωριστούς βρόχους, έναν για το υπόλοιπο και έναν για την ξετυλίξη. Στη Javascript, εκτελεί έναν απλό βρόχο προσθήκης σε μόνο το ένα τρίτο του χρόνου ενός κανονικού βρόχου (το testVal ++ είναι το εσωτερικό του κανονικού βρόχου):

λειτουργία duffFasterLoop8 (επαναλήψεις) {var testVal = 0; var n = επαναλήψεις% 8; αν (n> 0) {do {testVal ++; } ενώ (- n)? // n πρέπει να είναι μεγαλύτερο από 0 εδώ} n = parseInt (επαναλήψεις / 8); κάντε {testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; testVal ++; } ενώ (- n)? }}

Δεν είναι τόσο συντακτικό έξυπνο όσο η συσκευή του Duff, αλλά είναι ένας καλός τρόπος για να ξετυλίξετε με το χέρι έναν εσωτερικό βρόχο και να πάρετε την καλύτερη απόδοση για την πρόσθετη προσπάθειά σας.

Η συσκευή του Duff Andy King βελτιστοποιεί το JavaScript για την ταχύτητα εκτέλεσης



Μπορεί Να Σας Ενδιαφέρει

Η προσωποποίηση της κίνησης του δημιουργού: Brook Drumm

Η προσωποποίηση της κίνησης του δημιουργού: Brook Drumm


Το Πνεύμα του Maker που Haunts Halloween

Το Πνεύμα του Maker που Haunts Halloween


Φασματικές σταθερές στην Actioncript 2.0

Φασματικές σταθερές στην Actioncript 2.0


Αγοράστε ηλεκτρονικά κιτ, Βοήθεια HackerMoms

Αγοράστε ηλεκτρονικά κιτ, Βοήθεια HackerMoms