SF Scala: Grzegorz Kossakowski, Limits of Scala's Typechecking Speed

SF Scala: Grzegorz Kossakowski, Limits of Scala's Typechecking Speed

Recording: SF Scala: Grzegorz Kossakowski, Limits of Scala's Typechecking Speed

[Music] [Applause] thank you Aleksey for inviting me and thank you land up for organizing this Meetup I'm going to talk about a question that's been very important to me but all right so the question that's been important to me is like can scala go faster and specifically where Scala compiler can go faster and like what's the limit how much are we living of on the table right now and as I was thinking about this question I realized that the search for high performance compiler implementation can have two outcomes either there is a fast high performance compiler implementation that I'm looking for or maybe Scala has a design language flaw that prevents from building one it just thought you just can make it the SKA has been released in 2004 but it's real popularity right started in 2006 with Scala 2.0 release by 2012 as people were building larger projects and adopting skullet at companies the compiler speed became the top concern over the years many efforts went into fixing this problem I work in the redesign of zinc which is the incremental compiler for Scala there's a piece of software that figures out what to recompile in your project when you make a change and the algorithmic redesign led to like 10 to 50 ex improvements on large code bases and in 2018 a lot of people in the sky community liske compiler performance still as a top priority during my work and the incremental compiler I stumbled upon bread Victor's talk inventing on principle and it was a real revelation for me breaths talk was overflowing with idealistic ideas on programming should be done and they saw a deeply compelling case for this principle that he talked about where you make when you make a change in a program you should see the look experience the effects of it immunity and that consequence went much deeper than just saving time it just changed the way you program and after watching it I want to tell all of my friends about it and I started to wonder why I was working on a programming language it was so far removed from what I saw and did I work in the wrong cause the 2000 C 16 was the Hubble year for me that's actually the time when I pick up this this tile of outfit that I am wearing today in 2016 I don't have a purse cycle to worry about or like a paper deadline and in that year I interviewed I happened to interview with Facebook and I talked to a hack team and learn about their type checker project they have a project internally the handle static checking at the scale of tens of millions of lines of code it's massively parallel and distributed and now I became a hopper with a plan I started the Kentucky mill project with the goal to explore the limits of compilation performance instead of abounding the ship and going for JavaScript that read Victor using his talk I had an ambition goal in mind keep the best of the compiling run and make it so quick that it feels magical and while I was a hobo I still didn't want to waste my time on a hopeless plan so I ran an experiment I generated simple scale and Java code side by side and except for language differences they look the same and in in the code I stay away from scholars rich type system features that are normally attributed as a source of slow computation time people say scholar compiler is just solving harder problem and so I compile both and compare their execution times on the chart you see a wide gap between the two compilers and fundamentally both are solving the same problem the problem of the same complexity on the on the x-axis here you have number of classes generated of this shape so Scala compiler is six times slower than Java Java 1 and whatever Scala compiler is doing it's a waste this it's just a simple experiment but it if you didn't reveal anything dramatic it will be harder for me to convince myself that I'm off promising start so why am i experiment shows that there are potential gains in the single third performance I thought that the real riches are in weight in the world of parallelism and people working on the on programming language programming language is considered parallelizing compilers to be extremely difficult it may be like impossible to solve as a problem but the hack team building a non-trivial type checker with a massively parallel and distributed architecture interestingly they design the language enabled adding architecture so we can reframe our so kind of the new question is can Scala have a highly parallel compiler and can we borrow hoc ideas and can we do that without dramatically changing the language so ok so we want to build a highly peral compiler if you plot the time across the pipeline of different phases in the compiler you see one standing out which is typer this is the heavy heavyweight face that takes roughly 30 to 40 percent of the total execution time in the compiler it's also the most difficult one to reason about and will on it so this is the final architecture of a type-checking we're heading for and oh boy it's like a lot of going on in this slide so I'm gonna unpack it and then the goal is to stack as many boxes on each other that's the measure of parallelism we get and you see the parsing face on the far far left and which is trivial to paralyze you just parse service files independently in parallel then on far right and you have massively parallel type checking of your implementation of your metal bodies and that part depends on the stuff in the middle that I'll get back to for comparison this is the current design of Scala see it appears to be simpler but the picture is imperfect so can our complexity is packed into like what in software we know as a big ball of mud and what we have done in the previous slide is we have carefully broken up hidden complex into small manageable pieces so when I asked my friend does research in programming languages why researchers do not spend more time on parallel architectures for type checking she cut me short with it's a massive data dependence problem and I'm now getting at the core of it let's suppose we want to resolve a type team in this little example we we first asked is type T defining class B now is it defined in Class A yes is right there underlined so we got it now let's change the code a little bit and still have the same task we want to resolve type T I made a mistake so you guys we remove that declaration sorry so we want to resolve that I pretend it doesn't exist we want to resolve type t we ask if it exists in Class B it doesn't we asked if it exists in Class A it doesn't but we see there is an import with the wild card so we want to ask whether the type T exists in C but what is C so first we need to resolve C and again we go and ask is C defined in Class A it's not but we are declared in package objects so now I kick off global search for C and I see I see C defined in in packaged food in the other source file so now we have a handle on C and we can ask whether T is defined there and we resolve T to that declaration over here and and so that's kind of the shape of the problem that compiler is solve that's one of the many problems they they solve and we we can start untangling our like messy dependency problem by dragging codes to sides and drawing a dividing line between the two columns and the idea is you separate definitions and signatures they go on the left and implementation goes on the right and we'll call the the the interface of our program the skeleton and implementation at issue at muscles and the definitions hang on the skeleton they're attached to specific P points in in in skeleton where we're signatures of methods are so yeah we have skeleton on the left and we have little boxes for the implementation on the right and then the P R are a pink arrows represent dependencies so there is one property important property that dependencies go from the right the only cross this line and go to the left they don't cross reference here and then the skeleton is more tricky it has self references so types can refer each other signatures or refer other types yes there was the question yes I also the next sentence coming so for now we assume there's no type inference for method signatures as types are returned types for metals are set okay so we have one win here that we kind of divided decompose the problem into two big components type checking of this side and this side and then the problem with the skeleton is that it's expensive to compute in Scala and frankly in any other modern programming language so we have to paralyze the computation of the skeleton itself and it's it's a tricky problem because the the pieces of the skeleton our bones if you will can cross reference each other and that problem doesn't exist in hack that's one of the design decisions that they made over there that it's like these arrows exist but they're very easy to work out in Scala they can be very complicated in order to avoid a threat contention I would like to figure out the order in which to pre-process all those pieces upfront and this problem sounds silk is South Circular at the outset like the order is dependent determined by the dependencies in the skeleton and and those dependencies are only available when we compute the types and we actually want to compute the types so to break that cycle I came up with the notion of outline types and the idea is to approximate the real types with the very simple types that are similarly cheap to compute and capture dependencies they are good enough to just capture the dependencies so once outlying types are computed they give you in kind of Ikea style assembly manual ha for building up our skeleton outlying types give you a manual that tells you the order of bonds that you put together so let's go but go back to our architecture the computation of types in the tissue of the program is on the on the far right this is the kind of the muscles that we're computing here in the middle we have the computation of the skeleton and you can see many small boxes arranged in the order of arrows that we computed as our assembly plan and and then there is small box over here for outline types and this computation is not possible to paralyze but the bet is that it would be so quick to compute that the whole scheme will make sense and fast enough me or keep enough here means is that this little box is faster to compute order of magnitude faster to compute than the rest and and we would like in the end what we are aiming for is we would like to avoid this comical situation where we spend more time figuring out the plan for assembly than just building the thing so outline types are stripped down to their essence they are only concerned with signatures of classes objects type definitions and vowels I cut everything non-essential to computing the dependencies and outline types for example do not support a subtype checking which is weird in a programming language build around subject checking and there purely structural they they are so ugly types are so stripped down that initially it's hard to imagine that they can sustain Scala's complexity like the weight of the complexity and I had no idea whether this will work out and will be fast enough to compute but I was eager to find out and I went on building contactable project so as a proof of concept I decided to process scallop II which is not very well known project but tiny self-contained it has 200 thousand lines of code and so it's small enough that's easy to prototype on top of it to just process the code and it's not too small to be completely trivial and from the first line of Kentuckiana code like the decoding style I adopted was performance paranoid at each step of implementation I was very carefully measuring the speed that that that I was getting and the performance numbers initially look great I establish a baseline of processing four million lines of code per second it's just like compared to what we normally observe the kind of regular performance is 3,000 lines of code per second for compiler it's actually very good so that that that numbers was amazing so I knew that the the numbers I got so far were purely for validation whether my ideas like has likes to stand on it if that didn't work out like there is no point in investing anything more complicated but obviously there was not a representative sample so I went on more ambitious a kind of input that would include the language features that I suspect it will be very difficult to implement it in outline types and I felt they might be actually the potential breaker but deal-breakers so the next task was to beat deal-breakers head-on I picked our standard library as my input as a test case and I listed our language features that I need to implement starting with like a really great performance and my predetermined list of 21 features I went on implementing them and I won I not want to show you the result right now oh yes yay it's fine going to the right the trick is I don't see this on my screen I'm gonna turn around for a sec okay and it's good enough so yes we have attacking or running here and kind of division of where I'm going with Skylar Skylar's population performance is this even every keystroke we process thirty thousand lines of code per second all right sir we process 30 lines of code and you can see kind of the feedback loop where I'm doing some analysis over there kind of like global analysis of dependencies and for example if I introduce a cyclic dependency as a list inherits from sequencing here we make sequence we inherit from list we find that cycle and takes 104 milliseconds to find that so that's where I'm going with the compiler performance that's kind of where I long term I like Scala to be and if we type right yep so that's that's a living proof that this idea not bread but like what you saw we have to figure out how to go back to my talk yes so yeah in this demo you saw that it works it actually processes a very complex code base it takes 200 milliseconds to do the full analysis of 30,000 lines of code and that's a bargain for the assembly plan and inspires a great deal of confidence that this overall architecture actually can like pan out so now I would have to I would like to switch gears and talk a little bit about low-level bits so internally compilers often have a concept of a type computer and it's a function that from unit to type and it's a lazy computation essentially and recall the big ball of mud that that we saw on a slide earlier and and it's messy dependency problem because the order of type checking is not known upfront the way people deal with this in Java C or in Java compiler Scala compiler even Swift compiler is that they set up a set of LASEK computations and just let laziness to figure out the order and it's a it's a very kind of good technique but it comes with a set of downsides that I observed when I was working on Scala compiler it's essentially what what we do is we perform a deeply recursive depth first search throughout the graph of dependencies and what does this lead to is this different goal to attribute the difficult attribution of the cost so if you're looking at piece of code and trying to understand this performance characteristic you never know whether this is slow or it just happens to trigger a long chain of computations like lazy computations it's very hard to reason about this the other problem is that this deep recursive call Col chains are very unfriendly to JVM profilers so most of the tools that you use for understanding performance are out of window and lastly there is this problem that some of the types you load are coming from binary files on this browser like your external libraries and these loading these types is also done in a lazy manner you read couple bites you go back to type checking use this information figure out that you need more information go back to reading and and you kind of switch context back and forth and that leads to i/o thrashing and these pain points made me consider an alternative abstraction I came up with the notion of interruptible type computers inspired by cooperative multitasking it's the Niq for culture flow that was used in Windows 3.1 for example and the idea is that the computers are tasks that return a data type or yield the control back to the event loop if they are stuck on the the some dependency that hasn't run yet and then the control is returned to the event loop with the information what the complete error was stuck on like what's missing and once the dependency that missing dependencies satisfies satisfied the the scheduler will rerun this computation that's kind of the basic idea so in this scheme tasks are organized in a work queue and tasks are isolated from each other so they lend themselves to very simple performance attribution you just look at the tasks and that's their cost you we don't have the deep stack traces anymore we have shallow stack traces which are excellent for JVM profilers and we have now the freedom like for scheduler we can just ask assistance programing friend how to implement it and and the this idea is actually one single idea that I wanted to decouple the dependencies dependency discovery from dependency computation these are now separate in the old scheme when you trigger lazy computations there like as soon as you run into your dependency you go and trigger the computation and I reset recently came across this quote on spacecraft design and it actually could have clicked for me in software context and in software like all software deteriorates over time for a variety of reasons and compilers are not immune from that problem and the only thing that kind of prevents from collapse are good interfaces so the this simple idea of cooperative multitasking actually have has a far-reaching implications of by changing this the interface that can unlocked the application of decades of systems programming research people have thought about work use and schedules for a very long time and I had a profound aha moment when I learned from my systems programming friends or actually friends were sitting here in the audience that there is a very simple low overhead scheduler on scheduling algorithm for these interrupt from completers that it's a parallel scheduler so the computation of outline types themselves can be paralyzed and so there's one little box in my architecture slide can be actually broken up into smaller boxes and I was very surprised by that finally I would like to talk about it I'll make one point on on tactics so there are two ways to go about finding a fast implementation of a compiler for you can first implement our language features and go and implement our compiler phases and then start profiling and optimizing that's kind of the classical way the other way is to implement a tiny subset of language features let's say what language is supported in 70s and you implement that that set of features end to end you have actually working compiler and you want a great performance of this very small core and then you iterate over language features under this constraint of defending the X and performance you already have and and I like the second method more because the search space is simpler I each step I know what language features I'm missing yet to implement and each step is pretty small and I'm losing a performance for whatever reason I can back off and figure this out in the with the common approach you have this complex system and you're trying to poke at it and it's basically shooting in there you maybe figure out some inefficiency or maybe not and it actually quickly becomes demoralizing and that's one of the reasons why in Scala C is not improving its performance just you never know what are you like if you spend one more week more in with the profiler we like find something or not and then your boss comes and says like maybe you should switch gears to something else so it's time to wrap up so are we up for like another for a rewrite of Scala compiler and conveniently we have one rewrite at our hands called dory so recall the experiment we started with where I presented you a chart a performance chart I added dotty as is this blue line inland it's a fresh implementation of Scala compiler it lands exactly the same place as color compiler and I rerun this experiment on non-trivial code bases on the kind of actual projects it's kind of it's actually astonishing how close they come together so it's not about rewrite I believe that Scala compiler performance is the hard problem but it's also a solvable problem and my proposal is to re-examine the implementation break down the build big ball of mud into phases with the intent of parallelization pick interruptible completers as this basic building block and this interface enables decoupling and unlocks those opportunities of borrowing great ideas from systems programming community for performance and lastly start with a minimal end-to-end implementation iterate over language features and defend performance at each step thank you and I will have to run in like ten minutes so I'll take questions oh yeah I forgot I forgot to get back to that point the answer to this is basically the idea is that here you work with the assumption that the global resource which is the skeleton is fixed it's pre computed already but they're infer types I break that assumption so you insert a little ugly face here that says whatever infer types I have here I will like leave holes and then I fill out those holes here and that phase is sequential and the idea here is that if you have like you have one lever as a user of a language to kind of pull if you want more parallelism and notate your types if if you don't want to annotate then you kind of fall back to sequential execution yes thank you [Applause]