ipli-fast

Το project αυτό είναι ένας optimized interpreter για τη γλώσσα IPL που ήταν το αντικείμενο της εξαιρετικής Εργασίας 4 του μαθήματος Κ04 Εισαγωγή στον Προγραμματισμό (2020-21). Λύνοντας την εργασία στο φροντιστήριο του Κ08 είδαμε ότι ο reference compiler (ipl) είναι υπερβολικά πιο γρήγορος από τον interpreter που φτιάξαμε (ίσως περισσότερο απ' ότι θα περίμενε κανείς). Οπότε μου φάνηκε ενδιαφέρον σαν weekend hacking project να εξετάσω πόσο μπορεί ένας "καθαρός" interpreter να προσεγγίσει την απόδοση του compiler.

Ο περιορισμός είναι απλός: απαγορεύεται η παραγωγή κώδικα μηχανής σε οποιοδήποτε στάδιο (πχ τεχνικές just-in-time compilation απορρίπτονται). Πρέπει η εκτέλεση να γίνεται 100% από κώδικα του ίδιου του interpreter. Το πλεονέκτημα ενός τέτοιου διερμηνέα είναι ότι είναι πραγματικά platform independent, μπορεί να τρέξει σε οποιοδήποτε μηχάνημα αρκεί να έχουμε έναν C compiler. Ενώ ένα μεταγλωττιστής περιορίζεται μόνο στην αρχιτεκτονική για την οποία παράγει κώδικα.

To project δεν απευθύνεται σε φοιτητές που θέλουν να μάθουν να προγραμματίζουν (ο κώδικας είναι εξειδικευμένος και σχετικά δυσνόητος), αλλά θα μπορούσε να είναι χρήσιμο σε όσους ενδιαφέρονται για interpreters και virtual machines. Εγώ σίγουρα έμαθα αρκετά πράγματα στην πορεία.

Κάποια πρόχειρα benchmarks που έγιναν με το misc/programs/nqueens.ipl (linux binaries για σύγκριση υπάρχουν στο misc/implementations):

implementation	20 queens	28 queens	comparison to ipl
ipl (compiler)	0.22 secs	4.9 secs	-
ipli-reference	641 secs	timeout	3000x slower
ipli-k08	27.13 secs	timeout	123x slower
ipli-k08-optimized	3 secs	82 secs	17x slower
ipli-fast	0.4 secs	10.6 secs	2x slower

Ο ipli-fast είναι 2 τάξεις μεγέθους γρηγορότερος από τον ipli-k08 που φτιάξαμε στο φροντιστήριο, μία τάξη μεγέθους γρηγορότερος από την optimized version ipli-k08-optimized, και 2 φορές πιο αργός από τον ipl compiler. Σίγουρα κάποιος με μεγαλύτερη εμπειρία στον τομέα θα μπορούσε να μικρύνει ακόμα τη διαφορά (αλλά βέβαια και η απόδοση του compiler μπορεί να βελτιωθεί).

Τεχνικές που χρησιμοποιήθηκαν

Σύντομη περιγραφή κάποιων τεχνικών που προσέφεραν σημαντικά speedups:

• Virtual machine

  Το IPL πρόγραμμα μετατρέπεται σε κώδικα ενός πολύ απλού VM αρκετά προσαρμοσμένου στις ανάγκες της IPL (τα instructions περιγράφονται στο parser.h). Η IPL είναι μεν απλή γλώσσα, αλλά έτσι απλοποιείται πολύ περισσότερο (πχ τα loops αντικαθιστώνται με jumps) το οποίο κάνει τη βελτιστοποίηση πιο εύκολη.

• Direct memory access

  Το VM έχει 2 registers και κάθε πρόγραμμα έχει πρόσβαση σε έναν fixed αριθμό διευθύνσεων μνήμης στο host μηχάνημα (όσες οι μεταβλητές και τα arrays στο IPL πρόγραμμα). Για τις μεταβλητές, λόγω της απλότητας της IPL, κάθε instruction περιέχει direct pointer στην αντίστοιχη μνήμη, δεν υπάρχει κανένα indirection. Για τα arrays αυτό είναι προβληματικό διότι πρέπει να υποστηρίζεται allocation/deallocation. Αυτό όμως συμβαίνει σπάνια, οπότε χρησιμοποιούμε επίσης direct pointers, και σε κάθε allocation τους τροποποιούμε σε όλες τις εντολές του προγράμματος.

• Threaded code

  Η βασική καθυστέρηση σε έναν διερμηνέα προκαλείται από το "dispatching", την εύρεση δηλαδή της επόμενης εντολής προς εκτέλεση. Το dispatch τυπικά γίνεται με μια μεγάλη switch εντολή που εξετάζει το επόμενο instruction και εκτελεί τον αντίστοιχο κώδικα. Αυτό όμως έχει ως αποτέλεσμα ο χρόνος εύρεσης κάθε εντολής να είναι υπερπολλαπλάσιος του χρόνου εκτέλεσης.

  H τεχνική threaded code επιταχύνει σημαντικά το dispatching ως εξής: το array με τις εντολές του προγράμματος (vm instructions) μετατρέπεται σε ένα array με τις διευθύνσεις μνήμης που περιέχουν τον κώδικα για τα instructions αυτά, το οποίο ονομάζεται "thread". Οι σύγχρονοι C compilers επιτρέπουν να πάρουμε τη διεύθυνση του κώδικα που υπάρχει σε κάποιο label ως &&LABEL, και να μεταβούμε στη διεύθυνση που δείχνει ο pointer void* ptr με goto *ptr (ποιος είπε ότι είναι αδύνατο να κάνουμε dereference void pointers; :D).

  Ο instruction pointer (void** ip) δείχνει σε ένα στοιχείο του thread, και η μετάβαση στην επόμενη εντολή μπορεί να γίνει χωρίς κανένα switch, ως:

  goto **ip++;      // unreadable but beautiful

  Τα ορίσματα των εντολών μπαίνουν επίσης στο thread, ενώ οι jump εντολές μετασχηματίζονται ώστε να έχουν ως όρισμα απ' ευθείας τις διευθύνσεις στο thread.

• Super-instructions

  Η IPL μπορεί να υλοποιηθεί με ένα πολύ μικρό instruction set από απλές εντολές με λίγα ορίσματα. Κάτι τέτοιο θα μπορούσε να είναι επιθυμητό για διάφορους σκοπούς, αλλά σε έναν pure interpreter το dispatch των μικρών αυτών εντολών προσθέτει σημαντικό overhead. Είναι συχνά προτιμότερο να έχουμε "super-instructions" που να κάνουν τη δουλειά πολλών εντολών μαζί, χωρίς dispatch. Λόγω της απλότητας της IPL, μπορούμε τις περισσότερες εκφράσεις να τις αναπαράγουμε με super-instructions, πχ να έχουμε μια εντολή jump if not <var1> <= <var2>.

• Loop optimizations

  Έχουν επίσης υλοποιηθεί κάποια απλά loop optimizations. Πχ το if var == var υλοποιείται με unconditional jump. Επίσης στο τέλος ενός while loop κάνουμε πάντα ένα jump στην αρχή για να εξετάσουμε τη συνθήκη (και μπορεί να χρειαστεί και δεύτερο jump αν είναι false). Το dispatch time του ενός jump μπορεί να εξοικονομηθεί προσθέτοντας τον έλεγχο στο τέλος, ουσιαστικά αλλάζοντας το

  while(cond} { ...  }
  

  σε

  if(cond) { do { ... } while(cond) }
  

  το οποίο απαιτεί 0 ή 1 jumps.