Shark

Την περασμένη εβδομάδα ξεκίνησα να κάνω ένα μικρό πρόγραμμα για την προσομοίωση ενός συστήματος νευρώνων (εξωφρενικά μακριά από τα συνηθισμένα ερευνητικά ενδιαφέροντά μου). Έγραψα την πρώτη εκδοχή του προγράμματος με μόνο δύο νευρώνες σε Python. Αρχικά ήθελα απλώς να δω αν μια ιδέα που είχα για την υλοποίηση του αλγορίθμου ήταν σωστή και να παίξω λίγο με το σύστημα για να δω πώς εξελίσεται χρονικά. Χτες το πρωί αποφάσισα να τροποποιήσω το πρόγραμμα για αυθαίρετο αριθμό νευρώνων και σχεδόν ταυτόχρονα αποφάσισα να δομήσω τα πράγματα λίγο καλύτερα ορίζοντας τις σχετικές κλάσεις και ένα module για να το κάνω import σε διάφορα προγράμματα. Όλα καλά μέχρι εδώ. Για την ακρίβεια σε αυτό το στάδιο η Python έδειξε τις αρετές της. Μπορούσα να κάνω όποια αλλαγή σκεφτόμουνα σε ελάχιστο χρόνο. Η ίδια αίσθηση με το να δουλεύεις με πλαστελίνη χωρίς όμως να κολλάει στα χέρια. Από την άλλη πλευρά, ένα πρόβλημα της Python είναι ότι είναι αργή σε σχέση με compiled γλώσσες όπως η C. Σε πολλές περιπτώσεις αυτό δεν είναι σημαντικό αλλά εδώ αποδείχτηκε τελικά ότι ήταν. Χωρίς να μπω σε λεπτομέρειες, για να πάρω κάποιο αποτέλεσμα θα χρειαζόμουνα περίπου 3 ώρες. Αν αυτό γινόταν μόνο μία φορά δεν θα με ένοιαζε αλλά πρέπει να επαναλάβω τον υπολογισμό για πολλές τιμές των παραμέτρων του συστήματος. Γι' αυτόν τον λόγο αποφάσισα να ξαναγράψω τον κώδικα σε C++. Η «μετάφραση» δεν ήταν δύσκολη. Μόνο που το compiled πρόγραμμα (χωρίς optimization) έτρεχε πιο αργά από ότι το πρόγραμμα στην Python! Με optimization (g++ -O6) το πρόγραμμα ήταν 3 φορές πιο γρήγορο από ότι σε Python. Περίμενα πολύ μεγαλύτερη βελτίωση και πρέπει να ομολογήσω ότι ήμουνα απογοητευμένος. Στην αρχή έριξα το φταίξιμο στο ότι χρησιμοποιούσα εκτεταμένα την STL για να έχω λίστες και vectors. Είχα διάφορες ιδέες για το που μπορεί να χάνεται χρόνος και ήταν όλες λανθασμένες. Ευτυχώς, το διαπίστωσα πριν χάσω χρόνο κάνοντας αλλαγές στο πρόγραμμα που δεν θα βελτίωναν σημαντικά την ταχύτητα και θα το έκαναν πολύ πιο μπερδεμένο. Ξεκίνησα να κάνω profiling: g++ -pg και gprof. Δυστυχώς ο gprof έβγαζε βλακείες. Λίγο ψάξιμο στο Google επιβεβαίωσε ότι δεν έκανα τίποτα λάθος και ότι ο gprof στο Mac OS X έχει πρόβλημα. Και τότε θυμάμαι τον Shark. Είχα εγκαταστήσει πρόσφατα το CHUD και ήξερα ότι τον είχα κάπου αλλά δεν τον είχα χρησιμοποιήσει ποτέ. Ο Shark είναι ένας εκπληκτικός profiler και μπορείτε να τον χρησιμοποιήσετε για οτιδήποτε τρέχει στο Mac OS X. Δηλαδή τον ξεκινάτε και μπορείτε αν θέλετε να κάνετε profile ολόκληρο το σύστημα ή μόνο μια συγκεκριμένη διαδικασία. Έχει πάρα πολλές δυνατότητες και τις προσφέρει μέσα από ένα εύχρηστο γραφικό περιβάλλον. Αφού λοιπόν έτρεξα το πρόγραμμά μου μέσα από τον Shark και κοίταξα τα στατιστικά διαπίστωσα ότι το 90% του χρόνου πήγαινε σε μια sort. Το πρόγραμμα είναι πολύ απλό. Υπάρχει μια μικρή λίστα (το μέγεθος κυμαίνεται από 3 έως 6 στοιχεία). Σε κάθε επανάληψη (από τις περίπου 500000) αφαιρώ ένα στοιχείο από την αρχή της λίστας, κάνω κάποιους υπολογισμούς, προσθέτω ένα-δύο στοιχεία στο τέλος της λίστας και ταξινομώ την λίστα. Για αυτήν την δομή χρησιμοποιούσα μια list με την λογική αφενός ότι αφού χρησιμοποιούσα list στην Python το ίδιο θα έκανα και στην C++ και αφετέρου ότι χρειαζόμουνα μια δομή στην οποία να μπορώ να προσθέτω και να αφαιρώ γρήγορα στοιχεία. Αυτό αποδεικνύει ότι το να προγραμματίζεις αργά το βράδυ δεν είναι καλή ιδέα. Είχα ξεχάσει εντελώς το θέμα της ταξινόμησης και κυρίως είχα ξεχάσει ότι οι λίστες δεν προσφέρονται για ταξινόμηση. Συνειδητοποιώντας το πρόβλημα, άλλαξα την list σε vector (ίσως μια deque θα είναι ακόμα καλύτερη αλλά βαριέμαι να δοκιμάσω). Χωρίς optimization το πρόγραμμα έτρεχε 10 φορές πιο γρήγορα από ότι σε Python. Με -O6, 100 φορές πιο γρήγορα. Έτσι το πρόγραμμα που θα τελείωνε σε 3 ώρες τώρα τελειώνει σε 2 λεπτά. Τέλεια. Και για να κλείσει ο κύκλος αποφάσισα να μετατρέψω το πρόγραμμα που ήταν γραμμένο σε C++ σε module που θα μπορούσα να το κάνω import σε Python. Χρησιμοποίησα το SWIG. Η διαδικασία ήταν (σχετικά) εύκολη παρά την έλλειψη πλήρους documentation. Συμπεράσματα: (1) Ποτέ μην βελτιστοποιείτε ένα πρόγραμμα χωρίς να κάνετε πρώτα profiling. (2) Μην εμπιστεύεστε συγκρίσεις ταχύτητας μεταξύ διαφορετικών γλωσσών προγραμματισμού. Κάθε γλώσσα έχει τις δικές της ιδιαιτερότητες και για να πάρετε το μέγιστο χρειάζεται να ξέρετε καλά αυτές τις ιδιαιτερότητες. Αλλιώς βγάζετε συμπεράσματα του στυλ ότι η C++ είναι πιο αργή από την Python. (3) Μην προγραμματίζετε αργά το βράδυ.