An introduction to structs, traits, and zero-cost abstractions by Tim McLean - Rust KW Meetup

my name's Tim thanks for tonight I'm gonna be talking about structs traits and zero cost abstractions so this is going to be sort of an introductory talk I'm going to just assume you have a fair bit of programming experience so you should have worked with a few other languages before but I'm assuming you're fairly new to rust so just to talk a little bit about my perspective on rust so I'm a software developer but I'm also primarily a security engineer so I care a lot about security and correctness and making sure that code works properly in particular I focused on cryptography and encryption so that's sort of how I view raw straight that's as the source of I want to do with rust so for me rust actually works really well because it prioritizes things that I also care about so for instance I want to write high performance code because if encryption is slow and people won't use it so rust does some stuff around performance where it makes the performance cost really explicit it and they made a lot of design decisions that's basically forced you to write faster code or it'll make you uncomfortable at least if you don't write faster code so sometimes that's annoying sometimes it gets in the way because you don't really care about performance but if you do care about performance then it's very helpful that it nudged you in the right direction all right so I really appreciate that another thing about rust that's interesting is that it prioritizes code quality so generally it sort of nudges you away from writing bugs now again that's something that you might not appreciate if you're trying to just build a prototype really quickly but if you do care about quality and getting things to be correct then that's actually very useful lastly rust is a it feels a lot like a high level language even though you can't allow the level control which is very nice basically they they use trades and abstractions to give you a lot of expressive power in the language it's a very impressive so in this talk I'm gonna be talking about primarily two things structs and traits but in particular I'm going to talk about the performance aspects so where there's overhead where there's no overhead and the performance trade-offs that can occur so I'm gonna be using this term a lot zero costs abstractions and you can tell it Russ cares a lot about this because if you look at their homepage the first item in the features list is a zero cost abstractions so obviously the community values this this feature so what this means zero cost abstraction is that you can add some structure to your code you can add these new concepts or an abstraction but at runtime there's no actual performance hit there's no overhead to doing so so I'm over this a lot but it's a very useful concept if you care about performance but you also care about having nice readable quality code so okay first of all we're in some constructs so I hope this is fairly self-evident to everybody here but basically we have a struct for defining called point 2d and it's going to have two fields in it x and y and f/64 is Russ 64-bit floating-point value so I hope that's that's obviously right here so just quickly you can look at some syntax so if you want to create an instance we have point 2d we have a syntax for that we're justifying a value for x and value for y and then we're accessing the field so dot X dot Y easy enough all right so let's add some methods so we'll use inrush to use an input lock to add methods to a struct so you say input point 2d now we can add a method as a sort of a contrived example but we'll have a method called move right so this will move this point to the right by adding to the x value one note if you haven't looked at Rusted for rust tells us this thing called an implicit return statement so the last statement in a function body automatically is returned assuming there's no semicolon so it's this example there's implicitly a return keyword before point 2d just just to be aware of that it's kind of weird but you get used to it all right so now we can look at some example of using this this move right method so we create a point called p1 we specify a value for x and a value for y and then we can call p1 move right so we get a new point back point to p2 and then we access B to X and return that all right so now the question is is this code fast so we're talking about point 2d we have all these struts being passed around and stuff but is this fast so we can tell if as fast as we can look at the actual executable is produced by compiler and look at the machine code that was generated so if we do that then we see well it's actually very simple it just it loads some constant value and then it returns that cost of you in turns out that yeah that constant is exactly what you would expect actually because if you look at her code oh yeah right we're just adding two plus three is five so it makes a lesson so we just always return five so the compiler saw through all the stuff we were talking about with structs and then point to D and stuff cut that all emanated it but it by optimizing so okay let's make this a little bit more interesting because that's kind of boring just always return five so what an input here what a function argument called input and instead of moving right by two every time we move right by a input okay so I want to show you a little bit about what kind of optimization is the compiler can do so this is not going to be perfectly technically accurate because conflation process is very complicated has a lot of stages a lot passes I can't talk about all that but I can give you sort of a decent mental model at least to appreciate what sort of things like compiler can do for you so the first thing you can pilot can do is they can look at this method call here we have move right and they can say well move right is actually a very short method all right there isn't there isn't been much going on and move right so how do we just copy all the code from move right into this function so if we do that now we no longer have to do a method call all right so that saves a little piece of work there and also we can do further optimizations now so at this point we can realize well we don't actually need we're not passing around strokes here all this talk about point to D is contained within this one function so how do we just break up the structure into their fields all right so now we break up into the x and y components of all the point judy's and we no longer have this point 2d concept anymore in this function we've just optimized that away so we're talking exclusively in terms of f 64's now so we can keep going we can say okay we can remove these unused variables all right so the Y values don't actually matter for this computation because the X is what we're returning so we don't care about the Y values throw them away and then keep going we can sit by a little bit and we end up with just three plus the input okay so that's a pretty simple simple function actually and of course if we look at the actual generate machine code sure enough it's loading a constant which is three and then it's adding it to the first function argument which was our input and then returning so the compiler was able to see through all that complexity around point two D so this is sort of getting at this concept of a zero costs abstraction this is a case where we have this this structure called point 2d and this concept in this vocabulary we vocabulary like move right and we're able to make our code more elegant and more descriptive but then the compiler is able to see Theology a complexity and reduce it down to something very simple just three plus the input ru so these two pieces of code are equivalent in the compilers eyes so ok that's that's one sort of thing we can do with the zero cost abstraction but there are things we do too so I want to in enters another example call it append only vectors and basically the idea here is that's in your code you often have these invariants so you'll have certain conditions certain rules that your code follows but that are often kind of implicit if you're lucky then somebody will actually document them and write comments saying ok we follow this rule maybe this array should have between 3 & 5 elements or something like that right all these implicit rules in your code but still it's easy to break them accidentally or just not read the comments not realize what you're supposed to do if you're editing someone else's code that's over dia so with zero cost abstractions what we can do is we can create a new type some sort of like a structure a struct or a trait and we can define those invariants in that type and enforce them and the compiler will help us by catching mistakes so we're gonna be looking at append-only vak so the idea here is that's you're passing around some sort of vector event just for context avec is like a list or an array for about coming from rust so we're processing around a vac and let's say you're passing from function to function and all these functions are supposed to just add things to the vector they're not supposed to remove things and not supposed to look at things early wrong in the list they're just supposed to add things to the end so maybe you okay we add a bunch of things to the vector and then finally at the very end of the computation we say ok well use this list and will render a UI or something like that right it's fairly common use case so we can actually enforce that invariant and prevent any of those functions from tampering with the earlier parts of the vector so here's what we'll do so we'll create a wrapper struct so basically just a struct with one field in it and we'll call it a pendulum back there's a little bit of generics in this code but it's it's me very basic so this is just saying append-only vac contains elements of type T which where T is just generic could be anything and then inside we're gonna have a plain vector vac T which is similarly gonna have elements of type T so okay well we can add some some methods to this again a little bit generics there but nothing nothing fancy here so add a method we'll have a constructor in recipe call our constructors new just like you mentioned so the new constructor will take a plain vector and then construct an append-only vector from that next we'll have a push method so this is the just like in JavaScript you pushed on to an array to add something to the end and finally we'll have into vac so in to vac is the method that takes an append-only vector and returns the original vector so you can actually do stuff with it so that's it that's this is an entirely complete implementation of a pendulum back and if we use this type now we if if we provide it to a function that function can only do one thing to it I can just push elements on to it alright unless now there are ways to get around this so you can't use this you can't rely on this for security purposes but it catches accidents at least so ok let's look at an example of using this type so we have a dependent leave act we've implemented that so here's some code that might use it so let's let's pretend you're writing some sort of parser right so you're you're parsing some some kind of document an HTML document or whatever and you can imagine that you're parsing this large structure and there you could run into errors at different parts of the structure so ideally what we want to do is you want to collect a list of those errors and then put them all into this one vector and at the end you can show them in the UI or print out them to the programmer or whatever so here we have some code that would be creates a plain vector that's empty and then you wrap it inside an append-only vector so E is protected we're enforcing this invariant we call that parsing errors and then we pass a mutable reference de Parys to the purse document function okay so you then we look at the parsed document function so here I've highlighted the two relevant parts here but you can imagine this might be a very complicated function right I have lots of Ko going on so first of all we accept a parsing errors as a parameter to this function and we require a mutable reference so that we can change it and then second of all the second box we have parsing errors poor store and error message on to the specter and of course that's the only thing we can do with it right that's the only thing we're allowed to do with it because we have no other methods to find so you can imagine here's a bunch of stuff we can't do with this with parsing errors we can't look at elements we can't look at the first element look at the second element we can't remove elements because there's no remove method we haven't defined our move method on append only back and lastly and most interestingly we can't actually use into vac either we can't get back the original vector and this is sort of subtle if you don't know wrasse but it's because we only have a reference to append only back in this example code in parse documents if what we needs in order to use into vac is we need ownership and we don't have that here because of how we defined into vac in this function so anyway that's that's sort of the larger idea there so the recipe here is you defy some sort of variant like append-only and then you create a new type in order to enforce that variant so you define a white list of what methods you want to allow access to so and then if you actually use that type then you get compile time errors if you break the invariant so that's kind of nice kind of useful right so now of course the important question here if you care about performance well is this zero cost is there performance overhead to wrapping it in this this new struct right so you could consider these two examples here so on the top we have a plain vector right which is how you normally write this code on the bottom we have an append-only vector and the question is well is there overhead to using a pendulum factor and it turns out the answer is well we can look at the machine code and these are the same which you'll have to trust me on that but they are identical byte for byte so if you look at the generated SQL files they match exactly so yeah is zero cost abstraction there's no cost to doing this in terms of runtime performance all right so that's the first half of my talk so now I want to choose traits so first of all let's start with an example here so let's say we're trying to build some sort of locking mechanism in an application so this comes off for pretty much any moderately complex application and if you've ever done this before then you you go down this sort of rabbit hole of complexity right you you want to have configuration for your logging you want to be able to do more logging in development and less logging in production maybe sometimes when you really want more logging in production but then you want to turn on for a civvy component and other components so you want be able configure component in the application just gets really complicated right so the question is how would we structure this in rust how do we structure this so that we can change things elegantly so the first take would be well how would we have a logger struct right we have some sort of a logger type we have maybe some fields and that struct that define where where we're writing to a file or whatever and then we could have these four methods we could have error warren info and debug so this would allow us to say okay we want to log something at a debug level of detail or well log something at just like a warning level of detail so that's a fairly common approach the issue though is that it would be nice if we could have different implementations of these functions it'd be nice if we could have a different way of logging things depending on what type of log we're using so this is of course imagine having a file logger like a print log or an all logger maybe would just do nothing at all wouldn't do a logging or maybe like an external service logger it's in things something over the network etc so how about this how do we use a logger tray so that rate is basically like if you're coming from Java it's like an interface but a tray is where you define a series of methods and you'd find the method signatures but you don't define the actual implementation of the methods so now that we have this trait called logger then we can have a new type called print logger which is a specific type of logger right so we can implement logger for print logger which is which is saying we're implementing the logger treat for the struct print logger and then we provide implementations of these methods now we do the same thing with like null loggers and all it would be pretty boring but basically you just have these empty implementations of these methods to show that it's doing nothing all right so now we can we can use this trait and we can write functions or in code that's like this log example here that requires a logger type but it doesn't say what type of logger it requires so here we're using the info method on this logger but we don't actually know what type of logger we have it could be a null logger could be a print logger to be whatever so question is how does this work how does it actually how the houses implement in the compiler so the way this works in rust is that the reference to logger is a trade object it's called a trade object so a trade object has two things in it first of all it has a pointer to the underlying type so pointer to the null logger pointer to the print logger if you remember back print logger is a struct right so you can have fields in there so this would be a pointer to those fields the second thing in the trade object is a pointer to a virtual function table a vie table so now the things I'm telling you here I need to color these are compiler imitation details so they can change they're not guaranteed but it'll give you a general idea of what things look for respective so here's a diagram showing what straight object looks like in memory so on the far left here we have the trade object the reference to logger and then we have the pointer to the struct as I mentioned and this is a pointer to this specific file logger instance the second pointer is a pointer to the file logger v table and the V table you only have one B table for the type right so you if you have multiple file loggers you still point to the same V table because the V table is just information about the file logger type so you have some metadata in there which is like the size of the type and stuff like that but more importantly you have this sequence of function pointers you have pointers to implementations of each method for the logger trait so you've pointer to an error method you have pointed through a warren method etc okay so now how does a method call actually work so we have this code that calls logger dot info but again we don't know what type of logger it is at compile time how is this employed well it's really just two steps so basically the first step is you just look up the function address for the method invitation and you get that from the B table and then you just call to that function address you jump to it so that's pretty straightforward you might ask well is this slow and really the answer is it's not really that slow it's just pretty fast especially with memory caches and CPUs are pretty smart these days they can actually predict what the the jump address will be ahead of time before you actually figure out where it is that's kind of cool but there's a bigger issue with des that doesn't impact performance that you've probably aware of and the issue is that when you use a trait object you're preventing the compiler from doing some optimizations so let's say we have this code again log example and let's say that we know that most of the time the logger value the logger parameter is going to be a null logger so it's a longer object that does nothing at all so we know that logger dot info does nothing it should be possible to remove that completely the compiler should be able to optimize that away the problem is the compiler doesn't know that it's going to be a lot no longer it has to just write this has to produce this function that is it just works with any type of logger so the solutions that Ross has a solution to that the solutions that is generics so so far we've been talking about trait objects which was the the first line up here where we had just have a reference to a logger but with generics the what we do is we write sort of like a template for the function essentially so in the second example we have a generic type parameter l and this is saying that when you use this function you must provide a type you must provide a note and a null logger type or print logger is type and then L we were saying where L logger so we're saying that L must implement the logger trait so now we can use a linear function and it will just fill in whatever the type actually turns out to be so the way this works when is compiled is that when the compiler compiles this generic function it will produce multiple copies of this function one copy for each logger type so if you use this function with a print logger then it will produce a copy for log example print logger or if you use this function with a null logger they know produces a copy this function for no logger so you end up with this one function template being used multiple times to produce multiple copies of the same function and this is useful because it means that the compiler can actually do these optimizations specifically for the type it can look at what the type is and then do additional optimizations based on that so here's a little example how that would work so I'll get this to this kind of domination of a Fibonacci function right so and the only difference is between these two functions here on the screen is what's in the boxes so on the right I've added just one little logging statement write logger debug and of course this is inside the for-loop so that's really bad for performance because you wouldn't want to do logging and it tightly with it like that so but what I did was I made this generic is I'm not using a trade object here I'm using two New York's so when we pass in a logger object Earl a logger instance then we can make that whatever type to want let's say we made it a null logger so if we pass in a null logger then in theory we should be able to completely eliminate this debug statement all right because the debug statement does nothing logger got debug is just an empty function so hopefully the compiler is smart enough to do that and it turns out that yeah it is so if we passed a null logger to this generic function then it's able to completely eliminate the logger dot debug statement and we just end up it turns out that the decoder on the left is the exact same as the one on the right in terms of what's actually compiled - all right so that's sort of an overview of like generics versus trade objects these are - from ways of using traits and there's really they're really some trade-offs here one's not clearly better than the other in all cases so it with generics you're creating one copy of the function for each type that you use that function with and trait objects you're just creating one copy of the function that works with all types so the advantage with piercing multiple copies is that you can do optimization specifically to that one type the disadvantage is that of course you're producing a lot more code so you get longer compile times which is an issue in rust sometimes and you also get large executables potentially so there are trade-offs here right trade objects sometimes are have a little bit more overheads but maybe they generate less code and that could actually be faster in some cases so pros and cons all right they steal all you got to say so if you're interested in cryptography stuff I blog about photography on chosen plaintext lots EA I also am on twitter and mclean zero so if you have any questions happy to answer those come find me later after chorus talk or tweet me on twitter so that's that's fine so thanks listening

Channel: Rust

Views: 24,461

Rating: 4.9716983 out of 5

Keywords: rust, struct, trait, zero-cost abstractions

Id: Sn3JklPAVLk

Length: 21min 58sec (1318 seconds)

Published: Sun May 20 2018