SF Scala: Michael Pilquist, fs2.Chunk

SF Scala: Michael Pilquist, fs2.Chunk

Recording: SF Scala: Michael Pilquist, fs2.Chunk

all right welcome everybody this is the uh joined us of scala's caliber and vancouver scholar top through the mercy of virtual world uh we unite a lot of communities and uh i'm alexis roberto the founder and organizer of some of this and uh we're very happy to have with us today uh michael bilquist coming in from philadelphia who is a veteran scholar developer and architect um and he was a speaker at our meet ups and conferences so we're very happy to welcome him back we have the talk on fs2 chunk and uh the second talk will be by jovanza joseph who will talk about apache pulsar uh and when he recently published a book about it and it's transactions and so they're both scholar developers um and uh take it away michael all right great thank you for having me uh this is actually my first time speaking at uh sf scala but not my first time at vancouver so um really pleased to be back in that sense um so yeah so today's talk is about fs2 chunk um the fs2 chunk data type is a bit of a a workhorse of the fs2 streaming library but it tends not to get that much attention uh from the conference circuit if you will um you know it's a it's a basic data type but nonetheless i think there's some very interesting design decisions that went into it uh over the the many years i've been maintaining the library um so with uh without further ado let's let's jump right in um so what is a chunk uh a chunk you know to prepare for this talk i went and sort of did the rich hickey style um go to a dictionary and grab a definition of something in this case my dictionary is the scala doc of fs2 and so i grabbed these two lines from the the beginning of the scala dock of chunk so chunk is an immutable strict finite sequence that supports efficient lookup okay this gives us a bit of a feel uh it's immutable right we're functional programmers we like immutability um we've got this funny strict thing which we'll talk a bit uh about today um so so hold on to that one um it's finite we have a streaming library so if we need to do like infinite streams we can always you know emit chunk after chunk after chunk so our individual collection type that carries elements can be finite and then notably it has this efficient indexed lookup so this definition is interesting but it's a bit lacking and i say it's a bit lacking because really this is satisfied by vector really or satisfied by any index sequence in the scala collection library so why don't we just use vector as the main data type in the fs2 library let's take a look at these two capability traits so here i have one trait socket that has like a reads operation that gives us a you know maybe a potentially infinite stream of bytes coming from a network socket and i have a files capability trait that lets me read you know some some bytes from a path on disk um in both of these cases i get an fs2 stream back that evaluates you know any number of effects in the effect type f and gives us bytes gives us individual bytes streams move chunks of elements around not not single elements right a stream is like a vehicle of chunks is one way to think about it and yet you know our our type here is a stream of f comma byte not like a stream of f comma byte vector or you know list of bytes or something um so we want this nice compositional api that lets us look at streams as you know sort of these infinite sequences but for performance reasons and for efficiency reasons we're going to move around densely packed uh sets of elements at a time right the other uh sort of interesting thing just with this first set of capability traits is that both of these two stream types really represent some type of operating system you know io type uh interaction right we're reading things from the networks we've got some maybe kernel interactions here in both cases you can imagine probably things like maybe java nio direct byte buffers interacting with our underlying operating system and so we want to find a way to have as minimal copying as possible um you know we don't want to to take the individual byte buffers that maybe come back from a networking api and move all of their contents into let's say a vector and yet when i got first involved in this library back in like 2014 or so maybe 2015. um that's exactly what it did the emit the emit constructor of at the time what was called process what is now called stream emitted a sequence of elements and when you looked at the implementation of emit it basically wrapped elements in vector so i would do performance tuning i was working on applications at the time i did like mpeg-2 video processing um processing like big transport streams worth of video content um and i would have maybe performance issues and look at you know things in the profiler and one of the things i noticed was garbage collection pressure as a result of lots and lots and lots of tiny vectors so what i have here is a chart uh in the on the vertical axis we have different data types we have vector in scholar 212 and prior vector in 213 for anyone that didn't know there was quite a bit of performance work uh put into the 213 standard library improving vector and then a primitive array of bytes and then the fs2 chunk of byte and then on the horizontal axis i have like the size of each of those collections from empty you know to a single element up to 10 000 elements and what i'm measuring here in this chart is like the the memory size you know that the heap allocation for for a collection of that size so some things are kind of interesting here on the far left for for empty collections you can see a ray and chunk are each the same at 16 bytes apiece but like a 212 vector is 56 bytes for each empty vector a singleton vector is 216 bytes in scala 212 but only 24 bytes for a primitive singleton array and 32 bytes for chunk right and as you move to the far right there's other interesting things in particular when we talk about bytes right a primitive array of bytes is going to be densely packed but a 213 or 212 vector is really going to store bytes in object arrays right in like a tree of object arrays and so we have a bunch of wasted space as a result of uh you know those object arrays storing boxed bytes and you can see that you know pretty clearly in a you know a roughly you know 4x increase in storage space so um chunk we we can see here is competitive you know within a constant factor of primitive arrays so we need to augment our definition a little bit it's not sufficient to say that a chunk is just immutable and strict and supports index lookup we also want chunk to be memory efficient for both small and large collections and we want to chunk to avoid copying just like we saw in that network example defer that copy unless it's absolutely necessary so let's walk through these properties one by one and sort of build up a representative version of chunk since this is a slide and not the actual cross-building code i can use scala 3 and i don't have to use any braces but otherwise this is going to be representative of the types of things you'll see in the fs2 code base so a chunk is finite it has a known size at all times there's no such thing as an infinite chunk and that size is a 32-bit integer this is unlike let's say a bit vector from s codec where our sizes you know may be longs right maybe 64-bit longs if you have a use case where you need more than uh more than a 32-bit integer then you can always emit two chunks or n chunks in in a fs2 stream a chunk has this efficient random access and so when we say efficient that's sort of a loaded term what do we really mean by that uh in this case we chose to implement it in this way a chunk just like an index sequence in the standard collections library or just like an array is going to have an indexed based apply method that returns the element directly i'm a functional programmer at heart i want my functions to be total and yet you know it's the second function we've added to chunk and i've defined it in a non-total way right i can pass an index that's out of bounds and you can probably guess what's going to happen we're going to have to throw an index out of bounds exception i we don't wrap you know the result in option in this case because the access patterns we want to support are really index based access patterns you know looping through elements with while loops as an example and so we don't want to force all usage of the indexed api to be going through sequencing or traversing or otherwise wrapping and unwrapping options all right so we're already going to start making a little bit of a trade-off in our design space so how about that memory efficiency property how we're going to implement that um here's a bunch of constructors we have a constructor for an empty chunk and in fact it's a valve it's a single valve that's shared you know just like uh nil in in scala for lists right chunk.mp is a single chunk uh it's got a fixed size right that's how we managed to keep that to the minimum object footprint we have a singleton constructor that just wraps a single value of type a right so all we're paying for in this case is the reference to that single value of type a on the heap um and the object header of this instance of chunk again that's why that was just you know just slightly larger right there's only 24 bytes on the heap and then this third one maybe is a little bit more interesting we have an array constructor which wraps an underlying java array and note in particular we don't do defensive copying right so this is sort of a handshake agreement to get immutability if you construct a chunk via the array constructor and then go and mutate the underlying array that you gave us that chunk is no longer immutable but that's a trade-off we've decided to make in the design of of chunk to get the performance characteristics that we care about and we've got a few other likes like that we have the ability to wrap any index sequence including vectors again we don't need to copy those elements if you have an index seq that's already got uh you know already constructed with all your elements there's no need to move them into an array just to wrap them into chunk and likewise with support for network apis like java nio bytebuffer and again bytebuffer like the array case is not doing defensive copy you might say well wait a minute that first line of that method looks like it's duplicating the buffer but if you have not used the java nio api that's only duplicating the sort of cursors that point to the underlying data that's not duplicating the raw data itself so again we don't make defensive copies in this case so consider this example maybe we have some api that gives us you know a few megabytes worth of data from the network and we store that in this val huge and then we've got usage that maybe looks like this someone says huge dot take 10 take 10 bytes from that and then maybe again they say huge.drop 10. so we want to minimize copying in this case maybe we don't want to iterate through twice so maybe instead we'd write that with split and so in this case you know we say huge.split at index 10 we get a prefix we get a suffix and now we have an access pattern that's pretty common when writing stream combinators the access pattern is like process the the prefix do something with it maybe we're parsing bytes into text or you know doing some type of framing of a binary protocol but we're going to process that prefix and then when that operation completes we're going to go and store off the suffix maybe wait for more data to come in from the network right and then further process that later and so the challenge here becomes you know how can we ensure that that suffix doesn't have to do a full memory copy of the data stored behind that chunk the way we do it is via this array slice constructor so this is just an example of structural sharing the idea is that you know array slice itself will store an underlying array and then store a starting offset in that array as well as a count of elements from that offset when we look up an index in this we're just going to you know shift the index up to the offset and then we can implement split at in a constant time zero copy way right we can say if the index that we're asked to split at um is in bounds then we fall through to this last else case and we just have two array slice constructors right both of which are constant time so we get a free you know from a from a copying perspective we get a free implementation of split at but what did we give up by doing that um one thing we gave up is this notion of strictness right normally with a chunk we said we want all of our operations to be to execute immediately not to be deferred the way like maybe um a view would be in the standard collection library or an iterator right so we want all of our operations to sort of execute as soon as they can and in this case we're really delaying the copying right we're delaying the copying because it's you know in most cases a good trade-off for the performance of most applications um so we'll talk about you know how to deal with it when that's not the case um but we we sort of given up a little bit of this notion of strictness um similarly we've given up a little bit of predictability or maybe as a result of the loss of strictness we've given up predictability around memory footprint if someone is given a chunk that has size 5 or size 10 from some arbitrary function they might think that that chunk is only you know taking a small amount of heap space when in reality it may be an array slice pointing to an absolutely enormous underlying array all right so we've given up a little predictability in our reasoning around the memory footprint of our chunks so we'll come back to that but before we do let's look at uh the implementation of a few combinators on the chunk type um so the first is the simplest um it's for each the same for each that we see on list and on any other collection because we have constant time size and constant time apply we can implement for each for all of the different constructors of chunk as just a simple while loop um and in fact fs2 for a long time had these while loops inlined in all of the different operations on the chunk data type i'm thinking that like in lined while loops you know you can't get faster than that right like it's the compiler's gonna do some vectorization magic and it's just gonna be great um and we had recently switched all of that back to uh implementing all the combinators in terms of 4-h and 4-h with index to look at it in a second and actually got a performance boost so sort of interesting hot spot optimizations going on there all right we have 4-h with index same idea right it's a while loop we just pass the index i to the function as we walk through the elements of the chunk so now with these two we can start implementing more interesting combinators like map the same map that you know from any other functor uh including this you know vector so forth um and maybe our first implementation of math looks something like this we go and allocate an array of b of a given size you know we know that the map isn't you know mapping a function over all the elements in a chunk isn't going to change the size of the thing that we return so we can use the size of this chunk to allocate our target array and then we just run through you know iterate through all the elements using for each with index and apply each element to our function and store the result in the corresponding array index but this doesn't compile and it doesn't compile because we can't construct an array for some uh generic type b right the compiler complains it says hey you don't have a class tag in order to create an array you need a class tag for element type b so we do what all good programmers do when the compiler complains about that constraint we just add a constraint to the function so in this case we have this function i change the name of it to map concat now instead of map and i picked up this class tag constraint and now this works absolutely fine the body of the function didn't change at all it compiles it's performant there's no problem with this definition why did i call it map compact instead of math partially because i don't really want to redefine what it means to be a math function right partially because when you look at like a functor map i have a functor instance for chunk i want math to have no constraints i don't want it sort of limited in a certain way you can only be a functor if you can provide me this class-type constraint in some way um so partially for that reason but there's a bunch of other reasons as well and in fact map compact doesn't exist at all in the library we don't have this function in fs2 one of the reasons is that function one itself is not specialized for very many types now note as of now scala 3 doesn't support this but um 213 and prior you can see is not specialized for byte in the return type or in many of the parameter types um so just by the very nature of using this higher order function map you're going to do a bunch of boxing and perhaps a bunch of unboxing depending on what your target collection type is maybe more important than like function specialization and runtime characteristics is the fact that class tags you know virally propagate if our caller is a also in a generic context meaning like they're they're parameterized by some type parameter a and they call map on a chunk of a um they might not have a class tag for their target type b and so they might have to pick up that same constraint and those constraints start propagating up the call stack typically until you reach a point where you have a concrete target type from an api design perspective this really forces folks to have to make a hard decision if you're using chunk and you need to call the map operation if you got one version of map that doesn't have a constraint you got another version of map map from cat that takes a class tag now you have to you know make that the same trade-off for yourself like should i pick up the constraint on my own type parameters and use the fancier version or should i drop that constraint and use the one that maybe is less performant and then finally and this is the you know sort of the real kicker is that we're going to run to the same problem over and over again in the various combinators we define on chunk and we can't make this same decision you know you know of splitting of having a uh a concat or a or a uh you know dense version that that uses a class tag as well as a version that doesn't use a class tag and just stores things some other way we can't make that same dual operation for every single company so we need something that's orthogonal to this right we need a way to um to implement map first of all such that it doesn't require class tag constraint but then also to opt in to getting this compaction behavior so let's first implement map um the trick is the following it's the same trick that's used in the scholar collections library you don't normally see it because it's hidden way deep down um but it's the same trick that's used so in essence we are going to create an array of any right so we're going to have a an object array we're not going to use a primitive array in this case and yes that means if you were mapping like to a byte like your b type here was instantiated to be byte then that means we're wasting some space right because now we've got maybe four byte you know array elements instead of one byte array elements however note what i mentioned about function one not being specialized one byte things are already boxed so from a performance perspective you know maybe that doesn't matter even though a storage perspective is a different different thing okay so we construct this array of any um the rest of the function looks basically the same until the very end where we cast our chunk of any back to a chunk of b and of course this is completely unsound right um the only way we can make this work is if we absolutely guarantee that this underlying array is never directly accessed as an array of b if it is directly accessed an array of b things might work things might throw an array store exception things might throw a class cast exception so we have to be very careful that this array is kept as an implementation detail only but as long as we can manage that this does in fact work and is safe on the various platforms we compile all right so we have a version of map that doesn't need compaction but how do we get compaction if we really care like if we have a densely packed um you know object array now bites and we know we're wasting all that space we want to you know maybe compact it back down in certain cases so here's how we do that we have two operations you have a way to convert any chunk to a primitive array and in this case we'll just pick up that class tie constraint this looks very much like map except we're not taking a function right their original version of that so we just picked up a class tie concern and that generally doesn't have the same disadvantages as picking up the class tag constraint on map the reason i say that is that if from a caller's perspective if you're trying to convert a chunk to an array it's because you want like a primitive array like you want to go and allocate a byte array because you're about to pass this byte array off to a you know some input output library or something that works in terms of byte arrays um so just the the cases in which this come up the use cases in which you you want to do this end up being cases that already align well with either being concrete or having access to the necessary class type and of course if you want to just compact a chunk we can do that by just wrapping the result of two array in an array constructor now in reality in the library these operations are much more complex because we do a bunch of uh performance uh enhancements here there are cases where like if we know the internal array that's used in the array slice is already a primitive array and we know that the target array that you want to move to is the right primitive type that matches you know then we can do like a bulk array copy instead of you know moving elements over one by one and there's other specializations for various constructors of chunk but this is the general idea all right few more operations how about filter filters sort of like map right we're going to run through all the elements apply each element to a predicate and keep all the ones and the predicate returns true in this case we don't know the size of the array to construct but we can use the collection library's mutable array builder if you haven't used mutable array builder you should it's awesome um it's basically java's arraylist uh it's it's starts small and then um grows by powers of two using you know underlying arrays uh behind the scenes so in this case um we create an array uh sorry we create an array builder but we have the same class tag issue so we're just going to you know jump you know use the same trick um jump right to the solution we're going to create an array builder for any now we pass a size hint we say we feel like most of the time when people filter chunks they're going to keep most of the elements and of course that's not always true of course there are cases where you filter out all the elements or filter out most of the elements we sort of feel like you know most of the time that's that's a a good um you know common use case and so in that case we're going to give a size hint to be equal to the current size of the collection this is going to avoid a bunch of the intermediate copies as the array builder starts small and then starts doubling in size as we add elements while we iterate right and then you know we iterate through the collection you know the predicate passes we add the elements eventually we call b.result and dump all of those uh you know all of those elements back into a single array and array builder will do the right thing you know if if the target collection has fewer than the size hint then it will do the copy if it has to it's exactly okay so with combinators like that um maybe the next design choice we have to make is what to do about copy or how can we discourage you know bad usage patterns usage patterns which might have undesirable performance so let's look at this example again we have some huge maybe multi-megabyte chunk and then we have some tiny little chunk in this case like a character turn line feed you know just two bytes and here we're using stream.chunk which is like how you get a stream of elements from just one individual chunk but like these two programs here stream.chunk of huge concatenated with tiny little crlf that program is the same as the second program which says lift the huge chunk into a stream and then concatenate another stream to that which is the result of lifting this tiny chunk so we want the bottom one to be the one that folks write naturally we want the line four to be the one that's sort of avoided because we don't want this copy occurring right um so we take advantage of the fact that as programmers we like things that are elegant right we like things that are simple and and look nice and so for the uh pattern that we don't want folks doing we just make it ugly we make we make it um you know difficult in a sense we add friction as one of my colleagues likes to say um so we have this chunk dot concat method which takes a sequence of chunks in particular we're just not providing that plus plus method on chunk right because if it's there then folks will use it but they might not think about the fact that they're actually getting you know copies of data so let's look at chunk.concat so we take this sequence of chunks we take our class tag constraint um you know we we scan through our sequence of chunks adding up all their sizes to come up with total size we allocate an array of that size rip through them um you know maybe copying chunks you know directly into the array by offset using some copy to array operator that i'm not going to show you um you know fairly straightforward okay what could go wrong with this implementation well let's look at a potential use case for so this method on con's ends got a lot of syntax don't worry about all the types it's not entirely important let me just describe what this method's going to do this method does exist in the library in fs2 it's very common what uncons says is given some stream of elements you know s here stream of elements of type o and given a desired count of elements n pull on that stream until we accumulate exactly those n elements and when we when we've acquired those n elements emit it as a single chunk just one chunk of those n elements and then also give us the rest of the string in case maybe we want to process that more later so this type of like request northbound for and many elements then go do something very common pattern in uh stream libraries so to implement this we're going to use recursion so we're going to have this internal sort of loop function go and what goes going to do is accumulate constituent chunks right because our source stream might be giving us individual chunks like chunks with just one element it might give us empty chunks sometimes it might give us huge chunks that are much bigger than what was asked for right so we're going to accumulate all these small chunks until we reach our size n and then we're going to call go recursively you know building up this accumulator until we reach the right size so here on line 10 we say pull from the source stream that's what this s.pull.uncons does if the source stream is empty that's we get this none in which case we say well we couldn't get all of the elements you wanted so we'll just give you everything we've gotten so far so we're going to return chunk.concat with an empty stream since we reached the end but instead if we've got some some element some trunk from the source stream and then some tail remainder stream then we've got a couple conditions you gotta deal with if that head stream i'm sorry if that head chunk is less in size than the desired remaining number of elements then just cue it up stick it into our queue and call ourselves recursively decrementing our target size by however many elements we just got right and if not if the head size is greater than or equal to our desired size then we're going to use that split at combinator we wrote we're going to split the one we got into a prefix and a suffix we're going to cue up the prefix into our accumulator and then concatenate all those to a single output and then we also are going to take the suffix and cons it onto the remainder stream right since we didn't quite need to process that stuff yet so what's what goes wrong with this implementation the issue here again is that class tags virally propagate and so on cons n in order for that previous implementation to compile would need to pick up a class tag constraint on type o and that is an absolutely valid approach to solving this problem in fact i tried it recently again despite this method existing for something like nine years unfortunately this combinator ends up being really common like i said it's used all over the place in streaming libraries maybe you don't use it directly but a bunch of operations that you do use directly use this right and so it it really starts propagating all throughout the library you end up picking up this class time constraint another option is to change the game you know move the goal posts um don't concatenate right we're accumulating these constituent chunks into a queue maybe we just change our return type to just return that queue okay valid option you know might be okay might not be okay depending on the use cases for this method one of the problems with this approach is that this the total size that has been accumulated is no longer constant time like whoever gets this queue of chunk if for whatever reason they need to know the total size they're going to have to scan through that that q and add up all the element sizes right a third option is we could remove the class tag constraint from concat with a similar trick like we did with meth so let's take a look at that we have this concat tagless implementation um basically don't take the class tie constraint and instantiate an array of any otherwise everything seems fine but we do have this primitive boxing behavior the same primitive boxing behavior we have with math and unfortunately this one does start to have a performance issue when you look at the use cases for things like uncons n this does show up in a lot of places right so even though it's the exact same trade-off that we we had with the map operation um when you look at uh realistic use cases for these operations it ends up the trade-off not ends up not being as uh as much of a win so how can we fix this well we had this implementation for years which i now call concat too clever um concat2clever basically said well what if we could test and validate that every element of every constituent chunk is a certain primitive type right so the algorithm here looks something like this it says if the input chunks for every one of the constituent chunks they only contain bytes then call the version of concat that works with a class tag using bytes you know using the byte class type we're going to have an if else like that for every primitive type now of course that's a linear scan maybe it's not a big deal right maybe like when you think about concat from like an asymptotic behavior it's going to be linear anyway right and as we all know like when it comes to performance all we ever care about is asymptotic behavior of course right we don't care about constant times who cares if we have to do two passes through our data no of course not that's terrible so um you know performance is is a challenge we had a performance uh solution um one of the ways in which we invite we avoided double scans is uh we had this contains only method that had a shortcut to say if the target chunk knows for a fact that it has an element type of of a certain type basically it picks up and stores a class tag then we can do that with just a single check instead of having to look at all the elements inside of that chunk so okay like that that buys us a certain amount of constant factor performance um but really what what killed this approach was javascript um this is a fictional javascript rebel but if you haven't done a lot of javascript then maybe this comes a surprise but there is no primitive types in the javascript runtime right like the value one if you have a lot of experience in the jvm you think that's a primitive hint so clearly a primitive int is not an instance of fight but on javascript all of the primitive types are number um and these instant subjects all pass and so this was spotted by i believe it was ross baker when he was doing some work with http 4s reported some class cast exceptions and chunk that should never have occurred but it was all because of the performance optimizations in concat and not realizing that they would uh completely break on javascript runtimes so the real solution this is what exists in the library today is none of the above it's sort of option two where we shifted the goal posts but it turns out if we just change the result type to be a queue of chunk it ends up being a little bit difficult for one to use so what if we made queue of chunk a subtype of chunk here's what that looks like so in the chunk companion object we have a new constructor q q is going to store a scala collection immutable queue of constituent chunks okay and it'll also store the accumulated size of all of the elements inside of that so now we've been able to restore that constant time size operation if someone wants to do something with size they're guaranteed that it's constant time it's not going to be a scan of our constituent chance with this definition of q we can have both you know prepend as well as appending chunks we do have a pretty important performance trick here which is that we don't allow empty chunks in our constituent queue so all of our constructors these two as well as the the main constructor for creating one of these cues all of them are going to uh elide any of the empty chunks from from ever getting inside of the chunks queue and i'll talk about why that's important in a little bit but then with this definition we have to implement index based lookup an index based lookup in this case is going to be a recursive loop through the chunks queue through that constituent chunks cube right so it's basically going to say you know start at the head element if the um the target index is in within those bounds then you know do the lookup otherwise recurse on the tail uh you know adjust the offset for the size of the element we just the size of the constituent chunk we just skipped over okay with that definition then we can finally add our plus plus method to chunk we no longer need to discourage usage of plus plus again we have to do a little bit of logic to make sure empty chunks are handled correctly and efficiently but nonetheless we get an efficient plus plus operation and so then uncons n ends up being able to be implemented in a pretty straightforward way we don't need a class tie constraint we no longer need a chunk q our accumulator is just a plain old chunk of o in the same way you might write something with vector and in the various cases where we needed to you know emit that in this case here we no longer need to concat anything we just emit the accumulator and likewise when we add elements to our accumulator it's just via plus plus in fact uncons doesn't even need to be aware of the existence of this chunk q constructor it's only going to use this plus plus operation okay so you may have spotted the issue with this approach though um the question becomes what is the asymptotic runtime performance of that apply operation right well let's think about it if the constituent chunks that the number of constituent chunks in the queue is much smaller than the total number of elements in all of those constituent chunks then we have you know effectively constant time lookup right if you've got if the total size is 100 000 elements but there's only you know five constituent chunks then yeah technically it's you know linear in the number of constituent chunks but um it's dominated so much by the size of the collection that we can say it's effectively constant but as the number of constituent chunks approach than the total size then that lookup algorithm becomes linear right and this happens when each chunk has size 1. now note it can't get worse it can't get worse than linear we don't allow those empty chunks to show up in the chunk cube if we did allow empty chunks then we would have a harder problem to deal with we don't allow empty chunks to chunk q so absolute worst case all of them have size one and our apply operation becomes a linear scan okay maybe that's not a big deal well what's the runtime performance of for each remember for each and for each with index are used in map or used in filter used in you know a few dozen combinators on chunk so what's the asymptotic runtime of breach well looking at the implementation we see it's just a linear scan of the elements by their index and so you know when the constituent chunk size is small compared to the total size then this still remains o of n but uh when when the average constituent chunk size is size one we've now turned four each into quadratic behavior which then means map and filter and all of those operations are quadratic so that's bad um we released this we we put this in production and had someone find it unfortunately all right so what's the fix well um fixing for each tends up or ends up being really really simple we don't need index based lookup to implement for each we don't need index based lookup to implement for each with index in both cases we can get linear lookup regardless of the behavior of apply by just um you know doing nested for each and doing nested for each with indexes right um and in fact if it wasn't for you know that inlining i mentioned of all of the while loops before then this would be a great reason to do it right like if map was implemented with its own while loop um we could inline that y or we could get rid of that inlining of that while loop but instead just have it call for each and in in that way get linear behavior back but you know we did say one of our defining characteristics of chunk was the you know efficient lookup by index so can we restore um you know a nicer asymptotic run time there so we can and this is this is an algorithm that um diego one of my co-maintainers on fs2 came up with um but the the general idea is that we're going to compute two lookup tables right the lookup table is simple it's just all of the accumulated sizes of the chunks up into that index in the table and i'll give an example of this in a moment but if with that with that lookup table we can then do a binary search by index and when we find the right cell then we can go and grab the chunk at that same index and do a direct lookup of the target value there so what i mean by that here we have a chunk queue of five chunks you know first to size three the second is size 10 and so on we'll create a lookup table with uh consisting of two arrays side by side um the accumulated sizes array you can see starts with size three because this has size three the second element of size 13 right 10 plus 3 the next one size 14 and so on and then we'll also you know in this table have a chunk array that just references each element um in the queue so we don't have to walk it again to find each chunk and our apply operation looks something like this we say like let's let's go and do a lookup for the element at index 20. so what the algorithm needs to do is find the smallest accumulated size that is greater than 20 and it finds this element 34 here and returns index three and so we say okay um sort of a boundary condition that that means uh the target index is in this uh a corresponding chunk so move to the [Music] chunks table here that takes us up to this chunk here and now we just need to offset our index by the total number of elements prior to this chunk which is just available here so we take 20 minus four we get six and we've returned the sixth index of this particular chunk the implementation is not complicated it's just a little wordy um we we pre-compute this these lookup tables but we do it with a lazy vowel inside of the chunk queue so we have this lazy valve that is only accessed on apply when apply is called um just rips through and instantiates those lookup tables nothing really fancy and then on a call to apply there's a couple uh cases here we deal with like if you try to access the head element we have special logic because that's really common if you try to access the last element we also have special logic because that's really common but if you try to access any element between those we then go and implement the algorithm we just talked about um so we build the accumulated sizes lookups if it hasn't been built yet we binary search them and then we handle the various uh edge conditions um you know to make sure you know it's not like the last element in the previous trunk things like that so what's the run time of this implementation well the very first time we call apply ignoring the optimizations for the head element and the last element the first time we call apply it's going to be m log m where m is the number of constituent chunks right and it's m log m because we pay um 1m for building the lookup tables and then we pay a login for the binary search but then all subsequent calls are just login and in our worst case condition where you know the average constituent chunk size was one that means our overall lookup here is an amortized login so wrapping up um we mostly delivered on the properties of our chunk data type i'd say mostly because we did we did give in in certain ways right a chunk was immutable except for when it wasn't right except for when you constructed it with a mutable ray and played games with that array it was mostly strict except for when you're doing things like split at and take and drop and certainly it's mostly efficient with index based lookup unless you really care about that logarithmic you know parameter but that's okay um one thing that i think maybe this talk does and which i don't want to encourage is that you know it it may may give you the impression that the design of chunk was uh a series of logical decisions right looking at how you know what are the impacts of this particular design choice and how does that you know change usage etc and and this is clearly absurd right this process was like an eight-year process um in designing this talk i went and looked up how many bugs we had in chunk over the last few years i got tired of clicking you know older the older button in in the github user interface but i collected like these 18 or 19 issues i think over a three year period i think is roughly where these come from um but you know the the the state of the data type today is the result of hundreds thousands of folks using it in all sorts of different domains all sorts of different use cases and really us finding those sweet spots of where it really aligns well where the default decisions the default behaviors of the data type align with the needs of the user base and in fact when designing this talk i ended up putting four additional prs in uh to improve performance in various ways we're just putting out this plainly made that made us realize oh wait we can do this a little bit better and so you know overall i hope that gives you some type of insight into at least you know my uh journey in in the design of this data type um like i said in the in the beginning it is a relatively simple data type but just because it's simple it doesn't mean there aren't tons of challenges built into it and tons of opportunities for improvement and hopefully that journey shows the way in which you know we can lay out a constraint based design approach you know here are the things that we want our type to do but then know when to sort of you know bend and twist and push and um you know change the overall constraints that we're working with so anyway that's the end of my talk today i'm happy to take a couple questions but otherwise i'll hand it over thank you very much michael um that was a great great talk um folks feel free to ask questions can we ask it like uh on audio yeah okay so right no great talk and thanks a lot and interesting to see these internals and the journey right so yeah quick question like that so random access property of the chunk uh i'm not sure i'm grasping that's it's really needed like random access it feels to me that we still always accessing it like in sequential manner but what is important that it's like unfragmented unfragmented uh piece of memory to provide like good like cache cpu pipelining scene but no really rare that access is ever happening in in the internal implementation is this correct or sometimes we do like rear like random access on the chart in implementing something interesting yeah now i think that's i think that's correct um when when we actually introduced the performance issue by by making chunk.q a subtype of chunk um i mean we we knew that that was a a risk it wasn't like that surprised us um it did surprise us that folks had access patterns where the average constituent chunk size was one and cared about it right and like that we knew that would come up but we didn't think it would end up mattering we didn't think folks would run into a use case where they you know they were actually running like combinators over it what surprised us i guess was or we didn't really put together was that all of those operations on chunk had those in-line while loops right so you know someone calls map or or filter or something and there they're they're really have they have this random access looking access pattern but they really don't care about that they really just want it for each right yeah okay so it's really what triggers right the nexus it's uh in line while looks right exactly right here and and really i mean that was because we you know i think folks thought again like how could you do better than a while loop for each is clearly going to be slower because it's going to be like a lambda you know creation or whatever a stack frame etc um in practice we've seen the opposite or at least of course the internal right this is all about right also what's interesting for me i mean that's uh probably yeah so it was vector initially that was like internal structure but again this is like in scala this is still some kind of tree right or try whatever right and so it's important to understand that this underlying thing is actually array which is a fragmented continuous piece of memory right which is a good very good decision point yeah now thanks a well thanks a lot this is interesting actually and one of the things that's that's um perhaps interesting is that uh arbitrary updates of elements or patching of elements uh is not that that use case is not supported by chunk whereas like vector does that very well right because vector has that 32-way you know tree and and can just patch in with just the impacted node um we avoid that because it's not a use case we need and as a result we can get densely packed large structures exactly good old array rage that makes sense any other questions if not let's thank michael this was a great tour thank you very much