Baby Steps

A blog about programming, and tiny ways to improve it.

The 'Tootsie Pop' Model for Unsafe Code

In my previous post, I spent some time talking about the idea of unsafe abstractions. At the end of the post, I mentioned that Rust does not really have any kind of official guidelines for what kind of code is legal in an unsafe block and what is not.What this means in practice is that people wind up writing what seems reasonable and checking it against what the compiler does today. This is of course a risky proposition since it means that if we start doing more optimization in the compiler, we may well wind up breaking unsafe code (the code would still compile; it would just not execute like it used to).

Now, of course, merely having published guidelines doesn’t entirely change that dynamic. It does allow us to assign blame to the unsafe code that took actions it wasn’t supposed to take. But at the end of the day we’re still causing crashes, so that’s bad.

This is partly why I have advocated that I want us to try and arrive at guidelines which are human friendly. Even if we have published guidelines, I don’t expect most people to read them in practice. And fewer still will read past the introduction. So we had better be sure that reasonable code works by default.

Interestingly, there is something of a tension here: the more unsafe code we allow, the less the compiler can optimize. This is because it would have to be conservative about possible aliasing and (for example) avoid reordering statements. We’ll see some examples of this as we go.

Still, to some extent, I think it’s possible for us to have our cake and eat it too. In this blog post, I outline a proposal to leverage unsafe abstaction boundaries to inform the compiler where it can be aggressive and where it must be conservative. The heart of the proposal is the intution that:

  • when you enter the unsafe boundary, you can rely that the Rust type system invariants hold;
  • when you exit the unsafe boundary, you must ensure that the Rust type system invariants are restored;
  • in the interim, you can break a lot of rules (though not all the rules).

I call this the Tootsie Pop model: the idea is that an unsafe abstraction is kind of like a Tootsie Pop. There is a gooey candy interior, where the rules are squishy and the compiler must be conservative when optimizing. This is separated from the outside world by a hard candy exterior, which is the interface, and where the rules get stricter. Outside of the pop itself lies the safe code, where the compiler ensures that all rules are met, and where we can optimize aggressively.

One can also compare the approach to what would happen when writing a C plugin for a Ruby interpreter. In that case, your plugin can assume that the inputs are all valid Ruby objects, and it must produce valid Ruby objects as its output, but internally it can cut corners and use C pointers and other such things.

In this post, I will elaborate a bit more on the model, and in particular cover some example problem cases and talk about the grey areas that still need to be hammered out.

Unsafe Abstractions

The unsafe keyword is a crucial part of Rust’s design. For those not familiar with it, the unsafe keyword is basically a way to bypass Rust’s type checker; it essentially allows you to write something more like C code, but using Rust syntax.

The existence of the unsafe keyword sometimes comes as a surprise at first. After all, isn’t the point of Rust that Rust programs should not crash? Why would we make it so easy then to bypass Rust’s type system? It can seem like a kind of flaw in the design.

In my view, though, unsafe is anything but a flaw: in fact, it’s a critical piece of how Rust works. The unsafe keyword basically serves as a kind of escape valve – it means that we can keep the type system relatively simple, while still letting you pull whatever dirty tricks you want to pull in your code. The only thing we ask is that you package up those dirty tricks with some kind of abstraction boundary.

This post introduces the unsafe keyword and the idea of unsafety boundaries. It is in fact a lead-in for another post I hope to publish soon that discusses a potential design of the so-called Rust memory model, which is basically a set of rules that help to clarify just what is and is not legal in unsafe code.

Non-lexical Lifetimes Based on Liveness

In my previous post I outlined several cases that we would like to improve with Rust’s current borrow checker. This post discusses one possible scheme for solving those. The heart of the post is two key ideas:

  1. Define a lifetime as a set of points in the control-flow graph, where a point here refers to some particular statement in the control-flow graph (i.e., not a basic block, but some statement within a basic block).
  2. Use liveness as the basis for deciding where a variable’s type must be valid.

The rest of this post expounds on these two ideas and shows how they affect the various examples from the previous post.

Non-lexical Lifetimes: Introduction

Over the last few weeks, I’ve been devoting my free time to fleshing out the theory behind non-lexical lifetimes (NLL). I think I’ve arrived at a pretty good point and I plan to write various posts talking about it. Before getting into the details, though, I wanted to start out with a post that lays out roughly how today’s lexical lifetimes work and gives several examples of problem cases that we would like to solve.

