SBTB 2015: Buck Shlegeris, Automatically deriving efficient data structures in Scala
Recording: SBTB 2015: Buck Shlegeris, Automatically deriving efficient data structures in Scala
yes i believe it's 20 but I'd hide girl for boy maybe I'll go on for a longer than I wasn't anticipating good afternoon ladies and gentlemen my name is buck I'm a software engineer at PayPal I've been working there for about six months which means that about seven or eight months ago I was spending most of my time doing coding interviews and I did a lot of coding interviews I think I talked to 10 or 15 different companies my last job search so I did a lot of algorithms questions and by the end of my job search I was beginning to find them quite irritating and repetitive and with software engineers when you give them an irritating and repetitive task they start looking for a way to automate it and so I decided that by the time I next look for a job I was going to have a system which would automated Lee do my algorithms questions for me so this like might sound like a confusing and lofty goal I'm interested only in the subset of this task where you're trying to convert where the problem isn't to specify some behavior so you know you can walk into an interview and then they can ask you to write code to reverse a linked list I'm not interested in solving that kind of question I'm interested in solving the kind of question where it's obvious how to specify it somehow and you don't get points for that but the question is how to do it well so let's look at a pretty standard example question of this type this is from cracking the coding interview so we want to have a stack which in addition to push and pop has a function min which returns the minimum element push pop and men should all operate in constant time that makes sense guys cool so let's look at a bad implementation that doesn't work but well it works it's just not fast enough so this is some basic Scala we want to push and pop and the problem is this get min operator which doesn't work because it takes linear time does anyone off the top of their head know the solution to this yeah good yeah you want a second stack it's like this so the second stack is going to maintain the smallest thing you've seen so far every time you push you see if the minimum has changed and like push the minimum to this second stack and when you pop you just push birth and this means it's constant time for birth so let's imagine the question is now slightly different what about if you're allowed to do random modification to your stack so I'm allowed to say actually the thing that position 5 is now 20 can we do this with a stack anymore nor so the answer is our efficient solution which involves the second stack breaks as soon as we are allowed to make arbitrary modifications to our to our stack so in that case our previous data structure wouldn't work but what about if we're allowed random modification but the question is to return the sum instead of the minimum and that'll be easy because you just have to store the total sum of everything you've seen so far when you add something you add that to your some when you remove something you subtract it so what we've learnt is that when we're trying to find fast data structures for particular queries we're interested in two questions what kind of reads they're going to be making are they going to be asking for minimum or get or the song so the kind of property that makes the difference there is whether we're doing an invertible reduction or not the reason that you can just store a single number to keep the sum is that you can invert subtraction sorry you can invert addition with subtraction right but there is no operation which inverts are taking the minimum of true numbers so that's one question we're interested in the other one we're interested in is what kind of modifications are happening to our data structure so in the case of a stack that's basically the data structure where you are promised the early modifications is adding elements to this end over here and that means that it's really easy to maintain various invariants cool so let's look at what my system can do at the moment sir the one of the big lessons I've gotten from this conference so far is you always want to have dark backgrounds and your consoles was anyone at that talk yeah so so this is a question that I was asked at Google actually um so the question is you know I'm gonna be giving you like people one at a time I'm telling you about them and I want you to store for every nationality the 10 riches so I want to be able to ask this is this return type is totally alive but I don't actually check it sir her so I want you to be able to give me the 10 richest people of every nationality so we can look at the implementation here we're going to filter by the nationality of the person equalling this argument and then we're going to limit by is basically an order by and then take and we want to get the top 10 does that make sense so let's compile this without the ER to flag and we get this Ruby code long story as to why it's turning into Ruby but I will explain later and we get this shitty implementation where we select them by their having the right nationality then we sort them by the negative of their income and then we take the first 10 does that make sense cool let's turn on this oh true flag and compile it again now things are very different we've got this variable which has been hopefully named Zed which is a hashmap of empty min heaps so let's see what happens when you insert a person now well it pre calculates their priority which in this case is just the negative of their income then it looks up if it basically stores a min heap of the top 10 people if this person is richer than the 10th richest person then we need to pop our the like the 10th person out and then push this new person into our min heap and then we have this case here just in case we're at the start and we don't have 10 people with this nationality yet so this is the fast implementation this takes constant time guys and when we asked for an insertion it inserts into the heap which is indexed by a hashmap and when we try to read we just get a list of keys from the heap which is at that place in my hash map so that's the kind of thing I can do I'll just quickly show you another example we want to get the average income of whoop that's output we want to get the average income of people who have a particular age and gender and string gender is a string field because I'm not some kind of monster and we get the turtle in come here and we get the count here and we're going to compile it with o2 and we end up storing two hashes of hashes when we add a person we add one in to the number of people who have that gender & age and we add their income to the total income of people with that gender & age and then when we want to get the average we just divide them my system is not very good yet at realizing that we should just division instead of exponentiation but whatever cool that's what I'm doing question is how do you do that luckily Tobias has got many of you guys warmed up four phases of an optimizing compiler so I'm going to talk about that uh this project is currently about three thousand lines of Scala ok sir the java string that you passed gets turned into a java AST thanks to the java parser library which is referred to as calm git hub in its package name so i guess github has something to do with it I didn't write any of that so let's talk about the next bit first thing I do is I want to turn method calls that have chained like dot filter got limit x dot reduce with some i want to turn those into sequel style queries because it turns out that that makes it a lot easier to optimize so let's look at this sequel query quickly i'm going to point out a few parts of it which I'm going to use in my query data structure here we have the source so this is where we're going to get a data from it in my system has the type Java expression or query in this case it's just a reference to the variable people then we're going to have a list of where clause so a set sorry because where clauses can commute it you can swap their order so one of the where clauses is the height of a person has to be greater than hundred and eighty the other where clause is it has to be less than 40 that makes sense next thing is what I'm calling my limit by Clause note that in this case we don't actually care about the order of people's heights because we're just limiting them and then taking the average so order by is basically the composition of a sort by and then it take where we don't care at the order that's basically because I'm only looking at the unordered case of making fast queries at the moment it's a mile mile tack that I'm doing at the moment its representatives an option of limit by Clause because we might not have one and finally we have this maybe reduction which is a thing which takes the list of things that return and reduces them down to a single value why is this an option of reduction like what happens in sequel if they're like what's the kind of a null case for a reduction that yes da so it's like very possible to just return everything that's in that so we end up having this case class for an unloaded query which has a source a set of where clauses maybe a limiter and maybe a reduction and the queer ification step basically walks over my java AST and then everywhere it can stick in an honored query it does and the logic for that is pretty complicated but like an example that kind of looks like this when you try to call filter on a query we want to look at whether we are currently like whether we're calling query on sorry whether we're calling filter on a query which has no limit or or reduction in the case where you have no limiter or reduction we can just add the clauses in this filter to that query and return that otherwise we need to make a new query and like call we're on it that was kind of complicated and fast but I'm the speed through it anyway I promise it makes sense feel free to check out the source code one fairly major component of the system is a computer algebra system so to figure out things like you may remember the case before well we were talking about sums list versus a min list where you have to maintain the some versus the men whether it's possible to do this is quite closely affected by whether your functions are invertible so I had to write a computer out of the system that can determine things like how to solve expressions this is really hard it turns out that like there are only like a few libraries in the wall that do a very good job of this and I want to do a much more ambitious version of it where it can for instance tell you that you can invert like bitwise XOR or whatever that is like a whole other talk in itself but it's a major weakness of this system that I am NOT better at it currently the only thing I know how to solve is basically of the form like it's a sum with nothing complicated in it if you like tell me that zero equals x plus y plus Z I can solve for x is like basically what I can do or Y or Z cool so after that we've gone through our abstract syntax tree put queries in everywhere now we need to choose data structures so what is it that I mean by a data structure well here is most of the abstract class which provides the definition so a dollar structure might be something like a constant sized heap which knows that you should pop elements out if you're about to stick in a new element so it has an asymptotic query time which is a thing its resting bigger annotation which in the case of a constant sized heap is constant it has an insertion fragment which means a list of Java statements that you need to do when someone is inserting something into your data structure it's got a list of things you need to do when someone's removing them who knows why that's an option of lists of Java statement instead of just a list of Java statement yes not all data structures support insertion and removal if we've got a bloom filter it's not going to support removal and in the case before where we were talking about on like if I want to maintain the minimum of something it's really easy to just support that if no one's removing anything by just keeping it in one place so in that case my removal fragment would be none very good um I also have query curd which is the Java code to be executed when they want to actually get the value out and that can optionally call a method which is emitted to encapsulate that curd and is like special for this data structure um and then the question is for every query how are we going to choose the best data structure for it so in the case where we like want to limit by something and then reduce by something how we're going to do that well we have a list of helpful structures then we fold each of these structures what a structure means something like constant sized hash map or mono I'd memorizer or group memorizer it tries to create an instance of that useful class with my query then all the ones that worked it's flat map because try to create returns an option of query then we filter so that for every data structure it either doesn't need to be able to insert or it has an insertion fragment then we filter so that it either doesn't need to be allowed to remove things or it has a removal fragment then we sort by asymptotic query time then we take the head and some this is an option because maybe there is no data structure to represent the operation efficiently in which case we give up and return the shitty like dot filtered filtered sort biotech or whatever that I showed you before when my optimization flag was off okay that was a lot of Scala I am glad that you guys are smart enough to get through it what data structures do I have currently i only have pretty much the ones you've seen i can maintain the minimum of a reduction where we don't need to be able to remove things i can maintain a thing which has invertibility and I have this limited size heap why did I not put more work into that because it's fundamentally not that interesting compared to creating like the internals of all this stuff that I'm doing I will probably add more of them I'm not going to talk about mon Adam on memorizing KD trees okay so next thing we do we've chosen our data structures and we need to actually put them back into our Java abstract syntax tree it's pretty much just walking over it again and like replacing every time they call the query with the code that was defined in the data structure to answer that query it works I promise the other trick is when someone insults into your class you need to output all of the other things you have to do when they insert so you guys might remember in my example the insertion ends up like also updating these two hash maps right and that's that's done by like literally calling the insertion fragment kind of methods for all of the data structures which are being used and splashing them all together and returning it as a method okay um whoa so that's how we actualize them and then finally we've got a job or abstract syntax tree which is basically legitimate Java and we have to turn it into Ruby which is just like walking over a tree and putting brackets places and emitting types hey guys why is it that I used ruby is my target language what's that sir all right because i'm too lazy to include types everywhere in my objection text tree ah that's also why i chose java is my source language because it has types everywhere oh in the future I'll probably do a better job of this lessons I learned about Scala from this process basically i really want type union as an anonymous like way of expressing the thing which I passed you will be this type of this type there are ways of doing this in like various libraries but I wish it would directly build into the compiler i also want type- when i'm representing a sum I don't want any of the things so like some is a case class which extends like mathematical expression right I don't want anything in my some to itself be a sum because if it was going to be a sum I'd want to just like flatten it out right like with the blocks in Scala Jas and I want to be able to express the some ants in this sum must not be sums themselves you can do that in Scala but you have to use some crazy stuff that like you can only find in a stack of a flow answer by mouth saban which is like not robust software engineering um so that's my main lesson about scala where to go from here more data structures i would love to have some closing quote style specification of your data structures because currently the way that you explain to my system how to use a constant sized heap is basically literally writing a Java abstract syntax tree manually which is really irritating and I would love to do better than I would like to have more correctness the functions i showed you were like only slightly cheating but a little bit cheating because i don't do a lot of analysis that i really should i assume all functions of pure and referential e transparent which citation needed is not true in java uh which is dangerous I want to extend this to it so that I can talk about ordered collections so that I can actually answer the minimum query like the min stack question which I mentioned at the start of this presentation I want to automatically solve dynamic programming problems as well which turns out is like kind of related to this I would love to have auto generated test cases so that like when you tell me about this new neat data structure that answers a query really fast I want to automatically create dodge trackers that tests figure out if you use that in the code does it produce the same result as just doing the inefficient obvious implementation I could do that automatically I just haven't i also want more target languages Python would be nice I want to generate see extensions for Ruby automatically because it's not even that hard but it's tricky and people don't know how to write C extensions for Ruby normally and that'll be fun and then I could like have a website where you pay 99 cents to download like a sea extension to Ruby which has your domain specific logic in it and that'd be neat so in conclusion if I had to basically express what i'm trying to do with this there are all kinds of things that people don't do when they're writing code imagine that I actually gave you this problem here right in real life chances are you wouldn't want to actually store these hashes of hashes and update them everywhere because that's really hard and software engineers are bad at doing complicated things and keeping that data in step you know people dislike d normalizing their data for a reason I want to make it so that this kind of data denormalization is totally automatic and takes no marginal effort on the part of the programmer answer happens more easily and I want it so that next time I look for a job I can cheat on all my for interviews I have had a very good time writing this code you can see the various different haircuts i've had this is lowell commits strongly recommend installing thank you very much any questions hey so oh I don't actually uh the question is how do i turn my curd into sequel I don't actually turn it into sequel I just turn it into this data structure which kind of looks like sequel and could be like a transparently converted into sequel but good question so since you're passing parsing the Java yourself is there like a subset of Java Texas you're allowed to use in your specification I'm so either parse the job on myself I used yet is there a subset of Java types which I'm a lot which I am allowed to which I allow people to use a lot of the types I don't actually look at when i'm writing this code the only place where I actually consider the types of things is when I am looking at objects which have methods cold on them with names like filter and I'm saying hey should I turn this into a query and then I inspected to see if it's type is Magic multiset um there are a lot of things which like my compiler would totally let you do which it early illegal to do that a question of that Hey so yeah yep so you guys might remember transducers I've totally should have mentioned that buzzword in the main talk but yeah sir basically I do filter limit by reduce various things which you can write as reduce so you notice that I used count somewhere or some count and some are both just shortcuts for things which are turned into reductions internally if I extend this to ordered collections as well as unalloyed collections then there's a whole set of different things which make sense for them such as order by and take and drop as well as a more complicated set of modification methods such as push and push to the other end and insert and set and so on okay if I were the interviewer what question where I asked now the problem is the questions that are asked here actually pretty much my favorites like the thing that really annoys me is when people ask me questions that aren't about asymptotic complexity defining you know if people ask me about you know how to swap two variables in place without using a temporary variable it's just like you know i have i have nothing useful to say to you here i would ask people to build an interesting and complex system which requires them to develop novel abstractions and talk about it so i might have i'd probably just ask them to talk to me about this system actually at this point i wonder how that goes walking into an interview and saying heller your questions are bad may I suggest some new ones I'll give it a try anything else