Rust Programming Language Rust Linz, 25 Oct 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Boxes, Heaps, and Stacks - Tim McNamara - Rust Linz, September 2022

Description

When I learned Rust, I was a Python programmer. This meant that I had no idea what a pointer was. Luckily, the Rust compiler is a good coach.

Tim is an experienced programmer with a deep interest in natural language processing, text mining, and wider forms of machine learning and artificial intelligence. Tim is also the author of "Rust in Action", published by Manning. He is very active in open source communities including the New Zealand Open Source Society.

Rust Linz: https://rust-linz.at
Speak at Rust Linz: https://sessionize.com/rust-linz
Twitter: https://twitter.com/rustlinz

A

Okay, so that was a wonderful introduction. I won't go through it all again um boxes, Heats and stacks. uh What we're talking about today, um who am I first of all, the easiest way to find me is um on the internet as Tim clicks, and uh this is the book that I've written, uh which you may or may not recognize okay.

A

So this seems like a talk about rust, but actually it's really a talk about computers, because this talk will only make sense if we explain not just the syntax of uh box and referencing and dereferencing, but also actually what those mean and what a computer is doing when it applies those operations.

A

At the end of the talk, I would like uh you to know more about what a stack is. What a heap is as well as other things like pointer reference memory address, what the ownership system is and what the lifetime system is, um and uh one or two other things, even in this room and on the live stream, there will be people that actually know a lot more than me about these topics. So please do participate, uh feel free to interrupt me during the talk or ask questions on the live stream.

A

You're very welcome and I'll do my best to answer yeah or at least put it down to something that I need to learn about, and so uh just to be very clear about which type of box we are referring to it's this syntax. You would have seen in Rust with a capital B box and we have less than and greater than and then some type T in the middle.

A

Normally, when we create a variable, uh we'll have uh the variable name and maybe a sort of an optional data type, and then we create something.

A

Oh, we we have sort of the value on the right side, but when we put things in a box, we've got this different syntax, where we we start with the box and it's a new and then we just this kind of magically uh works and what's going on, there is the the essence of the of this talk, because creating a box is different because it allows us to link uh two different parts of memory which enable dynamic memory allocation or enables data structures to be creative.

A

That can grow and Shrink like string does and like vector. Does.

A

But first I want to just provide you with some permission for like not knowing what is happening so I want to explain my own learning path by just explaining how uh I mean I was thinking. Of this metaphor, I was wondering like what. What do we mean by box I assumed because I I before I, don't rust, I spent or about a decade or a little bit more in Python and I assumed that box must be something that could like open or shut, or perhaps it was.

A

Maybe there was like a a bite at the start and a bite at the end. You know some sort of tag left and right, and then the the value was in the middle. None of that is true.

A

And none of it, it's true, so I had the complete uh the completely wrong mental model, um which is quite useful when you try and learn a language where it's um kind of essential, um but like the first place to look, perhaps, would be the standard libraries documentation.

A

The point of the the this one sentence, which is a it, is a a box as a pointer type for Heap allocation that it's no good.

A

Unless you already know what pointer type means you need to know what a heap is and also you need to know what a memory allocation is without, though, that prior knowledge, the sentence is meaningless so, uh and it turns out that actually I think that there's one other really important part of this discussion, which is the the ownership system as well, because the Box takes ownership of the value that you're giving it it's one of its essential.

A

So um if I added my own addition to that sentence, I would include uh explicitly that we're talking about the ownership system as well.

A

So we've got the problem that before we can answer what a box is, we've got some further questions like what is a pointer, because we need to know what a pointer type is. uh We need to know what a heap is. We need to know what a memory allocation is.

A

What's an own value: okay, let's define pointer as a memory address that a compiler has info, for which the compiler has information about the type that the pointer is referring to or the pointer is pointing to so I am a an integer and I have a pointer over here. That is pointing to the integer. The compiler knows the width in memory that the integer uh uh is the integer is uh takes up in Ram, but I've actually introduced some new jargon.

A

So now we have a new question that we need to answer. um What is a memory address? A memory address is a number in the the CPU or the computer. Hardware can actually use to translate to some place on a physical chip.

A

The the mechanics of how this happens is a few degrees beyond the scope of this talk, uh but essentially your operating system and your CPU work together to convert that number into a physical place in Ram.