Nice Errors in LALRPOP

For the last couple of weeks, my mornings have been occupied with a pretty serious revamping of LALRPOP’s error message output. I will probably wind up doing a series of blog posts about the internal details of how it works, but I wanted to write a little post to advertise this work.

Typically when you use an LR(1) parser generator, error messages tend to be written in terms of the LR(1) state generation algorithm. They use phrases like shift/reduce conflict and talk about LR(1) items. Ultimately, you have to do some clever thinking to relate the error to your grammar, and then a bit more clever thinking to figure out how you should adjust your grammar to make the problem go away. While working on adapting the Rust grammar to LALRPOP, I found I was wasting a lot of time trying to decrypt the error messages, and I wanted to do something about it. This work is the result.

An aside: It’s definitely worth citing Menhir as an inspiration, which is an awesome parser generator for OCaml. Menhir offers a lot of the same features that LALRPOP does, and in particular generates errors very similar to those I am talking about here.

What I’ve tried to do now in LALRPOP is to do that clever thinking for you, and instead present the error message in terms of your grammar. Perhaps even more importantly, I’ve also tried to identify common beginner problems and suggest solutions. Naturally this is a work-in-progress, but I’m already pretty excited with the current status, so I wanted to write up some examples of it in action.

Parallel Iterators Part 2: Producers

This post is the second post in my series on Rayon’s parallel iterators. The goal of this series is to explain how parallel iterators are implemented internally, so I’m going to be going over a lot of details and giving a lot of little code examples in Rust. If all you want to do is use parallel iterators, you don’t really have to understand any of this stuff.

I’ve had a lot of fun designing this system, and I learned a few lessons about how best to use Rust (some of which I cover in the conclusions). I hope you enjoy reading about it!

This post is part 2 of a series. In the initial post I covered sequential iterators, using this dot-product as my running example:

1
2
3
4
vec1.iter()
    .zip(vec2.iter())
    .map(|(i, j)| i * j)
    .sum()

In this post, we are going to take a first stab at extending sequential iterators to parallel computation, using something I call parallel producers. At the end of the post, we’ll have a system that can execute that same dot-product computation, but in parallel:

1
2
3
4
vec1.par_iter()
    .zip(vec2.par_iter())
    .map(|(i, j)| i * j)
    .sum()

Parallel producers are very cool, but they are not the end of the story! In the next post, we’ll cover parallel consumers, which build on parallel producers and add support for combinators which produce a variable number of items, like filter or flat_map.

Parallel Iterators Part 1: Foundations

Since giving a talk about Rayon at the Bay Area Rust meetup, I’ve been working off and on on the support for parallel iterators. The basic idea of a parallel iterator is that I should be able to take an existing iterator chain, which operates sequentially, and easily convert it to work in parallel. As a simple example, consider this bit of code that computes the dot-product of two vectors:

1
2
3
4
vec1.iter()
    .zip(vec2.iter())
    .map(|(i, j)| i * j)
    .sum()

Using parallel iterators, all I have to do to make this run in parallel is change the iter calls into par_iter:

1
2
3
4
vec1.par_iter()
    .zip(vec2.par_iter())
    .map(|(i, j)| i * j)
    .sum()

This new iterator chain is now using Rayon’s parallel iterators instead of the standard Rust ones. Of course, implementing this simple idea turns out to be rather complicated in practice. I’ve had to iterate on the design many times as I tried to add new combinators. I wanted to document the design, but it’s too much for just one blog post. Therefore, I’m writing up a little series of blog posts that cover the design in pieces:

  • This post: sequential iterators. I realized while writing the other two posts that it would make sense to first describe sequential iterators in detail, so that I could better highlight where parallel iterators differ. This post therefore covers the iterator chain above and shows how it is implemented.
  • Next post: parallel producers.
  • Final post: parallel consumers.

Rayon: Data Parallelism in Rust

Over the last week or so, I’ve been working on an update to Rayon, my experimental library for data parallelism in Rust. I’m pretty happy with the way it’s been going, so I wanted to write a blog post to explain what I’ve got so far.

Rayon’s goal is to make it easy to add parallelism to your sequential code – so basically to take existing for loops or iterators and make them run in parallel. For example, if you have an existing iterator chain like this:

