Porting zlib to Rust: Compression & SIMD Performance

[00:00:00][Applause] yeah thanks so welcome to compression koniz implementing zp RS so like about that name it alliterates which is why I picked it but this word koniz comes from biology and it means to evolve a crab-like body plan which is a phrase I I really quite enjoy um and we'll see what we can do with this idea a little bit later but this this happened several times over the course of evolution because it turns out that being a crab is incredibly successful survival strategy so what is z RS uh well as the name sort of implies it is a rust implementation of a thing called zip and zip is a library for compression in particular for dealing with the gzip compression format and it is a very widely used format and therefore zip is used in a lot of places so for instance if you download a binary on the internet like rust analyzer um it is very likely that these are provided as gzip files both because the compression is pretty good and because most users already have some kind of program on their device to decode such files right so there are definitely better compression methods out there today but a lot of software is just compatible with gzip even if you haven't downloaded rust analyzer today you've likely loaded a web page like rust l.org and it's very likely that those web pages also use the Gip encoding and therefore indirectly use G uh use zip to encode that page so when you load a page you don't get raw HTML bytes but instead you get sort of a compressed representation and it gets uh decompressed on your local device so zip is used in a lot of places and it's really at the foundation of a lot of our Tech Stacks in particular of a lot of Internet infrastructure and so it's a very important project to get a bit of a sort of a better idea of what zup is is that in practice it is often a Dynamic library that is somewhere on your system at least once uh so here I've tracked it down on my own machine and we can see that it exposes a bunch of functions that have something to do with compression or or uncompression uh in their terminology and so applications on your system can load this library in and then make use of this compression and decompression functionality um in practice this is a c Dynamic Library which means that it exposes functions like this uh which looks very nasty uh from a rust perspective it has like pointer mutable pointers it returns errors but really it's an in because of course right C types uh it can do better than that we can um so um sort of that as sort of a summary of that so the idea of the zal RS project is actually to sort of aim high and replace that c Dynamic library to build something in Rust that pretends to be that c Dynamic library but secretly it's all you know nice rust inside um so that also means that sort of target audience is people that don't necessarily have sort of warm fuzzy feelings towards fust uh and so we need to somehow temp them to to upgrade right to sort of make that very easy and we can do that not by sort of reimplementing all of the logic in Rust and then saying like hey we made this really cool rust library but by actually sort of bringing it to them so that upgrading to Z RS would be just swapping out a file but of course you know like if we go through all the trouble of implementing that logic in Rust we may as well also you know provide it on crates iio and sort of make it available to rust ecosystem that still has advantages if you're using rust anyway then sort of importing it directly into your rust compilation is is better in various ways than uh relying on it as a dynamic Library using that very nasty C API So today we're going to go over sort of a crush course in compression soort of how does zip work what does it do and and sort of why is it effective um then having a look at the zelop ecosystem because when you are going to like rewrite it in Rust it's important to what you're actually rewriting so that you can sort of look at design decisions and make choices maybe you want to adopt certain decisions maybe you want to innovate in certain ways um and so it's a good way to have a a bit of an overview of what that ecosystem looks like what properties you want to uh preserve and finally some ponderings on porting on sort of this this project of like rewriting the bottom of the stack in safe rust which to me is really like delivering on the original promise of rust sort of bringing that improved language and Tool chain to all of those places um let's see what we can learn and what we can maybe do better so the sort of core idea of compression is why use many bites when few do trick um Right storage space and bandwidth are expensive and so we would rather send fewer bites than many bites also especially in the context of the internet um sending F bytes over a wire is is is faster than sending many bytes over that wire um now this is slightly more complicated because compression and decompression are not free and so you need to somehow make sure that the compression then sending fewer bytes and decompression is faster than sending the uncompressed stream um but in practice gzip is sort of used everywhere on the internet so clearly that must work um but that is something to keep in mind performance actually really matters here so the kind of compression that we're looking at is so-called lossless compression compression where if you have some data you compress it you decompress it then you want the original sort of input back out this is sort of a postal lossy compression where they can get away with the shocking out detail like in JP images or MP3s uh we don't get to do that we need to actually be able to replicate the the original input uh and so we can just conveniently forget information so the algorithm that is implemented here uh in IN Zip is one that looks at your input which is in general a b stream but because we're humans we're going to use characters today um and it's going to look for repeating sequences of characters in this input so here we have the string fuar Fu fo repeats and so what this algorithm does is it replaces this sequence with an offset length pair um and so what happens here uh uh really is that this offset length pair refers to an earlier part of the input string and this is more worth it this saves more bytes when that repetition is longer so if we had four characters instead of three we would gain basically by by um having fewer bytes to transmit at the end um this is also a um a representation that is fast to decode again right so this is relatively straightforward to like almost interpret it really looks like an interpreter Loop when we start decoding this information the tricky bit is finding how to insert these offset length pairs right if you look at this sort of seemingly arbitrary sequence of characters and ask you like okay what what offset length pairs do I insert what are the repetitions that you see that is hard uh and that is hard for humans but also for computers like if we throw a bunch of nestic for Loops at this performance would just be absolutely terrible right the big go of that would be bad and so we need to be smarter than that uh we need a couple of tricks to sort of break down this problem and make it manageable because again like we need this to work on web pages on the internet like sort of througho and time to First render are really important yeah and an additional problem is you want to not just find repetitions like finding one character repetitions is easy but they need to be as long as possible because that gives you the best compression so in practice how how zip works is it runs over your input and so we have a sort of current position a current character and we're going to search backwards for repetitions that match with the current curs of position and the sort of characters following it right so we run over our data uh character by character but then we need to sort of impose some restrictions on this to make it manageable to get that biger uh complexity down uh and basically this revolves around reducing the amount of work that we do per character uh and so the first limitation that we're going to impose is that we're going to only look within a certain amount of space backwards if it's sort of off to this side it doesn't count anymore we can't use it anymore and so this makes our search bace smaller but also it reduces the sort of the likelihood that we'll find a good match within this smaller window and if we make it larger then the chances are better but we spend more time searching through and because there is no objectively good answer to how big that window should be it is a user configurable parameter similarly the compression level um is another user tunable parameter and this is roughly a measure for how hard we're going to try to find the longest to sort of optimal match in our window so here if we search our window from left to right we find a three character match match and we have to sort of decide are we going to continue to search to find a four five potentially you know a 100 character match or are we going to just stop here and not waste any more time and move on to the next character of the input and so again there's no real like that's a gamble you just don't really know um but at a low compression level you basically say stop when you find something halfway decent at a high compression level you would continue to search sort of hoping for uh sort of getting lucky that still wouldn't really work though if if you go about it in this way and you search through this whole window linearly for every character this window is typically 32k or 64k that will be way too much work that you do per character of the input and so actually what we need to be doing is remembering some of that work um and so what we're going to do uh what the sealup algorithm does is it keeps track of substrings of the input three character substrings and the indices at which it has found the uh these substrings and so in this case we find the string fo at index Z we find o at index one and so on until we find our second F because in this case we're again sort of we want to insert the string fo but it's already there and so now we know sort of two things which is that at index zero which is in the sort of value set of Fu we find a match of at least three which is already pretty good that's sort of about Break Even in terms of do we gain anything with with that insertion of an offset length pair but potentially the the match is longer right that is sort of what we're hoping for but also any index that isn't in that set we know for sure that there won't be a match there like o will definitely not match fo and we don't need to actually go look at the data and compare that character for character but we know because of this this dictionary that we've kept that we don't even need to go look there and so in this way we can sort of skip over vast amounts of the input and just never treat them at all um so I hope that sort of sketches uh sort of roughly how the algorithm works and gives some intuition for why this is so incredibly effective on web data because if you think about HTML or css there's just so much repetition in there to repeating class names property names just words and text that even at low levels of compression you sort of achieve very good results and at low levels of congression you expend little time but you still get actually quite a sizable reduction in the overall payload there's one further trick that zip uses which is that it is a streaming implementation of these algorithms so that means that if you load ros.org you don't just wait for that whole compressed HTML page to arrive and then decompress it but instead your sort of device can start decompression as soon as the first bite comes in and so this really helps us overall sort of that time to First render um unfortunately for me it also really complicates the implementation uh boss like now you need to be dealing with like you get one BTE of input you get 300 megabytes of input you get three bytes again uh and so you sort of need to keep track of this and we make heavy use of fuzzing to make sure that the implementation is robust uh for sort of this this fragmented input all right so that's sort of roughly what the algorithm does and I hope that is useful um so what are we actually implementing though um well so generally when we talk about zip the zip that is is actually everywhere because it is a default in a lot of operating system distributions uh this say is called zelop Adler the OG um and its goal is stability this is a dependency from 1995 if you look at its source code you can really see that um it still supports 16bit systems who here is programmed on a 16bit system exactly um so um and also it doesn't use Modern Hardware very well right so it it it's sort of one generic implement ation that runs everywhere it is good C codes in terms of performance aesthetically I have thoughts but you know um and so it doesn't use a lot of sort of Modern Hardware instructions in specific ways and this is unfortunate because that is where most of the innovation in the hardware space has been for at least the past decade we can't run more instructions per second anymore and so what we're doing is sort of inventing more powerful instructions that do more effective work in a single instruction and to some extent compilers can sort of transform our sort of standard programs into programs that use these instructions but generally they just AR Inc capable enough and you need humans for the time being uh to actually write those implementations so because performance is important uh to many organizations several Forks have been made of of ZB Adler um the most prominent of these is ZB NG where basically they say we want performance we want performance spe specifically on Modern Hardware um so that means removing a lot of Legacy stuff amongst other things the 16 bit support um and relying on these modern instruction set to have these Syd instructions that do that sort of more work per instruction um but zip andg is still fully API compatible so that means it exposes all of the same names uh with all of the same type signatures as the original zip and so it is a dropin replacement for the original sealup uh just with less platforms that it supports but uh still the same AP now these are both C dependencies and C has various problems rust is various Solutions so all of the usual sort of points apply we have bounce checking we have borrow checking um rust is nice to write I think for sort of a project at this level of the stack it is especially uh important that we vastly reduce the surface area of our project um so in part this is reducing the amount of code that we write through good use of the Standard Life Library um we have one dependency which is lip C uh which I would like to get rid of we'll get there um and um in part though it is actually using cargo because it is I'm I'm going to pause it something here is my opinion that any sufficiently complicated C project contains an athoc informally specified Buck ridden slow implementation of half of cargo this implementation right you should like just so sort of like looking at you know an accident uh you should look at the build system of some C projects because in practice this implementation of cargo is a make file and a thousand lines of bash uh no one wants to write that no one wants to read that detecting errors in that kind of code is incredibly tricky and this is not hypothetical this is sort of part at least of the recent XZ attack uh on another compression format where a malicious maintainer added a single character to one of these bash scripts and it made the script take a different branch and then you are now you know compromised update your threat model don't use thousands of lines of bash so if we want to do better than that in in Rust the way to sort of use or or interact with gzip files the recommended way is flate 2 and this is a crate that provides a nicer API for zip and and similar functionality um so instead of that nasty pointer based thing uh we actually get imple read imple write we return results Etc very nice it's also used in cargo uh because again gzip is everywhere um but f 2 itself is actually just a shell it doesn't Implement any of the actual compression Logic for that it uses one of several backend crates which you can sort of toggle with a feature flag so you can use zip OG if you really want the compatibility or you want to just use the thing that's already on your system you can use uh zap andng if that is what you want um but also you can use rust implementations and until recently the only rust implementation available was mini oxide and this is a safe implementation of a subset of the zop API so it really covers a lot of use cases for rust users um but it leaves some things to be desired so it doesn't cover the full zip API it's not a drop in replacement and also it is relatively slow because it doesn't make sort of dedicated use of the simd instructions and Z RS fixes this right we still want safety in the sense that we implement this in Rust we try to be really careful but also we really want performance in order for this implementation to be competitive we need the performance to be at least okay and then hopefully over time better than the Alternatives um so uh we also yeah Implement a full Pi so in practice the sort of architecture that we get is this this unsafe sandwich which you know doesn't give fot poisoning but there's some stuff in there that we'd rather like you know um so at the very top we need an unsafe API uh for exposing with the outside world that is that nasty pointer based API uh that we need to provide that's sort of the point at the very bottom we have simd and even some inline assembly to achieve the performance that we want and these are sort of like we can't get around the unsafety here um probably ever and then in the middle we have mostly safe business logic there's some unsafe in there dealing with uninitialized memory uh but those are actually the code come from the sander libber is just not stable and so over time we can hopefully get rid of that so then like in terms of performance this is sort of what the landscape looks like this is um speed up versus zip OG um sort of as a factor of of its speed first of all Zopo performs uh not well um then Min oxide really tries and at low compression levels it's doing all right but at higher compression levels you can really see the difference between implementations that use and those that don't use the explicit syy um and in general that's like almost a 2X difference there at level six but just a default uh right and like higher compression levels basically do more computation so the effect of using CD becomes more pronounced also like we're doing all right with zop RS but it's still not quite there with zop and G um that just means I get to stare at assembly for many more hours so you can actually use this today if you're already using flate 2 uh we've been a little bit quiet about it but the implementation totally works so you can flip this feature flag uh please give that a go if you're already using flate 2 and let us know how it went both if it went well and if it went poorly um all right so finally I wanted to say some stuff about uh sort of this project of translating C into Russ because rewriting in Russ is e to say and the people who say it most rarely do the actual work you know typical so something I've been thinking about is this sort of spectrum of porting the sort of idea of we can have an organic implementation or a line by line rewrite of an existing SE project and there's various places on this spectrum with various tradeoffs that we can make so if we have a a sort of fresh implementation like russels or npds then they in a sense reinvent a wheel they they sort of throw out a lot of existing knowledge and code and start from scratch and have to sort of absorb and digest all of the information relevant to the domain on the other hand they can also innovate in terms of mostly architecture I think is the most useful one uh by sort of being unconstrained by existing implementations refactoring architecture is really hard in practice so in a sense this is high-risk High reward it takes a long time for you to digest all of that information and build an implementation that works then making sure the performance is sort of okay because that matters at this level of the stack um but ultimately you get a sort of very nice payoff in sort of the best rust solution that you could probably come up with on the other end of the spectrum we have line by line rewrites and in the most extreme case we could even do a mechanical rewrite using a tool like C2 rust um and the rapit project is an example of of such a project so this translates davit which is an an 81 video format decoder into rapit um and so what happens here is that you reuse a lot of that exis knowledge right um as you can imagine video decoding not an easy topic so uh you reuse a lot of knowledge about how that domain works and also the sort of performance engineering that went into making that implementation efficient you also inherit the architecture it really depends on what C codebase you start with whether that is a problem or not um but ultimately what you get is something that works on A1 it compiles with a rust compiler on day one it has the same behavior and performance as the C implementation you can test and fos it to sort of make sure that you never break sort of those correctness properties most of your work though is cleaning up code that looks like this this isn't even the worst of it but there's a lot of this code it's very sort of verose uh but it's input with C so what did you expect um and so while this is sort of annoying I also thinking that everyone here can see some improvements that theyd make to this code and so in practice cleaning this up is mostly is sort of a pretty Zen process of moving characters around um turning while Loops into far Loops Etc um it's only occasionally that you step on a Bor Checker land mine and you have to sort of take a step back and reconsider like okay is the architecture does it actually work do we need to rethink something are we going to use some unsafe code here um you know choices so in practice this is something that ravit has to battle quite a bit because the original Library uses threading and so you know you can imagine how that would be uh you know not a great time zip is somewhere over here um sort of off to the right where I did most of the translation by hand from the sea of zip this is actually a pretty straightforward process it just takes some you know editor skills um and we reuse a lot of that existing knowledge both in terms of correctness and performance we get very quick results like in a week or two you can actually have something that is very solid um and our architecture was constrained anyway so we didn't think we could really innovate there if we have that Capi we need to expose we need to sort of implement that streaming that really constrains what you can actually do so rewrited invest and you if you've seen the sort of marketing recently and also the the Russ stock yesterday I think what we're sort of realizing is that actually we need to be compatible with existing implementation so instead of like sitting on our high horse and saying like our rust implementation is better than yours we actually need to sort of bring it to the places where the software is actually used in order to achieve any real world impact which ultimately like that is what I care about I want my work to sort of be the foundation for modern digital infrastructure and so we're working on all of these compatibility layers and making integration with existing systems easier that is why Zeb is a drop in replacement also we have to be just better because for someone to mess with their existing configuration on some obscure server that they haven't touched in 10 years it takes a lot for them to upgrade to our version of a right um that is just not an easy process not really something you want to deal with and it's never urgent until it is um so we actually try to just add more functionality at better error messages ntpd is a better algorithm um Russell is actually a better and faster implementation of of DLS and we have to be better in order to get any uptake in the sort of broader community and then sort of um I don't know more complicated things funding is always a problem for this kind of work it is again very important but never urgent uh it's not very flashy is another problem of these projects right like what TLS implementation you use is never relevant for your customers until it is H and so it's never urgent to upgrade um but the funding has actually vastly improved versus a couple of years ago memory safety is a much more active Topic in conversation a lot of Engineers are really sort of on board with this and it just takes people to get over that hump of um sort of actually doing the upgrade process looking up the config file translating it over to the new thing and um uh actually using the stuff in production so if you can if you are in a position to sort of smuggle in some unglamorous Rust into the bottom of your stack please do and please let us know because it really makes our day and it really makes this sort of project of using rust at the very Foundation of our systems that much more possible all right so in summary why use many byes when Feud do trick compression is very neat and very useful and used everywhere in particular on the web it is unreasonably effective due to the type of content that we set if you are already using zop RS or if you are already using Flight 2 sorry you please try out zop RS let us know how it went right um please use more unglamorous rust in production it doesn't need to be worthy of a block post like just actually use Russel instead of open ssf and finally keep evolving crab-like body plans thanks [Applause] all right are there any questions I I have heard by the way from some people that we would like the question anwers to stand up so that the camera person can find them uh hi which levels of simy do you support do you only do apx apx2 52 um so in the current sort of like we're not entirely done with this so generally we want to support everything that x86 has so that would be it's like s the the various versions of s and then AVX and AVX 512 um and also on arm we support neon currently um and then I don't know there's some ideas about do we want to do risk five or do we want to do do other things this is sort of needs based uh and also based on what Hardware I have uh so like I don't have AVX 512 in my CPU and then actually implementing that is tricky so um we'll get there and sort of roll out support uh but this is really the easy part at least if we can sort of adopt that code from um from FIP and G um also PR's welcome I guess you know if you really like looking at simd code it's kind of rough about that hello um so I had a question about eror handling so you mentioned that the CI has m just uses Instant stuff but you also support that API yeah so internally are you able to use nust STS and then expose those back as the cap API or how are you managing that uh well sort of part of what the Capi uh means is that error handling isn't that present in the code that we translated right so it also just internally returns an integer and potentially sets a a a character pointer to a static string indicating roughly what went wrong so certainly what we aim to do is add more error messages because there are many cases where the computer just sort of says no uh you get a sec fault and it's not clear why and you just configured something wrong and and the system should be able to handle that so we can definitely improve there even for cap API users and then uh what we didn't really talk about but like our our rust API is not ready I think even then the goal would be to to use flate 2 as the actual interface to the implementation but right now what we use is is B basically the C API for interacting between uh flate 2 and uh well it's called lipy RS CIS uh because it exposes a CI even though all the implementations are actually in R anything else I see some here hello back to the topic of uh simed instructions how do do dispatch for different instruction types for different x86 processors for example you mean be different like yeah okay so there is a a macro in the renter Library which will um it's it's something like is x86 feature detected and you can query that at runtime it will resolve to something uh if at compile time you know you're going to definitely have a certain instruction set available it will hardcode that it will just be like true um otherwise it will query it runtime and then cach what instructions your CPU actually supports this is very important mostly for safety of that bottom sort of thing right like Cindy operations in general do like eight additions in one go so that is not unsafe the unsafety is computers really hate it when you make them execute instructions they don't know and so these instructions are not always available and we need to actively check and this is part of the unsafe contract so there is support in the r standard library for that and we plan to use feature flax for if we want to like compile with no standard so you have to explicitly toggle on like even though I am on some embeda device I still want AVX to uh optimizations okay more questions oh yeah the microphone's going all the way across so how many Buck did you find in the original implementation just by porting to rust so this is funny right so zp and G is used incredibly widely and what if like the way I think about it it gets F in production billions of times a day um and so in practice finding correctness box with the sort of general settings uh generally accepted settings I don't think you're actually really going to find much because any any input that could have been thrown at that algorithm over the past 30 years sort of like they would have found the edge cases it's much more around usability that if you configure something slightly wrong it will just like Seck fault your program uh which is acceptable in C I guess like don't do that but like we can do better um so it's mostly around usability not so much correctness of the algorithm that's been hammered out long ago okay great I see another question over there yes so that answer kind of makes me think of another thing which is like if you're building foundational libraries in Rust you know how how do you think of the strategy to encourage the adoption of those libraries more widely than just in say rust projects right so that they get more widely used more widely tested you know become part of the larger say you know open source ecosystem used by many languages and operating systems right so this is sort of a like one step at a time process where one by one we talk directly to an engineer at organization X and they smuggle in some of that rust code to the bottom of the stack we try to make it really easy right by making this a drop in replacement Russell is now working on op SSL compatible apis um and then otherwise it's it's also a matter of document like if you look up the documentation of zip it it shows sets from 1995 right we can do better than that uh we can have like a proper tutorial sort of explaining the general concepts and have proper API docs um so it's mostly about helping actual developers sort of make that process very easy because it is scary it is sort of a risk that you take in the short term hopefully preventing major catastrophe in the long term there was another question over there I think on the the standing row there there we go hi uh thank you for the talk uh so I think you mentioned somewhere and correct me if I'm wrong uh using fing to check if the impementation was robust I remember correctly yeah so uh which crates and tools did you use for Ping uh this is just a standard cargo fuzz which is unfortunately still nightly so you have to rebuild the whole thing but like just cargo fuzz and then we we have to be a little bit and I think we can still be smarter about this like what input you actually feed it cuz you can give it a random sequence of bites and it works well and that needs to work but it's usually not that interesting um and also especially for decompression we also try to give it invalid input to just sort of make sure that it doesn't do anything weird like run into a loop or a panic or something like that um and like yeah you just let that run for a couple hours and then if it's if it comes back good then you know you have increased confidence Mak sense thank you I mean there's lots of testing in in general of the library to uh based on test from the C code but also because we did sort of write it peace meal we have tests in the individual modules testing smaller bits of logic because the only test that the original C project has is endtoend tests um and that is fine if if the end to end thing works but if you have a buck somewhere in the middle and it's really hard to track down why that is exactly I would argue our implementation is better tested you're sure all right one final question over here um do you also focus on the C development experience so that c developers can directly use your project instead of using Z lip and or other called Generation stuff and uh yeah like Z lip provides on those platforms so this would be in a scenario where you would want to like statically compile this in right okay so that's that's not really something we've considered I'm not familiar enough with the sort of like how how people use deip in a static context for whether that makes sense to us if you're using C anyway maybe you want to just continue using C um but we can definitely invest some time in also making that experience easier so I do think it really helps that we have sort of rust do where we also sort of need to annotate all of these sort of unsafety assumptions that we make we occasionally need to make slightly stronger assumptions about like these two pointers should not Alias because otherwise things will sort of go sideways um and so also just that documentation in general will be helpful I think and also we can just make a a better introduction to the zip API and that web page from uh you know perhaps before my birth uh so H yeah I mean we we're happy to help out also for those use cases all right thank you so much please give a big hand to pker