Rust Programming Language Rust Linz, 22 Dec 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Profiling Code in Rust - by Vitaly Bragilevsky - Rust Linz, December 2022

Description

Profiling is a way to understand program behavior in terms of time and memory usage at runtime. Profiling is generally considered an advanced topic, but it doesn't have to be hard at all!

In this talk, I want to present and discuss various approaches, tools, and crates that help us to explore time and memory usage of our programs. We’ll explore a simple project, discover its characteristics and see what can be done to optimize them. We’ll see how to measure the timings of code fragments and functions reliably. We'll look at flame graphs and learn how to understand them. We’ll talk about such techniques as reserving memory in advance, avoiding creating auxiliary data structures, and removing unnecessary memory operations. We’ll also see that extensive correctness testing is a must-do when optimizing code because making programs faster and more memory-efficient should not lead to making them incorrect.

It's okay to profile our code along with writing it. It's not about unneeded premature optimization, it's about doing it right at the first run!

Slides: https://bit.ly/profiling-rust

Rust Linz:
https://sessionize.com/rust-linz
https://rust-linz.at
https://fosstodon.org/@rustlinz
https://twitter.com/rustlinz

A

uh Yeah uh so I'm going to talk about profiling, code and rust, and my name is really Vitali bragilevsky and I work at jetbrains and we are just brains. We love Frost, very much and I will use Sea Lion for doing this presentation, it's our main IDE for writing rust code, but in fact the things that I'm going to discuss here.

A

They are a little bit more General than doing rust, with our rust, plug and insulin and Stefan said a very important thing that he he doesn't do profiling and I would like to start with the results of some survey, which was held like a year ago, but this survey is actually very, very disappointing.

A

So we've asked what profiling tools do you use for rust and it turns out that 84 percent don't use profiling tools at all, and this is very, very disappointing and in this talk, I would like to discuss this situation. Why is it like that? So how can we do better? Do we really need that profiling? So this is what I'm going to discuss.

A

It's uh actually a very simple talk, so I will give you several advices but they're very simple and you can apply them and your code will be better and you don't have to work hard to do all that stuff. So, but profiling tools uh well not very popular among Ras Developers.

A

So let's discuss why so, maybe maybe all those people they just don't know what is profiling. So, let's start with discussing uh definition. So if you look at Wikipedia, you will see a definition of profiling, so Wikipedia says that and I will show you this definition part by part, because every word here is very important. So we have to understand it clearly.

A

So Wikipedia starts with this disclaimer, so we're going to discuss profiling in software engineering because well in real life we have some other meaning of profiling, but in software engineering it's a little bit special uh first profiling is a form of dynamic program analysis.

A

You may know that there is static program, analysis and dynamic program. Analysis and static is done during compilation and dynamic is what is what we do during runtime. So we run our program and we do some analysis. So we analyze some program Behavior at runtime, so this is what is profiling then this Dynamic analysis measures something. This is also important, so program analysis can do checks, for example, in Python they have Dynamic type checking, so they check types at runtime. So it's not measures measurement but profiling measures.

A

So we want to find out some characteristics of that runtime Behavior. So what are we going to measure? For example, we measure space or memory usage. How much memory is used by our program, then time complexity of a program? So how much time does it take to run that program, the usage of particular instructions? This is also important how many times we read this and that and finally, the frequency and duration of function calls.

A

So this is what Wikipedia says so we analyze runtime behavior of our programs in terms of memory, usage, time, usage of instructions and some characteristics of function false. So this is profiling.

A

No, why we don't profile and Stefan doesn't profile and he, as he confessed and all those away participants, don't profile. Why all right uh so why?

A

We can think about several reasons actually so reason. One, it's really hot or people say that it's hot, maybe that's not the case. Maybe the sometimes it's easy, but we don't know about that and reason: two is that it's not necessary at this time. So people say well. We don't need to profile it right now, because it's not a problem, so our programs are efficient enough. So it's just not necessary to do that now and then they also say so.

A

There are some very, very smart talks in our team and in that team, so they'll do that when it's necessary so like we have a team of 10 people and one of them is just doing profiling all the time.

A

But if we postpone that profiling, then just imagine how many things should be fixed if it's like, we, we develop our program for a year and then we just start profiling. Isn't that a big problem here uh and then there is also another reason, but some people say that they don't want to do premature, optimization, and you may know that this is a famous quote from Donald North, that primates optimization is the root of all evil.

A

So you may hear about that. So here's download note- and this is this uh quote so premature- optimization- is the root of all evil, but as it is usually the case with some funny quotes, they the real meaning of that quote, is a little bit different, because if we read it full quote, then we'll see that Donald doesn't ban premage, optimization so what he actually says, or he wrote in one of his papers.

A

So he wrote that the real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at their own times, and then this premature optimization is the root of all evil. So premature doesn't mean that we do it too early premature means in in his quote that we don't do profiling first.

A

So it's not about banning profiling. Banning like doing something to optimize our program. No Donald knuth suggests the real path. So first we profile our programs and second, we uh do optimization, and this is what we're going to discuss in this talk, so how to profile, how do I find? Which places are right places to do optimization.

A

So that's what we're going to do here all right uh to present some ways of profiling. uh I will use some small project, so I solved lead code problem number 22 I will just describe it in a second and using several methods, and then I just use this project as an example for doing profiling.

A

So this problem is about generating well-formed parenthesis. Combinations like we have opening parenthesis, closing parenthesis and we put them together just just to make it well formed. So, for example, if we have three pairs of parentheses, then here you can see the the output. We have five possible well-formed combinations here uh and in my project, I have three implementations. One is breadth first search. Second, one is depth first search and sub combinations. The there is an information about that in the readme file.

A

If you look there, you can see what's going on all right, so uh this is linked to the GitHub and we'll explore this project right now and we'll see. What can we do about that?

A

Okay, so if you are interested here, is the core chord and link to this project. So, let's, let's see it and remember I'm in silai, so I will use everything here so to to to present this project. So first, let's look at the project structure.

A

So, of course we have some source files here and I have three implementations. They are all uh I put them in separate modules. We have main file, we have Library, so just as usual, Library create binary crate and all those implementations aren't there. So we also have have benchmarks here. We'll talk about them a little bit later uh we have a Docker file. I will show you why I need Docker file. Here we have tests, of course, integration test here. So this is our project structure. Quite usual uh rust project, nothing special!

A

We can run this project. So let me let me show run it here. So first I can run it using command line, for example, cargo run- and here is it so I need to provide some arguments. There is some help. I can like I. Do that here. So a lot of information. So to run it we need to provide the following. So I will, for example, to be verbus and the size of the problem will be 12. Where is it 12 and then I am interested in breadth.

A

First search implementation like this, so if I run it I will see some information. So if I don't want to write all those arguments, I also have some run configurations in the project. So I can I can run them like, like here, for example, run BFS here. Is it breadth first search so I don't need to provide arguments all the time I just saved it in run. Configuration here is some some results and of course, I have tests and I can run tests.

A

So here is it. Everything is all right, so we're on the safe side and whenever we change something we can test against just to see that we don't break anything all right. So this is small project overview and now, let's get to the main stuff.

A

So what does it mean to profile memory? Usage here are several questions that we may be interested in, for example, how much memory is taken by some containers from string or a vector or stuff like that? How much memory our program uses in in total so when and how we allocate memory because memory allocation is some operation which requires working with the operating system. We have to do system calls. It takes a lot of time.

A

So we want to know for sure when that memory is located, so is it delegated correctly, like people often say that we don't have memory leaks rust, and this is definitely not true- it's possible if you use reference counting something like that, it's possible to get some problems.

A

So there are several simple things, then that we can do in this regard, so how we can profile that so I'm going to present them, but remember I'm not going to talk about something very sophisticated, not at all so no sophisticated things, but we can do a lot using just very simple stuff.

A

So let me uh show you some examples of the code how we do stuff, so I will start with this. So let me just just sort something: I will I will change some structure of my ID here, so just just to see everything and I'll get back to the presentation mode. So here we are so uh our first tool is just asking for length and capacity of our data structures.

A

For example, here you can see some information about memory usage in our program, so I just asked for the length of the vector just as usual and the capacity of the vector so length length is the number of elements in that vector and capacity is memory usage.

A

So how much elements we can put into Vector without changing its size, so very simple, but it's actually very helpful, so I think I think I can I can uh show how, when we run it so here you can see the size and capacity are just the same, all right, very simple, and we can do the same with strings, for example, string capacity.

A

We can check that too, and uh so I compute it here so here here is a problem with strings, and we know that if we have 12 parents, that means 12 pairs of parentheses. That means that the size of the string should be 24., but every capacity per string is 38, and that means that a lot of strings just use more memory that we actually need.

A

So, even if we look at such a simple characteristics, then we'll see that there are some problems like 30 percent of memory isn't actually used for good, so a little bit of problem.

A

Okay, then, let's look here. So what is this function? Dynamic usage usual Vector doesn't have such such a function. It comes from another crate, so I will show it here, it's from memus.

A

So if you add this dependency, you will go get this function, which tries to do its best to compute the overall memory usage of your data structure such as vector or hashmap. You can use this Dynamic usage function with everything. So just add this library and you can get a lot of your information and I also use human bytes. Here. Just just to present this information in this nice way, so you just seeing it 7.6, megabytes and stuff like that.

A

Oh by the way it's it's a little bit outdated, I can update it right now. Maybe it's better yeah awful enough. Nothing will break yeah.

A

Okay, let's, let's write check as usual as we do that we we write tests all the time and if it's fine, then okay, we have no say safe side, so just Justice okay, um so we can use very simple library to check memory usage like this Dynamic usage and just you can get a lot of information about that.

A

How many memory is actually used by our problems, but these are very simple things: let's use something more sophisticated, namely let's do real real profiling, so I will use uh instruments so I'm using Mac, OS here and then Mac OS. There is this program instruments that actually shows you a lot of information about your program, so it's profiler for Mac OS operating system.

A

So let me call it so here: I run the program with BFS and DFS one after another, and then I want to to see how the memory is allocated so I'm talking about memory allocation here.

A

So let me run it and it runs the program it compiles, all the all the information and when it's over it shows us how some information in a graphical way here is it foreign.

A

So this is BFS and you can see these steps. How memory is getting bigger and bigger like this allocation, then more locations even more locations here graph.

A

We can see, for example, that there is no memory leaks here, because this is our first BFS algorithm and then every memory is almost every memory is read, and then we start our second algorithm and then again we do a lot of allocations and then everything is read again, so this behavior is actually very good. One problem, one possible problem that we can see from this graph is that we do a lot of allocations here.

A

So we can. We can see its some stats here, but it doesn't matter for for this moment. So when we do a lot of allocations- and you see these steps, these steps here, you can think about time which is spent on that allocation. So every time we ask a trading system for to give us more memory. Maybe it's it's better to ask for that memory in advance, then we'll ask it for just once and then it will be. This graph will be a little bit different, all right. So I will close it now.

A

So very simple thing: in fact: if you are interested in this instruments Library you can, you can use it with cargo. There is a crate cargo instruments, you install it and it's just just some intermediate thing between instruments and your cargo project. But of course not, everyone has Mac OS like in uh Windows. You have Visual Studio profiler. Well, it's totally different, but the idea is the same. So you don't need to know a lot of things about your program to see this small graph.

A

It's very easy. So many people have uh Linux and in Linux we have the main tool for doing. Profiling is well green. So, let's run wild ring here, so I have special uh run configuration for Val, green and I use Docker to run it because well, we have Walgreens for Mac OS, but it's not supported in a very good way. So let's run it in a docker, so I have to Docker container I'll, discuss it in a minute. Let me write run terminal here and in terminal and go to the directory. With with this project.

A

I do cargo build and while it's updating crates, let's look at this Docker file, so Docker file is actually very simple. It's Ubuntu and I installed Al Green, some Clank C compiler, something very, very essential in order to make all these uh workable and then I also install rust and I use, table rust and so very simple. Docker container and I use here. Docker integration for selection and it's installed- you don't don't need to install it, because it's bundled with someone uh from the very beginning.

A

So, with this Docker file we can run everything we want in the docker container, so we have file green and we have Frost and then let's wait when this build is is over.

A

So my idea is to see that we can have the same graphs as an instrument, but for Linux, so we don't have to uh do something with our operating system.

A

Sometimes profiling in different operating systems is shows different results, but that's hard part, but we are talking here about easy parts. So for us, if it's okay in one operating system, then it's okay in another tool, all right, so we have we've built it. So I can run it. So this is my path to the executable.

A

uh It's Target Docker. It will be debug build. This is from program. So this is it yes, this is it so I will write, verbose version with size, 12 and this will be BFS. So here is it it just just run it and now I want to run it using valgrind. So it's just the same command line, but I, add 12, green and well. Grint is actually a family of tools, and one tool I want to use here is called massive.

A

It's memory analyzer in Valkyrie. There are several memory analyzer, so passive is one of them, so I run it and while we run it, it creates a file. We can see it here and it's it's actually very, very long text file, but fortunately there is a special program here to analyze it. It's called massive print.

A

Okay, so once again it's a lot of information, but there is something interesting in the very beginning. Let me show it to you, so here is it.

A

This is actually the same sort of a graph. We saw in instruments it's in text form, but still it gives you almost the same information. The behavior can be a little bit different like the behavior of allocation, because this this part depends on the actual operating system. They have different allocators and different system calls and stuff like that, but still it just allocates something, and then it's freed everything up.

A

So this is the behavior of our program and we can use it very easily and we can see what's going on here.

A

So, in order to profile memories, yes, and- and we also- we can see the the amount of number of bytes allocated and stuff like that.

A

So we can see these pictures and if we change something we can compare with those pictures and see if something is different. All right now, let's look at uh time profiling once again, very simple things. We want to know how much time does it take to compute results, and we also want to know where the programs spend most time and that means which functions are hot. So these two questions are actually the same thing. What means we spent a lot of time there so how we can do that?

A

The first, it's very simple thing: we just use standard time functions from rust, for example, here.

A

I check time in the beginning and then I run algorithm and then I see how much time is elapsed. So that's it very simple. So, let's, let's run it run it again. So, for example, this one. So it's it it's just just this information good result in this timing.

A

So in many cases that's enough so I just Mark the beginning, Mark the end and see how much time was elapsed at this algorithm.

A

Sometimes it should be a little bit more interesting. For example, we can do benchmarking and while doing benchmarking, let me show you my benchmarks: I use a Criterion Library here, so I will run it benchmarking, for example, this breadth first search and what is actually going on here.

A

Criterion run our functions many times like 100 of times, and then it computes some statistical characteristics. For example. Here we can see this is average time we run it, and so this is uh for different sizes, like if n equals to five. Then we have this two microseconds and 4N equals two. We have one millisecond and then 16 milliseconds for n equals to 12.. So we can think about these stats. So we just Benchmark them and we can remember- and if we change something in our program, we can Benchmark again and see what changed.

A

So this is profiling time. So now we know that our functions take this amount of time for these sizes. We can also do profiling with a special tool here. So let me run profiler, so I use the same, run configuration but now, no not that, but now I will ask for profiler here.

A

Is it and what we see here at so-called flame graph and this flame graph is extremely important and it's extremely important to understand what's going on so this is all our program like in time, and this is generate parenthesis function like it takes 63 percent of the parent of this or most of our program. So most of the time is spent at this function. But if we look further, we'll see that the problem is that most of the time is used for reserve for push operation, and this is something that goes from vectors brushed vectors.

A

So why, instead of generating parenthesis instead of solving our problem, what we actually do is we uh resolve memory, and then we also do some real occasions, and then we allocate new memory. So most of the time like 66 percent is taken for Vector operations, and this is definitely a very bad thing.

A

So we don't want to spend time on Memorial location and, if you remember, all those steps and now in our instruments, graph of Al Green graph- that's exactly because of this Behavior. So we look there. We looked here and we see that we have a problem in our software in our code, so we've done profiling and we see that a lot of time we spent on allocations- and this is not a very good thing. So we need to do something about that.

A

Okay, what can we do about that? uh Several very simple techniques I want to share with you like I'm sure everyone knows about them, but they're so simple. So sometimes we just don't do that, but they're not only simple but they're, also very powerful, so uh I'm not going to take your time writing code, so I will just show you what I already have.

A

Actually we are here and I have several commits in another Branch just to see to show you what's going on so how to change that, and our first practice is to reserve memory in advance, so we use capacity for that. So, instead of allocating memory when it's needed, we resolve it in advance and then we reduce the number of allocations.

A

For example, let's look here oops, not not this one I will I will need it here: okay, let's, let's make and restructure these.

A

A

I want to exit presentation mode to change and we will get this okay here. This will be better right.

A

So fixing capacity, but before we had creating just new string but in fact we know the exact size of the string like if it's 12 pairs of parenthesis, then we will have 24 symbols, characters in our string, so we know the capacity.

A

So, instead of doing U, we say string with capacity and we create string with exactly this capacity. So just uh resolving memory in advance, very simple technique, but it's actually very powerful. And if we do that there will be no excess memory usage inside strings and we have a lot of strings because you can imagine like hundreds of thousands of them, then we can do the same with vectors like here.

A

I was creating just empty vector and I pushed stuff to that. But it turns out that in our algorithm, I can compute the number the future number of elements in that vector and if I computed them I can spend some time on. Computing doesn't matter what I'm actually doing, but I've tried I'm trying to predict the number of elements and then once again, I use for Vector. This width capacity file so I create a vector of the specified capacity and then A reduced number of allocations.

A

So this is first very powerful but very simple technique. Then we can do resizing instead of resolving capacity. We can create new elements.

A

