Compile-Time Ephemerons

[leafpetersen]

@goderbauer commented on Wed Mar 25 2020

It would be cool if Dart supports compile-time Ephemerons (also known as "Weak Properties"). Among other things, this would enable Flutter to restore the state of anonymous Routes during State Restoration (see http://flutter.dev/go/restoring-anonymous-routes for details of that use case).

Functionality

A compile-time ephemeron is a const object that stores a key and a value. It can be instantiated from code only via a const constructor that takes the key and the value as arguments. The ephemeron gets special treatment from the compiler: If the key of a given ephemeron is not reachable from the app (outside of the instantiation of the ephemeron itself), the compiler may null out the key and value field of the given ephemeron. Otherwise, the key and value are left as-is.
When the key and value fields are nulled out, the tree-shaker can potentially eliminate more stuff from the final binary.
Essentially, the ephemeron keeps a weak reference to its key and only keeps its value around if the associated key is reachable from other places in the app. This will allow library authors to create dynamic invocations of methods only if they are retained by the tree shaker.

Interface

/**
 * Instances of this class are ephemerons, also known as weak properties, that
 * participate in determining which const objects will be retained at compile time.
 *
 * A const object is compile-time reachable if it is used in some function
 * transitively callable from main, or as the field of some other compile-time
 * reachable const object.
 *
 * If the key of a CompileTimeEphemeron is compile-time reachable, then its value
 * is compile-time reachable. If the key is not compile-time reachable, the key and
 * value are both replaced with null.
 *
 * All CompileTimeEphemerons created with any compile-time unreachable key are equal.
 * (That is, canonicalization happens after reachability is determined.)
 *
 * This extends the concept of weak reachability from runtime garbage collection to
 * compile-time tree-shaking. Ephemerons were first described in
 * https://doi.org/10.1145/263698.263733
 *
 * Note that a weak reference is a special case of an ephemeron where the value is
 * not used. In this case, we recommend setting the value to null.
 */
class CompileTimeEphemeron<K, V> {
  final K? key;
  final V? value;

  /**
   * This constructor must be invoked via `const`; it is a compile-time error to invoke
   * this constructor via `new`.
   *
   * (Because it is not currently possible to implement a runtime ephemeron in JavaScript.)
   */
  const CompileTimeEphemeron(this.key, this.value);
}

Implementation

The dart:core library would expose a CompileTimeEphemeron class that can only be instantiated via a const constructor. The const constructor takes a key and a value of any type and instances of the class have fields to retrieve both values again.

Tree-shaking compilers typically have a work queue of functions to be compiled. This queue starts with ‘main’ (and other entry points) inserted. The compiler takes a function from the work queue, compiles it, then inserts all functions that could be called from it; and repeats until the queue is empty. Any function that remains uncompiled is dead code and removed. To implement CompileTimeEphemerons, a few changes are made to this loop. When a CompileTimeEphemeron is encountered, it is added to a list of pending ephemerons, instead of being visited immediately like other const objects. After the work queue is drained, each CompileTimeEphemeron in the pending list is examined. If its key is compile-time reachable, then its value is visited and the ephemeron is removed from the pending ephemerons list. Visiting the value can insert into the work queue. After the whole list has been examined, the compiler again drains the work queue and revisits the ephemeron list. This repeats until visiting the ephermon list does not add to the work queue. Then all remaining ephemerons on the pending list have their keys and values set to null.

Use Case

State Serialisation and Deserialisation in Flutter: In order to deserialize a class from serialized data, we need to maintain a Map with serializable class ids as keys and deserialisation functions as values. However, when a certain class is unused in the app and tree-shaken out, we do not want to retain the deserialisation function (see "Restoring anonymous Routes" for details of this use case and how ephemerons can be used to solve it).

Further Reading

• Wikipedia article on Ephemerons
• The original paper by Barry Hayes introducing the concept of ephemerons: Ephemerons: a new finalization mechanism

Related Issues

• Link time sets and maps (Link time sets and maps #371): Flutter's use-case could also be solved with a link-time map and the condition contributing functionality described in the linked proposal.

Special thanks to @dnfield and @rmacnak-google for their help in creating this proposal.

---

@goderbauer commented on Wed Mar 25 2020

/cc @leafpetersen @Hixie @a-siva

---

@dnfield commented on Wed Mar 25 2020

@lrhn @eernstg as well

[leafpetersen]

Moving this over from the SDK repo. cc @eernstg @munificent @lrhn

[lrhn]

I have not read the literature on this, so can you )(or someone) explain why it would not be sufficient to have the value be private, and only accessible upon providing the key.
That is, treat it as a singleton ephemeron map where the values are only kept alive while the key is alive, because afterwards, nobody can look up the value anyway.
That would also be implementable using a JavaScript WeakMap without the const restriction.

I think that would put the behavior on more solid and deterministic ground. It would not expose whether a key is retained or not through the value side-channel, thereby introducing the notion of garbage collection and (some notion of) reachability into the language specification.

Obviously, if checking whether something is live is the goal, without having that thing yourself and thereby keeping it alive, then we can't require the asker to have the key.

We could even consider joining this with the"link time maps" (#371) feature, because one of the flaws of that feature is that unused parts of code may introduce entries into the link-time map even though the code itself is tree-shaken. If the link-time map is an ephemeron map, then that problem goes away. You can't iterate the keys, only look up values by key when you have the key.
(That's also very similar to an Expando, which is effectively the Dart weak map, which you can't use on values that have non-trivial identity, like num and bool)

A const object is compile-time reachable if it is used in some function
transitively callable from main, or as the field of some other compile-time
reachable const object.

Whether something is "callable from main" sounds undecidable.
The rest sounds redundant - if it's the value of a field of a const object which can be reached from a function callable from main, then the field can be reach from that function. Does it matter whether the function actually reads the field? Why/why not?
Static reachability is a very wibbly-wobbly concept, otherwise our tree-shakers would do better. I would prefer not to try to specify that.

I'm very concerned about the complexity of introducing visible garbage collection/tree-shaking as a specified part of the language semantics. We'll have to make our compilers do exactly the same, specified, tree shaking in order to preserve semantics, or let the semantics be looser "if the key and value are null, then we promise that nobody else has the key, but it might and might not happen" (and it is unprovable whether we were right since we can't tell what the key was any more, it was set to null).

I'm also not sure how this will work with modular compilation. There would have to be a final step to figure out whether the value is retained or not, but I guess there always needed to be a final step to do canonicalization of constants.

[leafpetersen]

I have not read the literature on this, so can you )(or someone) explain why it would not be sufficient to have the value be private, and only accessible upon providing the key.

I had the same question.

As a second question what does it mean for a primitive object to be compile time reachable? Does the following program have deterministic semantics (and if so, what does it print), or are there several valid outcomes depending on what optimizations the compiler chooses to perform?

void show(CompileTimeEphemeron<String, String> e, String key) {
  if (e.key != null) print(e.value);
}
void main() {
  const a = const CompileTimeEphemeron<String, String>("test1", "hello");
  const b = const CompileTimeEphemeron<String, String>("test2", "world");
  show(a, "test1");
  show(b, "test" + "2");
}

[dnfield]

These types are not particularly useful for direct usage like that in a regular dart program. The goal here is to have something to use in a kernel transformer that could point us to methods, only if the methods were not tree-shaken out. A represenative program for this might look like this before compilation:

// K and V are the same because this is really just a weakly referenced method.
const Map<String, CompileTimeEphemeron<Function, Function>> methodMap = <CompileTimeEphemeron<Function, Function>>{};

void main() {
  foo();
  if (methodMap['foo'].value != null) {
    // `foo` was retained during compilation. We expect this to be true.
  }
  if (methodMap['bar'].value != null) {
    // `bar` was retained during compilation. We expect this to be false.
  }
}

@specialAnnotationKnownToKernelTransformer
void foo() {
  print('foo');
}

@specialAnnotationKnownToKernelTransformer
void bar() {
  print('bar');
}

After compilation, a custom kernel transformer would fill that map out so it looked like this:

const Map<String, CompileTimeEphemeron<Function, Function>> methodMap = <CompileTimeEphemeron<Function, Function>>{
  'foo': CompileTimeEphemeron(foo, foo),
  'bar': CompileTimeEphemeron(null, null),
};

In this way, the program can weakly reference both foo and bar without retaining them in compilation - this is critical for the use case Flutter has because we want to be able to refer to potentially large chunks of code this way, without adding binary size to programs that are not actually using them.

@leafpetersen to answer your specific example, this type doesn't really make sense to use this way, but I would expect the output of the program to be hello\nworld.

In case it's not 100% clear, the real meat of this request is in changes that would have to be made to the compilers (VM and JS), but to tie it all together we'd want a well known type in dart:core.

[goderbauer]

I have not read the literature on this, so can you )(or someone) explain why it would not be sufficient to have the value be private, and only accessible upon providing the key.

For Flutter's use case making the value only accessible when you provide the key would be fine. We actually would set key and value to the same value anyways, as @dnfield already pointed out.

[lrhn]

If you set the key and value to the same object, and you can only access the value by providing the key, it's also assumed that you cannot get the key directly. It would not work for you like that.

What you appear to be asking for is a way to have "weak" references to program entities and a way to detect whether those entities were tree-shaken or not.
Since tree-shaking is not an existing language concept (nor is garbage collection for that matter), giving semantics to this would require quite a lot of machinery, or a lot of handwaving.

If you are doing a kernel transformation anyway, why not just create the "ephemeron" during that transformation too. No need for a language feature. All you need is for your kernel transformation to run after tree-shaking. (Which is obviously tricky since tree-shaking is an undefined optimization).

[goderbauer]

If I can have a kernel transformer run after tree shaking, that would work for our use case as well. As far as I know, there is currently no way to do that though. And in conversations with @rmacnak-google I got the impression that adding a hook to run a kernel transformer at that stage would be difficult/impossible.

[rmacnak-google]

I have not read the literature on this, so can you )(or someone) explain why it would not be sufficient to have the value be private, and only accessible upon providing the key.
That is, treat it as a singleton ephemeron map where the values are only kept alive while the key is alive, because afterwards, nobody can look up the value anyway.

