Reasonable Scala Compiler

scale.bythebay.io: Eugene Burmako, Reasonable Scala Compiler

Recording: scale.bythebay.io: Eugene Burmako, Reasonable Scala Compiler

you hello interesting can you hear me like that guys okay awesome let's get started we have a short session we have a lot to discuss as well so today in this talk we will talk a little bit about the vision behind the reasonable Scala compiler just a little bit together started and we will segue into the status what we have what are the numbers so I guess this is why you're here finally we will talk about the architecture so what makes our compiler fast slow the same well answer these questions very soon before I begin I would like to say the words of thanks because a lot of people were indirectly involved in this project inspired this project and directly helped us out we will start with Martin and Ayers case so Martin anarchy he wrote two compilers for Scala from scratch that's pretty insane if you think about it and yeah we very much like this fact then Greg my former colleague from EPA found and we collaborated with him while he was at live band a year ago he posted a very interesting article called the limits of Scala type check in speed and there in that article he said well look guys I've just hacked something up and it turns out to be more than 1,000 times faster than the Scala type checker well that was awesome and finally Dennis my former colleague from epfl he developed Scala native and he showed that skull applications can start really fast so startup time is a common problem on the JVM and with Scala native we can say it's pretty much solved so as you can see this these guys they showed us that it is possible to have a very fast call compiler so that was that made our job very easy so we just had to implement this and so you know one day I rushed into the office of my boss David Keenan who's the director of our department that does developer tools and told him look David I can compile HelloWorld superfast oh my god this is going to be ground and so this guy he didn't show me the door nothing like that this is how our project got started so I'm very very thankful to David then there's Shane Shane joined us quite recently our advanced skulls team and he's already contributed major design and implementation modules in the GNU Compiler that's quite awesome and of course this project wouldn't have happened without a coordinated effort of a large team of people as you can imagine Twitter is a big company so open sourcing these kind of things it takes a lot of effort and I'm very thankful it's possible I think that in a lot of companies that wouldn't have just happened you know doing some crazy greenfield work and then just making it available to the world I'm really happy to see everyone here Sascha Remi Julian Richard so thank you guys really appreciate that okay without further ado let's talk a little bit about the reasonable Scala compiler so clearly it's a Scala compiler as if you get out from the name but it has a very very narrow focus we only care about computation speed nothing else so there are other compilers in the community well the Scala compiler the ADI compiler type level compiler and a few others that have other focuses but when you think about compilation speed and we believe that it is possible to make Scala compilation faster essentially by an order of magnitude than typical Scala code bases and this is a very bold goal and this is a research project it's an experiment but we think we're well on track and soon we will show the numbers now to get to this undertaking this is a quite challenging write speed up Scala compilation by 10x we had to set up some ground rules some axioms if you will and the first rule was to write everything from scratch this sounds insane obviously but on the other hand it's not such a bad idea while I was preparing for this talk I went ahead and took a look at the code bases of Scala 212 4 and re 0 for 0 RC 1 the latest releases of the two major compilers for Scala and as you can see they're huge so if we would want to do some fundamental experiments like say change the representation of STS this is basically a hopeless task and such a big codebase and we believe that by starting from scratch we have unique possibilities to explore another ground rule is to start really small so instead of yeah you know you can imagine so here at Twitter we use Scala very intensely we have millions of lines of code so you would imagine that I would want to support parts of this code as soon as possible but we decided not to rush to implement a lot of features right away and instead we've come up with a small base line of language features we call this subset of scale a reasonable scholar and this baseline it will provide a solid foundation for our performance experiments for instance we would be able to add one single feature and then see how this affects entire come to a compilation speed and this is actually reasonable this is not some pipe dream because now we have this tool called Scala fix which can do automated called rewrites so we believe that we will be able to use Scala fix to downgrade normal Scala to reasonable Scala and as a result to be able to experiment on huge code bases and make our roadmap relevant and so finally this this idea to start smooth it had an unexpected benefit in October due to some reasons experimentation more experimentation we rewrote almost the entire compiler so in less than a month we've been able to get started this is pretty nice I think and so finally this is something that a lot of people were worried about when a couple months ago we announced this project we really really really do not intend to compete with scholars your diary instead with your compiler as a complementary effort so there are teams that wideband then that API fell hard at work pushing the boundaries of Scala and it would be crazy to try to compete with them as a result we wants to do our experiments in this small control setting and then provide insight that they will be able to integrate in their compilers if they decide to so you know if at some points say Adrienne from wideband was to our best ideas I would be super happy oh my god this is this is the best outcome for the project all right now let's talk about status enough of this preface I've been talking about the implementation that we hacked up over October so these are some line of code metrics and so here we count whitespace we count comments just like a few slides back we did the same for Scala C and re so our language model as you can see it's pretty modest 1600 lines of code and the majority of the compiler it's actually parsing which we found very surprising so as you can see more than half about half of this number of the total number is tokenizer plus parser and finally again the prototype of the type checker for this small subset of scale that we shows it's is again pretty modest it doesn't do much but on the other hand it already provides some foundation that we can build upon finally something that may be surprising to you guys for now we decided to leave cogent production of JVM bytecode out of scope because we believe that our performance experiments they would be interesting even without that just type checking it enables lots of things including developer tools as a case study for the numbers that will be shown in just a couple of slides we chose an implementation of Ritu so fast implementation of regular expressions it was done in go and then it was ported to Java and then was ported to Scala within the skull of native project so we just took this code and it's 11 K lines of code it's not a hello world by far it's non-trivial but it's simple enough for our compiler to handle why we find this corpus particularly interesting is that it provides an opportunity to directly compile compare our compilation speed with jealousy so there's a you know folklore saying that the Scala compiler is kind of 10 times faster slower than Java C so let's see whether we can you know disprove this hypothesis or confirm it okay I know that you were really anxious for the numbers but they're not one more thing I've been alluding to the fact that we just have a prototype of the compiler so it's been hacked up during the month so clearly you cannot implement the entire skull in it so it only supports a small subset of the language it does not read the metadata I don't know it cannot read the signatures from jars we have to write stops for that and finally it doesn't do type inference so that advanced stuff the Scala is famous for okay now I think we're really ready to see the numbers given all these disclaimers so first of all our prototype turns out to be 20 times faster and then Scala see so these are hot numbers which means that it's equivalent to running SBT constantly all the time so as you can see this 11 K lines of code we can type check them in 33 milliseconds which is about 300 thousand lines of code per second which I find pretty interesting really when I was starting the project I couldn't even believe that we would be able to do that so clearly all the disclaimers about still apply but I think that's a pretty interesting result another point that I would like to make that thanks to Scala native so just like 5 or 10 minutes ago I was thinking Danis for his work we've been able to improve cold startup time so as a result called RSC this is this is when you invoke as bit here when you invoke Scala C from the console without keeping it in memory it's more than 10 times faster than call Scala see that's pretty impressive and as you can see as you can see a 300 milliseconds it's not much so the first time when I was testing that when I wrote the first first version of the type checker I ran it and it immediately finished execution I was like no no way this is going to be a bug I mean it doesn't do anything but no it really does stuff so that's that's a pretty intense experience and finally I was talking comparison with with the Java compiler and as you can see again all the disclaimers apply RAC currently type checks Ritu s two times faster than Java C compiles v2 j so clearly Java C does more work but on the other hand it shows that we can have comparable performance yes please also whatever C type check means is that how much time it takes for our C to type check this code base OB this one this one what it says that code generation is out of scope here yeah that's right so as I said this claimers do apply okay that's a very good question what we're doing is just resolving names so something that's that's required for producing executable code or for for powering go to definition in IDs so we don't do type inference we don't do implicit inference this kind of stuff all right so this is it number wise and now let's talk architecture let's just go through a couple of examples that show how tricky Scala type checking is and let's see how scholars see Dadi and the receive handle this this problem roughly speaking you could say the type checking consists of two parts first of all we compute the signatures for instance for method foo that it returns you know class foo and for method B dot C that returns C and afterwards you go through the bodies of the Scala programs and then use this information the signatures that you've computed to do name resolution and type checking all the stuff that we've just been discussing so for instance during the second phase of the type checking the compiler sees B dot C and then it remembers that it has a signature for B dot C something like that so this this becomes trickier because Scala admits legal circle references between for instance we can have a Class A that returns something of type B and we can have Class B that returns something of type A so it's it's not as easy as just ordering these classes in some lexicographic order or you know doing any kind of sort you wouldn't you wouldn't go far just with that you know idea then the next step you know that there can be more and more complications including you know inheritance so what if we extend something now we need to resolve this name we need to account for inherited members what if we do wildcard imports so this gets hairy very very quickly and we have the question how do we worth their computation of these signatures and type-checking of method bodies so that's a big problem what's colossian dolly does they split this process into two parts something called the name ER which does signatures and typer which does the type checking and the trick here is that name ER is lazy so instead of computing signatures immediately after the corresponding method or value type is discard scala c and daddy they just create a lazy stub and move on and afterwards when the typer actually requests the signature for instance in our example that would be when the typer goes to B dot C then the lazy completer triggers and if we need to do more completions for instance to understand what the reference to Class C means well so be it unfortunately even though it's a nice trick and laziness is clearly you know one of the first pages in a functional program in one-on-one it also has its downsides well first of all when everything's lazy is really hard to understand what's going on so it's impossible to just take a look at the program and say oh it will be type checked in this order as a result debugging compilation performance it's quite hard so a lot of smart people have been doing that and it's just hard but the worst thing about this about laziness is that this map makes it very hard to parallelized I've shaken so laziness it involves global mutable state and as we all know global mute state does not work very well with the multi-threading actually I know this firsthand because back then at EPFL three or four years ago we were trying to make runtime reflection thread safe so we spent a couple months on that and didn't give up we just inserted a global log okay clearly that's not gonna speed up scala compilation and so what we do in RSC this is something we were inspired by the work of Greg because a Kowski in his Kentucky Mule project we think that we figured out how to do a single eager pass over the code so basically as I mentioned before it's really hard to order computation computations of signatures and type checking and so Scala seek and the bells out daddy does the same but I think we have found a way how to compute this order and then follow up on it and let's just have a really quick example where I'll explain the basics of the algorithm and the details are available in the documentation again we're looking at the same thing with a method foo that we need to type check and with all those circular dependencies and all those complications so here's how RAC will handle this first of all we do something called schedule so it's not a phase strictly speaking it doesn't Traverse all the trees it traverses just parts of the trees so the things that are highlighted in blue they will be processed by schedule so the compiler will discover the global definitions and then it will somehow figure out and we shorter to process them the next step is a phase called scope this is where we handle circular references so we believe that in order to make completers eager we just need to handle circular references created by inheritance and imports so as a result these things that that are marked in blue here we process them and just them and the rest we can do in parallel so that's that's the wonders of this algorithm and also something that Greg alluded to in Kentucky meal so the next step is called outline this is where we compute outline types which is an approximation of method signatures so the things that they marked in red they can actually be computed in parallel so you can just go and spawn four threads that would probably be very wasteful because why do you spawn a thread to just type check a single identifier but you get an idea so the previous steps they build enough information for this to be possible and finally after all those signatures are computed again we have a lot of red this is where we can do parallel type chicken and this is this is a major contribution of our work in RAC all right so this is I understand this is a lot of hand waving but on the other hand they have just a couple minutes or one minute oh my god it's good that mo is there so we are here at the final slide to sum it up what we've seen we have a really fast type checker for a small subset of Scala it's a prototype so remember that this disclaimer slide but I think it already provides very interesting insights into Scala compilation performance so if you click that link you will not see anything because it's all closed source but I'm going to remind you that real quick alright that was fast okay enjoy [Applause] [Music] what's the purpose that's an amazing question and this is what we'll be figuring out in the near future so what you see is a you know the first version that works we didn't do any micro optimizations or anything but now that we have it and it's about 5k lines of code we can study it and answer the questions like this [Applause]