1
2
3
let total_price = stores.iter()
                        .map(|store| store.compute_price(&list))
                        .sum();

then you could convert that to run in parallel just by changing from the standard sequential iterator to Rayon’s parallel iterator:

1
2
3
let total_price = stores.par_iter()
                        .map(|store| store.compute_price(&list))
                        .sum();

Of course, part of making parallelism easy is making it safe. Rayon guarantees you that using Rayon APIs will not introduce data races.

This blog post explains how Rayon works. It starts by describing the core Rayon primitive (join) and explains how that is implemented. I look in particular at how many of Rust’s features come together to let us implement join with very low runtime overhead and with strong safety guarantees. I then explain briefly how the parallel iterator abstraction is built on top of join.

I do want to emphasize, though, that Rayon is very much work in progress. I expect the design of the parallel iterator code in particular to see a lot of, well, iteration (no pun intended), since the current setup is not as flexible as I would like. There are also various corner cases that are not correctly handled, notably around panic propagation and cleanup. Still, Rayon is definitely usable today for certain tasks. I’m pretty excited about it, and I hope you will be too!

Virtual Structs Part 4: Extended Enums and Thin Traits

So, aturon wrote this interesting post on an alternative virtual structs approach, and, more-or-less since he wrote it, I’ve been wanting to write up my thoughts. I finally got them down.

Before I go any further, a note on terminology. I will refer to Aaron’s proposal as the Thin Traits proposal, and my own previous proposal as the Extended Enums proposal. Very good.

(OK, I lied, one more note: starting with this post, I’ve decided to disable comments on this blog. There are just too many forums to keep up with! So if you want to discuss this post, I’d recommend doing so on this Rust internals thread.)

Conclusion

Let me lead with my conclusion: while I still want the Extended Enums proposal, I lean towards implementing the Thin Traits proposal now, and returning to something like Extended Enums afterwards (or at some later time). My reasoning is that the Thin Traits proposal can be seen as a design pattern lying latent in the Extended Enums proposal. Basically, once we implement specialization, which I want for a wide variety of reasons, we almost get Thin Traits for free. And the Thin Traits pattern is useful enough that it’s worth taking that extra step.

Now, since the Thin Traits and Extended Enums proposal appear to be alternatives, you may wonder why I would think there is value in potentially implementing both. The way I see it, they target different things. Thin Traits gives you a way to very precisely fashion something that acts like a C++ or Java class. This means you get thin pointers, inherited fields and behavior, and you even get open extensibility (but, note, you thus do not get downcasting).

Extended Enums, in contrast, is targeting the fixed domain use case, where you have a defined set of possibilities. This is what we use enums for today, but (for the reasons I outlined before) there are various places that we could improve, and that was what the extended enums proposal was all about. One advantage of targeting the fixed domain use case is that you get additional power, such as the ability to do match statements, or to use inheritance when implementing any trait at all (more details on this last point below).

To put it another way: with Thin Traits, you write virtual methods whereas with Extensible Enums, you write match statements – and I think match statements are far more common in Rust today.

Still, Thin Traits will be a very good fit for various use cases. They are a good fit for Servo, for example, where they can be put to use modeling the DOM. The extensibility here is probably a plus, if not a hard requirement, because it means Servo can spread the DOM across multiple crates. Another place that they might (maybe?) be useful is if we want to have a stable interface to the AST someday (though for that I think I would favor something like RFC 757).

But I think there a bunch of use cases for extensible enums that thin traits don’t cover at all. For example, I don’t see us using thin traits in the compiler very much, nor do I see much of a role for them in LALRPOP, etc. In all these cases, the open-ended extensibility of Thin Traits is not needed and being able to exhaustively match is key. Refinement types would also be very welcome.

Which brings me to my final thought. The Extended Enums proposal, while useful, was not perfect. It had some rough spots we were not happy with (which I’ll discuss later on). Deferring the proposal gives us time to find new solutions to those aspects. Often I find that when I revisit a troublesome feature after letting it sit for some time, I find that either (1) the problem I thought there was no longer bothers me or (2) the feature isn’t that important anyway or (3) there is now a solution that was either previously not possible or which just never occurred to me.

OK, so, with that conclusion out of the way, the post continues by examining some of the rough spots in the Extended Enums proposal, and then looking at how we can address those by taking an approach like the one described in Thin Traits.