to wasm and back again: the essence of portable programs

posted on 2021-10-22

what is the essence of a portable program, a program expressed in a format such that it can then be interpreted or, ideally, compiled to run efficiently in a variety of different environments?

this doesn't just mean "different OSs" or "different CPU architectures", but can even expand to compiling programs to different forms of computing like GPU code or maybe even FPGAs.

when we tried to figure some of this out for web pages, we came up with "Native Client"; but it eventually became clear that that the LLVM intermediary representation that it uses wasn't a good fit for a variety of reasons, so we eventually settled on WASM; and now everyone is moving in that direction very fast despite its various issues.

alas, there can be a variety of factors that influence how a program should be compiled to take full advantage of the machine it's running on:

what is the size of pointers? WASM currently hardcodes this to 32, and another WASM variant will come out to hardcode it to 64; just 32 works for many uses but having these hardcoded at compile time is hardly a great choice in general.
how much CPU cache is available? currently, barely anything ever takes this into account, even though uncached memory access times can be a huge cause for inefficiency; and let's not get into cache-manipulation instructions, which nobody's using because we all like to pretend our computers are simpler than they are (which no doubt also encourages hardware designers to only make CPUs for programmers that have this expectation, but this is a story for another time).
how much memory can be allocated? how is it allocated? can programs and libraries share entire memory blocks with one another seamlessly? WASM currently takes a pretty naive approach to this with "linear memories", and a variety of conversion schemes are guaranteed to make the standard a lot more complex.
what instructions are available? instructions like count leading zeros/count trailing zeros or popcount can be pretty instrumental to some algorithms performing efficiently, but compiling those in terms of other instructions on instruction sets that don't have them natively can be quite the loss in performance.
how many registers are there? are some operations expected to use only certain registers? how efficiently can values be pushed and popped from the stack? how much stack even is there??
what is the expected alignment of various types in memory? how are those alignments checked? are unaligned accesses unsafe or merely slow?
and then everything to do with atomics and multithreading (WASM's attempts at addressing these seem at the moment pretty unsatisfactory)

more importantly, effects of questions like those can ramificate upwards: a change in pointer size (say between 32 and 64) or knowledge about the cache sizes, or cache-fetching or branch-prediction algorithms of a CPU should be able to lead to an entire data structure "choosing" a very different implementation (not just for algorithms, but also but for memory layout!). and those changes are even more far-reaching once parts of this algorithm (such as accessor functions for data structures) get inlined in various ways in other parts of the code. WASM just assumes some relatively common invariants and that's it; there's no ability to provide entirely different algorithms based on even pointer size or alignment requirements.

so, to be able to make arbitrarily complex decisions based on those environmental conditions, a portable program should not be just a flat WASM, but should in fact be a dynamic metaprogram which, upon initialization, examines the environment and makes all the right choices to produce a code that is able to run optimally on the target environment. ideally, that metaprogram itself should be written in yet another meta²program; but this one compiles the meta¹program for the compiling environment rather than the target environment (those can be different! think of a meta²program, producing for the CPU a meta¹program whose goal is to produce for the GPU the end program). ultimately, though, we need some form of basic language to bootstrap this whole process, at the top of the tower of metaⁿprograms: this is where WASM can come back.

such metaⁿprograms should expect to interact with an API that would be like that of a JIT compiler library, with functions like create_function(parameter_types, return_types) → FunctionId or add_function_call(function_id, parameter_variables) → ValueId used to generate pieces of the metaⁿ⁻¹program. ideally, different metaⁿprograms from different places could even end up getting their functions inlined with each other; a library generated by a metaprogram, and a user program generated by another metaprogram from another vendor but using that library, should be able to be inlined with each other, rather than "naively" loaded like current dynamic libraries. maybe their two metaprograms should even be able to "negotiate" optimizations with one another using specification contracts, but this seems hard to set up.

if "object programs" (meta⁰programs) — but also higher up metaⁿprograms — are expected to be safely sandboxed, the best way to do this might not be to dynamically check everything and then hope optimization can remove some checks, but instead the metaⁿ⁺¹program that produces them should be able to manipulate logical statements to "logically prove" to the compiler that the program being produced is safe; and adding a dynamic check would be just one way to guarantee this safety. the point is, demonstrating safety should be able to, like code generation, be an arbitrarily complex process, rather than a very strict one limited to whatever type system is available, and whatever hacks one can build on top of it.

ideally, metaⁿprograms should also be able to tap into a collection of optimizing code-transformation libraries, which could be updated regularly such that old programs can benefit from new optimizations; but should be proven to be correct such that this doesn't affect behavior we care about. in this way, logically proving behavior is not just a matter of sandboxing or program safety, but also a matter of optimization even in "unsafe" programs.

this approach, in some ways despite its lesser dynamicity, is more general than "runtime metaprogrammability" in that the metaprogram is able to create a mesaprogram (the opposite of a metaprogram) for a vastly different target environment than the one it is itself running on.

posted on 2021-10-22