SHAPES: easy and high-level memory layouts

Abstract

CPU speeds have vastly exceeded those of RAM. As such, developers who aim to achieve high performance on modern architectures will most likely need to consider how to use CPU caches effectively, hence they will need to consider how to place data in memory so as to exploit spatial locality and achieve high memory bandwidth. Performing such manual memory optimisations usually sacrifices readability, maintainability, memory safety, and object abstraction. This is further exacerbated in managed languages, such as Java and C#, where the runtime abstracts away the memory from the developer and such optimisations are, therefore, almost impossible. To that extent, we present in this thesis a language extension called SHAPES. SHAPES aims to offer developers more fine-grained control over the placement of data, without sacrificing memory safety or object abstraction, hence retaining the expressiveness and familiarity of OOP. SHAPES introduces the concepts of pools and layouts; programmers group related objects into pools, and specify how objects are laid out in these pools. Classes and types are annotated by pool parameters, which allow placement aspects to be changed orthogonally to how the business logic operates on the objects in the pool. These design decisions disentangle business logic and memory concerns. We provide a formal model of SHAPES, present its type and memory safety model, and its translation into a low-level language. We present our reasoning as to why we can expect SHAPES to be compiled in an efficient manner in terms of the runtime representation of objects and the access to their fields. Moreover, we present SHAPES-z, an implementation of SHAPES as an embeddable language, and shapeszc, the compiler for SHAPES-z. We provide our our design and implementation considerations for SHAPES-z and shapeszc. Finally, we evaluate the performance of SHAPES and SHAPES-z through case studies.

Η ταχύτητα της CPU υπερτερεί πλέον αυτής της RAM. Ως αποτέλεσμα, οι προγραμματιστές που επιδιώκουν να επιτεύξουν υψηλή απόδοση σε σύγχρονες αρχιτεκτονικές θα χρειαστεί πιθανότατα να λάβουν υπ'όψιν το πώς να αξιποιήσουν τις λανθάνουσες μνήμεις (cache) της CPU κατά το βέλτιστο δυνατό τρόπο, το οποίο συνεπάγεται ότι θα χρειαστούν να εξετάσουν το πώς θα διατάξουν τα δεδομένα τους στη μνήμη ώστε να εκμεταλλευτούν τη χωρική τοπικότητα και να επιτύχουν υψηλή ευρυζωνικότητα μεταξύ της CPU και της RAM. Η εφαρμογή τέτοιων βελτιστοποιήσεων όσον αφορά τη μνήμη συνήθως έρχεται σε αντιπαράθεση με την αναγνωσιμότητα του κώδικα, τη συντηρησιμότητά του, την ασφάλεια της μνήμης και της έννοιας της αφαιρετικότητας αντικειμένων. Αυτό επιδεινώνεται περαιτέρω σε γλώσσες όπως η Java και η C#, όπου το runtime αποκρύπτει από τον προγραμματιστή το πώς διατάσσονται τα δεδομένα στη μνήμη και, ως αποτέλεσμα, τέτοιες βελτιστοποιήσεις είναι σχεδόν αδύνατον να θυλοποιηθούν. Ως εκ τούτου, παρουσιάζουμε σε αυτή τη διατριβή μία επέκταση γλώσσας προγραμματισμού, εν ονόματι SHAPES. Η SHAPES επιδιώκει να παράσχει μεγαλύτερη ευχέρεια στον προγραμματιστή ως προς τη διάταξη των δεδομένων στη μνήμη χωρίς αυτό να συνεπάγεται απώλεια της ασφάλειας μνήμης ή της αφαιρετικότητας αντικειμένων, διατηρώντας με αυτόν τον τρόπο την εκφραστικότητα και οικειότητα όσον αφορά τον αντικειμενοστραφή προγραμματισμό. Η SHAPES εισάγει τις έννοιες των περιοχών και των διατάξεων: Ο προγραμματιστής ομαδοποιεί σχετικά μεταξύ τους αντικείμενα σε περιοχές και προσδιορίζει το πώς τα αντικείμενα αυτά θα διατεταχθούν στη μνήμη. Οι κλάσεις και οι τύποι εφοδιάζονται με παραμέτρους περιοχών, οι οποίοι επιτρέπουν τις λεπτομέρειες σχετικά με τη διάταξη των δεδομένων να τροποποιηθούν κατά τρόπο ανεξάρτητο του πώς ο κώδικας επεξεργάζεται τα αντικείμενα που ανήκουν σε μία περιοχή. Αυτές οι επιλογές σχεδίασης διαχωρίζουν την επεξεργασία των δεδομένων από το πώς είναι διατεταγμένα τα δεδομένα αυτά καθ'αυτά στη μνήμη. Επιπλέον, παρέχουμε ένα μαθηματικό μοντέλο της SHAPES, παρουσιάζουμε το μοντέλο της όσον αφορά την ασφάλεια τύπων και μνήμης, καθώς και το πώς μεταφράζεται σε μία γλώσσα χαμηλού επιπέδου. Επίσης, παριοσιάζουμε τα επιχειρήματά μας όσον αφορά το γιατί αναμένουμε ότι η SHAPES μπορεί να μεταγλωττιστεί με αποδοτικό τρόπο όσον αφορά την αναπαράσταση των δεδομένων και την πρόσβαση των πεδίων αντικειμένων κατά τη διάρκεια της εκτέλεσης του προγράμματος. Επιπροσθέτως, παρουσιάζουμε την SHAPES-z, μία υλοποίηση της SHAPES ως μία ενσωματώσιμη γλώσσα, καθώς και τον shapeszc, τον μεταγλωττιστή της SHAPES-z. Παρουσιάζουμε τους συλλογισμούς και τις αιτιολογήσεις μας όσον αφορά το σχεδιασμό και την υλοποίηση τόσο της SHAPES-z όσο και του shapeszc. Τέλος, εκτιμούμε την απόδοση της SHAPES και της SHAPES-z μέσω περιπτωσιολογικών μελετών.