Monday, June 19, 2017

Search-based compiler code generation

I've been thinking about something for a while now, and promised a year ago in my Optimal Optimization post that I would write it up.

One of the difficulties in writing a programming language compiler is that there is a tension between making the pieces of the compiler modular and maintainable, versus making the compiler produce good code. The biggest cause of this tension is over "phase ordering", and I'll defer to one of the many academic papers on the subject to explain it:
Current optimizing compilers typically contain several different optimization phases. Each phase attempts to apply a series of transformations, each of which consists of a sequence of changes that preserves the semantic behavior of the program while typically improving its efficiency. Many of these optimization phases use and share resources (such as machine registers), and also need specific conditions in the code to be applicable. As a result, optimization phases interact with each other by enabling and disabling opportunities for other phases to be applied. (Prasad Kulkarni et al, "Practical Exhaustive Optimization Phase Order Exploration and Evaluation")
Researchers have explored a variety of ways to determine, for a given piece of source code, which passes should be applied and in what order. The above paper, and several others by the same authors, describe efficient ways to search over all possible phase orders. Many people have applied genetic algorithms or machine learning techniques to this problem as well; for an interesting example plus good citations to earlier work, see Sameer Kulkarni & John Cavazos, "Mitigating the Compiler Optimization Phase-Ordering Problem using Machine Learning".

But you might ask, why do we divide the compiler's work into phases in the first place? It's in support of our old software engineering friend: abstraction. It's much easier to reason about a particular transformation if we don't have to think about all of the others at the same time.

Still, could we avoid the phase order problem entirely by structuring the compiler in some other way?

Strongly normalizing intermediate representations

Alan C. Lawrence, in his 2007 PhD thesis ("Optimizing compilation with the Value State Dependence Graph"), claimed a maxim of compiler folklore is that "The most optimizing compiler is the most normalizing compiler," explaining it this way:
Normalization refers to where many different source programs result in the same machine code after compilation—that is, where the same machine code is produced regardless of which form was written by the programmer. … This allows the programmer to select from such representations according to which is the easiest to comprehend or to fit his ideas or program into, and leave the compiler to select the output according to efficiency concerns.
Traditionally, compilers have represented the structure of a function using a Control Flow Graph (CFG) composed of "basic blocks" containing sequential instructions, plus control-flow edges between basic blocks that describe the different paths the program may follow.

The CFG representation locks in details of evaluation order that aren't inherent in the original program, so many optimizations that are designed for CFGs just re-order instructions in various ways. Different orderings may have different performance or code size implications, so the challenge is to identify the best ordering for your particular goals.

By contrast, the Value State Dependence Graph (VSDG) does not force instructions into a sequential order, but instead keeps track of data dependencies and serialization requirements using directed edges in a graph. As a result, a VSDG describes all equivalent orderings of the same code in a single, normalized, form. (Other program representations have done that for parts of the code that are free of side effects, but VSDG extends it to control flow and memory access.)

Lawrence later noted:
Many optimizations, which would be separate passes in a CFG compiler, seem trivial in a VSDG framework, due to the VSDG’s normalizing properties. That is, they automatically (or implicitly) occur merely by representing a program as a VSDG.
However, this does not entirely avoid the problem: rather, it merely delays the decision until the IR is transformed into some form which does make the distinction, namely until the sequentialization stage. Thus, sequentialization wraps up many such optimizations together, and concentrates their difficulty into one place. However, this approach does seem helpful in addressing phase-order problems…

Although a single VSDG can represent a large number of seemingly-different CFGs, it is possible to reduce the number of equivalent CFGs just by adding extra serializing edges. The edges initially present in the graph represent true dependencies: A must be evaluated before B, either because B needs the result of A, or because A and B have side effects that must not be re-ordered. Artificially adding more dependencies imposes a specific evaluation order for the remaining computations.

The VSDG sequentialization stage can be defined as introducing serializing edges until exactly one CFG remains. Producing a sequentialization optimized for speed is NP-complete, but because the only choices are over where to add serializing edges, the VSDG is a convenient way to express whatever constraints, heuristics, or cost functions you want.

Although Lawrence's thesis discusses sequentialization extensively, if you want to know more on that subject I recommend James Stanier's 2011 PhD thesis ("Removing and Restoring Control Flow with the Value State Dependence Graph") as well as Bahmann et al's 2015 paper, "Perfect Reconstructability of Control Flow from Demand Dependence Graphs".

