Add to Watchlist

Wrestling Python into LLVM Intermediate Representation

20 views

Citation of segment
Embed Code
Purchasing a DVD Cite video
Series
Annotations
Transcript
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
Email
Machine code
Just-in-Time-Compiler
Open source
System administrator
Mathematical analysis
Content (media)
Compiler
Bit
Student's t-test
Mereology
Compiler
Number
Subset
Subset
Video game
Subtraction
Algebraic variety
Library (computing)
Tuple
Programming language
Series (mathematics)
Algorithm
Assembly language
Cross-platform
View (database)
Source code
Gene cluster
Mathematical analysis
Compiler
Compiler
Intermediate language
Arithmetic mean
Compiler
n-Tupel
Software framework
Diagram
Representation (politics)
Subtraction
Computing platform
Algebraic variety
Tuple
Programming language
Digital filter
Algorithm
Mapping
Linear regression
Operator (mathematics)
Mereology
Functional (mathematics)
Computer animation
Operator (mathematics)
Lattice (order)
Order (biology)
n-Tupel
Cuboid
Loop (music)
Linear map
Algebraic variety
Tuple
Algorithm
Machine code
Wrapper (data mining)
Structural load
Linear regression
Dot product
Multiplication sign
Sampling (statistics)
Virtual machine
Electronic mailing list
Client (computing)
Functional (mathematics)
Subset
Computer animation
n-Tupel
Cuboid
Energy level
Backup
Implementation
Exception handling
Library (computing)
Library (computing)
Machine code
Standard deviation
Wrapper (data mining)
Wrapper (data mining)
Geometry
Multiplication sign
Direction (geometry)
Decision theory
Function (mathematics)
Limit (category theory)
System call
Usability
Subset
Proof theory
Computer animation
Feasibility study
n-Tupel
Data type
Algebraic variety
Code generation
Keyboard shortcut
Building
Machine code
Programming language
Abstract syntax tree
Compiler
Mathematical analysis
Machine code
Variable (mathematics)
Intermediate language
Compiler
Representation (politics)
Regular expression
Computer-assisted translation
Error message
Data type
Compiler construction
Electric generator
Trail
Expert system
Symbol table
Inference
Abstract syntax tree
Compiler
Single-precision floating-point format
Word
Fluid statics
Computer animation
Network topology
Vertex (graph theory)
Website
Trail
Numeral (linguistics)
Mereology
Variable (mathematics)
Data type
Symbol table
Metadata
Speicheradresse
Variable (mathematics)
Table (information)
Data type
Programming language
Computer animation
Expression
Vertex (graph theory)
Electronic mailing list
Representation (politics)
Functional (mathematics)
Data type
System call
Symbol table
Data type
Algorithm
Poynting vector
Inheritance (object-oriented programming)
Multiplication sign
Element (mathematics)
Virtual machine
Mereology
Vector graphics
Computer animation
Vector space
Integer
Data type
Algebraic variety
Data type
Computer programming
Pointer (computer programming)
Personal digital assistant
Connectivity (graph theory)
Electronic mailing list
Speicherbereinigung
Counting
Electronic mailing list
Functional (mathematics)
Arithmetic progression
Data type
Message passing
Machine code
Computer animation
String (computer science)
Function (mathematics)
String (computer science)
Electronic mailing list
Functional (mathematics)
Data type
Electronic signature
Data type
Curvature
Multiplication sign
Letterpress printing
Parameter (computer programming)
Mathematics
Root
Square number
Absolute value
Exception handling
Algebraic variety
Default (computer science)
Algorithm
Standard deviation
Email
Wrapper (data mining)
Functional (mathematics)
System call
Symbol table
Compiler
Computer animation
Function (mathematics)
Data type
Writing
Separation axiom
Library (computing)
Loop (music)
Concurrency (computer science)
Machine code
Computer animation
Branch (computer science)
Loop (music)
Data type
Conditional probability
Pairwise comparison
Machine code
Just-in-Time-Compiler
Order (biology)
Selectivity (electronic)
Bit
Electronic mailing list
Line (geometry)
Prime number
Subtraction
Benchmark
Number
Algorithm
Product (category theory)
Electronic data interchange
Line (geometry)
Debugger
Sampling (statistics)
Mathematical analysis
Mathematical analysis
Greatest element
Number
Computer animation
Compiler
Pairwise comparison
Sinc function
Algebraic variety
Algorithm
Machine code
Surface
Interior (topology)
Memory management
Mathematical analysis
Gene cluster
Usability
Range (statistics)
Mathematical analysis
Benchmark
Order of magnitude
Power (physics)
Message passing
Pointer (computer programming)
Computer animation
Oval
Compiler
Energy level
Subtraction
Mathematical optimization
Run time (program lifecycle phase)
Algorithm
Run time (program lifecycle phase)
Logarithm
Multiplication sign
Sampling (statistics)
Bit
Mathematical analysis
Client (computing)
Cartesian coordinate system
Thomas Bayes
Regular expression
Whiteboard
Resultant
Algebraic variety
Email
Computer animation
Root
Multiplication sign
Source code
Energy level
Software framework
Functional (mathematics)
Mathematical optimization
Resultant
Algebraic variety
Compiler
Point (geometry)
Hidden surface determination
Implementation
Multiplication sign
Gradient
Continuum hypothesis
Feedback
Letterpress printing
Electronic mailing list
Student's t-test
Functional (mathematics)
Benchmark
System call
Symbol table
Number
String (computer science)
n-Tupel
Extension (kinesiology)
Library (computing)
Form (programming)
Algebraic variety
Loading...

Metadata

Formal Metadata

Title Wrestling Python into LLVM Intermediate Representation
Title of Series EuroPython 2016
Part Number 146
Number of Parts 169
Author Herlihy, Anna
License CC Attribution - NonCommercial - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
DOI 10.5446/21106
Publisher EuroPython
Release Date 2016
Language English

Content Metadata

Subject Area Information technology
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.
Loading...
Feedback

Timings

  508 ms - page object

Version

AV-Portal 3.7.0 (943df4b4639bec127ddc6b93adb0c7d8d995f77c)