That's not an ephemeron. Ephemerons are strictly more powerful than non-enumerable weak maps (what JavaScript provides), and as powerful as enumerable weak maps: one can build weak maps out of ephemerons, but cannot build an ephemeron out of a non-enumerable weak map. Enumerability is useful when you need to convert from an external key (e.g., deserialization), or when you need to apply some action to dependents (e.g., updating a mixin should update all surviving mixin applications, but the mixin should not keep all mixin applications alive).

As a second question what does it mean for a primitive object to be compile time reachable? Does the following program have deterministic semantics (and if so, what does it print), or are there several valid outcomes depending on what optimizations the compiler chooses to perform?

Enumerability does create non-determinism (for a runtime ephemeron, when the GC runs; for a compile-time ephemeron, how clever is the tree-shaker) and a side-channel (an otherwise isolated realm can observe when another realm makes something unreachable). The folks on JavaScript committee thought it was important to prevent this particular kind of non-determinism, but I do not find their arguments convincing. The side-channel argument isn't interesting since Dart's global scope means there can only be one realm anyway.

[leafpetersen]

What you appear to be asking for is a way to have "weak" references to program entities and a way to detect whether those entities were tree-shaken or not.

I'm not sure the latter is part of the request, I think it's just accidental. As I understand it, the core of the problem that both this and the link time map proposal are trying to address is to have a way to provide a mapping from a certain set of compile time entities (Route identifiers, type objects) to values (Route constructors, DI constructors, etc) without constraining the elements in the domain of the mapping to be held onto by the compiler. This is indeed a form of "weak" references. I don't think the ability to detect whether those entries were held onto is part of the request - it's just that it's hard to avoid allowing it.

