5 ms·
There's a lot to think about here, but right now I just want to respond to one point, about vectors and SIMD. Performance limits what you can program on a plat
by kragen 4y ago
There's a lot to think about here, but right now I just want to respond to one point, about vectors and SIMD.
Performance limits what you can program on a platform, and there's a pretty wide range of interactive software where the performance bottleneck is generating pixels to put on the screen, just because there are so goddamned many of the fuckers. And fortunately that is commonly vectorizable; vector operations implemented by special CPU instructions have been a key enabling hack since BitBlt on Smalltalk in the 01970s. (In fact, the very first machine that ran a GUI had SIMD instructions in hardware, the TX-2, completed in 01958, but it didn't have pixels.)
This is even more important now than before, even without bringing GPUs into the picture. With optimized single-threaded C on an 8-core system, you're getting at best 12.5% of the machine's performance. If SIMD gives you an 8-fold speedup on slinging pixels around, which is common, you're getting at best 1.6% of theoretical performance with single-threaded SIMD-less code. With a naive, CPython-style bytecode interpreter, you have another factor of 40 or so slowdown, so you're getting 0.04% of the machine's performance: 11.3 Moore's-law performance doublings, so on today's machines you're back to 01999, age of Winamp, Quake III, ICQ, RealAudio, and Baldur's Gate. On the 02009 machine I'm typing this on you're back to 01987.
Now, people wrote a lot of interesting programs in 01987. Fractint, Hypercard, Quattro Pro, X11R3, a lot of the more elaborate Infocom games. And modern SSDs and humongous RAM mean you can do a lot of things now you couldn't do then, even if your CPU is clunking along with 01987 performance. And even a basic JIT compiler can probably get you from 0.04% up to 0.5% of the machine's performance, maybe 4% if it's multithreaded, though that makes determinism enormously more difficult.
But in theory Numpy-style vector operations can take advantage of both multiple cores and SIMD, usually giving you about 20% of the machine's performance even in a naive, CPython-style bytecode interpreter, at least on the kinds of operations where it's applicable, and without sacrificing determinism. Possibly with the kind of pipelining and tiling optimizations Numpy doesn't do you can do even better than that.
Of course, you can also design a virtual machine architecture in such a way as to permit efficient compilation, and not have to fall back on turbocharged vector operations. A lot of Wasm is designed with this objective in mind; for example, there is no dynamic typing to require runtime type checks, local variables can't alias linear memory, control flow is structured to help out the compiler, and so on, so that your interpretation/emulation slowdown is almost nil, reduced to the occasional bounds check that couldn't be hoisted out of a loop. And you can provide access to SIMD instructions, which Wasm now does, and multithreading, which it doesn't.
But all of this can't be done on a simple VM architecture. And for a given VM architecture I think an interpreter is always simpler than a compiler.
One of my stretch goals for the forever-platform is for it to be independently and compatibly reimplementable from the spec, that is, without access to a working implementation to test against, ideally within a few hours (as with Nguyen and Kay's "fun afternoon hack" desideratum for Chifir). There are indeed 300+ RISC-V implementations, but they aren't independent in the way the implementations of the UM were; the authors had not only a body of RISC-V software to work from but also other implementations of RISC-V to test the software on. But for Rosetta-Stone-level archival, we want the programmer-archaeologist to be able to get their implementation working even though they don't have an existing implementation to test against.
UM is a demonstration that this goal is achievable, if you're willing to accept that ceiling of 0.04% of native performance for the straightforward interpreter you'd write as a fun afternoon hack.
The hope with vector operations is that they give you an extra three orders of magnitude in inner-loop performance, without stretching the implementation task beyond what's achievable as a "fun afternoon hack", and without introducing so much ambiguity and so many tricky corner cases in the spec that in practice a given "ROM" will not run on an independent reimplementation. I don't know if I'll find a way to do it or not. But that's the objective.
And that's why I've been wrestling with SIMD, and don't think it's just a distraction.
So, thank you very much for the links to the relevant efforts! Oh dear, though, the V1.0 version of RVV is 111 pages, longer than the entire RV32/RV64 unprivileged spec.
- sitkack 4y agoThe Rosseta-Stone spec needs to have an executable test, otherwise how do you know it works? Even the software you want to get running is a sort of a test, you just need test oracles. > And that's why I've been wrestling with SIMD, and don't think it's just a distraction. I think in this instance, Wasm 128b SIMD is a distraction. I agree with everything you have said, and your goals. Wasm 128b SIMD was a stop-gap and distracts from what ultimately will be a much better solution (vector processing). It is the lowest common denominator (128b width registers) impl that they could come up with to satisfy necessary immediate perf needs. It does get good speedups on code right now, but it more than doubles the number of Wasm opcodes. It isn't tenable to have the same 128 -> 256 -> 512 path that CPUs have taken. Implementation complexity and having to recode software everytime the SIMD registers change shape is lame. CPU vendors are totally ok having a needless upgrade train. The future is the past with vector processing, like RVV and flexible vectors. For archival software, I'd argue that SIMD doesn't matter. I don't think it is fare to compare RVV against the base ISA spec, the base ISA spec is trying to be the simplest possible thing, it is just a bootloader for RVV and custom instructions. Being able to extract parallelism is way more important than constant factors, even for pathologically slow systems like Python. Thread counts for single socket systems are already at 256. One could probably implement Quake 3 in PyPy, maybe even CPython now and hit 60 FPS. CPython could definitely run Quake 1. Wasm does support threads now. https://web.dev/webassembly-threads/ https://web.dev/webassembly-threads/ Wasm SIMD didn't even need to exist, the AST could have been encoded in a call graph that could have executed a fallback implementation, or been converted to local SIMD. It could have all just been function calls, like a binary intrinsic. It didn't really need an instruction set extension. You could encode a vector program, or something shader like in a binary wasm call graph. I love that you use Moore Units in your comparisons, rarely do folks do this. When folks argue over 4% difference for some aspect of safety, they are talking about weeks of relative performance on a Moore Scale. But no amount of concrete performance gains will allow them to have safety or correctness. They are content to live in a ghetto all driving fast cars.
- sitkack 4y agoInteresting paper on a formally generated Wasm interpreter. https://github.com/WasmCert/WasmCert-Isabelle https://github.com/WasmCert/WasmCert-Isabelle Mechanising and Verifying the WebAssembly Specification https://www.cl.cam.ac.uk/~caw77/papers/mechanising-and-verifying-the-webassembly-specification.pdf https://www.cl.cam.ac.uk/~caw77/papers/mechanising-and-verif...