Combined Register Allocation and Code Motion

Neil Johnson, in chapter 6 of his 2004 PhD thesis ("Code Size Optimization for Embedded Processors"), proposed an elegant algorithm for combining a particular pair of traditionally-separate optimization passes using the VSDG, which makes a nice example of both the phase ordering problem and the ways VSDG can help solve it.

Register allocation is the process of assigning temporary values to specific hardware registers. Sometimes there are too many temporary values that the program needs to hang on to at the same time, and they can't all fit in registers at once. When that happens, there are traditionally two choices: either "spill" some of the registers to memory so they can be used for something else until the older values are needed again; or forget some temporary values and recompute them later. Both options result in a larger and slower program.

Code motion is a loop optimization that moves an expression out of the body of a loop if that expression will evaluate to the same value on every iteration of the loop. The only way this transformation could make the expression be evaluated more times than in the original program is if the loop never executes, so this is almost always an improvement.

However, code motion increases pressure on the register allocator, because there are more temporary values that need to be available throughout the execution of the loop. Under some circumstances, the program will actually be faster if it recomputes the loop-invariant expression every time it's needed, because that may free up registers and avoid expensive spills to memory.

Johnson uses the VSDG to implement a greedy algorithm that only performs code motion when it won't interfere with register allocation. His isn't the first algorithm to combine these two passes, but using VSDG makes his approach particularly easy to understand. I recommend reading his paper if you'd like to know more.

Recasting optimization as a search problem

Although several of the VSDG papers mention combinatorial search as a potential solution to various challenges, I have not found any signs that anyone has actually tried search with the VSDG. I'd be interested to see Johnson's algorithm, for example, revisited with an exhaustive search in place of the greedy policy, and an analysis of the compile-time cost versus run-time and code-size benefit of making optimal choices.

There is history of using search in various ways for code optimization:
  • I already cited "Practical Exhaustive Optimization Phase Order Exploration and Evaluation" as an example of using search to identify an optimal phase order for a traditional compiler on a given program.
  • Samuel Sanseri's 2001 Master's thesis ("Toward An Optimizing JIT Compiler For IA-64") demonstrated that for VLIW architectures, search-based instruction selection can produce more efficient code than GCC's hand-tuned heuristics. (It also promised to demonstrate that it could do so with fast enough compile time to be usable in a JIT setting, though I can't find evidence in the paper that compile time was actually measured. Still, I think the claim is plausible.)
  • João Dias' 2008 PhD thesis ("Automatically Generating the Back End of a Compiler Using Declarative Machine Descriptions") demonstrated using search to automatically generate the instruction selector in the backend of a compiler. Although compiler frontend techniques haven't changed dramatically since lex and yacc were written in the 1970s, instruction selection is still done today using extensive hand-written heuristics. Dias' approach replaces those heuristics with pattern-matching rules generated before compiling the compiler itself, so the slow search time is amortized across all the programs compiled for the same architecture.
These projects demonstrate a range of applications of combinatorial search covering both offline analysis used to generate better compilers, and online analysis to dynamically make better optimization decisions during compilation.

However, I have yet to find anyone who has tried using search to decide whether to apply a optimization/transformation at each individual location where it's valid. Since applying an optimization in a particular spot might prevent applying other optimizations in that spot, the current greedy methods may produce suboptimal results no matter which order they run optimization phases in.