A

So I'm just going to put say it's sort of what that means. So we can think of a memory address in x86 64. and the particular CPU architecture that your most unless you're doing, microcontrollers, which we just saw earlier, um has been between zero and two to the 64 to the minus one. uh uh At least, we've got a little bit more information to be able to Define what a pointer is.

A

The pointer is the memory there's some length, uh it's known at compile time and uh the first definition was a pointer type for Heap allocation. We've got two out of five questions answered.

A

So we need to add now answer like what is a pointer all of these types.

A

Are actually embedded the same way so the this first one here is a reference to T or what we call a uh a shared reference to T, and this and Ampersand mute keyword is an does. Anyone know what the term for this is yeah, so there are two terms: unique reference would be the C plus plus terminology, and in Russ we tend to use the term mutable reference.

A

They actually mean sort of the same thing, uh and then uh these two are a little bit different, const, T and I'll just get rid of that that doesn't quite work, const, T and mute t or that with the Stars. These are raw pointers.

A

uh And, lastly, so the rule pointer is less useful uh to most rust. Programmers I have, if in it turns out that functions, are actually pointers as well, but instead of pointing to data, they point to mem some space in memory that has been marked as executable, the CPU encodes program code as integers and in memory distance as well. It just happens to execute them, no I'll get out of this, but we actually are really interested in this bottom, one which is box. uh It has the same internal representation as all of the others.

A

They actually live. uh They actually look to in the final binary as exactly the same thing. This is an what we call a zero cost abstraction, the added semantics that we get with box, which involve uh its ownership of the value inside. It are a compile time construct.

A

Many of these times, they're called references I've been using that terminology without defining it. So now we have another question like what is a reference. um A reference is actually a pointer that also has lifetime information.

A

So what do I mean by a lifetime?

A

If I imagine a program started at zero and then, at the end of the program we're going to exit it's a team, a value might be valid from point like time, two to time five, and if I attempt to access that variable at times, six, seven or eight those would be invalid, axises or if I had started to access it before it had been initialized, say it T1. That would be invalid. The compiler actually does a similar thing with lifetimes rusts, difficult syntax.

A

The reason why rust requires you to sometimes use lifetime annotations is because it uses this information to guarantee that you will not access memory at the wrong time. You can't access some value before it has been initialized.

A

That is, you cannot access uh a variable before it's been defined like if the name doesn't exist and you will get an error at compile time by the way and as a python or an X python programmer. This was very, very handy. I. Don't have to worry about name error anymore.

A

um Well, we're kind of we're we're like creating a bit of a stack of questions.

A

Which is slightly intentional, uh so we've got this definition of a lifetime of tea is some span of time for which accessing a reference to T returns T and by T. There I mean a value of some data type. um It's uh now. If you are a systems programmer or if you've used, C, plus, plus or C or some other systems language- and you know what a stack frame is.

A

One thing to note is that rust's lifetime system actually is bound to the stack frame of the function, but I think it's an interesting thing to explore and I welcome. You invite you to do so, but I'm not going to talk more about that, because I don't want to scare people who don't know what a stack frame is.

A

uh We have most of the questions answered, although we keep adding more questions, so I don't know, hopefully we'll get to the end. uh We now need to ask this one answer this one which is like what is this: the Heap I'm going to answer that by introducing another piece of jargon, which is the stack um now so that's a problem, the stack is some. So we've talked about an address space, so the address space is this region of memory between 0 and 2 to the power of 64., and the top of that address.

A

Space like right up towards the maximum value is where the stack lives and right down the bottom towards zero, although not including zero actually uh is where the Heap starts.

A

That is um only relevant in the sense of if they collide for some reason, that's actually a big problem uh and in fact there are Protections in place to make sure that your stack doesn't grow too large. Your um this is where the term stack Overflow comes from anyway. I should start defining these terms.

A

The stack is a region of memory of the address space that is reserved for function calls it works really really quickly, because its memory model is very fast. Everything that exists in the stack is of fixed size.

A

Additionally, there was actually some Hardware support for the stack. There is a CPU register called the stack pointer and variables that live inside the stack tend to be very small. So what ends up happening is a lot of the CPU cache or a lot of.

A

If you call into a function, you'll typically keep all of your variables, either in registers or in a CPU cache, that's very close to the computer, and if you uh uh I are a language like rust and you really care about performance, that's where you want your data to live, because the alternative is that you have references and pointers, and that means that you have some memory address and some other part of the address space that you need to jump from the top of the address space down to the bottom and then find the part in memory where you're referring to and then you'll come back and forward and hop around and that kind of hopping or, alternatively, you can get even further.

A

We have references to references to references. This is a a very slow process that involves like a lot of accounting, there's a lot of extra work that is involved for accessing memory from the head, uh there's actually so much extra work that it's configurable.

A

If you want to really look into this, the rust provides the ability for you to control how the access works. This is called an allocator and uh one other thing to note just because it was relevant to the previous discussion. Is that microcontrollers typically don't give you access to uh two dynamic memory or you don't get a heap? You only have a stack.

A

Everything needs to be of fixed size, um so you can think of a uh you can think of a pointer or, like you can think of the box type, it's kind of a link between the stack and the Heap.

A

It provides you with the ability to access this very flexible, address space, but provide a very uh but keep a fixed size reference inside the stack. So our functions are always in the stack, but when we need flexibility because we want a data type that can shrink or grow all for some other reason, because we might want to share references between functions to some memory, it needs to live in the Heap.

A

Then we need some kind of way to refer back to it and the box is that tight because of its ownership? Semantics I'll just talk quickly about what a memory allocation is. That's a request for memory from the operating system and uh the ownership system was the last one to uh was there a question.

B

The last uh expression it has a little Asterix clue right, so you don't necessarily go to the operator.

A

Right, okay, yeah yeah, it depends right there, so so I put sort of in a couple of the other ones.

A

uh But I didn't hear now the the point was just for the uh just so that we're good and the microphone that we don't always get it from the operating system, or at least you might have asked for say, 10 kilobytes previously, and then you decided to tell the operating system that I don't need two kilobytes of that and then subsequently you asked for some more memory, but you already had it available, and this is what I mean by uh so you could think of a very simplistic way to implement.

A

This would be to always ask for more memory from the OS.

A

Alternatively, you could be smarter and and try to group requests for memory of very small data types into some into a single, larger request, because presumably asking for memory from the OS is going to take some time, and so we don't want to do that very frequently. And so this is configurable. But it's a complex, difficult subject and I.

A

Maybe I'll just put a hidden Asterix in there yeah yeah. It is true for the default cases and right, yeah, okay, yeah, that's right! It's always tricky when you try to write a talk for, hopefully a general audience without scaring too many people. Hopefully there aren't too many people who are just more confused at this point.

A

um There is one final concept that we should Define, and this is this is ownership, and this is like the easiest thing to Define in a hole of rust right. No one has in his rowing um okay, so like what is an owner uh in Rust. So the reason I think this is another metaphor that is difficult because it does not match our intuition for what the plain English definition is.

A

If you look in a dictionary for property and owner, it will probably say something like has exclusive access or the ability to uh if I, think of property rights, if I own my house and like it's little piece of land, because I have like a little single family house, I can tell people who don't belong there to leave and they would be required to leave by law and uh uh but that has no association with property or ownership in Rust.

A

The owner does not have the ability to say no, you cannot access this. My data type, uh in fact, even when you, uh even if you are the owner and like your scope, is the owner and you have a method, call you'll notice that all method calls have the Ampersand mute self.

A

So you still actually need to borrow from yourself, uh and this is because um the only thing that the owner does is safely delete, everything that it owns so you could think of, uh and that is the owner when it is dropped. It calls drop on the things that it owns the end. That's all all uh the the owner has no special power. They can't go to court and force your data to come back. You cannot go um uh so now we get to go and touch a little bit of code.

A

um I wanted to show the difference of uh I've got a here is in is our kind of normal one. Two three and B is uh is in in a box, and hopefully I can.

A

And I'm just gonna click, probably gonna link and if I create a main function and then I call math.

A

This should fail to compile, hopefully as long as I know a little bit about rust.

A

um So what this is saying first of all, is that it doesn't know how to add a value of. Let's say this: is we guarantee we like?

A

Let's say we say it's an i32 and uh this one here so the values- and these are the same, so it should in principle, work. Okay, it's saying I know how to add lots of other things, but I don't know how to add these two types, I can't add i32 to a box of i32.

A

In fact, we need to add a star, and this is not a multiplication. What this is a a request is of rust to go, follow and get out what is inside the box and bring its context back into local scope.

A

uh It's called dereferencing. So now we get a different compiler error, which talks about the um I need to print.

A

A

We should this is all fine, so um using box can be a little bit clunky or like if you can feel uh less comfortable, because um because you kind of get these kind of syntactic problems, but I wanted to show you and we we can put in anything that we want.

A

Oh actually, I will get to the next slide because it's important like. Why would we do this? um The the standard thing that we want to do is like. Why would we use a box is to return a reference to some local variable, so we could assume that we've got some difficult or complex structure.

A

Oh, this is sorry. I had a typo I meant to change. This uh I can create a which is some difficult or large thing, foreign and and then I can place it in the Heap. So a is at first a local variable and then after I call box, this difficult or large object is sent to the Heap and then a pointer is returned from the function, so it just an integer comes back, but actually this difficult thing actually moves to the Heap and the good thing about the Heap.

A

When you're dealing with functions and references is that um the lifetime of difficult or of a is no longer bound to the function call itself uh so normally, if this was not here, if I was just um returning large, the caller, the the function that called build would be the owner of large and then, when that function ended or when the variable came out of scope, it would be deleted um and yeah box provides us a little bit of flexibility.

A

uh We can also use box to create a vector of any of trait objects. Now the difficult thing about a trait object is that it does not have a size, that's determined at compile time.

A

So what this is saying is like I want a vector. We can think of that as a list of box din display. Does anyone know what is happening here.

A

Hands up, we've got two hands at the back, um so right. So we're saying we would like um give me. This is a victor of objects that Implement display. So if we had this uh in this pattern is actually implemented um in I found it in GitHub. So this is quite hard to read. Sorry, um you can see here that this person has created uh it's in line, 25, sorry that um they have a trait of fuzz Target, and so this is a um and the specific types that the that exist. Within.

A

This Vector are all different sizes, but because they Implement fuzz, Target impul, they can all live in the same Vector rust would just normally not allow things of different types to be um in in one Victor, because it likes to know of exactly how wide everything is in Ran, because its preference is to put things on the stack, because the stack is faster uh in this case, if I go uh uh I might play around with this.

A

A

Irritating the people with the mic, so I've got some Victor and.

A

I need to create an immutable vector, and it so- and this is answers a bad new name. So it's like printable things.

A

Okay, so what we're trying to do is create um a function that or some object that.

A

uh Standard I think it's.

A

In a format display, so the rust will allow me to use the absolute path in the name saying it doesn't need to be mutable saying that you never use it buddy, there's no need for them to be immutable, but it was developed code. It will actually compile and do nothing so thanks rust.

A

um So we can push our friendly one. Two three big and also printable I- should have given that short name.

A

Push a character and I would like to just add an emoji in there, but I don't have one so Ampersand I'm. Sorry, an answering all have to do and.

A

ah It's now saying that you need to actually put these in the Box, because you can't actually put the objects in there directly, so you're cheating, this error message is so nice. One of the things I really like about rust is like it can be a better programmer than me, like I. Don't need uh uh I honestly feel that that I learned one of the things I I like about the rust compiler, is like it feels like a coach to me.

A

Yeah yeah, it's really nice! um Well, the box is such a common.

A

uh It's such a an important part of rust that um it's it's useful to be able to I guess or it's important, to be able to give really helpful messages. Now I'm going to change things just a little bit, because I want to show what happens if you.

A

uh Let's say we get our difficult type again, this time, it's not large. In fact, it's zero size and I'm putting this in the Box.

A

uh First is saying so: it's saying that difficult does not Implement debug and what that means is the compiler doesn't know what I want when I tried so I can't just the compiler doesn't know how to convert difficult to a string, and so it won't allow you to put anything into any Vector. Instead, you need to be able to.

A

You need to actually do what you've said, which is like only rely on the trait that you have defined. The other thing that's important is um this: uh this trait object will only Implement one of them, even though uh debug I think relies on display or does display no I'm going to stop there.

A

Yeah they're independent should I should stop kind of going off track. uh uh One other thing that you may wish to do is that they've got a B and C here and let's say we want, and this might be uh say, small medium large.

A

And then I want to provide some sort of other category now, if I have multiple selection variables.

A

um How much memory this is one kilobyte, so this is an array of 1024 bytes. Now.

A

You should only need one byte to encode all of these three because they uh in fact just any bit pattern. That's different will be sufficient, but you need one kilobyte here. So if I had multiple variables.

A

Like S1 was selection, small and let S2 is selection, medium.

A

Hunter intuitively, this will actually take two kilobytes of space, because rust will always make them every enum the same size and the size must be able to fit the lot. The widest longest uh variant in.

A

The uh must be able to fit the widest variant, and so, if I put box, suddenly the size goes down to the size of one box, which is eight bytes. There's a question at the back.

B

A

As long as it comes more should be smaller, that's something I'm going to check and that's a very good question. Let's say that I have two immutable variables like these two here and I only ever create those two uh in fact, I, essentially never use large or other. If I comment them out, my code will still run so effectively they're irrelevant.

A

The question is, in that case, is the compiler not smart enough to just erase this large variant and just use the smallest or the type of what you um what you've actually used, because these are all immutable variables? Isn't that enough? My understanding and I want to double check this. Can you please correct me in the comments if I'm wrong, because I'm going to say something: that's that is likely to make someone like perk up first of all, when I'm talking more about rust here.

A

So this is a little bit off topic, but um immutable and rust is a lie.

A

When uh we use this term, uh we we say mutable and immutable. Now this is false, rust, because immutable variables are still mutable. That's why we have this notion of interior mutability.

A

What okay so allow me to explain if I, if I may so.

A

Immutable works conceptually most of the time, but what is actually guaranteed by rust is that two unique references or two immutable references will never exist, so there will be. There will never be two writers of the same data.

A

If, however, you are the income, if you own the oh getting myself into trouble, if you have that owner the mutable reference yourself or maybe a owner, did you if you can guarantee- and this is what cell does the cell type provides interior immutability? You can swap what is being referred to, and so it can pretend to be immutable, even though things are changing underneath now uh uh that still doesn't even that doesn't completely answer your question because you said to me but Tim, you will never use that variant in your entire code base.

A

I'd still think that I know that you'll get a compiler warning saying these variants are never used, but I don't think that rust will erase all of the uh all of the access to those unused variants like I. Don't think that it will create a type that is different than what you've written in source code now I.

B

Is allowed to delete the symbol if it's unable to inline every case and there is no unsafe functions and no references away from it, because everything else and you can swap it or she can do weird stuff and only then you can save the whole space, but then disabled will completely disappear. Yeah.

A

B

But anything else it will allocate for kilobyte and the bite, and if you have four of these on the stack, your program, validation, randomly crashes.

A

Okay, so I just want to get some of that on microphone, so hopefully I can replay this um correct, uh so the the rust compiler will only erase code or um if it can under certain guarantees, and those guarantees include the fact that you there is no uh unsafe. There is no. There are no other references into the data, um but uh essentially, even if you never use large or never used, other rust will still need is required to assume that somehow other might appear in your program and therefore will include the whole uh kilobyte.

A

um Alternatively, uh this is a much more niche area, but if you write a compiler or you have lots of intern strings, you can save a wonderful amount of like one byte. Oh sorry, no, no, eight bytes, actually uh one word width of um by using a box to Str stir with a little case s rather than using a string and, like you say what what is a box to a string or a little case s string.

A

uh This is a span of bytes that is guaranteed to be UT of eight there's, a massive downside to going with the Box, and that is, you cannot mutate. The box, like you, cannot mutate the string or no, no, that's you can't grow it. You can modify the data that you've got internally, but you can't actually go um and uh change it. Okay, Box by the way, is also the basis for collection types such as vector and string uh string by the way is a vector of as a vector as well.

A

um Actually there's a massive extracts there. It's actually not boxed. If you go and look at the internals yeah.

A

Yeah it'll be a good time to finish. No, no, um the uh almost it turns out that, because of the way that, because of some really nitty-gritty internals, we, uh the implementation is a little bit more complicated but um contentually it works.

A

And uh but the biggest thing you will see rust being uh box being used for is recursive data structures um and if I wanted to implement a linked list in Rust, I would call for box, because otherwise, if I didn't that's the end, I would try to create a type that's of infinite size and with that I think we'll skip the looking through the other sections of the books and I shall say. Thank you and um done.