Player is loading...
Double your performance: Scala's missing optimizing compiler
Li Haoyi, author Ammonite, Mill, FastParse, uPickle, and many more.
Wednesday, June 12, 2019 · 2:30 p.m. · 46m 36s
The JVM runs impressively fast, and Scala has reasonable speed, but you still need to contort your Scala code to reach peak performance. Whether turning for-loops into while-loops, manually fusing map/filter/reduce, or replacing functions with macros, these changes are tedious and error-prone. We present a new compiler that does this for you: taking high-level Scala and running it with optimal JVM performance. We explore how even high level concepts like monadic interpreters can be optimized into zero-cost abstractions, giving real-world speed-ups when applied to real-world applications.
Embed
Transcriptions
Note: this content has been automatically generated.
00:00:06
yeah
00:00:07
okay let's get started um hello everyone so my name is howie
00:00:11
and this part is going to be about how and optimising compiler works
00:00:16
um so would the number of optimising the scalpel system you have the skylight yes up to my theories criteria marked miser
00:00:22
you have the javascript how uh of the compiler you have
00:00:25
the data compilers colour l. d. m. up the miser um
00:00:30
and the question is if you want to write or not the miser how would you do that let's say anyone of you want to
00:00:35
say i want my own scallop the miser how do you write you always got up to my that to do useful optimisation it's um
00:00:44
so for most people the of the my that that box so code coding line and and faster code comes out the other
00:00:51
the go this talk is open up the black box so all of you can have intuition behind
00:00:55
up the miser works you will not have a total understanding because that takes a lot of effort
00:00:59
well if you have a sense of these are the kinds of techniques algorithms and data structures they're
00:01:03
going to adopt a miser there are enough to make it do useful optimisation is in your programs
00:01:10
so i'll myself um i've often hear data bricks so they that makes a lot of interesting work you also
00:01:15
already knows you know this morning it'll cool stuff local technology and all the cool customer problems that is holding
00:01:21
so we're hiring as offencive them an entire so if you got
00:01:24
a looking for a job in come talk to us after the presentation
00:01:28
um i also maintain a large amount of open
00:01:32
source cannot tools so who uses one of these tools
00:01:37
more than i thought okay so i'm glad you liked them um
00:01:42
but this talk is not going to be about either the the bricks or might open source of projects
00:01:47
rather than going to optimising compilation in three steps first we can handle to my
00:01:52
some source code in all the see what kind of of my faces you can do
00:01:55
second we'll talk about how to pull a tool can model the program in order to achieve those optimisation so
00:02:00
and lastly we'll see how we can make an automated tool actually perform the
00:02:04
same up my seasons we did by hand but automatically and not too difficult manner
00:02:11
so for us let's talk about hand optimising some source code um
00:02:16
oh so this is mostly the dallas source code um i'm using java throughout this top because it's
00:02:21
um it's a common language ever knows about the it compiles
00:02:24
totally straight forty two is by code and stand on the con
00:02:28
but still to this report lead to jobless all of you should be able to roughly read this in the what's going on
00:02:33
um so we have a main function takes an argument perform some computation logging returned returned value
00:02:39
um for now the signal with the fact that this function doesn't do anything actually useful because after my that with
00:02:45
this the dakota not question your business to and so we had this piece of code how do we optimise this um
00:02:53
so first we notice well this law directly are is not actually a logger is
00:02:57
a pretty lauder i mean though that because the right hand side of the um assignment
00:03:02
because we know that revolver this lower the log function call can only go to
00:03:06
one of concrete implementation which does is another print line so we in line that
00:03:11
next we can see the multiplied variable although it's assigned then
00:03:16
updated throughout this loop is assigned here and a big that here
00:03:20
it always you mean zero because that's of israel and the only updating it by multiplying it
00:03:25
so we can consider folded and say well everywhere multiplies you is just put
00:03:29
zero and don't even bother with this multi byte variable so we simplify like that
00:03:34
lastly optimisation is have left a bunch of code unused or dead so does lauder is not use
00:03:40
this ackerman call is not use this whole bunch of classes are not use we can remove them
00:03:45
um this it condition zero lesson hundred always good to be
00:03:49
true yes you move to check and just directly perform different line
00:03:53
um and to to all these document calls calls of ackerman
00:03:57
function have constant inputs that was one actor man to into
00:04:01
we'll always return seven that's just definition ackerman and you can evaluate yourself using this definition if you want
00:04:08
uh look at the table indicated yeah um the second one ackerman view and and
00:04:12
you can look at zero point zero in here i see i commend zero and always returns
00:04:17
and that's one over here three to four and that's one here and simplify the code for
00:04:23
lastly we can look at the last called i command and then
00:04:27
count which you cannot partial evaluate because both inputs on that one
00:04:31
we can see that this function if your it does not have any side effects about twenty logging
00:04:35
and it is only use within the body off if conditional block
00:04:40
so because when you've if condition you can lay schedule it into the body of input if condition
00:04:44
no so you never get computed unless actually is necessary so this
00:04:50
is what we end up with after don't follow up my stations
00:04:54
so off contact because one multiplies go on if they must go on to cause ackerman have
00:04:58
been either completely evaluated the partially evaluated and last call has been only scheduled into diff block
00:05:05
so this is the simplified code and you can do is automatically because many of these organisations i
00:05:10
just showed you x. e. v. mechanical you look at this this is always you remove it look
00:05:14
at this is only used it a movie late the this is always this ackerman call these are
00:05:18
the same inputs just evaluated put the results um so i can write a program to do that
00:05:24
um so what you're a it was so small demo i have with um here is the same code
00:05:31
that we saw earlier so isn't entirely jed wrapped in a class 'cause down i want to do that
00:05:37
um and what you are at the compiled version of the same
00:05:39
code um so this is the compiled using intelligent so all the um
00:05:44
local variable names like on but has more or less the same logic receive are three lesson hundred bar
00:05:50
bar forgot log agreement to to agreement are three part zero so this the
00:05:54
compiled was in the java compiler doesn't really do any heavy optimisation up front
00:05:58
so all of the code your is at almost as if we wrote it directly
00:06:04
so what you are i have a little optimise program c.
00:06:08
up demise as eleven megabytes of program and i can run
00:06:13
up demise on the source for the good destination folder and what
00:06:16
of method i wanted optimise us demo main picture in pretending integer
00:06:21
so you run it it turns away a bit and now it's without compromise demo class file
00:06:27
which i can get more there how do i make this bigger f. one o. r. that's not it um
00:06:45
just use your finger the correct answer um so yeah we have
00:06:51
the optimised version converted using is optimised tool i mean it's yeah then on most all the same up migrations
00:06:58
the first called ackerman as you pull evaluated the seven the second called
00:07:01
actor actor men have been partially evaluated and plus one the variable names
00:07:05
like on so called r. zero but it's the same as in we
00:07:07
saw earlier as argument um the if statement here was removed a lot
00:07:12
call has denied because you know exactly what the target uh by the destination
00:07:16
method is and the last cold ackerman has the in late scheduled input if conditional
00:07:22
um so this is not quite exactly zero to before one it's the compiled code to look slightly or
00:07:28
to something that's not quite clever enough to figure out yet for example this them all up
00:07:32
rely so hanging around being useless but overall imagine to almost all optimisation study done by hand earlier
00:07:38
so how how this eleven megabytes about demise going up to my south dakota
00:07:43
to perform all these years what limitations as without a program that can run have the same output i run my slides
00:07:53
well my slides in a
00:07:58
present and okay so you know the answer that question for somebody go to howie model the program as
00:08:07
a program inside up the miser devoid talk about how use that model in order to make inferences endoscopy migrations
00:08:14
so there are many ways and watching a program perhaps the one that most people be familiar with is as source code
00:08:20
so here's the agreement function we saw earlier as source code so source code should be familiar with
00:08:25
most of you that's what you right that's what you read in class or you go to view
00:08:28
but source code has some and fortunate properties the biggest one is that contains all sorts of um
00:08:34
miscellaneous information this isn't really relevant to execution a
00:08:37
program so all of these three are the same program
00:08:41
and if you want to you can write java like python is a subject that um but if you want to write for example something with
00:08:47
the reg x. not and like the source code to figure out what needs to change what the source code as it stands we very error prone
00:08:53
you can do it but tools that use reg access on source
00:08:56
code into requires you when oversight for example things looks code module
00:09:01
which you would run code more seed every factoring the did you review yourself to make sure that something sensible
00:09:07
so that's okay for a factoring tool maybe not okay for automatic optimise uh
00:09:12
the next thing that we look at is abstract syntax trees so
00:09:16
abstract syntax she is basically take the thing that you parse out
00:09:20
of the source code as a hierarchical tree structure and give it to you to work with so here's abstract syntax tree of the um
00:09:27
of the ackerman funky we saw earlier because it laid out is a diagram
00:09:30
of the tree and you see more this matches the hierarchical structure audio source code
00:09:35
so it be these are much more competent without source code and
00:09:38
many compilers use abstract syntax trees especially different tenses that's what they're really
00:09:42
front end gives you the parts that will give you abstract syntax tree before we can do anything else to convert to try that separate
00:09:47
representations all compared it to output um
00:09:52
so the probably abstract syntax trees is that they're pretty fragile in that
00:09:58
you can have many different abstract syntax trees to have every fourth exactly the same program
00:10:02
and not even it's not even very difficult to do this so here we have agreement a ackerman be both parents and i commend function
00:10:09
and it will reflect the same program has already know all three have different abstract syntax trees which may seem obvious but you can see here
00:10:16
we have this assign p. q. all that against having to replace that link you and
00:10:22
here we have a sign r. n. s. all identifies every be replaced by our yes
00:10:26
even though when your c. p. u. is running that we know intel i
00:10:28
nine see few is turning to your executable doesn't care what you call your
00:10:33
um identify as in a local variables or whether moving the back and forth so
00:10:38
this exact indexes that you had what with because effectively what you have here is your but she
00:10:44
is she had jesus i know it's these p. and q. identify no it's
00:10:49
when you know even those know what that no does look at contents so if else
00:10:53
you'd look at because because return if else because you go things look at q. and zero
00:10:58
but for q. you can just look at the content that you don't know anything about
00:11:01
you because q. itself is meaningless is simply reference to this assigned to know it up here
00:11:07
effectively what we have is a directed graph that happens to be
00:11:10
embedded within our tree structure using these referent references of assignments and identifies
00:11:17
this is the idea will come back to later i next representation we look at is
00:11:21
by code is the thing a java compilers gets out when you compile it into binary
00:11:25
so on the right of ackerman function same as earlier on the left of the byte code evelyn a set of instructions
00:11:32
by good works by executing top to bottom and each instruction either move something onto the stack
00:11:39
does code executes on the things on the stack for example maybe
00:11:42
adds two numbers on the stack we using one number or maybe
00:11:46
return the last someone the stack or it take something on the second puts a back into local variable array which is over here
00:11:52
oh this function at a local variable so the only local variables of the two input parameters which kind of makes sense
00:11:57
okay i get is that getting big and small that it puts things on in computing the pop stuff off so
00:12:03
the big problem with looking byte code is that working with byte code is pretty difficult to modify
00:12:08
um so he'll let's imagine we wanted to replace the ackerman function
00:12:12
the and ackerman call that and with the second ackerman to function call
00:12:16
and that's it doesn't take the first parameter we only one second parameter why going to do is
00:12:21
that signal for now as i say we want to modify this function in out relatively straightforward way
00:12:27
so you know to do that to but could you only have to replace the instruction which is down here with ackerman sacrament too
00:12:34
you also need to trace up the stack to see where the the variable that
00:12:39
is the first parameter came from remove that instruction look at
00:12:43
with that variables in input came from a remove those corresponding instructions
00:12:47
so even a small change things to require changes or even a small
00:12:51
change your logical program does require changes all over your bike could program
00:12:56
and that makes working back with great difficulty the tiny change reshuffle everything under the tiny
00:13:00
change reshuffle everything um and that's both expensive and easy to get wrong as a programmer
00:13:06
so only with talk of the graph structure of estes that's now talk about the the photographs
00:13:15
so the that'll graphs i basically basically estes but with all the ice
00:13:19
assigned identify appear as ray fight as fully fledged edges within the syntax tree
00:13:25
so he always you have after man ackerman a ackerman be the three representation
00:13:29
three there is you had earlier that we know will do the same thing
00:13:32
and you all compiled it the same a. s. d. which is here represented
00:13:35
with it and going directly two plus two equals equals into minus his case
00:13:40
um so the yes he doesn't care what good how you're moving variables in all the local variables or moving
00:13:46
them into on the on the expression stack that the a bit but it the photograph only cares whether right
00:13:52
where the value comes from and where the value goal is um
00:13:58
so in the data flow graph it it's inputs instruction as simply the incoming edges to destruction
00:14:03
so in if you're do modification that replace actor manufacture meant to in this uh data flow graph
00:14:09
you replace the no would i can recommend to look at the edge that was of us it's got
00:14:13
input remove it as if we remove ups you edges and their corresponding the woods from the data flow graph
00:14:19
so what good data flow graphs basically every node in
00:14:22
the graph which is instructional program is executed has direct edges
00:14:26
from its inputs and direct edges to the places where it's output is being used
00:14:31
to the fact that have their edges to basically everything the node cares about makes it very easy to
00:14:35
work within that would put an allied it ought to modify it if you want to change during optimisation
00:14:41
this description is greatly simplified so there's a lot more detail on control flow and on matching of state
00:14:46
our our n. x. actions and it only returns that we're going to for now but we can talk to about later
00:14:56
so we've talked about hand up the writing some code we've seen optimisation can do the scheduling in lining
00:15:03
a constant folding we've seen a a program can do that automatically on the piece about code
00:15:08
and we've looked at different ways in which you can model our program as a data structure it to work with
00:15:14
so the last section of this talk will go into doing the inferences optimisation
00:15:18
to actually perform those optimisation is given the data structure that we're constructing a a
00:15:27
so the first one will be type inference and cost constant folding
00:15:32
so in fact inference involves a bit inferring constraints about the values in a program
00:15:37
if you have a have a variable x. what sex is it
00:15:40
interesting is an area that has a considered multiple possibilities is something else
00:15:45
what you know about this variable x. can tell us what you can do
00:15:48
to change the program for example if you know the verb accessible certain types
00:15:52
then you can check any you think about any as instance also is o. k. removing the edges and solves that ah
00:15:58
redundant or you can convert any is instance also to either true or false and probably get
00:16:03
those to to to remove if statements to do what hans unfolding and other thought about the migrations
00:16:08
um i don't know if the more things that you can in for about the program the more optimisation you can do
00:16:14
so at optimising compiler because of the mice at two in for as much as possible and optimise based on though that those facts
00:16:22
so talking what type inference tax i usually model is a lack this so here the
00:16:27
simplified type that is any integer time sequences as you watching builder and every of floats
00:16:32
um so let you know that is if you have two things of different types for now we'll just
00:16:38
say that we're going to take the common super type of those two things at the type of the value
00:16:43
so the five of it uh if a variable x. which is i the sequencing builder is the time sequence
00:16:48
if of a variable x. which is either integer or string we'll just call the any for now
00:16:52
um so you can do this union tax another way the modelling it before
00:16:56
now this simplifies it for this discussion i i'm modelling singleton types like this
00:17:02
which are basically constance is also straightforward and integer can be zero one two
00:17:07
or any other integer a string can be any constant knowing value of the string
00:17:11
um and he basically that any other types in your program so it haven't is either zero and you can
00:17:17
as humid in the journalism is either hello already teachers string hello or string delay due to start sequence and so on
00:17:24
so singleton types really or just any other types with more specific our information about the value being described
00:17:32
so let's go to inferring values on the data flow graph so
00:17:36
here is the data flow graph for the simplified version of this um
00:17:40
simplified version of the minute that we looked at earlier so i removed a bunch of stuff that we don't care about for now we have
00:17:47
discount because the remote place you go you go zero while convalescent input and
00:17:51
it modified doesn't hundred a lot something increment count multiply multiplied
00:17:55
so there's a loop here which makes a program bit cyclic and so you end up
00:17:59
having a bit of a cycle in the data flow graph which is quite a bit messy
00:18:03
i'll walk you through this last so we can understand what's going on a first we start off at the top of the function
00:18:11
in dogs euro um we say what we look at this and see well it's assigning
00:18:15
zero to multiply zero to count so i can assign these two inferences zero and zero
00:18:22
next next block that executes is this count less than anything
00:18:27
and this is a check whether to going to if you go to the y. look what does exist and go return directly
00:18:33
so that's highlighted here in the data flow graph and i know the n. is an arbitrary
00:18:38
integer because like it's input parameter do not it is and i know county zero from earlier
00:18:44
so i know it less than of between arbitrary integer n. zero is arbitrary boolean
00:18:49
if good if statement i don't know what is gonna go do an if statement by need an light both cases i
00:18:57
for now of the signal block three could you just returned doesn't do anything interesting talk variables
00:19:02
a block one b. adopt one see i i will ignore as well since you also don't do anything to variables
00:19:08
um to simplify it and that's good about two which is you are in the program here on the data flow graph
00:19:15
so contrast because one corresponds to this these edges in the data
00:19:19
flow graph i think discount better than you i added together with one
00:19:24
they give me zero plus one is one and i say that back into account
00:19:29
so what happens i knew i knew county zero now i know count is one count is either zero or one talk is an integer
00:19:38
i do the same thing for multiplied and ice so modify time because count
00:19:42
i take multiplied and count the them into times zero times arbiter integer is zero
00:19:48
i put that back in the multiplied and the look in the commons what type of zero and zero zero
00:19:53
so this tells us that mother after this i and that does not analysis count is integer and multiply the zero or so
00:20:02
we just updated the infrared inferred type of count previously we thought it was zero now we know now we think is in danger
00:20:08
and so when you probably get it probably get a change for what to the data flow graph no the two
00:20:13
update anyone else to midi assuming that count is still zero in this case that to downstream nodes
00:20:19
um there's pass and is greater than or less and um
00:20:24
so count and count as integer n. as integer this becomes a billion is less than a block
00:20:33
because i was already arbitrary boolean before we can stop the propagation that
00:20:36
nothing changed i count which is indeed a plus one into that last one
00:20:41
is the limited i don't know what it is is an integer in some integer and i put that back into account which is now in it either
00:20:49
since we already saw confident in his earlier this does not need to you can stop the propagation
00:20:54
and so we end up with this set of inference as for this program graph
00:20:59
um multiply to zero these times is always zero to the times is the result of multiply times count which is always zero
00:21:07
counties in the the end you're use integer is less than is always a billion is pass is always an integer
00:21:13
so now that we didn't thought all this continue this information to simplify the program quite straightforwardly
00:21:19
for example getting multiplied anticipated zero everywhere it's use elegant tickle the coda computes multiplied which
00:21:25
we know is always gonna be zero as you move that code since you know the output
00:21:30
the removing all that couldn't data flow graph gonna be this simplified
00:21:33
beautiful graph wedlock zero just as one a zero designed is comparable
00:21:38
it goes and if if it meant looks around a few times
00:21:41
implementing want account and then returning something i i didn't specify this function
00:21:46
and this data flow graph can be c. relies on relatively straightforward fashion to this ah
00:21:51
this the program i'm in reality this is easy this year as a byte code
00:21:55
gardens here lies to source code probably the compiler but could you get this source program
00:22:02
so next in a look at is inter procedural inference um so this now
00:22:07
everything was inside one function i had a look said basic blocks you're jumping around
00:22:12
but you're still within one function bodies now we will look at when you're multiple functions what do you do
00:22:19
so here we have meaning and called me in calls called and and returns the result of cold after passing zero and and
00:22:26
how the n. like this we start off with zero at zero energy at the input integer goes into called
00:22:33
inside called we have an ice cold before we can continue highlighting mail because what the input value
00:22:39
of is called node is depends on what the contents of the call function tell that it is
00:22:44
so x. zero why didn't either you probably get that down time to
00:22:50
zero return is zero probably that i got called a zero return is zero
00:22:57
and we're done and we see that this is our final in france where
00:23:01
everything is zero because your times zero multiplied by things tend to be zero
00:23:05
this is a simplified case but the same can apply to other kind operations you
00:23:09
do that constrain what kind that that affect the types that are being probably get that
00:23:15
so now that we know this is zero we can simply make me in return
00:23:18
zero with all this remote role and is optimised program and optimise data flow graph
00:23:24
um i so next bit of fun is that going to look at recursive into procedural or type in france in constant folding
00:23:33
so recursive functions are relatively common within skylark functional programming up because it functions
00:23:39
and maybe for normal programming on normal compiler okay telling people annotate recursive function
00:23:44
but if your if your uh optimising compiler you want to say this because
00:23:48
the function is pure or even though the person didn't annotate it so how
00:23:51
do an ally something if you got a basis of your this is constant
00:23:54
or this is something that's more specific than it was annotated even those recursive
00:23:58
given how many recursive functions are we tend to write in the functional programming style
00:24:04
so let's get this is is a pseudo java version about factorial function um it takes an integer and i guess thirty
00:24:11
returns any it's not real real drama but it's you don't are that they say we don't know what this returns yet
00:24:17
the all the code does not know what this returns yeah we can see this clearly returns an integer
00:24:22
but how do we and lies that um the programmatic fashion so on the right is your data flow graph just got zero
00:24:28
check so that it goes without it is equal to one returns one is not equal to one i subtract one from and
00:24:36
cost and the factorial been multiplied and again then return that and is it because of all the victorian construct itself
00:24:42
so this more that's on the simplest or because it functions come up
00:24:45
with but these things are generalised other because of functions rachel because and
00:24:49
more than one because it call et cetera so we thought of a block one again in this case the forcible feces and double equals zero
00:24:59
uh one is one anything did a double eagle the one integer that we don't we don't know whether it's true or false yet
00:25:05
because it wouldn't really consider both cases so the other two cases easy
00:25:10
we return one so one is one returns one the next case is
00:25:16
more tricky so in the false case we need to pass in one and and into minus so
00:25:21
into the minus one is integer don't which integer um but when passenger factorial what do we do um
00:25:28
disagrees who knows what we do here are a few people not you we do so the this is not
00:25:35
a new technique but is is a technique that's more in the compiler back into another compiler front end field
00:25:40
so what we do here is we say that it's a new type called bottom at the bottom of our type that is um
00:25:47
bottom bees below every other type but other than that it behaves just the same as any other type would behave
00:25:52
and you guys use nothing is colour which is basically the same as bottom and you're familiar with it
00:25:57
so for us i come and okay factorial as bottom so i don't know what it
00:26:02
is it's bottom um and bottom probably cascades so bottom times into just bottom it returns bottom
00:26:09
so bottom bottom bottom next what do you do well now we know that this factorial function either returns one or bottom
00:26:18
and you can look up one and bottom in our part that is and see the least upper bounds one
00:26:23
so these are bonds one i can think this one and place it back into these factorial call actually that because it
00:26:29
call this number is what always return one to one times
00:26:34
the arbitrary integer is arbitrary integer in our times an integer
00:26:39
we can make one more round around this uh type that is what really
00:26:44
suburb on the one integer usable buttons integer put that back into the factorial cold
00:26:51
and feed that back in the times into justin vintages integer and because he was already in video
00:26:56
for the last iteration we can stop the propagation and get done so this is our final inference
00:27:03
of a recovery cause effect or a function telling us every ties into the even though was annotated to not return anything
00:27:09
um it's so you may notice that too if two of the cases we walk to so far we have come iterative
00:27:18
propagation approach we make one pass around the functional one pass around the recursive started because of functions
00:27:24
yeah we have to keep propagating more passes until it's the inference stable rises so in general any anyway
00:27:32
that yeah but do you have a cycling a program without cycle the loop what does cycles are because and
00:27:37
you're going to need to you're going to need to do multiple passes of inference in all the get the most precise inference
00:27:42
on the other hand if your program has no loops and all records and then is it possible
00:27:46
to do one pass from the top prompted logically from the top of the program the bottom and do
00:27:51
get the most precise output um so you know the number of iterations we do is bound that
00:27:59
and not the durations we do is bounded because every time you go around this cycle of propagation
00:28:04
our tax rise when the at least one level in the lack this prototype did not right use of the
00:28:09
propagation so if given the lack this up despite the number of iterations is completely bounded high to the lattice
00:28:17
and if you want to be can control how you can trade off number
00:28:20
of iterations against a precision off precision of inference by making a that is more
00:28:27
or less a detailed for example could easily have a lap this habit separate
00:28:30
notes on on zero indigenous abilities cover separate no it's a positive and negative integers
00:28:36
or that that is good have separate notes funnel or separate nodes for strings of particular length
00:28:41
and all of these allows it more precisely what what of model the program you're in france and in a more precise inferences
00:28:47
but at the cost in that because alexis taller you need require more iterations around this
00:28:52
uh data flow analysis nodded converts it so the last thing i'm going to
00:29:00
talk about is lightness invisibility analysis so light that's in the to the the analysis
00:29:07
are to pay the related things we say this code never runs all this code always runs
00:29:15
but it doesn't actually do anything is outputs not used enough end of the program
00:29:19
and in either case the code is safe to remove and you can do so to me the program show the smaller faster without affecting its output
00:29:26
i um let's look at this last there into the main method which i've mangled in a different way
00:29:33
i'm here we have this total funk total variable which ad which gets aggregate
00:29:39
the data to but never in the be using the return value of the program
00:29:43
on the on the other hand we have discount function which does get using returned count variable without using
00:29:49
the return value of the program but we have one at the site which is never going to get run
00:29:55
so total is fails a lightness analysis can be removed
00:29:59
just content because one fails the readability analysing can be removed
00:30:03
so how do we do that optimisation in a programmatic fashion rather than just looking
00:30:08
at it as humans plus you can do the same are constant volume we did earlier
00:30:14
earlier so we know multiplies or the b. zero this is always gonna be false
00:30:20
next we end up with this simplified three if our program and simplified it'll
00:30:24
graph where if zero look great great in hundred do this consciously goes one
00:30:29
so look at the data flow graph because either you have zero
00:30:32
hundred created and this is always going to be false and so the
00:30:37
if statement can only be we can remove the falls down to
00:30:39
the statement and all of its downstream nodes in the data flow graph
00:30:44
so one pass this arrow this arrow are all in this
00:30:48
reid falls are all in the true block and can be removed
00:30:54
so that is the simplify data flow graph so we can now we do the lightness
00:30:59
analysis to say we scored in this graph is not using the return value the program
00:31:04
and that ends up being relatively straightforward um analysis you just started return value
00:31:09
do about for sets up the graph and you see here or all the black nodes other ones is
00:31:14
appearing my breakfast that's all the red nodes are the ones that do not appear in my breakfast such
00:31:19
so even though we have total adding to itself and depending on itself and none of these
00:31:23
nodes have zero inputs are the outputs we know that totally is not and i'm not being used
00:31:29
and is greater than node and i'm not being used so we can remove this from the data flow graph
00:31:35
giving us this which is a simplified data flow graph of the early of function with all the
00:31:40
rubbish removed total is go on the if check is gone multiplied is gone simple graphs that some zero
00:31:47
oops are dupes around a few times this if around this conditional if statement
00:31:52
increments count and returns at the end when if statements are fails so
00:32:01
oh
00:32:05
so to wrap up we've seen some optimisation so we can perform manual evaded
00:32:08
type in france in lining constant folding that could lead nation bands initially scheduling
00:32:13
there are many more you can keep doing and you can just the market good income pilot
00:32:17
x. we're gonna be a whole chapter four different places you can do one by one um
00:32:21
after we do not do them all manually so that we can just day
00:32:24
you can write the program children overcast file and do all the other magicians automatically
00:32:30
so rather than you're spending all human brain how to do so is
00:32:33
really a laptop to turn away as without and more optimised program um
00:32:38
next look at the modelling a proper program the different ways in which they say
00:32:41
this is the program data structure in memory and a different trade off which off
00:32:45
the the different trade offs of how easy it is to what with them
00:32:48
and lies them or modify them um for this demo i use data flow grass
00:32:54
both for the implementation of the program is sawyer and for the slides you're but you can do the
00:32:58
same work on a estes upright code does it more or less effort depending on which representation you choose
00:33:04
i'm nancy we look at how to do it into
00:33:07
these inferences optimisation automatically resort type inference constant folding um
00:33:12
how constant folding really is just type inferences singleton types um
00:33:17
and we we saw inter procedural inference when you're one function calling the other end and lighting both one after the other
00:33:23
and he saw how to do recursive interpretive inference really recursive
00:33:27
function okay and why did you take advantage of this bottom
00:33:31
that sentinel node in your pack that is not the to do multiple iterations
00:33:35
around of the raw data for propagation and end up with the correct answer um
00:33:40
natalie looked at two the two other optimisation to to not type inference in constant holding the politeness analysis
00:33:47
which is removing things we cannot use and find out what i mean look at readability analyses which is removing
00:33:52
things that will never get run even if they even though if they do we run it will affect the output
00:33:57
and we saw how we could do this using relatively simple data structures is just a directed graph it maybe some cycles
00:34:02
in in them and relatively simple algorithms resistor bottles over the data flow graph possibly making one more one on one arm
00:34:09
cycle and finally stayed lighting and using the infrared values or
00:34:14
in four types of your program not that make up the migrations
00:34:19
um so i didn't come up with any of this stuff myself all of this is well known in parts of industry
00:34:25
so if you're interested in learning more about optimising compilers and you want
00:34:28
to go right with cassie out the miser java programme up the miser
00:34:32
or you can optimise for the language as a most of these techniques
00:34:36
we'll go we'll transfer e. will transfer relatively easily from started java too
00:34:41
um c. sharp to see justice maybe the javascript or maybe not okay and these
00:34:47
two books i think a good reference renting your compilers very thorough reference of the general
00:34:51
architecture compiler with many section mini chapters based optimisation techniques and uh combining analyses combining
00:34:59
customisations like if click that is easy the system ninety ninety five is a good are
00:35:04
introduction to this idea of data flow graph modelling
00:35:07
and data flow graph graph analysis using this particular technique
00:35:11
um so that's it for how optimising compiler works i think um i have a bit of time for questions so of have acne
00:35:28
it's really not a whole
00:35:35
yeah oh so the question is i did not go talk about high
00:35:38
ago from class files the data for when out the data for programs um
00:35:43
so let's go back to the castle representation can going to be the details is i have some time
00:35:48
so if going from yes he's today the full program does easier you
00:35:52
just take these identify assigned edges and you make them into really edges
00:35:56
and actually the flow graph um so going from castle the date of
00:35:59
local programs to be trickier but if you look at how cost files look
00:36:05
you see as we move things on and off the stack for example here we um this okay this section
00:36:12
where we are load the forest look though the first argument put the constant one subtracted to get another value
00:36:20
load another constant one invokes added yet another value and then return it so these cool uh
00:36:28
abstract variables that call it being moved on and off
00:36:30
the stack basically for my setup edges between the node which
00:36:36
constructs the abstract variable for example node twenty two i sub constructs useful and the node
00:36:42
it consumes abstract terrible in this case i'm ugly this one with the number twenty seven
00:36:49
no wrong number thirty uh invoke static so if you follow these in nodes along the uh
00:36:56
the orbital stack you basically end up with a graph of whether values come from and go to and that is our data flow graph
00:37:03
so if you want to learn how to do that you should go look at arm caught
00:37:07
the yes m. java byte code engineering library to the very good tutorial for data flow analysis
00:37:12
specifically converting data flow from byte code to data flow graphs using the library and that's
00:37:17
what i use for them already i didn't have to write all myself i'm gonna questions
00:37:25
do you how benchmarks i didn't have benchmarks so unfortunately this
00:37:30
is not quite at that stage yet so i've demo it
00:37:33
it working i've not them what their efficacy come on top of the t. v. and shit on digits
00:37:39
um you're going to be open source ah i don't think isn't good enough beethoven's office uh is a bit of a mess
00:37:47
yeah but i don't think you'll get much reading a call it so if you want to know
00:37:51
how it works this is basically everything about how it works on the slides um yeah in front yeah
00:38:05
and when you do we need to procedural reminiscence do you do like do you consider the context um
00:38:16
yes so if you look over here um where am i
00:38:21
you look over here when propagating is euro from the main function to call function
00:38:26
basically that means that analysts called separately for every different parameter it gets
00:38:31
um so obviously this doesn't scale if i call call it a thousand different functions like on a thousand different too because
00:38:37
and you have to prove those with you to stick slightly j. v. m. c.'s if if three different minimal fig
00:38:42
the three different uh dispatches the polymorphic all side it does she
00:38:46
says volume offing doesn't hide in line similarly for this kind of
00:38:49
thing get to prune it eventually say that too many different um
00:38:53
context as an lies within i'm just going to take the conservative you
00:38:57
um but that's also nothing can trade off like if i have zero if there's only one course i and
00:39:03
one call function is very easy to probably get the context zero to zero does it up to my dutifully
00:39:08
if i have to call sites is also easy probably the context you especially people that constance
00:39:14
if i have a million different call sites with different contexts they need you made is
00:39:19
that you have to start collecting them in order to make the uh um analysis more tractable
00:39:24
but that's the thing you can trade off into an an optical higher or lower precision high and low performance
00:39:30
yeah you mentioned a few saying i'm not filter and things
00:39:35
like that ah is that in the talk description uh yeah so
00:39:40
i don't have the demo here now but using that until
00:39:42
there's basically lining once you busy in lining to a concrete function
00:39:48
so instead of so if you're a map function and you copy them you copy the map function with
00:39:53
only one lambda get in line to that land diner function to effectively fuse it
00:39:59
um i i sometimes if you if you wanna build them out first work transform
00:40:06
a list or something you can save a lot of performs like creating of you
00:40:12
uh yeah so it doesn't do that kind of using but it
00:40:15
does the in line into primitives kind of using not so that's
00:40:18
a crack terminology that the wrong for the midterm analogy on the
00:40:22
basic complex like chains of options that maps into straight line code
00:40:26
um it does not look on arrays yet it does what connery seeks due to implementation problems
00:40:32
um but in in general a lot of decided not production idea is mostly a demonstration of the principles
00:40:43
what is also artifacts would work for um that's a very interesting question so
00:40:51
this data flow graph analysis of what this technique is basic copied from fifty clicks he's yes
00:40:58
and click click click pieces and that energy vienna you all running as fast as hotspot uh
00:41:03
of the miser so if you look at the hotspot documentation we'll talk about that in short
00:41:08
it looks a lot like the uh hi all monad so we basically pass it because you have
00:41:14
knowledge to stick in our you world and pass out the change the world as a separate band you
00:41:19
and so these nodes have more than one output value and the once it's up your will not need to take in order to in the world
00:41:25
and wondered does it forward thinking return the world i mean it would be the draft of also that we saw earlier all the kind of flows dutifully
00:41:32
i mean it doesn't need that much special casing any other questions about the back
00:41:44
um
00:41:52
oh i'm so used to torture zulu general introduction to on
00:41:56
optimal version of compilers but would be interested
00:41:59
in what what's your on application independent scholar
00:42:03
i grew systems what were you planning to reduce kind
00:42:06
of optimisation visitor compiler blocker in or at what's your cool
00:42:12
it's unclear i see yeah really i have what i have now is it kind of works
00:42:17
what to do with it is and is not that obvious um in principle they
00:42:22
should be able to do much more aggressive optimisation then that's callously optimise it can do
00:42:26
because quality of the miser doesn't look close what does a sumo clothes while it is still out multiple separate compilation um
00:42:33
if you consider how much of the skylight yes up to my that's the that's the ideas call it does anyone know under
00:42:42
well the question how mats like i think something like two to ten x. depending
00:42:48
on the code so you can get very aggressive optimisation wanted will close what analysis
00:42:53
um so in principle if you get to the tennessee doubles guardian call even one point five to five it'd be pretty cool
00:42:59
um but there'll be a a lot a lot more work in this demo of the other questions but the back there i
00:43:15
i ski
00:43:23
ah hi i i'll thank you very much for program
00:43:31
i i just i started well essentially just oh oh oh
00:43:41
oh oh oh yeah sorry for my uh huh mark reform um
00:43:49
zoe was really in anne's from him interaction to the um oh sorry um
00:43:57
your t. minus i'm working on my own level by go to buy or
00:44:04
on the scam shores or this of the miser works in a byte code uh_huh or it does the same
00:44:10
technique i described earlier where you walk the byte code in order to build a consolidated one controls all graph
00:44:16
um these are label which one is better i was using but could because that's more well defined and i'm more familiar with it
00:44:22
ah is it based on a assemblyman sciences yes is based on or
00:44:27
oh object web yes um hum at least for the front end parsing
00:44:31
and a graph construction after that yes and doesn't do anything okay um
00:44:38
one thing i was curious um when you one of the techniques uh oh
00:44:43
well let me sometimes is michigan's hand particularly if you look at the form
00:44:49
more function rooms and or are planning should surely something call him deforestation the
00:44:54
process by which um your mobile to mention the call your like camping away yeah
00:45:00
intermediate data start storm yes i can talk
00:45:03
about that so deforestation basically requires heap analysis
00:45:08
which is a separate field of program optimisation i did not touch
00:45:12
on at all so um yeah i i have not implemented keep
00:45:17
analysis and therefore this does not do either deforestation and boxing as
00:45:21
if analysis none of that um that would be it's all in project
00:45:27
ah one last thing is i'm a yeah yeah i
00:45:33
and i don't think i'm thinking is that if you have from which you prefer the functions time or
00:45:39
starr you like to pass our memory to frame
00:45:43
accurate functions now lotions are being implemented that's um
00:45:47
only morphing orson you about like having if you have like
00:45:51
animals course through the stock market may end up having like um
00:45:57
seven am references to or without then can have many
00:46:03
numbers try the implementation of function more market seems kinda how
00:46:07
when there's a mm not to mention that change with us
00:46:13
um it would take more time to describe in i think we have so i can come talk to
00:46:17
you later after yeah i think we are done as far as time goes so thank you for listening
Conference Program
A Tour of Scala 3
Martin Odersky, Professor EPFL, Co-founder Lightbend
June 11, 2019 · 5:15 p.m.
8337 views
A story of unification: from Apache Spark to MLflow
Reynold Xin, Databricks
June 12, 2019 · 9:15 a.m.
1267 views
In Types We Trust
Bill Venners, Artima, Inc
June 12, 2019 · 10:15 a.m.
1569 views
Creating Native iOS and Android Apps in Scala without tears
Zahari Dichev, Bullet.io
June 12, 2019 · 10:16 a.m.
2232 views
Techniques for Teaching Scala
Noel Welsh, Inner Product and Underscore
June 12, 2019 · 10:17 a.m.
1296 views
Future-proofing Scala: the TASTY intermediate representation
Guillaume Martres, student at EPFL
June 12, 2019 · 10:18 a.m.
1157 views
Metals: rich code editing for Scala in VS Code, Vim, Emacs and beyond
Ólafur Páll Geirsson, Scala Center
June 12, 2019 · 11:15 a.m.
4695 views
Akka Streams to the Extreme
Heiko Seeberger, independent consultant
June 12, 2019 · 11:16 a.m.
1552 views
Scala First: Lessons from 3 student generations
Bjorn Regnell, Lund Univ., Sweden.
June 12, 2019 · 11:17 a.m.
577 views
Cellular Automata: How to become an artist with a few lines
Maciej Gorywoda, Wire, Berlin
June 12, 2019 · 11:18 a.m.
386 views
Why Netflix ❤'s Scala for Machine Learning
Jeremy Smith & Aish, Netflix
June 12, 2019 · 12:15 p.m.
5026 views
Massively Parallel Distributed Scala Compilation... And You!
Stu Hood, Twitter
June 12, 2019 · 12:16 p.m.
958 views
Polymorphism in Scala
Petra Bierleutgeb
June 12, 2019 · 12:17 p.m.
1113 views
sbt core concepts
Eugene Yokota, Scala Team at Lightbend
June 12, 2019 · 12:18 p.m.
1656 views
Double your performance: Scala's missing optimizing compiler
Li Haoyi, author Ammonite, Mill, FastParse, uPickle, and many more.
June 12, 2019 · 2:30 p.m.
837 views
Making Our Future Better
Viktor Klang, Lightbend
June 12, 2019 · 2:31 p.m.
1682 views
Testing in the postapocalyptic future
Daniel Westheide, INNOQ
June 12, 2019 · 2:32 p.m.
498 views
Context Buddy: the tool that knows your code better than you
Krzysztof Romanowski, sphere.it conference
June 12, 2019 · 2:33 p.m.
394 views
The Shape(less) of Type Class Derivation in Scala 3
Miles Sabin, Underscore Consulting
June 12, 2019 · 3:30 p.m.
2321 views
Refactor all the things!
Daniela Sfregola, organizer of the London Scala User Group meetup
June 12, 2019 · 3:31 p.m.
514 views
Integrating Developer Experiences - Build Server Protocol
Justin Kaeser, IntelliJ Scala
June 12, 2019 · 3:32 p.m.
551 views
Managing an Akka Cluster on Kubernetes
Markus Jura, MOIA
June 12, 2019 · 3:33 p.m.
735 views
Serverless Scala - Functions as SuperDuperMicroServices
Josh Suereth, Donna Malayeri & James Ward, Author of Scala In Depth; Google ; Google
June 12, 2019 · 4:45 p.m.
936 views
How are we going to migrate to Scala 3.0, aka Dotty?
Lukas Rytz, Lightbend
June 12, 2019 · 4:46 p.m.
709 views
Concurrent programming in 2019: Akka, Monix or ZIO?
Adam Warski, co-founders of SoftwareMill
June 12, 2019 · 4:47 p.m.
1974 views
ScalaJS and Typescript: an unlikely romance
Jeremy Hughes, Lightbend
June 12, 2019 · 4:48 p.m.
1377 views
Pure Functional Database Programming‚ without JDBC
Rob Norris
June 12, 2019 · 5:45 p.m.
6374 views
Why you need to be reviewing open source code
Gris Cuevas Zambrano & Holden Karau, Google Cloud;
June 12, 2019 · 5:46 p.m.
484 views
Develop seamless web services with Mu
Oli Makhasoeva, 47 Degrees
June 12, 2019 · 5:47 p.m.
785 views
Implementing the Scala 2.13 collections
Stefan Zeiger, Lightbend
June 12, 2019 · 5:48 p.m.
811 views
Introduction to day 2
June 13, 2019 · 9:10 a.m.
250 views
Sustaining open source digital infrastructure
Bogdan Vasilescu, Assistant Professor at Carnegie Mellon University's School of Computer Science, USA
June 13, 2019 · 9:16 a.m.
375 views
Building a Better Scala Community
Kelley Robinson, Developer Evangelist at Twilio
June 13, 2019 · 10:15 a.m.
245 views
Run Scala Faster with GraalVM on any Platform
Vojin Jovanovic, Oracle
June 13, 2019 · 10:16 a.m.
1342 views
ScalaClean - full program static analysis at scale
Rory Graves
June 13, 2019 · 10:17 a.m.
463 views
Flare & Lantern: Accelerators for Spark and Deep Learning
Tiark Rompf, Assistant Professor at Purdue University
June 13, 2019 · 10:18 a.m.
380 views
Metaprogramming in Dotty
Nicolas Stucki, Ph.D. student at LAMP
June 13, 2019 · 11:15 a.m.
1250 views
Fast, Simple Concurrency with Scala Native
Richard Whaling, data engineer based in Chicago
June 13, 2019 · 11:16 a.m.
624 views
Pick your number type with Spire
Denis Rosset, postdoctoral researcher at Perimeter Institute
June 13, 2019 · 11:17 a.m.
245 views
Scala.js and WebAssembly, a tale of the dangers of the sea
Sébastien Doeraene, Executive director of the Scala Center
June 13, 2019 · 11:18 a.m.
661 views
Performance tuning Twitter services with Graal and ML
Chris Thalinger, Twitter
June 13, 2019 · 12:15 p.m.
2003 views
Supporting the Scala Ecosystem: Stories from the Line
Justin Pihony, Lightbend
June 13, 2019 · 12:16 p.m.
163 views
Compiling to preserve our privacy
Manohar Jonnalagedda and Jakob Odersky, Inpher
June 13, 2019 · 12:17 p.m.
301 views
Building Scala with Bazel
Natan Silnitsky, wix.com
June 13, 2019 · 12:18 p.m.
565 views
Diversity and Inclusion Panel: Bring the Thunder!
Panel
June 13, 2019 · 2:30 p.m.
244 views
Asynchronous streams in direct style with and without macros
Philipp Haller, KTH Royal Institute of Technology in Stockholm
June 13, 2019 · 3:45 p.m.
304 views
Interactive Computing with Jupyter and Almond
Sören Brunk, USU Software AG
June 13, 2019 · 3:46 p.m.
681 views
Scala best practices I wish someone'd told me about
Nicolas Rinaudo, CTO of Besedo
June 13, 2019 · 3:47 p.m.
2706 views
High performance Privacy By Design using Matryoshka & Spark
Wiem Zine El Abidine and Olivier Girardot, Scala Backend Developer at MOIA / co-founder of Lateral Thoughts
June 13, 2019 · 3:48 p.m.
754 views
Immutable Sequential Maps – Keeping order while hashed
Odd Möller
June 13, 2019 · 4:45 p.m.
277 views
All the fancy things flexible dependency management can do
Alexandre Archambault, engineer at the Scala Center
June 13, 2019 · 4:46 p.m.
389 views
ScalaWebTest - integration testing made easy
Dani Rey, Unic AG
June 13, 2019 · 4:47 p.m.
468 views
Mellite: An Integrated Development Environment for Sound
Hanns Holger Rutz, Institute of Electronic Music and Acoustics (IEM), Graz
June 13, 2019 · 4:48 p.m.
213 views
Closing panel
Panel
June 13, 2019 · 5:54 p.m.
400 views