Rust Programming Language Rust KW Meetup, 9 May 2018

Previous Meeting Next Meeting

⏯

youtube image

►

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

Description

This video was recorded during the Rust KW Meetup in Kitchener-Waterloo, ON, Canada on May 9, 2018.

https://www.meetup.com/Rust-KW/events/250122657/

This talk is targeted at programmers with experience in other languages but who are new to Rust. We will start with a quick introduction to structs and traits, then look at how we can use structs, traits, and generics to build abstractions and write better code without sacrificing performance.

Talk written and presented by: Tim McLean (https://twitter.com/McLean0)
Recording: Mark Sherry

A

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.

A

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.

A

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.

A

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.

A

To give you a lot of expressive power in the language. It's a very impressive.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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?

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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?

A

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.

A

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.

A

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.

A

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.

A

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?

A

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.

A

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.

A

This has to produce this function, that is, it just works with any type of logger.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.

A

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.