Since tree-shaking is not an existing language concept (nor is garbage collection for that matter), giving semantics to this would require quite a lot of machinery, or a lot of handwaving.

We're not going to specify tree-shaking, full stop. So that means we have two possible paths if we support one of these features. The first is to accept non-determinism in the semantics (the "weak references" approach), and the second is to constrain the problem so that it is not observable whether or not a key/value pair is present in the map/ephemeron.

Avoiding the non-determinism is hard. The following would, I think, do it:

• Make the ephemeron a mapping (so you can't read the value or the key, just ask for the value associated with a key)
• Require the key to be drawn from a set of compile time enumerable objects which cannot be synthesized at runtime.
  • non-generic Type objects would work
  • Strings do not (you can synthesize them at runtime, and defining the enumeration gets you into related problems about whether you mean before or after constant-folding,etc).

I think that's enough to guarantee determinism: you just enumerate the objects at link time, and null out any ephemerons whose keys aren't enumerated. But I think for the Route use case, you need to use keys which are synthesized at runtime (i.e. by reading Strings from a file).

I should say, I don't consider non-determinism a non-starter here - just that it's one of the considerations in play.

[Hixie]

We're not going to specify tree-shaking, full stop.

Whether we specify it in prose or not, we are specifying it in code and depending on that specification, as are our customers.

FWIW, we're definitely not married to this solution, if there's a better way to solve the original issue then I'm certainly eager to hear it because I'd rather not depend on kernel transforms and tree-shaking magic to solve it. :-)

[goderbauer]

Require the key to be drawn from a set of compile time enumerable objects which cannot be synthesized at runtime.

I think this requirement would be a problem for us. We need to retrieve the value based on something that we read in from disk (e.g. a string or integer).

[leafpetersen]

Whether we specify it in prose or not, we are specifying it in code and depending on that specification, as are our customers.

So you're saying that it would be a breaking change for one of our implementations to implement better tree-shaking? :)

Currently, every implementation is free to do different tree-shaking. A modular compiler can choose to do no tree-shaking, an optimizing compiler can provide flags that tradeoff tree-shaking vs compile time, and code size vs performance, and compilers can implement smarter tree shaking at will. If we specify tree-shaking in the language spec, all of those become technical violations of the spec.

So yes, doing good tree-shaking is part of the implicit contract that we provide to our customers, but we're not going to specify what compilers must/may do here, full stop.

[Hixie]

I'm saying it would be a breaking change for an implementation to implement worse tree shaking, and that when our developers expect tree-shaking at all, if we don't tree-shake large chunks of code they are using, they will treat this as a bug.

Require the key to be drawn from a set of compile time enumerable objects which cannot be synthesized at runtime.

@goderbauer We could live with this if there was a map that mapped synthesizable values to these values, right?

[dnfield]

The core problem is that we need to be able to discover if a method is present in the compiled code without directly causing that method to be present in the compiled code (i.e. only if someone else is also using that method). And we need to be able to discover that method using a serializable (read: non-const) key, so that we can persist that key to disk, read it back, and use it to find the method again.

[goderbauer]

We could live with this if there was a map that mapped synthesizable values to these values, right?

Right, we could have the kernel transformer generate a map from string/int to non-synthesizable values and when we get back the string, look it up in this map to obtain the key for the ephemeron or link-time map.

[goderbauer]

Let me try to rephrase the problem a little bit:

While the app is running, it may call some specially marked static methods. When that happens, I want to record that this method was called in a serializable way. The next time the app runs, I want to deserialize that information and execute that method again (to recreate the state of the previous run).

So, somehow I need to create a bi-directional mapping between a serializable identifier and the static methods that my app may call. I need to do this in a way that prevents the static methods from getting retained if nothing in my app is ever calling them (in other words: this mapping shouldn't get in the way of tree-shaking).

So, I don't actually need a way of discovering if a certain method is present in the compiled code or not. I need a way to somehow get a reference to a static function (that I know has been called in a previous invocation of the program) based on serializable information.

[leafpetersen]

I'm saying it would be a breaking change for an implementation to implement worse tree shaking, and that when our developers expect tree-shaking at all, if we don't tree-shake large chunks of code they are using, they will treat this as a bug.

No it isn't, and no they won't. There is an implicit contract with our users for code size. Tree shaking is an implementation detail. So long as we uphold our contract, it is irrelevant to our users how we implement it. If we make tree-shaking worse in order to improve something else in a way that is code size neutral nobody knows, or cares.

Specifying the details of tree shaking makes the procedure by which we uphold the code size contract itself part of the contract. And this is something that I am tremendously resistant to doing.

[leafpetersen]

I need a way to somehow get a reference to a static function (that I know has been called in a previous invocation of the program) based on serializable information.

I'm not saying that this is the right solution, but just so I understand the space a bit: is there a reason not to just do this in the embedder via FFI? It seems like it would be relatively straightforward to have an embedder API which maps a static function to a serializable key, and vice versa.

[goderbauer]

We could live with this if there was a map that mapped synthesizable values to these values, right?

Right, we could have the kernel transformer generate a map from string/int to non-synthesizable values and when we get back the string, look it up in this map to obtain the key for the ephemeron or link-time map.

Thinking about this a little more, I don't think this would actually work. Wouldn't the presence of the non-synthesizable value in that generated map keep the value in the ephemeron alive? @Hixie How were you imagining this?

[goderbauer]

I'm not saying that this is the right solution, but just so I understand the space a bit: is there a reason not to just do this in the embedder via FFI? It seems like it would be relatively straightforward to have an embedder API which maps a static function to a serializable key, and vice versa.

We would need two API methods: One that given a static function returns a serializable identifier and another that given that serializable identifier returns that same function object again. Is this actually implantable? Do you have any pointers regarding how to do this mapping on the native side? If we can get this, that would work for our use case, I think.

This would actually make things simpler on our end as we wouldn't need a kernel transformer step...

[Hixie]

Wouldn't the presence of the non-synthesizable value in that generated map keep the value in the ephemeron alive?

For such a solution to work the map would need to only include the entries that correspond to things that were referenced.

[Hixie]

One that given a static function returns a serializable identifier and another that given that serializable identifier returns that same function object again. Is this actually implantable?

Basically a serializable version of PluginUtilities... cc @bkonyi

[goderbauer]

PluginUtulities looks actually very promising! It seems like the information it utilizes behind the scenes is already serializable: https://github.com/flutter/engine/blob/96a1a843cba2417f948a5e604f07310c83dfe779/lib/ui/plugins/callback_cache.cc#L74

I’m going to experiment with this a little bit tomorrow. Thanks for the pointer!

[goderbauer]

Quick status update: PluginUtilities.getCallbackHandle and PluginUtilities.getCallbackFromHandle are providing all the functionality we need to solve the problem. The handles they are returning are serializable and stable across app launches.

One problem: This API is currently not available on the web (see flutter/flutter#33615) and it has been pointed out that it may not be possible to implement there. I am doing some more investigations into this.

[leafpetersen]

This API is currently not available on the web

I commented on that bug, but I'd be surprised if you couldn't get something that works through JS interop. You might need to make it a static method on a class, with a well-known name for the method instead so that you could use a class ID as the serializable token, but that seems like it would work. I may be missing something though.

[mraleph]

I want to suggest an alternative way to look at this problem: instead of looking for primitives needed to implement custom serialization, we could consider looking at exposing some sort of builtin serialization mechanism for object graphs, which can be used inside the same app (but can't be used across application updates).

On the VM we already have such mechanism and use it for isolate communication - it supports serialising static tear-off among other things. So the question is, why not expose this mechanism to the end user as dart:pickle for example with the following interface

/// Serialize the given object and all its dependencies transitively into a binary representation.
/// Supports everything that [SendPort.send] supports.
/// Resulting binary representation is not stable across versions and can only be deserialized 
/// by the same version of this application. 
Uint8List pickle(Object obj);

/// Inverse of [pickle]
Object unpickle(Uint8List list);

There are two open questions here:

• how much of this functionality can dart2js support (I don't really see any obvious issues, but maybe @sigmundch and @rakudrama see something).
• what are the implications on tree-shaking and size reduction efforts (e.g. does is cause us to retain metadata that otherwise could have been removed from the AOT compiler output).

[goderbauer]

@mraleph My understanding is that the pickled object graph of a static function could be rather large since it would contain all its dependencies. This may be a problem for our use case. For state restoration you're only supposed to store as little data as is necessary to restore state (Android limits you to about 500KB, we could get around this by writing things directly to disk, but that would make things more complicated). So, a small identifier for a static function would be preferred over storing the binary representation of that entire function.

[mraleph]

@goderbauer no, that’s true for closures in some sense, but for static functions it would just be three identifiers (library, class, function name). That’s the encoding we currently use for isolate sends (and that’s the same thing PluginUtilities does internally)

[lrhn]

That's because we are not actually sending the static closure, just the reference to the similar static function on the other side. It does not close over global state. Nor do local function closures for that matter, it's only the local state which is captured in the closure, Global state (things with static access) are not part of the closure that's being sent.

[goderbauer]

for static functions it would just be three identifiers (library, class, function name).

Oh, that would be perfect then! Yeah, such an API would work for us and if it is available in dart:pickle or something like that we could also remove our homegrown PluginUtilities.

Would such an API be susceptible to the same problems that @Hixie identified in https://github.com/flutter/engine/pull/5539/files/3341e83e0714d3fbd2ae6d3ecc7c671c56d662e4#r199692130 with the original API design of PluginUtilities where we were just sending the strings of library, class, function name to user land? Or would the pickled version be opaque enough to avoid those concerns?

[mraleph]

@goderbauer Some concerns apply. It is possible to make pickle opaque - but it would require too much engineering in my opinion.

If someone uses this API directly with input that is in any way under the control of the user, it's a ripe for becoming an attack vector, where the user causes the app to jump to arbitrary top-level static functions.

This concern would apply - though I don't really think it is a big issue. I mean - yeah if you use this API with user input you have an issue; no, I don't believe it is worth guarding against this.

This seems like it will be abused. For example, someone might store this data, pass it over the network to another instance of the program, then look up the address to jump to and do that. This would be very sketchy code, but this API doesn't make it feel bad.

Yeah, this works. Again I don't see it's a problem. If anything sounds like a cool feature.

What happens if someone caches these values across version updates, then uses them in a subsequent version of their code where the function has been tree-shaken out?

This can be caught by embedding snapshot version/hash into the "pickle" and rejecting pickle on mismatch when loading it.

[sigmundch]

Sorry for the very slow response here.

how much of this functionality can dart2js support (I don't really see any obvious issues, but maybe @sigmundch and @rakudrama see something).

If I recall correctly, back in the day when we supported dart:isolate on the web, the JS implementations to only allowed sending json-serializable values. I don't recall that we had support for sending complex objects that require mapping their types on the other side. I don't recall, but it is possible that we allowed references to static methods back then in some form.

@rakudrama do you believe the new-rti could be helping make these serializations simpler to some degree?

It would definitely be a much simpler change to add only support for static methods initially if that's enough for the problem at hand. I mentioned in flutter/flutter#33615 that we'd like to restrict these serialized values to only work on the same version of the app, but not across different versions. The documentation from @mraleph on the pickle API seems to match that constraint, so we'd be good on that front.

---

Re compile-time ephemerons: @leafpetersen Dart2js used to support a LookupMap API, a (take a deep breath) non-enumerable compile-time constant tree-shakeable weak map implementation. The code is now deleted, but it wouldn't be hard to revive it if that was desired. It relied on constant keys, so it wouldn't support deserialized keys out of the box. To make it work with deserialiezed keys we'd need to define that any such keys will be ignored for retention purposes. Here some pointers from just before we removed it: readme, api

[goderbauer]

It would definitely be a much simpler change to add only support for static methods initially if that's enough for the problem at hand. I mentioned in flutter/flutter#33615 that we'd like to restrict these serialized values to only work on the same version of the app, but not across different versions. The documentation from @mraleph on the pickle API seems to match that constraint, so we'd be good on that front.

Restricting it to static methods that only work within the same version of the app would work for the use case at hand (state restoration).