Rust Programming Language EuroRust 2022, 4 Nov 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Optimising stable sort in Rust and mostly failing - Lukas Bergdoll - EuroRust 2022

Description

Lukas Bergdoll
FOSS Advocate and Rust Enthusiast at MVTec Software GmbH

Inspired by a promising C sort implementation, Lukas set to porting it to Rust. Over the course of a couple months Lukas build a suite of tests and benchmarks that helped him develop and validate improvements to the existing slice::sort implementation in the Rust standard library. Along this journey he made all kinds of different mistakes, ranging from basic implementation errors, to subtle test methodology issues, and even more subtle issues he isn't even sure are technically bugs but yielded very surprising results. Lukas wants to share his experiences and learnings.

This talk assumes basic Rust knowledge, and will touch on speculative execution and the effects it has on Instruction Level Parallelism (ILP). It does not require knowledge about sorting algorithms. The methods I used and mistakes I’ve made also apply to other fields of programming.

A

Okay, hello, um welcome to my talk, optimizing, stable sword and rust, and mostly failing um I've, seen many talks that talk about great results. Success and this talk I really want to focus on failure on like making mistakes.

A

um Recently, I had a project where I wanted to Port a promising sea, sorting implementation to rust and maybe improve the standard library with it and along the way, I made many mistakes and I want to focus on these mistakes and talk about them.

A

um A bit about myself, I'm a open source and rust, Enthusiast I love. Reading books, mostly sci-fi I, enjoy board games cooking and many other things I'm terrible at Whistling I. Just can't do it I never learned to drive cars and I work for MB Tech software game. We are and we are a munich-based software company focused on high performance and high quality Machine Vision um a bit about what I do. At my day, job I work on an IDE focused on rapid prototyping, Machine Vision applications.

A

It's called Edge develop inside of this there's a custom programming language with some neat properties and I also maintain and develop language interfaces. So we have a core library and there's the C, C plus plus C sharp python interface for it and even some older stuff yeah. So that's about it. Let's take a quick overview.

A

What this talk will contain um at the beginning, there's some basic implementation errors and some that then later some test methodology, mistakes and, at the very end, I want to talk about a subtle issue: I'm not entirely sure I would call it a bug. That's why I named it issue. So, let's get started. My very first mistake was to underestimate just how much work this would be right.

A

um I looked at this implementation, I discovered it and the documentation describes it as a hybrid merge in quicksort named fluxot, and it's stable adaptive branchless and has exceptional performance. I mean I. Looked at implementation about 240 lines of Code.

A

Zero includes how hard could it be um turns out it's more than a thousand lines of code, because the headers, including the C files, something I hadn't, seen before they're lines of seven statements in them like seven semicolons, so it's quite dense when you, when you try to look at it, it only works for integers and what I wanted to create was a sort, that's General right. It works for all types, all user provider types and it should not only work for them. It should work well for them.

A

It should not just follow the performance skill for user provider types that don't look like integers and turns out. The implementation is not actually stable as far as I can tell so. There were some functions in there that maybe have potted them wrong right, but at least this father could tell they produced. They had tests that checked if a if the sort is stable. If it upholds this property and they failed this test, so I had to change them. It has, as far as I can tell right.

A

Maybe I did mistakes in parting again, but as far as I could tell there's some function that exhibited undefined Behavior and a very big difference is also. There is no Panic in C right, so the the implementation you provided, a user provided comparison function, but this comparison function can only return in rusts. A user will provide a comparison function that can panic, it returns normally, but it can also panic and the implementation has to maintain that um in any possible scenario where this is less function is called, appendic happens and they Define.

A

The result still needs to be well defined. You, the original elements, still need to be in your slice and they need there. There should be no kind of um unsound Behavior because of a panic.

A

So let's look at some basic implementation. Mistakes. um I did some basic mistakes when I parted, C logic to rust logic. There was some off by one errors and unsaved rust code and many other mistakes, but I want to focus on this like incorrect part from C to rust.

A

um So, let's take a look at how this how this user provided comparison function, how it is defined um internally, at least so. This is an internal function of the standard library and to the outside. The users provide a function that returns an ordering as a result, but internally this gets translated into a function that only returns a Bool telling you whether or not one element is less than another element, and that's all you have to work with, in contrast in C, in the standard, Library, Q sort and in fluxot.

