Expressive and efficient streaming libraries

Abstract

Stream processing is mainstream (again): Widely-used stream libraries are now available for virtually all modern OO and functional languages, from Java to C# to Scala to OCaml to Haskell. Yet expressivity and performance are still lacking. This dissertation identifies the key high-level differences between various implementations, observes that future use cases are tied with past design decisions, and shows that simple abstraction mechanisms are not sufficient. Is it possible to modularize the implementation of streams to enhance such libraries in terms of extensibility and performance? We present a twofold modularization of streams. To begin with, we untangle streams from the definition of their syntax and semantics and afterwards we liberate them from the need of a ``sufficiently-smart'' compiler. The utmost goal of this dissertation is to make streams extensible and performant, while maintaining their high level structure. Our contributions are preceded by a performance assessment of the current state-of-the-art of streaming libraries. Subsequently, we first propose a mechanism to enhance the maintainability of streams, supporting a high-level of extensibility. We treat streams as a domain-specific language and we design and implement StreamAlg, a library that has the ability to accept new operators and semantics à la carte. Next, we port the library design we used for streams to Java itself, with a lightweight tool named Recaf. We show how to create dialects in Java, override its semantics, support new syntactic elements and much more. Among many examples and case studies we build an extension of Java with a keyword that enables us to construct streams similar to C#. The culmination of our work is a library design, Strymonas, for very efficient streams while preserving their high-level nature.It explicitly avoids the reliance on black-box optimizers and ``sufficiently-smart'' compilers, offering highest, guaranteed and portable performance. Our approach relies on high-level concepts that are then readily mapped into an implementation.

Οι ροές επεξεργασίας δεδομένων είναι και πάλι στο προσκήνιο: ευρέως-διαδεδομένες βιβλιοθήκες για επεξεργασία ροών υπάρχουν σε κάθε μοντέρνα γλώσσα προγραμματισμού και οικοσύστημα, από την Java στην C# και από την Scala και OCaml στη Haskell. Ωστόσο, καίρια χαρακτηριστικά τους όπως η εκφραστικότητα και οι επιδόσεις έχουν σημαντικά περιθώρια βελτίωσης. Στην παρούσα διατριβή, εξακριβώνουμε το ποια είναι ακριβώς τα ποιοτικά χαρακτηριστικά κάθε βιβλιοθήκης και παρατηρούμε ότι παρούσες αλλά και μελλοντικές χρήσεις τους, είναι άρρηκτα συνδεδεμένες (και δεσμευτικές) με την εκάστοτε υλοποίηση. Απλοί μηχανισμοί αφαίρεσης δεν είναι επαρκείς. Είναι εφικτό να διαμορφώσουμε την υλοποίηση των βιβλιοθηκών ροών και να τις κάνουμε πιο επεκτάσιμες και με μεγαλύτερες επιδόσεις; Παρουσιάζουμε δυο λύσεις προς την επίτευξη της επεκτασιμότητάς τους. Κατά την πρώτη, διαχωρίζουμε τους ορισμούς του συντακτικού και της σημασιολογίας των βιβλιοθηκών και κατά τη δεύτερη λύση απελευθερώνουμε τις εν λόγω βιβλιοθήκες από την επιτακτική ανάγκη ύπαρξης ενός ικανού και έξυπνου μεταγλωττιστή. Ο στόχος της διατριβής είναι να δημιουργήσει επεκτάσιμες βιβλιοθήκες ροών, υψηλών επιδόσεων, διατηρώντας όμως την υψηλού επιπέδου δομή τους. Η παρουσίαση των ερευνητικών μας αποτελεσμάτων έπεται αξιολόγησης επιδόσεων σε σύγχρονες βιβλιοθήκες που διεξήγαμε για διάφορες σύγχρονες γλώσσες προγραμματισμού. Στη συνέχεια προτείνουμε έναν μηχανισμό για την ενίσχυση της συντήρησης βιβλιοθηκών ροών διατηρώντας ενός υψηλού επιπέδου επεκτασιμότητα. Για να το επιτύχουμε αυτό, θεωρούμε τις εν λόγω βιβλιοθήκες ως γλώσσες προγραμματισμού ειδικού σκοπού, σχεδιάζοντας και υλοποίώντας την βιβλιοθήκη StreamAlg, μία βιβλιοθήκη που προσφέρει την δυνατότητα να δεχθεί επεκτάσεις με νέες μεθόδους και συμπεριφορά κατ' επιλογή. Στη συνέχεια, παρουσιάζουμε την εφαρμογή της προαναφερθείσας τεχνικής σε μία γλώσσα προγραμματισμού, την Java, για να επιτύχουμε την ίδια γενικότητα κατά την επέκταση της, με το εργαλείο που ονομάζουμε Recaf. Δείχνουμε πώς δημιουργούμε διαλέκτους στην Java για να υποστηρίξουμε νέο συντακτικό και νέα σημασιολογικά στοιχεία στην ίδια τη γλώσσα. Ως αποτέλεσμα, δημιουργήσαμε επεκτάσεις της Java, μία εκ των οποίων μας έδωσε τη δυνατότητα να δημιουργήσουμε βιβλιοθήκη ροών στη Java, όπως ακριβώς γίνεται και στην C#. Τέλος παρουσιάζουμε την πρότασή μας για βιβλιοθήκες ροών υψηλών επιδόσεων που υλοποιήσαμε σε δύο γλώσσες προγραμματισμού με τον ενιαίο όρο-ομπρέλα Strymonas. Η βιβλιοθήκη που παρέχουμε, χωρίς να βασίζεται σε απροσπέλαστους βελτιστοποιητές ή ``ικανοποιητικά-ικανούς'' μεταγλωττιστές, παρέχει, υψηλού επιπέδου, εγγυημένη και φορητή ταχύτητα ως προς την επεξεργασία δεδομένων. Η προσέγγισή μας βασίζεται σε έννοιες υψηλού επιπέδου οι οποίες στη συνέχεια υλοποιούνται.