Rust Programming Language Rust KW Meetup, 27 Mar 2018

Previous Meeting

⏯

youtube image

►

From YouTube: Writing a Crate (Kahan Sums) by Mark Sherry - Rust KW Meetup

Description

This video was recorded during the first Rust KW Meetup in Kitchener-Waterloo, ON, Canada on March 27, 2018.

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

This talk is about the Kahan summation. Mark describes how he implemented a generic Kahan summer in Rust, and how he extended all iterators over floats to support a new kahan_sum method.

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

A

So, what's this talk a few months ago, I was writing a rust clone of the UNIX utility Mini stat that have does the simple statistical analysis on benchmark data. Here's two benchmarks was there's also to seek a significant other means, medians, etc and I decided, though a little report and a common summation, so I were a little great to do that and posted in run great cycle.

A

So this talk will cover what conservation is why consummation is useful, then walk through building a bare-bones implementation of a crate that does it then adding progressively more polish until we end up with something roughly to what I posted online so to properly understand consummation and why it's necessary beneath understand how computers store floating-point numbers. The first thing you need to know about point numbers is that they are terrible, it all sorts of untruth behaviors, especially against the realm of infinite ease and nothing of our values, but even with other pieces, it's still bad.

A

This is because they have limitations.

A

Unfortunately, we are not doing computations on that strategy. Machines capable of arbitrary precision, they actually have to store stuff in memory and the operations have to be reasonably efficient, using NAND gates and all that, so there are trade-offs so.

A

For anyone who is not too familiar already with how floating point numbers work, they looked a lot like scientific notation.

A

We had the point whenever stores fees of Kimber mentis, the three point: zero, seven, seven, nine, seven, seven six and his first exponent. Of course, this being computers, first of all, binary and of course we only have so much Precision's. We have loosen digits there.

A

How much precision do we have then depends on the type of point value and what standard you are using. Rust uses I Triple, E 754, which is the most common standard these days. Technically it also supports decimal floating point numbers. I, don't know anyway, that actually uses that rust has two floating-point types at 32 and x64. There's a chance that one day you will also get f-16 and at 48.

A

There is a lot of complexity about floating-point numbers I'm skipping over here, like everything to do with not number the type of there's positive, negative infinity values. The type of minus zero is a thing in here about.

A

If you want to learn more, there is a paper what every computer scientist should know about. Floating-Point numbers, that's probably a good place to start.

A

So, let's talk about sounds of problems that floating point numbers have, because these store values in essentially binary. This means that whole load fractions, even if they have finite representations in decimal, no longer have fire referent representations when represented in base two, for instance, one-tenth is zero point: zero, zero, zero one, one, zero, zero one, one 1 1, 0, 0, 1, 1, etc. So some point you have just draw a line cut it off, which makes me there's a bit of precision, and you end up with weird things like.

A

If you add 1/10 10 times, you don't get one, but you still have problems even who need eight and just deal with integers, because an f32 only has 24 bits of mantissa once we start storing to the 24. If we add 1 to it well, we had to drop our ones digit, so the one just gets lost. You can add 1 to it as many times as we you want, and nothing will change.

A

If we go to 2 to the 25, all sudden we lose the two stitches as well than the fortune horse, digit and so on.

A

So this has consequences when you're, adding together numbers of different orders of magnitude, it had a large number, too small to be necessarily loose of the precision of the small number.

A

First, if you keep having numbers together, the error grows proportionate, with the worst case, proportionate to the number of terms that you're adding out for since.

A

16,777,216 million seven hundred seventy seven thousand twenty sixteen, but if you instead compute 1, plus 1 plus 1, plus 1 plus 16 minutes 2,216, you get sixteen million seven hundred seven 220, so we just lost associativity yeah. So for point, numbers are terrible, but conservation is a way to manage these errors and the cost of making four times as many floating point operations.

A

There are other techniques, the pair pairwise summation bounds, the error to log and but only takes it twice as many operations.

A

So this is how conservation works.

A

In addition to tracking our sum, we also store in a separate variable, the precision that we've lost and then, when we try to add the next term, we try to add in our error term to correct for it how to compute the error term. Well, we take our new some. We subtract out the old some or whichever was the mark of the true, but it's usually gonna be your son.

A

Then you subtract out the term that we just tried to act and the result I was a rainy should be zero, but because productivity routes but they'll contain our error.

