Merken

Wrestling Python into LLVM Intermediate Representation

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
next presented as in as presented there is an entirely he she is engineer admin that they India further everyone clearly excellent so my name is on a really and then I'm going to talk about m which is a small compiled from a subset of Python 2 LVM that was built as part of a larger project was a student so I think it appear and tell you that this is the best little compiler you've ever seen in that you should all be using in production of but I will tell you that it is reciprocal projects that was built in a true open source paths so basically advancements code that was abandoned about 5 years ago and breathe new life into it so if there is a moral to this talk beyond the technical content of it is that you have to be careful with the open source projects the anything that they're dead but someone like me will find them on the Google Code archives and you will once again have to answer e-mails so a little bit about me and I am a suffering junior of the deviance Stockholm student I worked on a couple different open source Python among the dealer the library but this is actually some work I did what I was not employed by my so 1st of bit about what you're in for a I'm a talk with the motivation behind this project and a very specific requirements that we need to me I'm going to go through the features do on a little bit of talking about related work mostly number which is a specializing just-in-time compiler from Continuum Analytics and do some analysis and benchmarking before concluding so how did I get
involved in this project while tuple where I is a distributed and all analytical framework built at Brown University that is for users who want to run analysis on large data and have their and there other be automatically deployed on a distributed clusters so I'm not gonna go too deep into the details about how to were actually works because that is an entirely different project done by entirely different people but when I worked on was integrating Python with the to work front so there are plenty of distributed and analytical frameworks of their of what makes 2 were unique in that it aims to be both language and platform independent so what does that mean
so language and platform independent means that we want you to be able to write your algorithms in any language you want to say you have an engineer that is convinced that they wanna write their algorithms and for channel we want to know support that and if they have read the views on the clusters we also want them so how do we do that we do it with LVM so LVM it's a lot of different things and it is officially a series of compiler and twitching technologies but what we care about is all the empire which is an intermediate representation which basically means and it is a way of representing code in between the source language and the machine-dependent assembly code so as you can see my diagram we have all these different languages that are all really popular and they are looking at compile down into all of the empire which is the dragon is that be mother and then a once again get compiled down into a bunch of different cities so a huge benefit of tuple where is that there are a ton of existing compilers for a bunch of different popular languages so
the goal of this project and was to basically prove that you created tightly integrate a higher order language such as Python with 2 which is written almost entirely in C + + usually I would go into why Python that since we are all here and we're all properly indoctrinated so
when How does it fit in with the tuple where project itself so you have the blue boxes which is what the user provides you need to provide an algorithm that you wanna run on your data and the need to provide a workflow so like MapReduce combined except the yellow boxes are what I worked on so 1st we needed to just be able to call the back and operators from Python as use boost for that which is pretty straightforward since we were using boost for a bunch of other stuff into border and then we needed to compile our which stands for user defined function into LVM this is in my opinion the more interesting part and also the more difficult so I
want to give an idea of of what a sample to this it would look like so you have a linear regression algorithm here don't think too much attention probably typo in there and that the idea is that if you take a look at the actual code that's been compiled you can get a pretty good sense of what you would mean what subset of Python you would need to support you basically don't need super fancy pipelined functionality like decorators list comprehensions excetera where the usage of tuple where is for is machine learning algorithms which tend to be very easily optimizable mathematical functions so that some edges to focus 1st on primarily a static type of verbal and then in the red box you have how you would use it to the work package so pretty much the easiest workplace you come up with 1st you loaded it as a matter of Proc clients so 1
level down and if we look at the tuple where library itself you have the 1st thing you do is you try to compile the UDF using prior all the other if that fails then we use a backup method which basically leverages the Python CPI to produce an executable so the idea is you want to use have to have to worry about whether or not the code they have yes is technically covered under pi the Imran not we just want them to feel like it's all covered but most the time we want to be able to use our primary outcome if the backup method fails chances are you have Python in your UDF and so we reason the higher
limits when I 1st found projects like any good engineer 1st Google to see if hopefully somebody had done the work for me I but what I found was a project called type to LVM which was an unfinished proof of concept that basically showed that you could take Python syntax and converted into of using so to users of the empire became kind of confusing because there's really only so many ways you can combine fun and all the m by LVM time is a wrapper around the C + + IR builder tools so it's basically just a weighted call the only and tools from what's kind of cool about this project for me is that what I found it out which is about 2 and half years ago there was pretty much only this project there wasn't really anything else out there and when I was writing this fine not too long ago I did some research and it turns out that a bunch of other people have fought the same rebo and have taken in totally different directions so as an engineer that's very satisfying to see how other people have solved the problem that I also have tried to ones 2nd
as so like I said before we really wanted to be able to anticipate the common requirements of the tuple where user so A-bomb are decided to focus on easily optimized mathematical functions as they go through each feature of him on a talk about the design decisions we made in the interest of sympathy so someone was going to cover this project after left and then you need to be able to read what I had written and feasibility which we had deadlines and most standards to graduate and then usability which I think I might have on but basically what a user people to write Python comfortably and not have to worry too much about the syntax so this is an
overview of of the way the compilers design looks like this is where the compiler experts in the audience might get a little bored because this is all very standard so if you want to compile code your 1st step is you need to pursue and build an abstract syntax tree which is basically a tree representation of what the code is doing so the 1 person is handled by a preference compiler package out which is very nice for me but this is where your syntactic errors would be caught in the proceeding in a city building stage answer for example say you were coding and your cat walked across a key words that would be a syntactic IR unless you have an especially adept cat so the next step is semantic analysis so this is where we actually begin to what the compilers doing the site with the code is doing and so we use a visitor to visit all the nodes of the AST and then we call ell the empire for actual code generation this is where semantic search become
so something really important about all of the empire and other intermediate representations is that of an asset which stands for static single assignment basically it means that if you have a register you can assign to it only once before it frozen that means that if we wanted to implement a Python just based on registers or we would ask our users to write the Python and assessing which is totally not reasonable so what are we doing we used a symbol
table so symbols are basically variables that contain the memory location where the data is stored in the name and type and some other metadata we keep track of our symbols using a symbol table which we implemented the scope to make up for it as a step to make scoping much easier for us this part was implemented before certain contributing
so I LOVE America by numerical targets as well as 5 derived types I We unimodal about how I represented the various Python types has all the imperative so since
LGM Irish is the statically typed representation and Python is not it is necessary to be able to infer the types of expressions before we actually have to evaluate them so to do this used the the inferred type function but which was partially implemented forested contributing but the idea is that given a node on AST you want to recursively descended until you find something that tells you what the type of expression will be so say you reach a leaf node and a constant that's pretty straightforward you know what the type that's already say you have a variable and then you have to look it up in the symbol table if you have a function call you also have to look up in the symbol table or a chat with a list of intrinsic functions that are built language so numerical
values found pretty
straightforward integers are integers and I added billions not thinking too
exciting there next up as
vectors and so we we provide support for for for element amenable floating point vector type which was implemented before started and was also a huge part of why I chose to build my project on this 1 on because these vectors which are based on the whole of the empire vector type and are passed by value super common in machine learning algorithms that just come up time and time again so having this implemented for me was a huge next up is
less so lists are work in
progress on the case implementing efficient dynamically resizable list on is and open problems and so another issue with list is like anyone who has ever program see before knows if you create a list of pointers many return that list for a function the Pi the pointers immediately go out of scope so how do we deal with this our well I chose to just move on the heat and then be very careful when removing it from the stack by garbage collection and reference counting is something that is way beyond the scope of this component on that could potentially be added 1 this is 1 of those places where we kind of went deeper and deeper into the problem before taking a step back and realizing this is not a battle that we wanted to that makes up a string as
so strings luckily enough
are basically lists of characters and character basically integers so we got this 1 for free the next step is
functions and so unfortunately Python functions don't usually indicate what type their returning if anything and so we have to be able to determine what the type of a function definition will be before we actually generate the code so this is 1 of the places where we do to pass since we do 1 pass to determine what the return type of functions and then 1 pass to actually generate the code once we already know what the function signature will be so
function arguments have the same issues except it's actually much harder to infer what function arguments are given in a function definition so this is 1 of the places where I did what is in my opinion kind of a dirty habit but I basically took advantage of the default argument syntax to allow users to indicate what type they were passing and as the parameters of the chances that somebody's writing in ML algorithm they don't know what types that they're the parameters are were they need a dynamic type is pretty well I type contend that thing out when I wrote this maybe I would have considered trying to use those on it was so the next step
is intrinsic functions 8 huge benefits for writing algorithms is to not have to import separate math libraries so if you can call square root absolute value etc. without have to to do any importing really so the all the Empire Builder actually provides functions for a square root and other things like that but unfortunately because they are in your features and all of the empire which is the wrapper around them on C + + tools is an older project that is not strictly supported they're not accessible so we could either choose to rewrite the whole library and where we could just try to get around it so what it is you get around this problem is basically defined in the header the calls to these and back and functions add them to the symbol table and then at a later time it'll get linked so that we can call those functions that we don't directly access to so this works for the math functions and also works the same as print out friends getting pretty working was probably 1 of the better feelings I have ever had that since I had already spent so much time working on this compiler and I could tell a flat executables respectful thing but I had no idea if they were doing what I expected so when my mystery executables started printing stuff the standard out so that like indicated it was working it felt really really good so branching
loops and LBM
has concurrent jump instructions as well as relatively straightforward ways to define what's code and there are some idiosyncrasies if you're curious I recommend you look up what final are but I'm not gonna go into detail because they are to begin tracking so I related
work and so the obvious
comparisons with number of which is a just-in-time compiler from Continuum Analytics that moves code from python to all of the empire the thing that number is that the primary purpose is not to generate all of the empire it is to run your Python code really really fast so number actually moves the Python code encoded in 2 6 different arms stages and all the MIR is only 1 of the stages selection to do a bit of gymnastics in order to pull it out at that stage another big difference about numbers that it's a too so with sleazy which means that it doesn't actually compiled code unless you run code which makes benchmarking and comparing on a pile of the EM with new but quite tricky because you can run covered primal and you can only compiler so the bottom line
and is that number is much much more mature and comprehensive project I like I said I would not recommend users in production but I would totally recommend you use number of another huge benefit of writing our own compilers that was built in house and so basically a needed something to work on and I always wanted to write and we compare so that for
analysis since work on the project looked like before started was entirely C + + and the user had to rate the UDF since he was plus and what I wanted to make sure it was that by adding this Python front end EDI make it harder on the user so I picked for a sample of algorithms and I took
a look at whether the the resulting use it would look like for C + + versus right and as you can see it's not very different just actually kind of a good thing so the huge benefit of using Python is not because you would expect your algorithms to be shorter it's freed from worrying about memory management and pointers and things like that so
for an actual benchmarking and wanted to compare try all the in the number and but unfortunately because of the jet thing it's complicated and instead of going into the data since I would have to do a lot of explaining and is going to tell you that I is slightly faster and hailed him a slightly slower but it's only by like to refer to it it's not an order of magnitude which is important because compared to the cost of analyzing the workflow and applying to the distributed clusters and actually doing the analysis of the compilation from Python 2 of the happens once so it's very very small relative to everything else so as long as we're not an order of magnitude slower than refine if anything thing I wanted to compare way is the actual generated of from claims which is what we were using before and high so something else and about the way that all of the empire works is that you generate optimized of the empire before passing it into the back and these incredibly powerful optimization passes are going to happen before it's converted into machine code so the idea is that if no matter who generates the LVM it should be the surface level differences should pretty much be wiped out by those optimization passes so
we used those for sample all good algorithms and we compared the runtime and the results of our
yeah indeed blue is try all the on the red is crying and the y axis is time so as you can see pretty much across the board the is a bit slower then client which is actually a pretty good considering crying is a huge project and that is very mature and has a lot of resources so the actual
results and we range from quite slow to not that bad I by k-means has a particularly large spike so I wanted to figure out why k-means was so much lower it turns out that my ingenious header had actually probably cost as the performance because I had assumed that calling these header functions would get optimized away but it it's what it looks like is that the optimization passes were actually people to get rid of that 1 level of indirection so every time you call square root instead of just calling square root but you would incline you call a function which then course again so that's an a problem because we can rewrite the empire and and we can re which contribute to it since it's the project is long dead and so not much to do here except for maybe pull out all the entirely which is a big undertaking and since they don't actively work on this project anymore if 1 if you want to do it that's often Anatoly encourages so the last to
conclude over all and we were pretty successful in proving that you could tightly integrate Python with this and distributed analytical framework and there is still a ton of future work to be done and like I mentioned I'm not doing it right now we are currently working on other among the the and but if anybody is interested in contributing I'd really encourage it also if anybody is curious about a relatively simple compiler I recommend you look at the source code because I find it pretty easy to fall I I have a lot of people to think
I think you to 10 who my advisor I'm Alex and you try hard and if you are the grad students who wrote tuple where thank you to the people who wrote to LDM have you don't mind that I've been mucking around in your code and and thank you to all my mentors among DB for encouraging me to go out and give talks so I
have some time for questions but I'm also going to make a brief and somewhat entirely unrelated announcement I am I am currently working on a library for reading data directly from the Sun which is among the DB data and directly into number 5 so if you use an empire and longer DB or 1 or none of them from you want Tommy about something I would really appreciate any feedback and so please come talk to me or between mean thank you for you do soldiers for the dog just wanted to mention that at from invited to points and you do this by changing the dual of the adult students all right totally missed that have you know an extension of this project but maybe it's not too late and you no and you should strings with a list of characters that make them some mutable In the use of EM implementation that much of the of the of the of yeah the only time that the real distinction comes up between strings lessons and the print function so we know whether to print characters into the thanks for the call I was very curious the future benchmarking convert to the selected burn implementations of the symbols now and I didn't actually I looked into it and that was immediately overwhelmed by just how like large the project is and how moving Python to unoptimized all of the American seems like very hard for me to pull out and so eventually just decided to focus on them but instead and did you work and consider using the land lights library the number that is of the form of talking tool for generating yes that's on the list of things that we want replace it and all the empire with but when I picked up this project it was already using some of the empire and not all of them right so I figured that it would take a significant amount of time to swap out of the it's existing IRA builder findings and so decided that my time would be better spent adding features conclusions and the continuum and checking
Videospiel
Subtraktion
Bit
Just-in-Time-Compiler
Open Source
Compiler
t-Test
Systemverwaltung
Zahlenbereich
Maschinensprache
Teilmenge
Mereologie
Programmbibliothek
Projektive Ebene
Inhalt <Mathematik>
Compiler
E-Mail
Baum <Mathematik>
Analysis
Programmiersprache
Subtraktion
Übersetzer <Informatik>
Sichtenkonzept
Assembler
Compiler
Reihe
n-Tupel
Zwischensprache
Quellcode
Systemplattform
Framework <Informatik>
Portabilität
Arithmetisches Mittel
Diagramm
Algorithmus
Projektive Ebene
Compiler
Cluster <Rechnernetz>
Stochastische Abhängigkeit
Analysis
Programmiersprache
Lineare Abbildung
Nichtlinearer Operator
Lineares Funktional
Schnittstelle
Lineare Regression
Quader
n-Tupel
Digitalfilter
Nichtlinearer Operator
Kontextbezogenes System
Computeranimation
Metropolitan area network
Algorithmus
Front-End <Software>
Mereologie
Projektive Ebene
Ordnung <Mathematik>
Bitrate
Lineares Funktional
Quader
n-Tupel
Mailing-Liste
Maschinensprache
Nichtlinearer Operator
Datensicherung
Datensicherung
Systemaufruf
Computeranimation
Übergang
Portscanner
Teilmenge
Virtuelle Maschine
Last
Client
Algorithmus
Lineare Regression
Stichprobenumfang
Wirtschaftsinformatik
Programmbibliothek
Compiler
Implementierung
Benutzerfreundlichkeit
Feasibility-Studie
n-Tupel
PASS <Programm>
Systemaufruf
Computeranimation
Entscheidungstheorie
Richtung
Maschinensprache
Beweistheorie
Datentyp
Wrapper <Programmierung>
Inverser Limes
Projektive Ebene
Compiler
Informationssystem
Standardabweichung
Funktion <Mathematik>
Web Site
Weg <Topologie>
Compiler
Codegenerierung
Selbstrepräsentation
Zwischensprache
Parser
Regulärer Ausdruck
Maschinensprache
Abstraktionsebene
Analysis
Computeranimation
Übersetzerbau
Netzwerktopologie
Knotenmenge
Maschinensprache
Abstrakter Syntaxbaum
Implementierung
Expertensystem
Datentyp
Übersetzer <Informatik>
Gebäude <Mathematik>
Symboltabelle
Variable
Einfache Genauigkeit
Bildschirmmaske
Generator <Informatik>
Wort <Informatik>
Computerunterstützte Übersetzung
Cloud Computing
Compiler
Fehlermeldung
Datentyp
Symboltabelle
Kardinalzahl
Symboltabelle
Zeiger <Informatik>
ROM <Informatik>
Variable
Computeranimation
Keller <Informatik>
Metadaten
Metropolitan area network
Weg <Topologie>
Variable
Ganze Zahl
Array <Informatik>
Mereologie
Datentyp
Speicheradresse
Informationssystem
Tabelle <Informatik>
Magnetbandlaufwerk
Programmiersprache
Lineares Funktional
Data Encryption Standard
Datentyp
Abstrakter Syntaxbaum
Selbstrepräsentation
Systemaufruf
Symboltabelle
Mailing-Liste
Oval
Symboltabelle
Variable
Computeranimation
Zeichenkette
Mailing-Liste
Knotenmenge
Arithmetischer Ausdruck
Ganze Zahl
Loop
Datentyp
Data Encryption Standard
Prinzip der gleichmäßigen Beschränktheit
Datentyp
Element <Mathematik>
Division
Vektorraum
Element <Mathematik>
Matroid
Computeranimation
Zeichenkette
Virtuelle Maschine
Mailing-Liste
Algorithmus
Ganze Zahl
Funktion <Mathematik>
Bit
Loop
Analog-Digital-Umsetzer
Ganze Zahl
Poynting-Vektor
Mereologie
Datentyp
Vererbungshierarchie
Punkt
Projektive Ebene
Lineares Funktional
Data Encryption Standard
Datentyp
Mailing-Liste
Zeiger <Informatik>
Zählen
Computeranimation
Keller <Informatik>
Zeichenkette
Mailing-Liste
Arithmetische Folge
Loop
Konstante
Zusammenhängender Graph
Zeiger <Informatik>
Speicherbereinigung
Optimierung
Informationssystem
Tabelle <Informatik>
Lineares Funktional
Data Encryption Standard
Datentyp
PASS <Programm>
Mailing-Liste
Maschinensprache
Symboltabelle
Elektronische Unterschrift
Systemaufruf
Variable
Computeranimation
Zeichenkette
Mailing-Liste
Ganze Zahl
Zustandsdichte
Funktion <Mathematik>
Loop
Datentyp
Compiler
Message-Passing
Zeichenkette
Krümmung
Compiler
Mathematisierung
Hochdruck
Schreiben <Datenverarbeitung>
Betrag <Mathematik>
E-Mail
Computeranimation
Mailing-Liste
Algorithmus
Datentyp
Wrapper <Programmierung>
Programmbibliothek
Wurzel <Mathematik>
E-Mail
Default
Trennungsaxiom
Lineares Funktional
Parametersystem
Datentyp
Krümmung
Systemaufruf
Ausnahmebehandlung
Symboltabelle
Variable
Sinusfunktion
Quadratzahl
Zustandsdichte
Betrag <Mathematik>
Funktion <Mathematik>
Projektive Ebene
Standardabweichung
Zeichenkette
Data Encryption Standard
Loop
Datentyp
Loop
Datenparallelität
Verzweigendes Programm
Befehl <Informatik>
Maschinensprache
Variable
Computeranimation
Subtraktion
Bit
Primzahl
Just-in-Time-Compiler
Singularität <Mathematik>
Just-in-Time-Compiler
Zahlenbereich
Maschinensprache
Paarvergleich
Systemaufruf
Trennschärfe <Statistik>
Compiler
Ordnung <Mathematik>
Gerade
Benchmark
Mittelwert
Lineare Regression
Mathematische Logik
Übersetzer <Informatik>
sinc-Funktion
Stichprobe
Zahlenbereich
Biprodukt
Analysis
Computeranimation
Algorithmus
Maschinensprache
Front-End <Software>
Stichprobenumfang
Debugging
Minimum
Projektive Ebene
Ordnung <Mathematik>
Elektronischer Datenaustausch
Analysis
Subtraktion
Übersetzer <Informatik>
Minimierung
Oval
Maschinensprache
Analysis
Computeranimation
Übergang
Algorithmus
Zustandsdichte
Flächentheorie
Speicherverwaltung
Größenordnung
Zeiger <Informatik>
Cluster <Rechnernetz>
Message-Passing
Speicherverwaltung
Analysis
Benchmark
Leistung <Physik>
Resultante
Physikalisches System
Client
Bit
Algorithmus
Singularität <Mathematik>
Stichprobenumfang
Rechenzeit
Kartesische Koordinaten
Projektive Ebene
Analysis
Whiteboard
Resultante
Lineares Funktional
Lineare Abbildung
Lineare Regression
Datentyp
Gerichtete Menge
Minimierung
Compiler
Vektorpotenzial
Quellcode
Variable
Framework <Informatik>
Computeranimation
Übergang
Physikalisches System
Mailing-Liste
Zustandsdichte
Front-End <Software>
Projektive Ebene
Wurzel <Mathematik>
E-Mail
Informationssystem
Sichtbarkeitsverfahren
Rückkopplung
Lineares Funktional
Punkt
Kontinuumshypothese
Hochdruck
n-Tupel
t-Test
Implementierung
Zahlenbereich
Systemaufruf
Mailing-Liste
Symboltabelle
Gradient
Bildschirmmaske
Programmbibliothek
Projektive Ebene
Maßerweiterung
Baum <Mathematik>
Zeichenkette
Benchmark

