scala.bythebay.io: Buck Shlegeris, Automatic composition of fast data structures
Recording: scala.bythebay.io: Buck Shlegeris, Automatic composition of fast data structures
good evening afternoon how are you guys doing Maxon on hey hey hey how's this super exciting well hello everyone good afternoon it's lovely to be talking to you guys my name is buck I'm an engineer at triple byte and today I'm going to be talking to you about a project I've been working on for the last on and off for the last couple of years I've wanted it for quite a long time so start engine two data structures sir a data structure is a way of organizing data to efficiently support a particular API right so given that a Dodge truck - search engine is just something that can take such an API and return an efficient implementation for it Norman no matter what it is so my goal here has been to make something which can search through potential data structure implementations and I want it to be extremely usable and extremely powerful so I wanted to be usable enough that you can basically cheat on furn screens in job interviews by instead of answering data structure questions yourself just using it to tell you the correct answer but I also want to be powerful enough that even tricky companies like Twitter which like asking you tricky questions I want to be powerful enough that it can express all the facts that you would need to know to answer all of those questions so let's look at some of the questions that I would like us to be able to answer so here's a classic one from a cracking mccurdy interview how would you design a stack which in addition to push and pop also has a function min which returns the minimum element so you know you see we have these three methods push pop and min which we only which we need to implement all efficiently another one from chora there's there's dozens of these on Quora or more dozens until I get tired of looking at them you know I want to support find me and find max delete min delete max insert and delete a less carefully written one on Quora you know can I delete an element from the middle of an array using queue and data structures which I'm going to optimistically interpret to mean how can i implement a queue in such a way that deletion in the middle is fast so these questions will have a very similar form so our input is a set of that we want to be able to implement correct quickly and our output is a set of composite data structures which end up being able to influence and sir the software I've written for this is it dslrs comm I might change that URL at some point in the future but for the moment I like an excuse to force people to learn how to spell my last name so it's going to stay like that for at least a little bit so let's let's look at some asses so we want to find in addition to push and pop we have min let's have a look so I want to have the push I'm gonna have in set lost for pop I'm gonna have delete lost and get lost and min get minimum I have to have slightly longer slightly along the names so that there's less ambiguity even if there's a lot of implementations which as you can see there are so I can see that what I have is an ArrayList which is implementing the main stack pot and a stack reduction memorizer which is the data structure which as you guys might have heard this data structure before right if you want to memorize any reduction of a function over a stack you can do it by just having another stack of the reductions and then whenever you push you compute it according to how it works at the end and then when you pop you just pop an element off the stack so that works if you want to take the minimum of the stack or the md5 hash of the stack or literally any operation you could possibly want and so what my system knows about this is that for any reduction I can do it in constant time and I support insert last so you insert at the end and delete at the end so that's that's that's that's like the idea of what we're building here let's look at the next one we won't find me and find max delete and delete max insert and delete let's have a look okay looks like the fastest way of doing it is a value ordered order statistic tree how many of you guys have heard of order statistic trees many no one oh man you probably have used another name a value ordered order so an order statistic tree is just a variation on a binary search tree where every node has a count of how many nodes it has right which means you can iterate over it quickly anyway so it turns out that if you have a order statistic which is storing an array but instead of storing things in order stores them in the order of their values you can implement all these things with these times and the last one of these we wanted to have a cue which supports delete at index quickly and we'll see that we have two options and/or statistic tree lists and a TN vector so a TM vector is a table structure from a paper when is it a while ago now it's it's not actually that cool it's mostly a trick but it does legitimately give you constant get by index and command square root time delete by index so anyway so the idea is there are a whole lot of data structures here like I suddenly had not heard of all of these data structures when I started building this thing and the problem with data structures is normally people don't explain very clearly precisely what problems they solve and a lot of the time you don't care about reading a very long list of old data structures you just want to find the data structure which works for your particular problem so let's talk about how we might make this so how do we choose table structures so here's the first idea let's consider all of the data structures that are possible and then choose the fastest one so this sounds like it's not going to be that hard let's just say like a data structure is a map from methods like insert an end or get first to a bit at a time in bigger so this is the idea that you get if you looked at bigger cheat sheet comm which just has a very very long list of table structures and how fast they all could be various things but from looking at this you'll see the kind of problems that come up and you'll see that this is fundamentally the wrong way to approach the problem so so let's see so for instance insertion in a singly linked list takes constant time well that's sort of true I guess but they haven't mentioned that insertion in a singly linked list actually like to insert by index you also have to find the thing which takes linear time and it kind of makes sense that they expressed it this way because it's a lot more natural to talk about inserting offer a given nerd in a linked list and it's a lot more natural to talk about searching by a particular position in an array and so we try to make this table expressing in the same in the same methods what all the different data structures can do even though I think that's like fundamentally the wrong way to approach the problem so let's um let's try it let's try coming up with some fast implementations for some some combinations of methods alright so we want to get by index and update by index who can tell me a good data structure for this this set of methods cool yes an array is gonna give me someone as a functional programmer and they set a tree they are of course correct but let's very fast so get my index and update index but it's gonna take constant time in an array right everyone agree thumbs up yeah cool what about if I want to have insert an end what's a good data structure now yes still an array this is so in particular like a Java style ArrayList or a dynamic array as you'd call it in I don't actually know on Wikipedia you'd call it that so this essentially which I'm just gonna call these three three methods stack right so stack just means like that combination of three methods we need to support what about if I want to just support the method insert last who has a good data structure for that so this is the only method I need to support does anyone have any ideas you said list I have an easier idea which is unit so unit is just the type with one element in it it's just an empty tuple and this totally perfectly supports all of these methods you say you want to insert last time like sure I did that that definitely happened doesn't like I am going to answer every query totally correctly about each of these so the moral of the story here is you don't actually have to support every plausible method you just need to support the ones that were required by the API so it's totally fine if you don't actually know everything about your input so let's talk about memorization a little bit so memorization is the idea where instead of computing the result of a read method every time you need it you store it on the writes in such a way that it's easy to access so how about if we want to support insert last and get some so I need to support two methods you put a thing into the list and you get the sum of the list what's a good God structure to that int yes so I just like have a single int somewhere which is maintaining the sum what yes Oh memorize some what about if I want to store I want to have inset lost and also get minimum what's a good data structure for that yeah absolutely so an inch is gonna work totally fine for this at this point you might do the totally incorrect thing of saying well I guess there isn't really a difference between these two situations if I need to support insert last and a reduction it doesn't really matter what the reduction is because I can just store it in a single int and I'm basically done and as we'll see that doesn't actually quite work so what about if I want to have a stack but also has get some what can I do so it supports all the methods on a stack as well as supporting get some who has any ideas yeah so we want to dynamic irate and memorize the sum so the idea is we're just going to be doing both of the things in in in birth and we're going to be using the faster read method well yeah so like each one provides naturally one of the read methods and we're going to use the the memorized some forget some and we're gonna use the dynamic array for the other read methods okay how about if we want to have a stack which I guess I didn't edit out and also get min can we do the same thing can we combine the memorizer form in with the stack no we can't it just doesn't work because when you try to pop things off the end of the stack you'll realize that there's no way of inverting the min operation so even though it when we just had insert an end and get some and inside it end and get min it looks like memorizing these things behave exactly the same but it doesn't so you'd have to use something like a heap or a binary search tree and I memorize min doesn't work so the moral of the story is data fractures are more complicated than just a table of things you can look up and combine so for instance you know they can support only a subset of all methods and they can rely on other structures to work so a better idea than considering all the different data structures separately is to consider all possible combinations of data structures and choose the fastest there are a number of obvious problems with this such as the fact that all possible combinations sure looks like exponential time to me which indeed is going to take but let's just deal with the fact that it's probably gonna take exponential time for now and talk about how we're going to do it so the question is how can we represents full-on knowledge about data structures so that we can reason about their behavior when combined right let's talk about how to do it so a data structure is going to be a collection of what I'm going to call method implementations let's look at any one here's a linked list a linked list has get first which takes constant time and get next which takes constant time does anyone disagree fantastic we can also have implementations which do not live inside a data structure and are simply true facts about the relationships between implementations sir for instance debt by index can come from get first plus n times get next does that make sense for everyone so this is a very natural way of expressing how you implement get by index in a linked list it also makes sense to have this method implementation around so get first comes from get by index and the reason is when I'm describing what an ArrayList does it's a lot more elegant to just say that get by index kicks constant time and not have to explicitly say that get first also takes constant time like get first it takes constant time because you just passed 0 and to get by index similarly get next can be implemented by get by index so one of the things like getting by the way this is I'm just gonna very quickly say this but uh whenever I say get the things like getting is like an abstract idea of everything we could possibly want to know about that position in our list so that includes its index and its value let's just I'm only saying this so that no one yells me about it later because I wasn't very precise if you just like kind of fitted intuitively it kind of works ok so it's an ArrayList here's like a more complete implementation of what an ArrayList gives you it has get by index it has update nerd which is the method which given a nerd which we've got bytes and that's probably we can change its value and we have delete lost in insert lost at the end does that make sense ok so now let's look about how we might want to combine these okay so we have an ArrayList on the Left which has these these methods get by index update nerd deletloss them in so lost and we have a some memorizer so let's look at how these four methods are implemented so remember that the some memorizer is just an inter at the West or in somewhere so you can get the some you just return the int does that make sense you can insert at a particular indexed sir inside it indexes the method that takes an index and the value and inserts the item at that index can anyone guess the implementation of insert hat index you add it to the end right yeah plus plus is the implementation you can also given a particular nerd you can also change the value of that nerd so update nerd is the one that assumes we already have a copy of the value and changes it so if we already know that the value of a particular position is five then update nerd means you know we're gonna be able to subtract five from our int and then add seven to it or whatever if we want to change the value from a five to a seven and if we want to delete a nerd that we already know the value of we can turn that we can just subtract that and we have a few relationships between these to be useful so for instance we know that we can do get lost with get by index we know that we can do delete lost with delete nerd and get lost and we can do insert lost with inset by index yeah sir let's talk about how we would get the method x given all these we have to figure out a way to start out with some like base cases like these and some inductive cases like these I guess and get fastest implementations for everything and we want to use a graph such and here is a lie of an implementation it's basically Dijkstra's algorithm except for the fact that we're on a multi graph instead of a graph this isn't actually quite a correct implementation but I invite you to look at my actual code but the basic idea is you figure out the fastest way that you could possibly you have like a queue of dot structure implementations that are potentially the fastest and you pop them off one at a time and then add them to like a result which is the the fastest implementations for every method so here's an interesting thing when we have multiple data fractions we might combining them together if there's two different ways of getting the read method you take the faster one right because when you're doing a read you only have to read from one of them but when you're doing a right you have to write to both of them and that's like a fundamental really important difference between read methods and right methods and so that means that we have our overall method which looks like this we want to get all the times for a set of data structures so we get all of our read times by taking the union of all of the read implementations of the data structures we've chosen and adding in all the default read implementations and calling get whole times on it which I guess I didn't write this isn't real code and then separately for all of our data structures seeing how fast oh man I really did not proofread this you take all the times from the read methods and for each data structure you put all the read methods in with the right methods and then we add it all together search for all those times combine all of the right times together and return that and we are done in real life actually it's much more complicated than that because of stuff like this if I can compute a range query in constant time if F is idempotent and I want to use this I have to pass along all of my conditions all of the time and so it has to like be able to maintain that kind of thing okay I'm out of time almost future work most important one I need a better name des what flavors com is not good enough and I want to add a bunch of other things as well I invite you to cheat on questions in job interviews with this as much as you can thank you very much it's been a good time do i apartment for questions on them hey yeah what's up sir yes the question is did I think about using a logic programming framework the answer is I did I didn't know how to use one this seems like more fun and additionally the logic programming frameworks I've looked at on obviously they'll tell you whether something is possible but they didn't seem to very naturally Express like it's cost so like I'm more complicated logic framework where like where like like you know what this is just like they're improving right from like a set of set of propositions in a set of like things but I didn't I I I would need to use a logic which had costs associated with theorems and I wasn't sure of a nice way to do that additionally there's a lot of complexity associated with the fact that there's actually multiple ways of doing everything with different costs and you have to maintain like a dominance frontier of all the different ways at once anyone else in in real life or in the design of this project in real life you give up because that's too hard and do things that seem pretty reasonable and then optimize when you find your bottlenecks thank you very much have a good day [Applause]