Scale By The Bay 2018: Pathikrit Bhowmick, ArrayDeques and How to Contribute to Scala 2.13
you I'm here to talk about headaches and in in general bus color 213 collections and any particular data structure color red X while preparing for this talk I learned how to pronounce this correctly it's on English Dutch Stack Exchange it's not a raid EQ it's not array it's not array array dekes it's a raid X it's like a deck of cards alright alright so about me my name is fatty cred I work in a hedge fund called core to management I've been doing for Scala for six years I love data structures and functional programming so this fits in well so yeah let's talk about 213 collections since we don't have too much time it's only a 30 minute talk I wouldn't go too deep into it some things highlights can build from is gone if you don't know what it is great you don't need to know you shouldn't know unless you want to lose your sanity that's gone so before a map looked like this which is if you think if you stare at it for a little bit and you know what can go from is it makes sense but not really but now map looks like that which what your part map should look like and and at a high level though to abstract over collections is moved up here which is the CC which is the abstraction so you can go from one type of collection to something else alright so there are some new api's I'm not gonna give you a tour of the api's you can look at the scala doc you can click on what's new in 2.13 and you will see the new api's some examples are this is one of my favorites where you want to do a group by and you also want to map values at the same time and there's something called group map so these are kind of like syntactic help that about common operations in place mutable api so the few of you who you use mutable collections this is pretty useful if you want to if you have a mutable buffer and you want to filter and map but you don't want to each time create a new collection you want to just mutate the mutable collections you have filter in place map in place a couple of these there's some more stream versus legend list streams are gone they listen in there's better support for views use are a first-class thing not an afterthought it's built into every collection we don't have the traversable versus iterator versus iterable dichotomy I myself I don't own the top of my head which one does what after doing five years of Scala now it's just the kerbals and there's some new collections so let's talk about array decks it's a new collection in Scala 2.13 it's also known as circularbuffer in the literature it's a replacement for most mutable collections it's faster than mutable array before when you use it as an array when you're doing random indexing and it's faster than a linked list when you use it as a linked list when you want to insert things at the beginning of the end and are at a particular index and there's my first contribution to Scala I have written a couple of libraries before but I've never actually contributed to Scala lines so that's cool all right data structures 101 this might be a little hard to see but this is essentially a table of asymptotic complexity and the mutable collections that you have to offer so at the top you have array buffers so these are basically your array lists from Java or just vanilla erase that resizes when you run out of capacity so the cool thing about Aria buffers is you get constant time random index so what that what that means you can get the element at an index I or update an element at the index I in oh one which makes sense you computers have random access memory and you can go jump into a Cell go updated you can append to it you can put an element at the end in constant time which makes sense I mean you already have a pointer or you know the size of the array you can just go OOP one more at the end but the moment you try to prepend something when you want to insert an element at the front of the array it's no longer constant time it's a linear time operation because you have to move everything in front of it to the right same for if you want to delete something from the beginning of the array it's no longer constant time because you have to shift everything left but if again delete last is easy you just move the last thing back and this problem happens because why do you do move things around when you do them stuff in from the front because you still want to have the random indexing property if you contrast that with something like a linked list it's kind of the opposite the linked lists have nice properties where you can append and prepend in constant time because you have a start and end pointer and you can quickly switch around pointers and insert things in the beginning without shifting everything to the right you just move the head pointer back but now you don't have constant time random indexing because too if you have a linked list of million items in you want to update the thirtieth 30,000th item you have to follow your pointers till you reach the 30,000 item and this is where a rednecks are cool because it's the best of both array buffers and linked lists you have not only have constant time random indexing but you also have constant time through band and append and delete first in the Lee class and even the insertions at the ayap index is faster than the waveform it's faster than the link list one and for the array buffer it's it's the how far you are from either end so 2 inserting at the ayat index it's men of I and the size minus I and same for delete also and I'll show you in a bit how we achieved that there's also java.util since Java 7 has a narrow deck it has couple of short comments I mean besides being in Java which is it doesn't have a public get it has a private get for some reason I don't know why and the insert and deletes are not optimized and the one in the Scala 2.13 it's faster so this one does a very naive one okay so let me try to zoom this there you go okay let's start with a very vanilla implementation of an array attack so okay we create this class or a deck underneath it's just an array initially let's start with the 64 items in hand all right and you have a start and end pointer they both point to zero I mean and the invariant is and the start is inclusive the end is exclusive so Breton on the array is empty okay how do I insert an element at the ayat' index so we this is a key operation you do everything offset from start okay so start an end you can assume could be anywhere it happens to be when you initialize it to be zero but it may not be it could both be 17 for all I care and you do everything with the offset from the start index and you don't want to overflow the capacity so you do modular arithmetic so you do modulo and where n is the size of the array okay and similarly for get so similar to for the read and you do the same thing ok so that's simple okay how did the pen so band is basically you insert at the end index and you increment the end pointer and here I mean obviously I'm not actually moving pointers around I am moving incrementing and decrementing variables okay so prepend prepend prepend looks very similar to a bank and what i did was i decremented the start pointer and inserted the element at the start so i mean you can see then you could screw up here and have an off by one error but follow with me here so the idea is you have start and end pointers and when you insert at the beginning you move it back and when you insert at the end you move it forward and you do modular arithmetic all the time to make sure you don't go out of bounds all right delete last this is easy you just move the end pointer back there are some caveats regarding garbage collection how go to it in the end because you actually have also have to deallocate but that's details delete first okay you move the start pointer to the right and clear you want to clear the whole array again you can just set the start to the end no you just emptied out as if you pretend that nothing existence exists in the array and lastly sighs this is cute and - size and - start and if you do modulo and it handles the case when start an end are when start is not less than end I hope this pseudocode I mean know this code compiles convinces you that this kind of data structure is possible if you see none of the operations are linear time they're all constant time operations and I have managed to write and update and apply an append a prepend a delete fast and delete left a clear and a size in constant time I mean obviously if you actually look at the 2.13 code this is not what's there there's a lot of devil in the details like how do you handle resizing you have to do smaller resizing which is doubling up at appropriate times or shrinking down if you're doing a lot of deletes you want to shrink it down also a lot of times this code also doesn't show you the insertion at the ayat index which is non-trivial to write because there are many cases to handle and what else up you will see the implementation everything is actually done in the 2.13 collection in scholar repo in using array dot copy which fans out to mem copy which is pretty fast so this doesn't do that this is just for the slide to show you a Minimum Viable data structure and I hope that makes sense why it's now called an array deck it stock it stands for array doubly ended queue it has both start and ends and you can insert and at both ends and you can do modular arithmetic from the start to get to be either index fast alright time for a little demo let's see okay so so initially when you create a arrayed FMD here I'm trying to create an empty data structure of characters as I said your start and end pointers which are just integers they're not pointers what I like to call the pointers are set to 0 the invariance is that your start is inclusive and is exclusive in this case there's nothing in the array the array is empty and instead of 64 back in the slide I created a size of 64 for the purpose of this demo i created a size 8 array so it's right game it's allocated this little pie means null which is slightly different from the 0 here so initially it just pull up in ops when you create a empty array it's there's nothing in it well at least for primitives it has whatever the Java primitives is things the zero byte state code okay all right so what happens when I do an append well I increment my end pointer which is add one to the end and fill it out yeah well I insert at the end pointer then I increment so and what 0 and this is where it goes inserting a B that's the same where I again insert at the end point where it was at the want index and increment and increment n so n becomes 2 and I inserted d1 okay a fancy fendi fendi okay now this is cool I want to do a remove head in Scala 2.13 that is remove head and remove head option for the mutable collections and remove head options obviously safer because or to handle the case when you have an empty collection so in this case when you remove head I look at the start index so start is 0 I returned that which happens to be a at this point and increment the start pointer so and set that index to now so if you see here at the 0th index down here it will return a and set that to no so let's do another move head option and that's the same thing it increments the start pointer it returns B and shrink the size and if you see that size of the array is still a start - end which doesn't matter n - start start - n is 3 or minus 3 but if you do modulo the size of the array 8 you get 3 so that's the size of the array right so now the remove had option you get back C remove head option once more you get back e now this is cool I'm gonna do a prepense so what does free pen look like i decrement the start pointer and insert added element so in this case start was 4 I decrement it becomes 3 in certain apps and doing cute or depend F so the way this diagram works this is where the operation is this is the internal state of the data structure and this is the external state of the this is also the internal state of the data structure and this is the external state so as far as the outside user is concerned the zeroth indexes F but internally the third index is F and the fourth indexes e-even though externally you're saying it's 0 & 1 hope that makes sense okay so prepend pre bench G I sorry pengie it goes to the other end append H now this is cool so because of the modular arithmetic when I try to append now it will append here at the 7th Index but that's how big my array is so but it will wrap around the end pointer will wrap around and you see inserted I but now end is 0 because it is doing modular arithmetic it's doing 7 plus 1 mod 8 which is 0 and right so if I append J now it comes so as you can see the external the external API is 0 1 2 3 4 5 FV G H I J that's the current state of the mutable data structure but internally your array is all chopped up you have it starts at 3 it goes still here then it wraps back here and you have the start and end point curse and you're doing offset from the start or the end and doing water arithmetic ok so remove last option remove more so again it wraps back so when I again remove from the end the pointers wraparound wrap back and yeah and after I did enough to remove last options all my race clean and you see I ended up with start and end pointer at some random kids at the flip index but that's fine because the size of the array is zero and again if I do another remove adoption it's going to return none because there is empty a parent case so let me do some more pens so boom boom boom so what happens now so now the array is almost full and I champion cert one more and this is gonna resize from it will go from eight to sixteen elements and you've seen during the resize it actually moves the block from start to the end of the array which is KLM and from zero to the end pointer into a continuous sequence here the way it does that it uses array dot copy which is mem copy down underneath which is pretty fast so it is basically three month three at most two to three mem copy operations when when it does resizing so again I'm going to do some more appends free pens and by the way all this code is on github so I'll put a link to it and yeah it's another resize and you can see again it resize corrects correctly it moves things into contagious blocks and clear again just sets the start and the end pointer to the same so if I call Claire it's just and it also needs to obliterate out all the elements in the self so this is a current bug in Scala 2.12 array buffer collections if you call Claire on a mutable array buffer it doesn't actually deallocate the cells which means there is not visible to the garbage collector so that's a bug we just fixed because we noticed it in a rate Dex into 30 so watch out for that and yeah so there are two kind of clear operations is clear and clear and shrink because sometimes when a mutable collection you have already because of internal resizing you might have grown the array to a lot a huge size in this case Claire grew to a 32 cell element and sometimes you want to also shrink the array so there is a clear and shrink of in this case we'll shrink back to the default size which is 8 or 16 in 2.13 and that's it for the demo so all right right so performance as I said all the operations bottom out to mem copies all the complex operations insert a delete add anything slicing and moving so it's pretty fast clone slice insert or prepend all we do preemptive allocations which means when you're doing insert all it doesn't actually go one by one resize one by one resize resize it actually does a single scan figures out the optimum final size and again does a mem copy there's a cute bit hack you don't have to do modulo if your size of the array is a power of two you can do at Amazon operation and so I percent and it's the same as I am person in minus 1 if n is a power of two here are some benchmarks as you can see it's the only operation that is randomly taxing a little bit slower because you're paying that bitwise operation for doing the modular arithmetic but everything else is much faster in cases like if your prepending few things atom partically faster instead of it just a constant factor game and the cool animation that I did is actually just 30 lines of Scala it's a cool library I came across at this conference last year called rectory what it does is you get access to private members of the array deck and you can create render of the state which is pretty cool it made me generate that slides with 30 lines of color alright takeaways please contribute contributing to Scala is not scary if I can do it anyone can they're cool a lot of cool data structures people kind of try to love algorithms but there are a lot of cool researchers out there their papers and things that you might be able to have a good time implementing visualize your data structures use the rough tree library it's and for instructional purposes if you're teaching data structures to students yeah go check out 2.30 so all these slides and the visualization corn isn't my github and lastly we're hiring so we're hedge fund located in San Francisco and New York we do a lot of quantitating data science College Park come talk to me if you're interested [Applause] your questions you