A

Here is an example to make things simpler, it's all working a decimal and I assume that we have four digit precision, so we have one hundred thirty five thousand two hundred we were added by hundred.

A

We don't have any errors are just starting out, so we don't have to modify her Paul better. Together we get 126,000 173, but because we try scored four digits of precision, we run out of 23 6200.

A

Now we subtract away our original sum and get one thousand subtract 973 from that, and we have our error term of 27.

A

Hey we decide to advise and be free again. We subtract our error term, get minus 46.

A

We add that, to our running total, get up, interchange, seven thousand one hundred forty six- that rounds it down to three thousand seven thousand four hundred we subtract our four old son get 900 subtract the term that we, the new term, that we added after the multiplication. So it's 946 and our hair is now minus 46.

A

And our expected value that your tad would be under 727 thousands of 146 there on the slide, which is exactly what theatre we expect from our error term. So we were perfectly tracking the error here under the height, if we didn't do consummation well, the first step is the same. We end up with them hundred twenty-six thousand one hundred or two hundred. Then we added 973 again and we round up again and every time we add minus v3 we're gonna write on up again is adding another twenty seven error until well.

A

How many time having us?

A

Okay! So hopefully now you can ready you under to have an understanding of how consummation works and might be able to president rest, because we're going home has been arrests so first from the defying a struct to store our running total and our error term, and for now we're just going to hard-coded to be F.

A

Thirty twos some day didn't cover it in his talk, but the drive statement up there basically tells rust, create default implementations for debug, which means we have a debug representation of two string, which is useful for debugging and clone, which means we can make copies of this I deliberately did not make some or error public fields, because there's no useful way for anyone to want to find them. If you change area, you've just made things wrong to change some. It should be also setting air to zero.

A

So there's no point, then we create an info for our new struts. This basically gives our struct bunch of methods, so we give it a default constructor new that just initializes the sum to zero. We have new value that initializes it with the default value.

A

Notably rust does not have option overloading. So we can't have local functions with the same name of different signatures. Then we just write to in her methods. Rusts in liner is very aggressive, so there is absolutely no cost it'll. These will just get them lined out. So it's the same as read-only access to the fields.

A

And we'll also had pad method that takes our struct as a mutable reference and f32 is right hand, side and both times the implementation of comments out there we subtract off the error term. We added two new some we subtract out the old some subtract office, the new term and update the variables.

A

We can make it slightly nicer by checking whether right hand, side or self dot. Son has a large registered value and swap them if it's the wrong way around. But I want to keep this simple, and here you see it's working.

A

It tracks the lost turn we had more twice and we end up with 12 million blah blah blah and 18.

A

So we have our structure, we can analyze it and access its values can hide items. So we're done right. Well, it only works to death. 32 anthony explicit function calls to averages hang a date. This might be stood here from java world, but we can do better and there's a really nice method on it that will sum up numbers if it's an iterator of her integers close it simmer so it'd be nice if we could have a time. Some method that does the same thing so doesn't been thinking.

A

These been nice regimes post guilty, probably being Hartford f/32 until much later. So let's talk about custom operators, as some jameth mentioned something added the tragical that are fermented using traits and rust. So if you want the custom, add or just trying to just implement the add trait for it, and most of these traits also come in a assignment later, I did not design in favor.

A

One crucial difference between the two of them is that the assigning version takes a mutable reference. While the non assigning version takes the value by it takes ownership, which means that if you have ownership of it, you can get a mutable reference from that. But if you have new full reference, you can't steal ownership from the owner. It has to be given to you. This means that if you have add something you can implement add in terms of a design, but you can't go the other way around so.

A

We'll just take the clue from our add method or air and drop it into an aside here and nothing has changed. It changed to set for the top line there. We do have to say you standard ops, I, designed to bring the train into scope.

A

Then we can just bringing a data scope and use it. Implement is an aside to implemented.

A

Okay, so now, let's try to repentance iterator son, but before we covered how to do that and I took over a more general topic. Banning new methods to a trait rust has a thing called the orphan rule, where, if you want to add, implement a trait for a struct reasoning to own the struct or you need to own the trait that is, it has to be defined in the same module.

A

The reason for this is so that you can't have two third-party libraries implement ad for something in incompatible ways, but doesn't mean that if you create new traits, you can implement it for a whole bunch of existing code or already so we don't own iterator and.

