TITLE OF PAPER: Faster than C: Static Type Inference with Starkiller URL OF PRESENTATION: _URL_of_powerpoint_presentation_ PRESENTED BY: Michael Salib REPRESENTING: Dynamic Languages Group, Computer Science and Artificial Intelligence lab, MIT CONFERENCE: PyCON 2004 DATE: 20040324 LOCATION: _venue_and_room_in_venue_ -------------------------------------------------------------------------- REAL-TIME NOTES / ANNOTATIONS OF THE PAPER: {If you've contributed, add your name, e-mail & URL at the bottom} Thesis work -- paper is a chapter from the thesis. Overview: Starkiller is a Python to C++ compiler Handles all of Python except for 1 tiny, insignificant, morally deranged part Starkiller has one goal: lightning fast native code Of course, if we wanted speed, maybe C++ wasn't such a good choice, but... uses C++ for simplicity (!) Python is slow High speed network servers databases AI Spam filtering Sometimes, straightforward Python code is much clearer and easier to write than fighting with Numeric For the 15% of apps where speed matters, pure Python alone can't do the job. (and sometimes you don't want to use crappy C++) Why is Python slow? It's not the VM: p2c showed that. p2c unrolls the VM, eliminating VM dispatch overhead. experience showed only 15% improvement over CPython. Layers of indirection everything is a dictionary, nothing is static, everything has to be checked at runtime Dynamic binding Dynamic dispatch No structure/size information Run time choice points foil the last 30 years of optimization research Speed comes from eliminating run time choice points Other languages suck Java sucks beyond all measure and comprehension C++ and Java suffer the same perfomance problems as Python when it comes to dynamic dispatch Dynamic dispatch (read: virtual functions) prevents the compiler from using all the cool optimizations like inlining Inlining is the canary in the coal mine: if you can't inline you probably can't do loop hoisting, strength reduction, etc without all these optimizations you lose all the benefits from the last 30 yrs of research The Present Starkiller type inference nodes and constraints functions and templates Starkiller Compiling to c++ is no enough (same gains as p2c, with equally "bad" results) Need static type inference to eliminate dymamic binding and dispatch Starkiller compliments rather than replaces CPython Covers the entire language except eval, exec, and dynamic module loading covers the entire python language except the places where you can insert runtime code (dynamic) Not all run time choice points can be eliminated, but many can. Starkiller type inference Based on Ole Agesen's Catesian Product Algorithm (see his Stanford thesis) Represents Python programs as dataflow networks Nodes correspond to expression and have a set of concrete types that those expressions can achieve at runtime Constraints connect nodes together and enforce a subset relation between them Types flow along constraints constraints enforce subset relationship Type inference in action A simple example x = 3 y = x z = y z = 4.3 The way you figure out contraints is by looking for nodes that have assigments Types flow along the graph and you try to get the type sets to converge (ideally to one type) You do know the types of the constaints and you propagate types thru and then it enters a quiescent state Flow insensitive algorithm Doesn't depend on time Functions and templates Parametric polymorphism (same function w/ different argument types) reduces precision We regain precision by taking cartesian product of argument type list and analyzing one template for each monomorphic argument list (combinatoric explosion?) Ex: Given polymorphic class max(1, 2) and max(3.3, 4.9) we analyze templates for (int, int), (float, int), (int, float) and (float, float) Polymorphic functions can cause starkiller to return information that may not be helpful, for example the max call above will show that the return node is both an int and a float. Agesen decided to use the cartesian product of the above result to create four different max product templates to cover the set of monomorphic arguments. If you do that you end up with a maximum set of templates that do only the required number of argument combinations. The cartesian product sufferes from combinatorial explosion Functions and Definitions A Python function creates a first class object at runtime Function objects can capture variables defined in their lexical parent(s) Starkiller models function definition using a function definition node that has constraints from all default args and expression the function closes over The definition node takes the cartesian product and generates monomorphic functionality Objects and Classes Class defintion works just like function definition! Instance work in the same way a as classes Calling a class triggers the creation of an instance definition node Foreign code Type inference cannot see into an extension module A mini language is used to describe types of extension modules the type inferencer cannot handle foreign code because he wanted to avoid parsing header files - so he is thinking that any foreign languages would be handled by the person creating a external type description language Status: Type inferencer is done except for for loops and simple / boring stuff Compiler is in an early state compiler will be GPL runtime library under LGPL Release in May Simple benchmarks; 60x on for loop written in very Pythonic style. Other applications for Starkiller ideas Free threading Static error detection Object lifecycle tracking Static garbage collection Vectorizing and loop fusion -------------------------------------------------------------------------- REFERENCES: {as documents / sites are referenced add them below} paper: http://www.python.org/pycon/dc2004/papers/1/paper.pdf starkiller: http://web.mit.edu/msalib/www/urop/ !starkiller: http://www.starwarz.com/starkiller/ -------------------------------------------------------------------------- QUOTES: "When this talk is over, I want to feel that the idea is out and I can die because I'm not important anymore" "I wrote emacs, will you sleep with me?" - RMS And too many other good ones to catch -------------------------------------------------------------------------- CONTRIBUTORS: {add your name, e-mail address and URL below} Ted Leung, twl@osafoundation.org, http://www.sauria.com/blog Ryan Wilcox, rwilcox@wilcoxd.com, http://radio.weblogs.com/0100544/categories/rpwconferences/ -------------------------------------------------------------------------- E-MAIL BOUNCEBACK: {add your e-mail address separated by commas } rpk@blue-newt.com, ark3@email.com -------------------------------------------------------------------------- NOTES ON / KEY TO THIS TEMPLATE: A headline (like a field in a database) will be CAPITALISED This differentiates from the text that follows A variable that you can change will be surrounded by _underscores_ Spaces in variables are also replaced with under_scores This allows people to select the whole variable with a simple double-click A tool-tip is lower case and surrounded by {curly brackets / parentheses} These supply helpful contextual information. -------------------------------------------------------------------------- Copyright shared between all the participants unless otherwise stated...