Radix Trees: How IntMap Works

Scale By The Bay 2018: Tikhon Jelvis, Radix Trees: How IntMap Works

Recording: Scale By The Bay 2018: Tikhon Jelvis, Radix Trees: How IntMap Works

yeah so this is kind of a bit of a bait-and-switch if you were here for the Ruby talk so I'm gonna be talking about radix trees and this is a data structure that actually goes way back historically I think the first version of this data structure the paper about it was published in 1968 that version was of course mutable but since the data structure has also come up as a very effective way to have immutable persistent key value maps in functional languages now in my case I'm going to have some code that's in Haskell but all these ideas apply just as well to Scala and in fact I just looked this up there is an inch mat in the sky low standard library so if you want to go back after this talk and see some actual Scala code implementing the same ideas then you can do this in just just in the standard library so the question I might want to start with is why did I get interested in radix trees at all like where did they come up so for me what happened is that I was exploring how to write code that works with graphs and I'm not talking about you know complicated graph databases or really big graphs that are hard to work with I'm talking about working with graphs that you know exist in the domain of our application but are small enough that you could just work with them in memory without anything too complicated so what I was interested in was not just a way to implement graph algorithms but a way to do it that actually felt functional see the problem with a lot of the ways that traditional graph algorithms and graph data structures are presented is that they are kind of unrelentingly unrepentantly imperative right so one of the things I found was that there's this really beautiful library called the functional graph library which actually came up with a way to let us work on graphs backed by an immutable data structure that we could recurse over now I won't go into details about how this library works although I do encourage all of you to check it out but the interesting thing here is that there was this purely functional operation where we essentially pattern matched on a graph and then took a note out and recursed on the remainder and I was really curious how could a kind of purely functional graph representation like this implement this kind of operation you know reasonably efficiently and what I looked in a bit a bit deeper this was backed by a Haskell containers data type that's actually pretty widely used in the Haskell world called int map and as it happens int map is backed by a radix tree so what this means is that int map as the name implies can only work with integer keys and the radix tree data structure takes advantage of the fact that you can look at the key bit by bit to have a different way to store a key value map then for example a tree based map or a hash map and again at least in Haskell this is one of the more popular containers and in practice tends to be faster than the data map that people use in a lot of code so the actual data structure was originally called Patricia a Patricia try and I think the story is that the creator of the data structure really wanted to name it after his daughter because the acronym is incredibly tortured it's a practical algorithm to retrieve information coded in alphanumeric so in practice these days most people call this kind of data structure and variations on the same data structure radix trees but due to bad habits I tend to mix the different names inconsistently okay so why is this data structure you interesting and useful so at heart it is just a and a key value map that can be implemented relatively efficiently in a persistent functional style but on top of this it has a few properties that actually make it an interesting alternative to hashmaps in some specific use cases so the original paper bio kesakhian gil that motivated the inte web container in both Haskell and Scala focused on the fact that these maps can be merged efficiently so this lets us take two maps and combine them while applying some operation to combine shared values that is values that have the same keys so this lets us do all sorts of things like an efficient map Union or efficient zipping and again in a functional style it is actually pretty common to have multiple maps that are then combined in some function to build a bigger map so that's one of the upside it's very easy to write an efficient merge function for in maps in this way it's actually pretty similar to tree maps but a little bit different from hash maps which make this kind of operations somewhat more complicated but the other thing that makes radix trees and impacts very interesting is that they let us efficiently do operations based on prefixes of keys so as we'll see when we look at the data structure the keys are stored by the nature of the structure itself in a sorted order and this order lets us in linear time read the keys of the map in order and also really efficiently read all of the key value pairs where the key has a certain prefix or even do operations do updates on all of the key value pairs with a certain prefix and the really cool thing that this allows us to do is to take two keys put them into a single integer so share the bits so we can say 32 bits goes to key one then the next 32 bits go to key two and then we can store this kind of hierarchical data in a single efficient map and still quickly look up every single entry that has some specific key one no matter what its corresponding key two is and so this is actually something that most other maps make difficult or relatively inefficient so while in practice the absolute performance of int map vs hash map is usually in favor of hash if you need to work with sorted keys or with prefixes then in spand radix trees really come out ahead and one other nice property is that an int map will with the same key value pairs will always look identical in memory regardless of how it was constructed and this is not a property good with hashmaps because hash maps often have internal implementation details that allow multiple representations for the same set of key value pairs and often depend on the order in which keys were set or added to the map so again if you need a really fast just purely memory based equality comparison radix trees can give this to you and this also just makes it nice for for example serializing radix trees just based on what they look like in memory so how does this data structure work how do we get these interesting properties so the core idea here actually goes back before Patricia and this is a whole class of data structures called tries and the name comes from the word retrieval and I believe the original person who coined the name wanted everybody to pronounce this word as tree but because we have other trees that's a completely awful idea so everybody calls them tries so what is a try so the idea is that we have some kind of key where we can inspect the components the simplest one to think about is we have strings of characters and then to actually access a node from the key value mapping we read off the key component by component so for example if we had a tree that looked like this and we have the key B we just take the first letter we follow that and we immediately see that B is set to the node one if we have a longer key then we still go letter by letter and we take in the case of a three letter key we take three steps we look up the first letter then we look up the second letter and then finally we look up the value associated with the entire key so what this means is that all of the operations on a try my data structure have performance that's proportional to the length of the key rather than the number of elements in the try and that that is actually a very different sort of asymptotic performance from pretty much any other kind of key value data structure that you see so why like what about this lets us efficiently work with prefixes well the interesting thing is that the way the data structure is set up looking up the sub try for a given prefix takes exactly the same amount of work and in fact has exactly the same algorithm as looking up a key value mapping we just follow the path exactly the same way but we just stop earlier and return the entire sub try instead of just the only value and so looking things up by prefixes isn't some complicated algorithm it is in fact the default operation for a try now the problem here so oh yeah so tries as I said like you can remember what they do by remembering the word retrieval unless you retrieve a key character by character but the problem with the approach that I outlined earlier is that like strings can be arbitrarily complicated so we can have an arbitrary number of different characters and this means that each node when you're working with strings has to let you look things up by letters and this might be pretty inefficient you can imagine strings having you know all the possible characters in Unicode and so each node of a try using actual strings would have to be some kind of key value data structure itself so we can make this a lot more efficient by looking at the binary representation of the key so looking at the key bit by bit instead of looking at it as a text string or anything like that and if we did this we could imagine laying out the entire tree for all possible keys now unfortunately the tree for any non-trivial number of bits gets really big really fast because the number of values is 2 2 the number of bits you have so even for a 3-bit key if we wanted to fully populate a binary try with all those bits we'd end up with eight eight elements and then as the key gets longer and longer this just becomes more and more wasteful so once we go with this binary binary route we do need to figure out some way of kind of compressing the parts of the tribe that we're not using so the first kind of compression that we care about to make this efficient is called path compression so sometimes we have a tree where we have a bunch of keys that all share the initial prefix they share some initial path having all of those branching nodes spelled out would waste a lot of memory and force all of our operations to needlessly traverse a whole bunch of pointers to get to the answer so what we do with a patrícia tree or a radix tree is we actually let each node store the prefix that it corresponds to and so if there's some number of bits in that prefix we just skip that entire prefix when we do a lookup and then the other kind of compression we have the other kind of path compression is what when the same thing happens at a leaf and the neat trick with leaves is that because it's not a prefix anymore we can actually simplify the logic a bit and just have each leaf store both the key and the value and so this makes the logic relatively simple when you reach a leaf in your recursion you look at whether the key matches whatever key you're operating on and then you're done and as a bonus it also makes it easy to write efficient code to traverse all the key value pairs in the map okay so data in map this is the half the library was talking about is a binary try with this kind of path compression and this is what is usually called a radix tree repetition tree so now I'm just gonna go into a little bit of code to demonstrate what this actually looks like when you go to implement this data structure so in order to actually support this we need a type with three constructors we need an empty constructor which is useful because we really want to have some starting point to build Maps and then we need a leaf and a branch constructor so the leaf constructor represents a key value pair we're done and the branch constructor represents those nodes where we actually have multiple paths that we can follow so when we turn it into code it actually looks somewhat similar to the kind of pseudocode you might write when you're sketching out how you would solve this problem and the one tricky thing is that when we have a branch we really need two pieces of metadata to work with we need to know what the prefix was so what amount of key did you skip over in order to get to this branching node and then we also need to have a mask or some indicator that tells us what bit in the key this actually branches so this means that for every single branch we end up with in our data structure we have about two inch worth of extra metadata overhead which in the grand scheme of things especially for persistent data structures by the way is not very much so one of the upsides of in map is that it has a relatively simple in-memory representation and is also reasonably compact so I'm not going to go into too much detail of how this works but I'll walk you through a single lookup function and then all of the other more complicated operations have the same feel to them because we're always going to be recursing down the try data structure in the same sort of way so here we're gonna start with the base cases of our recursion and one of the base cases is just if the tree is empty and then we just return nothing because there's nothing in the empty tree then if you have a leaf because we stored a pair of a key and a value we just check whether the key matches and then if it matches we return the value and if it doesn't match we return nothing the interesting logic all happens in how we deal with branching nodes because with branching nodes we actually have to figure out a couple of different things the first thing we have to figure out is does the key that we are looking up have the prefix that the branch has because if the key the prefix of the key does not match the compressed prefix of the branch we know that the key is not in the map then once we've done a check for that we need to look at the mask and figure out if the bit that we're branching on is the 1 or a 0 and then if it's a 1 we recurse down one side of the tree and if it's a 0 we recurse down the other and so at the end of the day the lookup logic is not all that complicated there are some fiddly bit wise operations here that are a little bit harder to work with and do need to be fast but the high-level logic is pretty easy to follow and personally one of the reasons I prefer this over hash maps is that you avoid a lot of the complexity inherent on depending on some kind of hashing function to manage your data structure ok so I just walked you through I think enough to re-implement you know either Haskell's or Scala's int map or at least the basic operations it look like if you actually want to do this exercise you could sit down with the Okazaki paper I mentioned and actually write a working version of this in a few hours at most this is actually how I myself learned how how this data structure works so it's pretty simple but it has some pretty serious downsides and in particular when I use the word binary it kind of had two hidden meanings one of which is that we're actually looking at the bits of the key in order to make decisions within the data structure but the other sense of binary is that the data structure I described always branches on one bit at a time so there are always two branches in the data structure now unfortunately this isn't always very efficient it means that our trees when they have a lot of keys are going to be pretty tall in principle if we have 64-bit keys a pretty you know heavily populated into map might have 64 levels to traverse and that's a lot of pointer lookups and tends to mess up your performance to a pretty large degree but as it happens we can take exactly the same idea but generalize it to looking at more bits at a time so for example we can change the span of the tree and look at for two bits and so if we're looking at two bits every single branching node has up to four children so this means that our trees get a lot shorter and in principle right this seems like quite a big victory and in practice having a larger span than two works really well at least for mutable data structures in the immutable case the all the updates become a little bit more complicated because the bigger the node the more you have to allocate whenever you make any changes but the other fundamental trade-off with this approach is that the bigger your span the shorter your trees are but the more memory overhead you have and the reason you have memory overhead is because if you you need to allocate a full array for the number of children at each node that you have so if you go back to this picture but we imagine having a tree that looks at 8 bits at a time this means that every single branching node has to allocate an array of 256 pointers now this works really well if your map is pretty dense but if you have a pretty sparse map where each branch only has a few children you're wasting a lot of space on these large arrays that are just full of nulls they tell you ok there's nothing down this path and there's a paper that I'm gonna talk about a little bit later which actually did this very nice empirical experiment on this and found that until you get to about more than 16 bits at a time there's this very elegant inverse relationship between the height of the tree and the amount of memory that it takes right and so one of the things that we want to look for as we think about how we can do better than this normal radix tree is whether we can get away from this fundamental trade-off is there some way for us to both have the advantage of shorter maps without wasting all this extra memory on big arrays for each node and as the graph kind of hints there is a way to do this and that's exactly what this this paper talked about and actually think this paper is incredibly elegant and had a some really promising performance figures and benchmarks and it's kind of a shame that most of the people I talked to haven't seen it and I think what happened is that I just know programming language people and this was published in like a data conference anyway so I'm going to talk about how this paper works and how we could adopt this to functional programming and persistent data structures now as the name implies the adaptive radix tree has nodes in the middle that adapt based on how full they are and in their paper they outlined a data structure with four different kinds of internal nodes with different representations depending on how sparse that particular branch was so their tree always looks at a a byte at a time so it looks at eight bits now beyond the advantage of a high span a bite at a time also fits really well with modern architectures because a lot of instructions and a lot of operations can naturally be performed on bytes and then I won't go in the details of what each of the four representations are but the idea is that we can tune different data structures for different numbers of children so for example we start out with just an unordered array for four children but when we insert an extra child we upgrade that unsorted array to a larger sorted array that can hold up to sixteen children so the downside here is that all of our operations get some you know significantly more complex because now instead of carrying about one case we care about four cases but actually we care about eight cases because we have four node types and four ways to upgrade and then of course once we get to implementing a merge algorithm we now care about sixteen cases because we care about eight cases for each of the two maps so honestly the original paper the data structure was implemented in C but I have no idea how you would get some of these algorithms correct without pattern matching and without nice checking and this is actually I think a really great example of where algebraic data structures can really help you get very tricky logic correct because the compiler ensures that you handle each of these you know 8 to 16 possible cases that you don't forget any and that every operation always handles exactly what it needs and I mean if you look at the data type we could define for an adaptive radix tree it looks just like the data type for the normal radix tree except instead of having explicit left and right branches so instead of hard-coding a branching factor of two we have some kind of children type and then the children type itself can be different depending on how many children it has and again I don't want to go into the details of how each of these subtypes works and in fact in my experiments I found that it's not necessarily the case that the exact set of node types that works well for a mutable tree would also work well for an immutable tree so why am i interested in this paper because this paper was actually designed for an efficient data structure for in-memory databases and it was all written with a mutable try in mind so and what happens my roommate wrote a version of this data structure in Java right that is persistent so it gives us the kind of expressiveness and correctness advantages that were used to in working with functional programming but still has some of the performance advantages of this more complex and more flexible data structure and at least on his benchmarks the Java version performed quite well when I went to implement the same logic in Haskell it did not perform well at all and to me it's actually still an open question about whether we could implement an efficient version of this in Haskell because as it happens Haskell X lacks some of the primitives that we need to do this efficiently but Java lets you write an implementation which on the inside is actually kind of ugly and mutable and in this case I think might even use some custom allocation system but on the outside is nice and persistent and I think this this conference is actually a great place to plug this project because if you're using Scala you could just call this directly and see if it works well for your application okay so we're going to review the few things that we talked about here the basic idea and this is by the way I think the most important idea to take away is this whole class of data structures called tries so structures that look at keys component by component and let you make decisions based on that these structures have a different kind of performance characteristic than other Maps and so especially if you need to work with sorted keys or you need to work on prefixes they can be a lot more efficient than a hash map and while I didn't go into details here radix trees are actually not the only kind of data structure inspired by tries in particular in the functional world thanks to closure the hash array Maps try has become a kind of pretty famous data structure and the details are different but it does use exactly the same kind of prefix operations on the inside to give us an efficient hash a persistent hash map and then if you look around there's been a lot of research on other kinds of try data structures which in in detail look totally different from what I've talked about but still follow the same high-level idea okay and then I talked about data on intimate so int map as I said is a pretty common container in Haskell and then it's also available in the Scylla standard library although I should say when I looked up the Scala documentation it suggested that you use hash map most of the time so and that is actually probably good advice and the way in trap worked is it's a binary try with path compression and if that's all you remember you could probably recreate the whole data structure from scratch in like a day and then once we move beyond internet we move beyond these much relatively simple radix tries we get to this world where we want tries with different spans and even tries with different kinds of data structures for each node and I think that this is actually a very interesting area to fluor for coming up with new efficient persistent data structures that can help speed up the kind of simple functional code we lecture right especially for some applications like graphs okay so are there any questions [Music] sure so the question was how do you scale these things and so it depends on what you mean by scale so first of all these structures really only makes sense for in-memory data and when I was doing my explorations I focused on the kind of use cases you might have for a normal map so relatively small Maps but you could actually implement versions of this which scale to larger larger sizes and the way people do this in practice is actually by having for example custom allocation areas for the different kinds of nodes and having an efficient allocator to create the structure and then if you can do operations in batches so instead of adding one key at a time you add a whole bunch of keys all at once you can do this in kind of one pass of the map without needing to allocate a bunch of copies and a bunch of extra pointers and so if you can batch up your operations and you have an implementation that takes advantage of these batches to avoid extra copying it can actually be pretty efficient okay Russians yeah [Music] sure so the question was that I you know I compared tries to hashmaps a lot and it might be make more sense to compare them against other kind of sordid structures so honestly the reason I kept resident hashmaps is because for a lot of workloads this kind of try or especially the adaptive radix chart is actually competitive with hashmaps so you get some of the advantages of being sorted while having really good performance in the real world and in fact the art paper if you look it up had some interesting benchmarks that showed that they actually outperformed the hashmap in the java standard library now the downside is they were like I found some other paper which did deeper benchmarks and essentially the story is that if you're willing to take the time to configure a hashmap to your uses so choose the right hash function and choose the right intermediate representation the hash map can still be a lot faster than a try but at least they're within range of being comparable and honestly while again tries and sorted structures have some advantages in theory they have much more efficient operations on sorted keys in practice hash maps are often sufficiently faster that you can get away with using a hash map even if it's not the best to it just because modern hash maps have been implemented and optimized really well and I think like hash map is just today the absolute gold standard for a key value map other questions [Applause]