A

Also the contract they're going by is this comparison. Function returns an integer and we can take a look at the documentation, but in essence it means you get a negative number.

A

You get a negative number and I guess I'm standing in front of the screen. Okay, um you get a negative number. If the com a is less than b, you get zero if a is equal to B and you get one or like a positive number. If a is more than b- and this is the original I had in C- was checking if a is more than b right and initially, this is how I translated it I ask if a is not less than b, but that's incorrect.

A

The correct version would be to ask if B is less than a and let's just really walk through it, to see why that is so. If we take a look, a is less than b. We don't take this Branch. If a is equal to B, we don't take this Branch either, but only if a is more than b. We take this branch and my incorrect version. It was the same for less and more, but when the elements are equal, it also took this branch and it shouldn't the original didn't.

A

It was not a true part of the logic, and if you do it this way, where you ask, if B is less than a, then you get the exact same behavior. So the mistake I made is I incorrectly translated the logic from C to rust, and the effect was that the sword isn't stable anymore. So this property, that if the elements are equal it shouldn't take, this Branch was necessary to maintain that the elements retain their original order.

A

If possible. Okay, let's talk about some methodology. Mistakes. I did many. Many different ones like false Randomness. Bogus tests Benchmark in general, is tricky and bad distributions. I want to focus on false Randomness and bad distributions.

A

So let's take a look at the like at the beginning, my benchmarks look really really promising and some benchmarks that outperforms the unstable sort by like a factor of two that look good but then as I added more stuff and changed things. Okay.

A

So let's take a quick look to at some point during development to limit the effect that modules and pre-compiled standard Library Parts had I copied the source code of the sort implementation from the standard Library into my repository and each I put each inside a single module, so it was kind of comparable um at the same time. I did another change, but I didn't correlate it in my head back then I didn't realize the correlation.

A

um Let's, let's look at this other change. I did but because it was full for me I did it because I wanted to change something about how the tests work, not how the benchmarks work. I wanted to have a fixed seat for my Randomness, so I put random numbers into some tests and I wanted to make sure that I could repeat what happens if something goes wrong right.

A

If test fails, if it crashes or something else happens, I want to have a way to repeat it, even though it's random and unique per session right so I had this uh I used the rent Library, it's a probably the most popular random number library for rust and I initialized this uh this one value this like a seed and then I use that as my building block for all other Randomness, this random back function produces me a back of i32 and it gets seated with this fixed seat and.

A

There was some time in between I spent some weeks doing something else and whatnot, and then I came back and suddenly The Benchmark results contradicted all my micro, architectural understanding. Initially I thought it was because I copied the source from the standard library and now, like the compiler. Somehow differently sees the code in a different way, and it just gives you very different results, but it just didn't really make any sense.

A

So, let's look at how these benchmarks worked. I used Criterion to do the Benchmark, and we see here we have a function that the sort functions get called with some test data and it's provided by this pattern provider which gives us different patterns so like random, ascending and whatnot a bit more on this later and we use either batch.

A

That's the really important part here where we say for each iteration I want a new input and then I had this like I was writing up something and then I was like wait so like how what exactly does a fixed seat mean for the Rand library, because this is what I believed it meant. So you put in you have a fixed seat and then it gives you. For example, we ask for two random numbers.

A

We get two random numbers and then ask for two more random numbers and I get two different random numbers and it keeps going. But if I put in the same seed, I would get the same sequence of random numbers. So there's some internal stated tracks and it can produce the same sequence of events essentially, um but then I did a little test and this is actually what it means like.

A

If I ask for two random numbers, I get two random numbers, but if I ask for two more random numbers, I get the same two random numbers, and the fact was that every Benchmark used the same numbers again and again and again and again, and the branches also sort with branches which the existing sort is compared to this, like branchless sort, can outperform a branchless sword if it has perfect. Branch prediction and I had spent like several weeks working on this and then like I, felt I felt pretty stupid.

A

At that point, yeah like there was a lot of work down the drain, but okay, so that's the that's. How I fixed it I have a new function, called disable fix seed and um if this function gets called by default, it uses a fixed seat. But if a function is called, it will then start using just random numbers as seeds and um inside the Benchmark.

A