Metadaten

Formale Metadaten

Titel Wrestling Python into LLVM Intermediate Representation
Serientitel EuroPython 2016
Teil 146
Anzahl der Teile 169
Autor Herlihy, Anna
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Unported:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben
DOI 10.5446/21106
Herausgeber EuroPython
Erscheinungsjahr 2016
Sprache Englisch

Inhaltliche Metadaten

Fachgebiet Informatik
Abstract Anna Herlihy - Wrestling Python into LLVM Intermediate Representation The LLVM Project provides an intermediate representation (LLVM-IR) that can be compiled on many platforms. LLVM-IR is used by analytical frameworks to achieve language and platform independence. What if we could add Python to the long list of languages that can be translated to LLVM-IR? This talk will go through the steps of wrestling Python into LLVM-IR with a simple, static one-pass compiler. ----- What is LLVM-IR? The LLVM Compiler Infrastructure Project provides a transportable intermediate representation (LLVM-IR) that can be compiled and linked into multiple types of assembly code. What is great about LLVM-IR is that you can take any language and distill it into a form that can be run on many different machines. Once the code gets into IR it doesn’t matter what platform it was originally written on, and it doesn’t matter that Python can be slow. It doesn’t matter if you have weird CPUs - if they’re supported by LLVM it will run. What is Tupleware? TupleWare is an analytical framework built at Brown University that allows users to compile functions into distributed programs that are automatically deployed. TupleWare is unique because it uses LLVM-IR to be language and platform independent. What is PyLLVM? This is the heart of the talk. PyLLVM is a simple, easy to extend, one-pass static compiler that takes in the subset of Python most likely to be used by Tupleware. PyLLVM is based on an existing project called py2llvm that was abandoned around 2011. This talk will go through some basic compiler design and talk about how some LLVM-IR features make our lives easier, and some much harder. It will cover types, scoping, memory management, and other implementation details. To conclude, it will compare PyLLVM to Numba, a Python-to-LLVM compiler from Continuum Analytics and touch on what the future has in store for PyLLVM.

Ähnliche Filme

Loading...