A

So how do we add new stuff to it? Well, the answer is we create our immune from trade was a message we watch and then import first things so I'm just say: I sign a frog message to everything and probable, just snail frog and also implement this for every wristband.

A

So we create a trump trace put in our method signature in there, then we generically implement our trait for every single type in the language.

A

You have to pull frog behavior into the scope in your module for this to actually do anything which means I can create a stupid trait like this. In my code and while I Drive in my library and have you put and all of a sudden, the residents get weird stupid traits you have too often, but you can actually do really amazing things with this and you're just working.

A

So let's say we wanted instead our frog method to say the name of the value as well. Okay, so just print line have a print itself, and that doesn't work, because not all types of my display, which is what's necessary to I, should actually incorrect just to strength there. So how do we fix it? We had a tight bound to our implementation.

A

Instead of implementing for all T, we implemented only for T's routine, also increments, the display trait and now it works the first fruit and sit works for Strings. It doesn't work for options because options started a display.

A

So if we wanted to add some method to iterators, we create a new trait and then we implemented for all integers, whereas the iterator type value is f32.

A

And we just a bit of functional, create a neutron and some full number into having on.

A

And this works we just added a new message to it or reduce. So if you have some iterator over of 32 and now the quickly computer comments up, if you'd said want to manage, you can try to throw on your own, you can just add a new term for st. inspection, so still already works without 32. It only works on f30 iterators above 32, but not reference instead of 32.

A

So if you're doing this on a vector, for instance, you need to consume the vector, you can't just borrow it and it also doesn't work on the box at 32 or cf-30 tour or any of those smart pointers.

A

So let's fix that first thing: let's do fix it so that works on all flow types, both at 32 handouts to 4. So we could just create additional impulsive stuff, but.

A

Instead, I'm going to pull in the num traits crate, this is a third party crate as part of the num crate family, that imparts a whole bunch of numerical types. The float train is implemented for a 32 and F 64 and also implies a whole bunch of other nice traits. Like add subtract, multiply copy part for equality, etc. Fat flow types implement but means we don't have to specifically spell them out, just as we don't use them.

A

So our struct definition now has a type parameter, and that type has to be the float.

A

Our initializer has to be done a bit fancier and, in addition to so that various traits, the floats trait, also has methods on for the constants zero and what we need to use this, because we can't just use a float before anymore, because we don't actually know that the fam permitting float is NF 3464, just that it behaves like one so something out there, homebrew at 128 and to primitive blood port. This code will still work force.

A

For the add sign, we just died the type parameters. Everything else is exactly the same.

A

When it comes to our summation trait things, a little trickier, we have to have to type balance for the implementation. One say: okay, we have to that. Our type has to be an iterator and then another to say that the type of iterating over it has to be float.

A

But that's still, we still need an only have 32 or 64 whatever time we can't work on preferences yet, and we could just create multiple implementations of that just copy and paste the code.

A

So variety is iterator of to your iterator, for every city etc, or we can use one of the bank's your types in the system, which is the Borel trait.

A

If tea implements four of you that, if I have a tea I'm, giving you reference and just have abstracts over all the different ways that you can get a reference to your type, so there are simpler mutations so that you can get to stir reference strain, have reference from a path, buff, etc, but it also gives us all these. So if you have the reference to type obvious, you can give you a reference. They can remove the meat from a reference.

A

It can tell you you do reference to it, don't get the references from osmosis all types of smart pointers from a copy on right, so this is perfect for our needs.

A

Okay, so we just update our type about there. So now we want to commit this, for an iterator over type of items of type, V or V is implements or O over type, T or T as a float. So it's a tricky.

A

The other change that we had to make is called item table or o to get the reference and then immediately turn around and dereference such.

A

And finally, a few nice things to implement, if you have an honorary constructor, it is really nice to just implement default for it default. It's just a trait that says.

A

Call the horn and I'll give you a basic default value.

A

And then, if you have a memory, constructor like new they're, just implemented in terms of default, and yet that's my talk. I didn't cover writing tests. I didn't cover great documentation. Those are both very important, but also both really big topics and I didn't cover how to actually publish on create I/o, because it would basically just be me cribbing the documentation, because I've already done it twice before. I chose the next time I'm going to do it I'm going to be reading the exact same documentation so.

A