3 ms·
One thing to note is that borrowing in Rust is more powerful than escape analysis can ever be in other languages, because in Rust it's in the type system and th
by pcwalton 8y ago
One thing to note is that borrowing in Rust is more powerful than escape analysis can ever be in other languages, because in Rust it's in the type system and therefore works well with separate compilation and higher-order functions.
To give an example, suppose we have the following:
struct A { ... }
fn g(a: &A);
fn f() {
g(&A { ... });
}
And let's say g() is defined in another crate and separately compiled. In Rust, we can safely allocate the instance A in f()'s stack, because we know via the type system that that instance can never escape. But compare the equivalent example in, say, pseudo-Java:
class A { ... }
class G {
public static void g(A a);
}
class F {
public static void f() {
G.g(new A());
}
}
Can we promote A to the stack? Well, it depends. If the compiler can see the source of G.g and prove that A never escapes, then it can. Otherwise, it has to conservatively assume that A could escape.
(Incidentally, this sort of thing is one of the main reasons why the JVM usually uses a JIT: because Java allows you to replace the bodies of classes at runtime via classloaders, you really want to be able to do these kinds of interprocedural optimizations based on the information you know at the time, but reserve the right to back them out if the class bodies change. Only a JIT is able to do this.)
This gets even more difficult when you get to higher-order functions:
class A { ... }
interface G {
void g(A a);
}
class F {
public static void f(G g) {
g.g(new A());
}
}
Can we allocate A on the stack? Well, it depends on whether any possible instance of G could possibly have its argument escape. Java's HotSpot compiler is quite clever here and can actually make assumptions based on the classes that are currently loaded (as a side effect of devirtualization). But Go, for example, will always allocate that A instance on the heap, as far as I'm aware.
This is not a problem for Rust, because the type system ensures that A can always be allocated on the stack in the analogous code:
struct A { ... }
trait G {
fn g(&self, a: &A);
}
fn f(g: Box<dyn G>) {
g.g(&A { ... });
}
Because the signature of the method G.g() ensures that every implementer must not let the instance of A escape, the compiler can soundly place A on the stack. In this way, lifting the escaping behavior of values into the type system is a very powerful technique that allows Rust to go beyond what typical escape analysis can do.
- ridiculous_fish 8y agoThis claim is too strong, because Rust can't reduce heap allocations to stack allocations. Java, Swift, and others can optimize apparent heap allocations into stack allocations. But (in my understanding) Box, Rc, etc. can never allocate on the stack.
- kibwen 8y agoI'm confused; in Rust, you use Box when you want a value to escape the function. That's the whole point of Box! Likewise I can't think of any situation where you'd ever want to construct a value in an Rc without that value escaping somehow, because in a single scope you're better off just handing out shared references (I think you may be confusing Rc with RefCell, since they are often used together and RefCell can be useful within a single scope--but note that RefCell never allocates). You have no need to cleverly promote these things to the stack because nobody is using them for data that they don't want to live on the heap; you have to go out of your way to use them! :)
- pcwalton 8y agoThey could allocate on the stack; we just don't implement that optimization yet. That's because, as kibwen said, it would almost never kick in in practice.