Just in the very beginning, those elements will be empty and then using mutation we can put the right values there. So, uh for example, I'm doing in the next commit like precise in advance, so how we can do that. Where are our changes like uh instead of having a vector now I have a mutability reader and uh instead of putting element to the vector I use that iterator to put things there so I've I've created a large vector and all the elements are already there, so I'm not pushing those elements.

A

I have them already, but those elements are empty, so I just mutate, their values, for example. Here the result element is combination and I, put a new line, so I change line inside that combination, so I'm the data okay and here I, create new vector and that I resize and then I put. These are my new elements.

A

They will be empty, but the the size will be correct and then I will change those elements here is it uh my next technique is avoiding temporary structures.

A

It's not always possible to avoid, because borrow checking can make it hard to do that, but still when it's possible, it's a good idea to do that. So, for example, here uh before I had a new vector and now I just remove it, I don't have a new Vector. Instead, I use the same vector and I resize it to be able to to get all those new elements.

A

So I go over first part of this vector and I put elements in the second part of that vector. So you know in Russ it's difficult to mutate, several parts of vectors like beginning and end. So it's not that easy.

A

So here, I use very nice functions, split at mute, which gives you two parts of vector and both of them are mutable, so you can just do the old part of the vector is first half new part of the vector is second part and you mutate something in the first part, and then you can imitate something in the second part and during one Loop, so very powerful, and you don't need a new Vector anymore and once again you reduce number of allocations, so really really very powerful and one other technique here like it turns out that we don't need all those uh memory reservations at all, because we know exactly how much parentheses will be in this problem size because it's so called Catalan number and we can compute them.

A

So if you have this function, it doesn't matter what is it, but it gives us the size so, instead of pushing instead of resizing, we just say well: total capacity will be this one and then there will be no allocations at all.

A

And of course, whenever we do these changes, we have to check if everything is all right. So whenever we do all those uh optimization techniques we have to test so for now, let me check out this optimized version. Okay, here we are.

A

And then, of course, I'll write around tests, so this is optimized version. Okay and now let me.

A

See what's going on in our uh instruments, so, what's going on with our memory? Okay, we're on this program, foreign, okay,.

A

And this is it.

A

Okay, do you remember all those steps that we had before and now there are almost known steps like we reserve as much memory as possible. We've reduced allocation and this program behavior is much much better, so real difference, okay, and if we, of course we can, we can also run our profile okay from the first with profiler and, let's see.

A

This is our generate parenthesis function and before we had a lot of memory reservation stuff here and now we don't have it: we've just removed it.

A

Okay. What about timing? Is it any better than before? Maybe it's not better? Let's, let's try our benchmarks.

A

Here are some benchmarks. We can pile it again. We run benchmarks and Criterion library is so powerful. It shows us how much uh better our program, our implementation is.

A

Okay, now it's improved 55, better, it's for smaller size and for another size also improved, uh and uh for for the last time I I think it will be improved to yes, yes, so everything is improved, so Criterion just is able to compare it with the previous ones.

A

So you see that I have showed you very simple things very traditional rust things, but if you do profiling at early stages, you just see all that stuff and it's really really very powerful.

A

Well, of course, it's still hot, so I think I don't need all those windows so.

A

A

My slides, so it's still it's hard, but uh there are many tools and I've showed you about Green family I've showed you instruments. If you are interested, you can look at this Library, uh the head arrest, which was designed specifically for rust, and it allows you to introduce profiler into your program. You just add several lines. So then you have a lot of possibilities, it's also very, very powerful.

A

So it's difficult to know all those tools, but it's a good idea to at least to get familiar with some of them.

A

uh If you use Linux tools, they are mostly terminal based, so you just run them and you see all those huge files. There are visualizers. You can look at them, but one important thing is that you don't have to understand everything in those those files or just not necessary. Instead, you just try to look at important parts and that's enough for many cases.

A

If you look at tutorials when usually they focus on hard things, but it's not necessary to know all those hard things. In fact, in most cases you don't need that.

A

So I've showed you a couple of graphs and then it's clearly visible that we have a problem and then we've applied some simple techniques, and now it's clearly visible that we don't have that problem anymore.

A

So you don't need to apply very sophisticated instruments, very sophisticated techniques, techniques to make your programs better. So that's important idea as usual for doing 80 things. You just need to master those instruments at twenty percent. No additional Pareto rules, so it's hard, but you don't need all that so I want you to start profiling as well as possible. Don't postpone it! Don't delegate it to other professionals, because it's easy and it allows you to write better programs and that's it for this talk.

A

So you can download these slides here is a link and feel free to talk to me in Twitter and whatever, and thank you very much.