Hey comrades, I just had an idea that I won't be able to work on in thenext couple months and wanted to release it into the wild. They say ifyou love your ideas, you should let them go and see if they come back toyou, right? In that spirit I abandon this idea to the woods.
Basically the idea is Wizer-like pre-initialization of WebAssemblymodules, but for modulesthat store their data on the GC-managed heap instead of just in linearmemory.
Say you have a WebAssembly module with GCtypes.It might look like this:
(module (type $t0 (struct (ref eq))) (type $t1 (struct (ref $t0) i32)) (type $t2 (array (mut (ref $t1)))) ... (global $g0 (ref null eq) (ref.null eq)) (global $g1 (ref $t1) (array.new\_canon $t0 (i31.new (i32.const 42)))) ... (function $f0 ...) ...)
You define some struct and array types, there are some global variables,and some functions to actually do the work. (There are probably alsotables and other things but I am simplifying.)
If you consider the object graph of an instantiated module, you willhave some set of roots R that point to GC-managed objects. The liveobjects in the heap are the roots and any object referenced by a liveobject.
Let us assume a standalone WebAssembly module. In that case the set oftypes T of all objects in the heap is closed: it can only be one of thetypes $t0, $t1, and so on that are defined in the module. Thesetypes have a partial order and can thus be sorted from most to leastspecific. Let's assume that this sort order is just the reverse of thedefinition order, for now. Therefore we can write a general typeintrospection function for any object in the graph:
(func $introspect (param $obj anyref) (block $t2 (ref $t2) (block $t1 (ref $t1) (block $t0 (ref $t0) (br\_on\_cast $t2 (local.get $obj)) (br\_on\_cast $t1 (local.get $obj)) (br\_on\_cast $t0 (local.get $obj)) (unreachable)) ;; Do $t0 things... (return)) ;; Do $t1 things... (return)) ;; Do $t2 things... (return))
In particular, given a WebAssembly module, we can generate a function totrace edges in an object graph of its types. Using this, we canidentify all live objects, and what's more, we can take a snapshot ofthose objects:
(func $snapshot (result (ref (array (mut anyref)))) ;; Start from roots, use introspect to find concrete types ;; and trace edges, use a worklist, return an array of ;; all live objects in topological sort order )
Having a heap snapshot is interesting for introspection purposes, but myinterest is in having fast start-up. Many programs have a kind of"initialization" phase where they get the system up and running, andonly then proceed to actually work on the problem at hand. For example,when you run python3 foo.py, Python will first spend some time parsingand byte-compiling foo.py, importing the modules it uses and so on,and then will actually run foo.py's code. Wizer lets you snapshot thestate of a module after initialization but before the real work begins,which can save on startup time.
For a GC heap, we actually have similar possibilities, but the mechanismis different. Instead of generating an array of all live objects, wecould generate a serialized state of the heap as bytecode, and anotherfunction to read the bytecode and reload the heap:
(func $pickle (result (ref (array (mut i8)))) ;; Return an array of bytecode which, when interpreted, ;; can reconstruct the object graph and set the roots )(func $unpickle (param (ref (array (mut i8)))) ;; Interpret the bytecode, building object graph in ;; topological order )
The unpickler is module-dependent: it will need one case to constructeach concrete type $tN in the module. Therefore the bytecodegrammar would be module-dependent too.
What you would get with a bytecode-based $pickle/$unpickle pairwould be the ability to serialize and reload heap state many times. Butfor the pre-initialization case, probably that's not precisely what youwant: you want to residualize a new WebAssembly module that, whenloaded, will rehydrate the heap. In that case you want a function like:
(func $make-init (result (ref (array (mut i8)))) ;; Return an array of WebAssembly code which, when ;; added to the module as a function and invoked, ;; can reconstruct the object graph and set the roots. )
Then you would use binary tools to add that newly generated function tothe module.
In short, there is a space open for a tool which takes a WebAssembly+GCmodule M and produces M', a module which contains a $make-initfunction. Then you use a WebAssembly+GC host to load the module andcall the $make-init function, resulting in a WebAssembly function$init which you then patch in to the original M to make M'', which isM pre-initialized for a given task.
Some of the object graph is constant; for example, an instance of astruct type that has no mutable fields. These objects don't have tobe created in the init function; they can be declared as new constantglobal variables, which an engine may be able to initialize moreefficiently.
The pre-initialized module will still have an initialization phase inwhich it builds the heap. This is a constant function and it would benice to avoid it. Some WebAssembly hosts will be able to runpre-initialization and then snapshot the GC heap using lower-level facilities (copy-on-write mappings, pointer compression and relocatable cages, pre-initialization on an internal level...). This would potentially decrease latency and may allow for cross-instance memory sharing.
There are five preconditions to be able to pickle and unpickle the GCheap: 1. The set of concrete types in a module must be closed. 2. The roots of the GC graph must be enumerable. 3. The object-graph edges from each live object must be enumerable. 4. To prevent cycles, we have to know when an object has been visited: objects must have identity. 5. We must be able to create each type in a module.
I think there are three limitations to this pre-initialization idea inpractice.
One is externref; these values come from the host and are bydefinition not introspectable by WebAssembly. Let's keep theclosed-world assumption and consider the case where the set of externalreference types is closed also. In that case if a module allows forexternal references, we can perhaps make its pickling routines call outto the host to (2) provide any external roots (3) identify edges onexternref values (4) compare externref values for identity and (5)indicate some imported functions which can be called to re-createexernal objects.
Another limitation is funcref. In practice in the current state ofWebAssembly and GC, you will only have a funcref which is created byref.func, and which (3) therefore has no edges and (5) can bere-created by ref.func. However neither WebAssembly nor the JS APIhas no way of knowing which function index corresponds to a givenfuncref. Including function references in the graph would thereforerequire some sort of host-specific API. Relatedly, function referencesare not comparable for equality (func is not a subtype of eq), whichis a little annoying but not so bad considering that function referencescan't participate in a cycle. Perhaps a solution though would be toassume (!) that the host representation of a funcref is constant: theJavaScript (e.g.) representations of (ref.func 0) and (ref.func 0)are the same value (in terms of ===). Then you could compare a givenfunction reference against a set of known values to determine its index.Note, when function references are expanded to include closures, we willhave more problems in this area.
Finally, there is the question of roots. Given a module, we cangenerate a function to read the values of all reference-typed globalsand of all entries in all tables. What we can't get at are anyreferences from the stack, so our object graph may be incomplete.Perhaps this is not a problem though, because when we unpickle the graphwe won't be able to re-create the stack anyway.
OK, that's my idea. Have at it, hackers!