Hunters I call this function at the very beginning, I call it a little test function to make sure that I produce two random vectors, I compare them, and they should not be the same right to ensure that I don't make the same mistake again. So I changed multiple things at once: right we rarely change a single character and then rerun all our tests and benchmarks and Analysis and whatnot, and in my head I incorrectly correlated these events.

A

I thought that I changed something that only affects the tests, but it only it also affected the benchmarks in a very significant way. It was combined with like multiple weeks of pause and whatnot, so it wasn't as clear-cut as it's shown here, but that's that's kind of the mistake. I made like uh one correlation of cause and effect.

A

Let's talk a bit about the benchmarks themselves: I had different dimensions along which I wanted to test. They had different types, so like an I-32 which is just a basic one used for many many benchmarks. That's also the only one used by the provided benchmarks for Flex sort, but I wanted to use different types because right, it's a general purpose sort and it should work well for all kinds of different data, so u64 a string, one kilobyte of Stack value uh to f64s that have a relatively complex comparison function.

A

Some some patterns like random, ascending and whatnot, many more different sizes and hot and cold prediction state. But I will not talk much about this last one. It's not relevant right now and let's take a look at the results. Maybe let me describe this graph so, as we saw, we have many many dimensions. This gives us a huge space.

A

So let's say we fixed it down to like hot prediction: State one type i32 at the very top. You can see this and we want to know how much faster the new version is versus the old version, and each dot is one combination of size and pattern. That means 100 means the new one is twice as fast as the old one and minus 100 would mean the old one is twice as fast, so it's symmetric in that way and we can see there about a thousand dollar dots along this and also a small spider I.

A

Think- and this is what the Baseline looked like so for the random pattern which is drawn in it's really good for many patterns, it's about equal for some patterns, it's worth or some patterns in between, but if we compare this to um u64 like very similar type. Essentially, that is also small, easy to copy. That's there's a very curious shift. You can see a lot of points go from the from like not changing much many patterns go.

A

They now look like the random pattern um and that's curious right, because they, my intuition, tells me i32 and u64 should perform similar, not identical but similar and that's a very, very different result. In essence, U6 performs like the random pattern across most patterns, and so I asked myself. Why is that?

A

Let's take a look, how I transformed the i32 to u64 I looked at it carefully, and my idea was back then I wanted to have values that are actually inside the u64 space, so I multiply it by itself and multiplying a 32-bit number by a 32-bit number should be inside a 64-bit space.

A

um But if you look at it, if you just put in some like some numbers, the result doesn't maintain the the pattern at all like this is an ascending pattern, but we get random numbers. The mistake I did was like I turned an i32 into an i32, because I used a closure and didn't never specify the return type I thought I specified u64, but I didn't um so this is a better version.

A

This is a fixed version, I'm very explicit about the kind of types I want and then I get actually something that maintains the input pattern and works. Even one change a bit more was that it now only works within the u64 space while maintaining the info pattern.

A

Another very similar issue was that I looked at my statistics for comparisons like I, wanted to know how many comparisons are done for a different for different types and sizes and comparing it to the old one, because the comparison function is user, provided so it could be arbitrarily complex and arbitrarily expensive and if you do way way more comparisons- and this is your bottleneck, the performance for the user will be worse, even if maybe the stuff around it is faster, and this is curious right.

A

This tells us that, for the all the sizes below 20., somehow there's one type, there's way more comparisons for the ascending pattern, and that's that's strange because I know that the new implementation does the absolute minimum of comparisons. If the input is already sorted. So if it has 10 elements, it will do nine comparisons guaranteed and that's it and that's the same that the existing one that it does for sizes below 20 insertion sort.

A

So how on Earth does one type suddenly do more comparisons than the other and the the story is a similar one right. The transformation I wrote that went from uh i32 to this like f-128 type.

A

um It was wrong. I will not go into the details. They're not super important here, but just to give you an idea um before. If we just plug in 0 1 2, for example, we get zero, gets turned into Infinite, and this I accidentally by like not maintaining the input order. With this ascending pattern, it hits the absolute worst case of the new implementation and it does way more comparisons, because the very first element is not.

A

The first element needs to be pushed to the very end, so yeah, the the mistake I did was I wrote bad time. Transformations I wanted to add some basic data, some random data or some basic pattern, data that always encoded as i32s and I tried to turn them into different types for my tests or benchmarks and the effect I got by writing these bad Transformations was I, got Benchmark results which are misleading and wrong. They're, not useful in that sense, because they don't talk about the kind of pattern they're talking about.

A

They talk about some some other times, random, sometimes kind of different. So yeah and now I want to talk a bit about a rather subtle issue. I would say it's let's. Let me talk about the discovery. How I discovered this issue and um I have statistics that look at just how many comparisons are done in my sort and they say that to sort slice with random elements of 10 elements on average, so I uphold it a thousand times or so and measured how many comparisons it does on average, it takes just three comparisons.

A

At the same time, my tests all claim that it works that it's correct so like across pattern sizes. My tests pass let that sink in somehow it is both simultaneously correct but somehow uses impossibly few comparisons, and this makes no sense right coach. My first assumption is my tests are wrong. Somehow it must be can't be correct, but I look at my tests and I'm pretty sure it works correctly and, what's even weird, is like the thought statistic produce reasonable results for the existing implementation. So.

A

Let's, let's maybe just look at the sort statistics, maybe something weird is happening there. We have a type um called compound. It has a value again, an i32, that's actually used for the comparison, and then it has a cell. This uh counter and In the comparison function. We use the compound to increment each time this, like user provided function, which we defined here is being called and we do the comparison and then, at the very end, we go through the slides and kind of sum up. All the elements.

A

It works for the existing implementation this, but it didn't work for the new implementation, so I asked myself: what's the difference and I really did some Ben like some debugging and everything I looked really at the implementation and I wanted to see how this works and what what the effect is and at the top you have a function. That was what is part of the existing slice sort implementation. It takes uh the first element and pushes it as far rightward as it needs to go to, assuming that everything after the first element is already sorted.

A

So that's the core of a insertion slot essentially and the other function. The new one, I wrote, is very, very similar. It just takes the last element and assumes everything before it is sorted and pushes it to the left very, very similar.

A

Let's look at this insert tail function that we just saw. Let's just take a look at the internals. This is just an extract, but essentially this is what's important. You have the setup for the loop where we take this this last element. We read it into some temporary memory on the stack. We do. A comparison, if we don't need to do anything, then we relieve- and we say: okay, it's already sorted, it's good and then afterwards this happens, and now maybe I should talk a bit about Panic safety. That's something I mentioned earlier.

A

That in C doesn't need to like care about this, and we have the idea that this user provider function could Panic at any time, and inside of this like loop, we're seeing here, it will go and duplicate elements inside of the slice and instead of doing a swap each time with a temporary, it creates one temporary and then duplicates elements, and only at the very end it copies the element into the place. It needs to go. That saves on some moves essentially, and especially if the type is Big.

A

These moves can be expensive and how this works is by having this insertion hole type and it has a job implementation which takes source and copies it into test, so the source will get copied into the destination, and we update the pointers of insertion Hall in a way that, at any point, where is less, this user provided function, which could Panic is called if it panics.

A

We correctly patch up the thing we just duplicated I'll, look at it in a second to see just it going in action to get an idea how this works and then at the very end, if it exited normally no Panic, it uses this to patch up the hole and if it exits with a panic, it also uses mechanism to make sure there's no duplicate elements, because duplicate elements for a string, for example, would be disastrous.

A

It would have the same pointer, double free it and that there's some other issues too right, like you shouldn't duplicate elements once you give them back to the user.

A

So, let's take a look at what this looks like we have a slice with elements: 2, 5, 6 and 3., and then we just we will run through in the middle. You see the execution just the line, that's happening on the left. You can see kind of like a like a simulation of memory and then we're creating the pointers to it and I'll. Just let it through now we're in the loop. We we did the compare first comparison already now we're inside the loop. We set up the pointers.

A

Then we do another comparison. We check. Okay, it's three less than six. Yes, so we need to keep going and then we copied it. This is what I said. Now we have two five six six in this Heap allocated user provided slice and it should never be given out like this to the user. So we keep going. We do another comparison and then okay, we check we do and then we update the pointers.

A

We again duplicate the elements, this time we're taking the five duplicated and then we keep going another time we go to the loop again. We do another comparison, but this time oh yeah, okay, we found the right spot, so we leave the loop and then we call the destructor like the drop implementation of whole, and this does this copy of source to desk that we talked about and we can see now it's two three five, six, it's sorted looks good okay.