Here's a rough outline of an approach that I think would be interesting to try:
  1. Construct a VSDG, and aggressively normalize it using equivalents of common subexpression elimination and partial redundancy elimination. These are not guaranteed to be a good idea, but they can be selectively undone later using node splitting if necessary. Also apply optimizations that are guaranteed to be improvements, such as constant folding, algebraic identities, and dead node elimination. Furthermore, some optimizations, like constant propagation and copy propagation, are implicit in VSDG construction (e.g. if there's no "copy" node available).
  2. Begin a search over the space of VSDGs that may be formed from the initial graph using any sequence of these operations:
    • first, split some subset of nodes whose results are demanded multiple times;
    • then, fully cover the graph with target machine instructions;
    • and finally, add serializing edges and spill registers until the graph corresponds to a single CFG and all edges can be assigned to registers without conflicts.
  3. Evaluate each candidate CFG according to the current optimization criteria, such as smallest code size or fastest execution time.
Although this still looks like a multi-phase optimization pipeline, the key difference is that we allow the compiler to backtrack over any decision that might turn out to be a bad idea. There may be multiple reasonable choices for nodes to split, multiple ways to select target machine instructions that compute the same results with different tradeoffs, and multiple ways to sequentialize and insert spills. I'd like to know what happens if you effectively check all combinations of those choices.

Of course, the details matter if the result is ever going to be used in a serious compiler. I have some questions about how to handle certain things, like pointers or break statements or exceptions, in a VSDG; but ignoring those concerns, the search also needs to produce reasonable answers quickly or most people will reject it. So a practical implementation needs good heuristics for value-ordering and for branch-and-bound pruning. Given those, I suspect Limited Discrepancy Search would be a good search strategy. (Sanseri reported good results with these choices in his thesis on IA-64 instruction selection, which seems like a good confirmation for my intuition.)

Anyone want to give this a try? I don't have high hopes that anyone reading my blog has spare time for such a project, but there's no harm in asking, right?

Delegating search to SMT solvers

As a side note, I also want to highlight various efforts to use SMT solvers to improve optimization. Effectively, such projects delegate the search to the SMT solver, which implements a good set of general-purpose heuristics. This is a smart approach, although querying an SMT solver is still a fairly expensive thing to do, so people have resisted doing it during normal compilation. As a result, these tools are primarily used offline, to identify improvements that should be made to a compiler, rather than online during compilation.
  • Sebastian Buchwald's "Optgen: A Generator for Local Optimizations" generates all possible peephole optimizations smaller than a given size limit, and in the paper he reported finding that GCC, LLVM, and the Intel C Compiler were all missing some optimizations that Optgen found.
  • Souper examines output from LLVM's optimization passes and looks for patterns that can be shown using SMT queries to have better alternatives. I can't find any published papers about this, but see John Regehr's blog for some reported results, such as "A Few Synthesizing Superoptimizer Results" from 2015. 
  • Lopez et al built Alive, a tool to prove LLVM peephole optimizations correct or generate counterexamples explaining why they're wrong; see "Provably Correct Peephole Optimizations with Alive".

Conclusions

  • Compilers are structured with many independent optimization passes because they're hard enough to get right that way, and worse if you try to combine them; but keeping them separate leads to suboptimal code.
  • Choosing a different intermediate representation in the compiler changes which parts of the compiler are hard to write. That may enable more sophisticated compilers by pushing complexity to places where it is easier to manage.
  • Since optimizations interact in complicated ways, I'd like to see more research into different ways to apply combinatorial search to find the best combination of optimizations for a given piece of code. I've proposed one approach that I haven't seen attempted yet.

Responses

Edit: Thanks to CalChris on Hacker News for the link to Unison, a recent LLVM pass that performs combined instruction scheduling and register allocation via constraint solving. See Lozano et al, "Register Allocation and Instruction Scheduling in Unison".

Thursday, April 6, 2017

Corrode update: control flow translation correctness

I've been pretty quiet about Corrode for a few months. That's partly because I was traveling some, partly because I've been busy with non-Corrode client work, partly because I've been setting up my next Rust-related contracts that I hope to get to announce soon... but mostly, I've been quiet about Corrode because I've been trying to fix some very difficult bugs since December, and it was demoralizing to fight with my code for so long.

So I'm very pleased to announce that Corrode now translates arbitrary C control flow to Rust, correctly!

One thing this has already enabled: the new rust-lzo crate on crates.io is a Rust implementation of the LZO compression algorithm, translated using Corrode from the Linux kernel's implementation. Hooray!

I last talked about the challenges around getting control flow right in November ("Go To Statement Considered (Mostly) Harmless"). At that time I mentioned that Corrode couldn't handle "irreducible" control flow, or some other cases. Later I discovered that sometimes it wasn't even producing correct answers for the cases that I thought were working.

Corrode's new control-flow algorithm is based on Emscripten's "Relooper" algorithm, as described in "Emscripten: An LLVM-to-JavaScript Compiler". I'd like to thank Brian Anderson of the Mozilla Rust team for reminding me that Emscripten exists and already solved almost exactly the problem I faced! (Unless I'm mixing people up again, in which case I'd like to thank whoever actually told me that, instead.)

The Relooper is fully general: it can handle any control flow that you can express in C, including arbitrary 'goto' statements. And I have confidence that my implementation really will handle any wacky control flow you can come up with, partly because at this point I have tested millions of randomly-generated control-flow graphs against relatively simple correctness properties using QuickCheck. I found so many bugs that way! QuickCheck then simplified each bug-triggering control-flow graph down to the smallest graph that would still trigger a bug, making it easier to figure out why it failed.

I now have Travis-CI testing 100,000 random CFGs after every build. This is not a hardship because the implementation is fast: on my 2013-era laptop, testing that many examples only takes around 20 seconds!

Some of the bugs I encountered were in cases which are not covered by the Emscripten paper. I never found the current implementation of the Relooper when I looked at the Emscripten source code, so I don't know whether those cases are covered by Emscripten's real implementation and were just left out of the paper, or even if they were covered in the paper and I just missed it. I also discovered that one of the cases in the paper can't happen because it's subsumed by the others. I intend to ping the paper's author about these surprises sooner or later...

This algorithm is tricky to get right and requires very carefully defining invariants and preconditions. Because I needed to reason about the algorithm in a very formal way to have any hope of getting it right, I thought it might be a good use case for annotating the implementation with refinement types as implemented in LiquidHaskell. Unfortunately, I had too much trouble writing types that LiquidHaskell would accept, so I gave up. Still, just making the effort to write down a semi-formal model helped my understanding a lot, so it wasn't wasted effort! I hope to find a good excuse to play with LiquidHaskell again sometime.

Although I wasn't able to formalize my reasoning for why Corrode's implementation of the Relooper is correct, I at least wrote down an English-language sketch of the correctness and termination proofs for the algorithm, as part of the Literate Haskell documentation for Corrode's CFG module. Please read it, I spent a lot of time writing it ;-)

I'm slowly evolving this algorithm beyond Emscripten's implementation, because for Corrode I want the output to be as human-readable and maintainable as possible. (Emscripten's output is only intended for a web browser to parse, and you need only glance at JavaScript that humans write to realize that nobody's much bothered if we give our web browsers massive headaches.) So far I have a simple post-processing pass to merge any "Simple" block with an immediately-following "Multiple" block, which eliminates the need to introduce an extra variable in the most common cases; and a straightforward check to avoid using labeled "break" and "continue" statements when referring to the most immediately enclosing loop. I have more clean-ups planned, inspired by trying to read the output from Corrode on real C source files.

I'm sure the question you're asking yourself by now is, "But how is the CVS Rust port coming along?" Significantly better now, thank you! There are now only five source files that Corrode refuses to translate, for various reasons, although quite a few more still won't compile after translation. And at least one source file now works fine that previously, when I tried converting it to Rust, made CVS fail its test suite. So a lot of the remaining work is just in cleaning up the output, plus a bit of handling more corner cases of C.

Corrode has many limitations left to fix. But at least control flow isn't one of them any more!

Tuesday, January 3, 2017

Which projects should convert to Rust?

Since the 1.0 release of the Rust programming language in May 2015, people have been exploring different ideas about what to use it for.
  • Does Rust make C obsolete?
  • If so, should we replace existing C programs with Rust equivalents?
  • Or should we leave existing code alone, write bindings that let us re-use it from Rust, and just write new code in this new language?
Of course, there's no one-size-fits-all answer to these questions. But I think there's enough evidence now from various experiments to put together some pretty decent guidelines, which I'll summarize here in case you're impatient:
  1. Rewriting existing software in Rust is an excellent educational exercise, worth doing if you just want to learn something.
  2. If you want your Rust version to be adopted, be prepared to give strong evidence that it's equivalent to the original implementation. This is easiest if the project has a comprehensive test suite, and if much of your translation work can be automated.
  3. Translating a project to Rust is justifiable if the bugs it has the most trouble with are the kinds of bugs Rust is most helpful on—notably, memory safety bugs.
  4. If a project's community is resistant to switching to Rust, any effort you put into porting may be wasted. Make sure you build community support around your work!
For more details, read on.

I'm taking this evidence from two kinds of projects. First, from quite a few efforts to replace pieces of C with Rust equivalents, such as:
  • rusl: an experimental musl libc incremental rewrite in Rust
  • Librsvg gets Rusty: incrementally rewriting parts of an SVG library in Rust, while maintaining binary compatibility with the fully-C version of the library
  • uutils/coreutils: rewriting GNU coreutils in Rust from scratch
  • Trust-DNS: from-scratch implementation of a DNS client and server, inspired by CVEs in BIND
A second source of evidence comes from my efforts at automatic translation from C to Rust using Corrode, and especially my Mozilla-supported experiment on translating CVS.

Education

Bear in mind that many of these porting efforts, such as rusl and librsvg, were started for educational purposes (see, for instance, rusl's goals and non-goals). I think it's safe to guess that everyone who has made a serious attempt at a project like this has learned a lot! So let's make that guideline #1:
If you want to learn a language you don't know already, one very educational way to do it is to rewrite some piece of software you already understand.
(That guideline isn't even specific to Rust. In 2002, I did an exercise in writing a run-length-encoding compressor in as many languages as I had patience to try; I picked C++, Perl, Java, Smalltalk, x86 assembly, and Haskell. It was very helpful for discovering some pros and cons of each language. I had not tried Smalltalk or Haskell before and that exercise led to my continued interest in Haskell years later.)

But what if you want more return on investment than just an educational experience? We'll have to look at the results of these projects more closely.

Correctness, safety, and security

These projects all share at least one big challenge: How can you be sure the Rust version behaves correctly? Nobody wants to replace code that works with code that has new bugs, and while Rust rules out certain classes of memory and type safety problems, it makes no guarantees about program logic. But then, how can you have any confidence that the original version is correct? Perhaps the answer to that question can answer the earlier one.

The above examples all use automated testing to gain confidence in their correctness. The musl, librsvg, and busybox projects each provide a test suite that these porting efforts adopted to test that their Rust rewrites produced the same results as the original implementations. So, assuming the tests pass for both implementations, we can be sure that the Rust version works exactly like the original, at least for those parts that are tested.

That's not as satisfying as I'd like. For example, the author of rusl points out that not only is the test suite for musl incomplete, but musl doesn't pass all of it. Still, re-using an existing test suite provides pretty good confidence.

Trust-DNS doesn't re-use an existing test suite, but its author wrote a test suite based on the relevant DNS specifications, and some of its tests query well-known public DNS servers as a simple interoperability check.

That approach has hazards as well. NASA Langley Research Center's 1990 follow up to the Knight/Leveson "Experimental Evaluation of the Assumption of Independence in Multi-Version Programming" from 1985 found that when multiple teams attempt to write separate programs implementing the same specification, their bugs are not statistically independent. When multiple implementations failed on the same inputs, they found that "lack of understanding by the programmers of key points in the specification was a major contributor".

Trust-DNS encountered an instance of this problem, in fact, related to this bit of RFC6840: "The guidance in the above paragraph differs from what has been published before but is consistent with current common practice." Different DNS developers interpreted a particular specification section in different ways, leading to non-interoperable implementations.

But if the implementation and the tests are written by the same person, then on top of the problems of incomplete test suites, any mis-interpretation of the specification will affect both the implementation and its tests, resulting in an incorrect implementation that appears to be correct because it passes its test suite.

That said, writing a test suite from a specification is far better than nothing, and I'm sure this approach has caught bugs in Trust-DNS.

Anyway, correctness isn't all that matters. The safety and security properties that Rust guarantees are not the only such properties you might care about, and test suites can't cover the gap. If some invalid input causes the C version to return an error and keep going, but causes the Rust version to panic or go into an infinite loop, that could be an exploitable denial-of-service bug. Or if the Rust version is missing an access-control check, it could disclose information that an attacker wasn't authorized for. It's not feasible to write tests to catch all of these cases.

Equivalence

I'd summarize all these concerns as guideline #2:
If you want to replace existing software with a Rust implementation, then the Rust version must behave equivalently to the original, aside from inputs that crash the original. To convince other people to adopt your new implementation, you must give them confidence that the new implementation really is equivalent.
Reusing the original implementation's test suite is a good start at providing this confidence. Demonstrating that the new implementation can interoperate with other implementations, as Trust-DNS does, is another good step.

But I think better approaches are available for demonstrating equivalence when the new implementation is supposed to match an existing one. (These don't help Trust-DNS, but do help the others.)

First, you could mechanically prove that the two implementations are equivalent. The developers of KLEE tested equivalence between busybox and GNU coreutils, for example. KLEE automatically generated test cases that maximized code coverage in both code bases, finding inputs which produced different outputs. In several cases, those differences represented significant correctness bugs; in others, just features that weren't implemented in one version or the other. The Software Analysis Workbench from Galois is also designed for this, and I suspect afl-fuzz could be used in a similar way. Each tool has different trade-offs between performance, completeness, and ease-of-use.

I'm surprised that I haven't seen any of the port-to-Rust projects use any of those tools, to be honest.

Second, and my personal favorite, is to automate as much of the porting effort as possible. If you've been following my blog posts on Corrode, then you know this is the approach I've been working on. This changes the problem from "do I trust the Rust version?" to "do I trust the translator?" Don't get me wrong: establishing trust in the automation is hard too! But so long as the translation tools can be reused across many projects, it's worth spending a lot of time on their correctness.

Any of the above techniques for establishing equivalence may be enough on its own to convince people to adopt your shiny new Rust implementation. But when the software you're converting is especially important, you may need to combine techniques. For example, in my CVS experiments, I'm using Corrode to automate much of the conversion, but I'm also relying on the extensive test suite that CVS has to check that neither Corrode nor I made mistakes. Since Corrode is still young, I've found bugs in it this way, making the test suite an excellent sanity check.

Time and resources

This suggests guideline #3:
The amount of energy you put into converting a project to Rust should be proportional to the importance of that project, and to the consequences of those bugs which Rust can help with.
A program that doesn't interact with the Internet or with files that might come from untrusted sources, like a single-player game or a scientific simulation, may not be worth spending much effort converting to Rust. To be clear, I think there are benefits to choosing Rust when starting work on scientific simulations or games! But once you have already written and debugged code for these sorts of programs, the marginal benefit of switching to Rust is much lower.

On the other hand, a small library that is used by a huge number of programs and often handles untrusted data, such as zlib or a multimedia codec, might be worth spending a lot of time on:
  1. because Rust's memory-safety guarantees address these libraries' most common sources of bugs,
  2. because the consequences of those bugs are widespread due to the number of users,
  3. and because the amount of code to translate is small enough that the effort is nicely bounded.
Widely used network programs such as NTP, SSH, web servers, etc., may be strong candidates for the same reasons.

For libraries that are not worth translating to Rust, it's probably worth at least using tools like rust-bindgen to generate Rust bindings so Rust developers can take advantage of the time and effort that have gone into those libraries.

Ideally, grant programs like the Linux Foundation's Core Infrastructure Initiative or Mozilla Open Source Support should fund efforts to translate critical open-source projects to Rust. Of course, until there's a significant example where a Rust implementation has replaced its predecessor, this may be a hard sell.

And on that note, here's guideline #4:
If you want your Rust port of a project to be adopted, you'd better make sure you have buy-in from that project's community.
This is just standard project management advice, of course, and applies to both open-source and commercial in-house projects. A project's community is deeply invested in their existing implementation, especially in projects with a long history. The larger and more established the community is, the harder it will be to convince a critical mass of their developers to learn Rust to continue working on a project that many of them probably feel is fine as-is.

You could say that the reason I chose to try converting CVS to Rust because not only does it satisfy guideline #3, but it also has too few people caring about it to complain about my attempts. 😉

I find it unlikely, for example, that the Linux kernel will ever switch to Rust. (Although that won't stop me from testing Corrode on it!) In fact, I'd expect some hypothetical new operating system to supplant Linux before Linux developers would switch programming languages. (I'm cheering for seL4, personally, perhaps together with Genode.)

On the other hand, it looks like developers working on GNOME libraries like librsvg may wind up being relatively early adopters.

The gap between "nobody wants this" and "everybody's on board" will move over time, as Rust's advantages are demonstrated in more projects. For the moment, it's still a young language: while I expect projects willing to make the switch will be relatively rare for the moment, I believe we'll see some significant early adopters soon. Naturally, I hope my work on Corrode will help make that happen sooner!

Summary

To recap:
  1. Rewriting existing software in Rust is an excellent educational exercise, worth doing if you just want to learn something.
  2. If you want your Rust version to be adopted, be prepared to give strong evidence that it's equivalent to the original implementation. This is easiest if the project has a comprehensive test suite, and if much of your translation work can be automated.
  3. Translating a project to Rust is justifiable if the bugs it has the most trouble with are the kinds of bugs Rust is most helpful on—notably, memory safety bugs.
  4. If a project's community is resistant to switching to Rust, any effort you put into porting may be wasted. Make sure you build community support around your work!
Discussion elsewhere on this post: