Scale By The Bay 2018: Eugene Burmako, Towards Parallelizing Scala Compilations
Recording: Scale By The Bay 2018: Eugene Burmako, Towards Parallelizing Scala Compilations
you all right so let's talk about parallel computation in Scala this is a pretty hard topic right because we all want our Scala compiler to be faster that's one of the ways to approach the problem let's see so here at Twitter we developed a whole new experimental compiler to explore revenues in that direction let's see what kind of numbers we arrived at some of you may have already saw the spoiler that was very careless of me but anyway a few words about myself from 2011 to 2016 I was a PhD student in Martin and there's his lab in Lausanne Switzerland and shortly after graduating from getting my PhD from Martin I joined Twitter so currently I serve as a tech lead of the advanced costing here and you know speaking of my work in the community you may have heard of Scala macros that was my PhD thesis there is this column meta thing the meta programming library for next-generation tooling I gave a few talks about that about it before but not today and I receive that's that's a new hotness so a year ago we announced that we'll be developing a completely new compiler from scratch to see how far we can get in speeding up Scala and today at the same conference just a year later we're really happy to show some initial results all right so concretely in the talk today I will give a brief recap of the thing that we presented last year for those of you guys who are not completely sure what Ric is then we will discuss the avenues that we explored how to make our prototype last year's prototype useful because it was fun but they it wasn't immediately useful for anything that was quite a challenge and we'd like to share this experience with others so they can benefit from it then we will talk about the key inside that's one of our team members had how to use our SC how to use our compiler tag to speed things up in real projects like you know like an SPG for instance and finally I'll demonstrate the experimental results okay so the quick recap our SC is that's the tagline from github it's an experimental Scala compiler focused on compilation speed so the experimental thing it means that we can just you know at some point throw it away and call it then it will be great right as long as we learn from our experiments well what's cow and what compiler means I guess that's that's pretty clear and focused on compilation speed this basically says that we are not interested in anything else just compilation speed and this is very very narrow focus it allows us to do super targeted experiments so perhaps the results of those experiments would not be immediately useful for the Scala compiler for daddy but you know at least we'll know the boundaries where we can go so concretely our research goal that would be the success criteria if say in a few years Scala compilation for typical code bases for whatever definition of typical right if it's five to ten times faster than we're golden and I believe we're on track to achieving that goal but as usual since these are experiments it's research everything can fail although today we will see evidence of you know moving towards that number all right so when we start when we started our AC already mentioned that it was designed from scratch we figured out three axioms so first of all we decided to rewrite it completely so last year I talked about this a little bit more but you know existing scala compilers they're pretty big ATK lines of code 140k lines of code so clearly if you were to do fundamental experiments in such a compiler say completely remove existing their CS and replace them with something else that would be very hard in comparison our compiler is about 20k lines of code so you know it's feasible to just throw away everything completely and we write it in a month and well that's what experimentation is about then last year we decided to start small that is to pick a very small subset of Scala and just implemented see how fast you can get so clearly this result would be not useful for practical use but it would show the limits of Scala compilation speed and finally so this was a bit controversial at the time of our announcement we do not intended to work the language instead that our goal is to contribute to the community through our experiments so ideally if Scala C or the Dali compiler the new Scala compiler if they become much much faster because they use some of our ideas that's awesome and that's great this is what open source is about and we're very happy to give back to the community let's take a super quick example of how RAC works and this will familiarize us with the terminology that we'll need further so here we have a HelloWorld program with you know some random classes and methods but the bottom line is that on the left hand side we have one source file on the right hand side we have another source file and clearly the user other definitions like X or C which are not shown here so what happens now what happens when RSC sees those across those source files it will parse them into something called abstract syntax trees some representation for the program and then it will do something called schedule so basically it will go through definitions that are visible from other files and it will mark them somehow it will remember them in a list or the hash map whatever so what's critical here is that these definitions we call them outlines this is the only thing that is necessary to figure out dependencies between source files so for instance you know valdine that is shown on the left it's completely relevant to other files in the project because no one can reference that will be right but you know method foo in Class A is definitely relevant and type checking other files and the project may need the type signature of that method so we make a note of all those definitions and then we do something called scope that was another that's another face in the phase in there C compiler so we resolve the imports and we resolve extends clauses so basically at this point we know exactly what kind of names are visible everywhere in the program and the next step and now things are colored in red it's pretty special so thanks to the work the preparatory work that we did before in the previous two phases we can do everything else in parallel so just because we know all the names that are available at any point in the program we can resolve those names completely in parallel so those foo C a and B that's that's pretty neat but that's not the main cool thing the really cool thing it happens here so again read parts they signify parallel processing so after those names have been resolved and after we know all the type signatures of publicly visible members in the program so those type signatures I will be calling them outlines from now on so once we know the outlines everything else can be done in parallel so we can create you know if we're really adventurous we can create a thread per method body and just you know with this fictional hardware that has tens of thousands of threads we could be a Baretta Klee can do things very quickly so that's the kind of experiments that we were running in a year ago and the results were quite promising so we act up a prototype type checker for a small subset of Scala so this thing it wasn't meant for real use that's why when we supported source dependences so we could not link to jars for instance everything had to be defined in sources and finally you know it wasn't quite a type checker because it only could do name resolution so it did not do type inference implicit search nothing like that so we just we were interested in obtaining a hard upper bound of how fast things could be and well here are the numbers so we took intention of regular expressions ported from Java so it was super simple Scala code it was super simple but not trivial so it still contained method calls you know class definitions type applications and what we figured out in this case study is that our prototype type checker which is very limited as discussed on the previous slide it was 20 times 25 times faster than the full scholarship type checker so that's that's quite promising I think however you know this brings up another question so you can resolve names super quickly we cannot do type inference you cannot do anything else we cannot omit bytecode so what now it was fun so what happens do we now we know close the project and move on right that was that was a really tough point in the life cycle of the of RSC because we just did a very impressive demo and we did not know what where exactly to go from there and so in this part of the presentation I I'd like to share some of the ideas that we explored first of all here's the obvious one how about we just implement the entire compiler so in addition to this type checker for the small subset of the language how about we create the full scholar compiler for a small subset of Scala and since we resolved all the names were already very very close to a meeting bytecode so let's just resolve the names and then you know some co-writer back-end so back end there's a thing that takes those names in its class files perhaps we could make this happen however there were some reasons not to do that so first of all the first reason was that if we were to write all of this on our own the scope of the project would blow up significantly before I told you guys how cool it is to have a small compiler like you know 5 K lines of code 20 K lines of code but you know if you have to do everything it becomes and we all do very very quickly so our only other hope was to integrate with backends and other compilers like the Scala compiler or dari but unfortunately at this point both backends they're tied to compiler internals of individual compilers there is a proposal that Adrienne from light been submitted to the Scala Center recently to have tasty as a unified intermediate format but it works across colossian body and in that case if we have that standard then we have we can have one single back-end that works for everyone rs included so that's that sounds very promising but that was definitely not not even in the cards a year ago so long story short we discarded this idea what happened next is we thought about producing semantic d-beam instead of class files so semantic DB is to put it in a nutshell it's a data schema for semantic information about Scala and Java programs so here you can see a plot above definition of a central data structure in the schema basically we can omit very simple informations the compiler Diagnostics compiler synthetics whatever for source files that you have and then based on that information we have a bunch of tools that can leverage those payloads so meta browse it's it's a static code browser generate static websites metals is Scala meta LS language server it's kind of like an IDE and so on so forth so clearly what we could do with the RSC with our ability to resolve names very quickly we could have a cure feature we could have a keyword tool that's so fast that it's just unbelievable and it makes things much much better so of those tools I will not go into details but you know superfast ID it would actually be nice so IntelliJ indexing sometimes it's quite annoying especially on big projects so what if we could do that super super quickly that's definitely we didn't reach however you know an idea a full-fledged ID it's it's more than just indexing or type checking that's again you know a scope blow up so we thought about this and decided that it's not super practically feasible at least not in the near future and then there was another idea and so at one point we had an improvised meeting with one of my colleagues as to hood who works here at Twitter as well so he dragged me into the meeting room and stuff and explained what I'm going to explain to you guys so he said so hey Eugene you already computed outlines but how about you save them in the two-disc in the format the Scala compiler understands and then after all the stuff is saved this you can launch multiple Scala compilers not other C compilers but Scala compilers and this way you could compile things in parallel supposedly making things faster so that was a real breakthrough so finally we saw something that can be implemented within a few quarters as opposed a few years and the rest of the talk is going to be about just that so enter multi-phase compilation let's take a fictional example of a four project configuration so you have projects a b c and d a is that the route it does not depend on anything then B depends on AC depends on a and D depends on C sounds very confusing but I hope that this chart this Gantt chart it will help you out so this is how normal compilation would work this is how you know a scholar go-to would work without you know pointing fingers or anything so that's first to compile a completely from from beginning to the end and then you start the dependent compilations B and C and finally once C is compiled to compile the end you know here you go so that's that's how build tools basically work at this point and you can notice that there is already depending on the configuration dependencies between projects there is already some degree of parallelism in those builds so thanks to outlines we can do this a bit faster so let's say we have outlining we have implemented outlining via our AC or other means and outlining takes just 50% of compilation time because we don't emit bytecode we just you know compute public type signatures nothing else and so in that case to start compiling projects B and C we just need an outline away you don't need to wait all the way up to completion of Scala CA and as you can see this already brings significant speed ups so we were at four point five seconds now we're at three seconds obviously this is a fictional example this is all theorizing so in practice it's a bit different but you see the idea so that's pretty good but we can do even better so remember RAC was very fast at resolving names so actually for our CD the picture looks like this my outline is so fast and again now we're more than two times faster but that's not the end we can do even more so how about we take those you know big red bars and how about we split them up like this so in this example we took every each project and we split that project into two parts and then we compile those parts independently of each other so we literally create independent compilers for all of them and clearly this raises the questions so what if you know first part depends on the second part how do what do you do with this and a critical insight here that once you compile once you compute out lines for a for the entire project a that's all that's necessary to resolve those dependencies so if a one depends on a two then this is taken care of by this small blue outline a thing what's pretty cool about this were more than three times faster than the original number just because of splitting things happened because there is this outlining tool that's available and that because we can dump out lines in the format the Scala compiler understands well clearly you need to have you know impressive hardware to take care of this so here we we have eight or even more than eight threads depending on the time but if you have that Hardware you can be very fast so another another fun thing fun experiment that we did it didn't quite pan out but I wanted to mention it so how about we put all those targets together all those projects together ignore any boundaries between them and then we you know outline everything all together at once and then we slice and dice that unified project this super project super target into eight parts so ideally what that would lead to is uniform usage of all cores that are available on your computer disregarding all the you know dependencies between different projects but why this did not work out well in our case is that see now there's a big blue line which is blocking everything so we do not support parallel outlining at this point at this point which means that this super target parallelism thing it doesn't work out quite well so perhaps it will in the future but not at the moment a little bit of practicalities again I'd like to just share the experience that we obtained while working on the project so first of all with this approach we don't need to limit ourselves to a small subset of Scala because you know in order to type-check type signatures actually you don't need to support too many features right so there's type applications you know they're projections blah blah blah but it's not too much and whatever is happening in method bodies you don't care about this at all if you do this one weird trick right you require that return types for all the apps and vows are explicitly annotated so in case when you don't rely on type inference and public signatures you completely disregard method bodies so that's arguably one could say that this is already a best practice to do this but you know this is still a significant change to the developer workflow luckily we have a tool called Scala fix which was developed and semantics DB perhaps you guys saw that in one of the previous slides that can take care of that automatically so at least that's taken care of there are some complications regarding Java support but I'm running out of time so I'll just skip that part so anyway let's get them to experimental results the numbers that they promised before well first of all a little bit about the hardware the only thing that's of notes here for these benchmarks is that we use the pretty powerful CPU it's actually a two CPU configuration 16 cores each well whatever memory whatever SSD as long as you know memory is enough and it's SSD not HDD and it's not holding us back then we took here's the software configuration so we use a Scala 211 for our experiments we use JDK 128 we use whatever build of RAC and there is something called warp that I'll mention in just a few words so warp is a toy build tool that we hacked up just specifically for demo how cool is that right so we were to give a talk and then we just wrote a simple build so I wouldn't call it simple I would call it J BT it's like joke build - it doesn't even do finger printing it doesn't do incremental compilation all it does it just calls RSC and Scala C in the right order so this thing again it shows upper bound of performance that we can achieve now speaking of the case study so we took a real-world project which which uses actually a lot of advanced Scala features so there's something called Twitter you - it's a collection of utilities that we use in our mana repo internally and they are also available in the open it contains 60 of what we call targets which is basically small projects right so here at Twitter we use a build tool called pants and this is how projects are called there and it's possible to have lots of those projects targets and which is why 75k lines of code that we target it has 60 projects so here's that and now what exactly did do a benchmark so we benchmarked one phase compilation with a JVM on you know different powers of two threads and we benchmarked a three phase compilation which is basically compute out lines compiled Scala targets and then compiled Java targets some things that we noticed that you know hyper-threading did not work well in those benchmarks so we didn't even try with 64 threads not on the graphs anyway it just makes things worse somehow and then speaking of splitting targets into parts we split targets into batches of five files so the number of parts is dynamic actually now finally can we get to the numbers Jesus Christ is 20 minutes already where are the numbers so here they are first of all one phase compilation this is what you know your regular build tool can do so with the build configuration like we haven't Twitter in Twitter util things actually can scale up to four threads so you know see with one thread it starts at 37 seconds and then four threads it's at 18 seconds and then pretty much flattens out so that's 2.25 X speed up on 32 threads and here's what we can do thanks to RSC and thanks to this outlining compilation strategy we start way way up I didn't even fit into the slide right because there's lots of work so remember there were there were lots of red and blue bars on the picture so this is where the extra work comes from and then as you can see it scales well up until 16 threads which is so much better than the blue thing and ultimately it settled down a little bit about 6 seconds which is 2.7 times faster than what you can achieve with you know your regular build tool so some comments about that we don't have much time to to look into to discuss the results here why it ended up being like this but ultimately thanks to outlining I believe we're able to extract more parallelism even from you know unfavorable dependency dependency configurations and your builds then than usually so you know you saw it was just 75k lines of code it's not a big project by by any measure but still we obtained 2 point 7 XP dubs so hopefully you know four really big projects and we have plenty of them here at Twitter it will be much bigger but clearly you need the power of hardware to make use of that now we're almost at the summary so quickly go through related work the slides will be posted shortly on my Twitter but basically there is related work so this call outlining thing is started from a project called Kentucky mule which was done by my former colleague from PFL Josh the Sikorsky and then you know we took that AG and we ran with it in RSC but there's also other work done concurrently so there is a build tool or not a bill to anyway called bloop that's developed at Scala Center are they experimented with something similar although they don't have this this fast outlining as we do and the result also related work going on in dari the new Scala compiler so speaking of credits lots of credit goes to Martin and their ski because you know writing a Scala compiler from scratch this was this is you know terrifying in there were and just knowing that Martin did that twice it was a big help so then I would also like to thank my former colleague from PayPal Dennis Chaplin who develops colonnades him so he demonstrated that Scala programs can be very very fast so thanks to Scala native you can have CLI tools that start in milliseconds as a posting no second so Greg we already mentioned him for outlining and then guys my colleagues from Twitter we have the advance call tools team who worked on RAC a we have Stu who came up with this idea of two-phase compilation and our build him they're working on integration between RAC and pants at the build tool that we are using at Twitter okay so to sum it up we can outline things very very quickly both for Scala and Java and apparently that's useful if you have powerful hardware thank you [Applause]