A

But if you change the scenario very slightly, what if you say, we have two five, six, seven, just the last element change. We have two five, six three and now we have two five, six. Seven we see. Okay, we'd, create this temporary On The Stack.

A

Then we call the comparison function, we hand in uh as a reference our the stack value. Oh it's already sorted, so we leave the function. We leave it. The whole was never created, so source does never gets copied back into list. We attempt just disappears. It's a manually drop, so nothing happens, it doesn't get dropped and in essence, what the user now has is a slice. That's sorted, it's what they provided, but it's also the park right. If you look at what the user observes as values, we created this temporary stack value.

A

We use it and pass it into this comparison function, that user provided and then we never copy it back. In other cases where, like the execution continues, as we saw earlier, it gets copied back and then the user sees a unique version of this iPad here, essentially the type the value diverges and like what versions are seen of it.

A

This would be the fix. We just move this creation of this temporary stack value after this check. At the very beginning, we use the address of the Heap based slice element.

A

So if we take, if we return here, then we're sure that um it's will have never seen this other version that we haven't created yet and if we continue, we create this version. We only use this new version for comparisons, and this new version then gets copied back at the very end and I want you to ask yourself: do you consider this a bug?

A

Because if you look at the documentation and the contracts of what the sort implementation says, I'm not sure it promises anywhere that like, if you self-modify yourself inside the comparison function, you will see all effects. This has on your own types. I. Would it's, as father can tell it's sound? The fix is easy right like we should. Probably.

A

This is a good idea to do this, because it produces surprising results but I'm, not even sure what the name for this thing is I called it uniqueness preservation that probably has a name somewhere, just don't know it, but I found this quite subtle and if you had just told me at the beginning, if I looked at this like 20 lines of code with like panics, where, like Panic safety and unsafe everywhere, when I wrote, this I had all different kinds of things in mind. I was very focused on not making soundness mistakes.

A

This was not something I had in mind. I only discovered this because I wrote this like thought statistic. As far as I can tell the standard. Library didn't have tests for this, so probably it would be caught at some point if assuming this would have landed in the standard library. At some point, some user would have noticed, but it's quite a subtle issue, where it's not clear what kind of behavior is expected.

A

I would say it's expected that you can observe all changes that happen to your own types, but I, don't know it's I found it quite subtle and yeah. So the mistake I made is I made a very small change when I ported insert head and made a copy in the tail. That's very similar, but just goes the other way. I made a very small change and had a very, very surprising effect on self-modifying types.

A

Something I didn't anticipate something I didn't think about at all at the time yeah, and with that we come to our conclusion: It's Perfectly, Normal and okay, to make mistakes like from beginners to experts. Everyone does mistakes and.

A

This is something where like for me: it's very important how you deal with these make mistakes, how what you do against them, but it should be a reality that we all do mistakes right. We work on complex problems and we are humans. We make mistakes and that's okay, um if you can try to attempt to to like find ways that prove that what your assumption is of how the world Works try to prove that it's wrong. There's an idea that comes from science, essentially like come up with ideas and ways to test that.

A

What you believe is true is false. Now, if you run out of ways to prove that you're wrong, maybe you're right and don't be afraid to go back and revalidate assumptions, because things change, sometimes even if you're, the only person working on a project and as we saw earlier with this, like with this, like randomness I, didn't realize the correlation of my change. So something changed. My assumptions that had beg at the beginning, drug but I didn't realize something had changed, but I saw indications that what I saw didn't make sense.

A

So I went back and revalidated my assumption and that I put random numbers into my sword and I get have random numbers, but they're not really random. They're all done the numbers all the time again same numbers. So even if you don't have a strong indication that something is wrong, it's not a bad idea to go back from time to time and test that. What you believe is true is still true right about your system, about what you're, building or whatever and here's some links at the very beginning.

A

This is where I did all this like research in it's still work in progress. uh The second link is my repository for my presentations can find all the sources there and the last one is a pull request for this. Like improved, stable sort, it's still work in progress. So there's like one outstanding issue, I'm working on it. I just didn't- have a lot of time recently, but yeah that's about it. I want to say thank you for attending my talk.