initial commit

1 files changed, 130 insertions, 0 deletions

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..081ccaf
--- /dev/null
+++ b/README.md
@@ -0,0 +1,130 @@
+# Prospero challenge with `ejit`
+
+This is my implementation of the
+[prospero](https://www.mattkeeter.com/projects/prospero/) challenge using
+[`ejit`](https://metanimi.dy.fi/cgit/ejit/).
+
+As a quick introduction, here's an excerpt from the `ejit` README:
+
+> `ejit` is a generic JIT/bytecode interpreter with a
+> strong focus on compilation speed and portability. It's built on top of the
+> excellent [`lightening`](https://gitlab.com/wingo/lightening) pure JIT library,
+> but adds a bytecode layer for systems that `lightening` doesn't support. The
+> bytecode layer also grants some QoL improvements, such as an (effectively)
+> unlimited number of virtual registers and a register allocator for mapping
+> theses virtual registers down to physical registers and a slightly easier to use
+> API (at least IMO).
+
+`ejit` is primarily inteded to be used as the main execution engine for
+experimental/toy scripting languages, so the **prospero** challenge is arguably
+a bit outside the intended use case of relatively heavy computation. Still,
+this was a good opportunity to see just how well/poorly the library can handle
+such tasks.
+
+## Running
+
+```
+git submodule update --init --recursive
+make
+```
+
+The produced binary has a few command line parameters:
+
+> usage: prospero [-j threads] [-r resolution] [-c]
+>  -j how many threads to run
+>  -r length of one side
+>  -c enable JIT
+
+By default, the binary runs a single worker thread, produces an image of size
+1024x1024 and does not enable the JIT part of `ejit`.
+
+## Results
+
+Here are some runtime results for when the JIT compiler is enabled:
+
+| Params  | Runtime for JIT (s) |
+|---------|---------------------|
+| -j1  -c | 8.943               |
+| -j2  -c | 4.357               |
+| -j6  -c | 1.678               |
+| -j12 -c | 1.617               |
+
+I have an AMD Ryzen 5 5600X with 6 cores and 12 threads. I was kind of surprised
+that `-j12` wasn't any faster than `-j6`, but if I had to guess as to why,
+presumably there are only so many physical floating point units (FPUs) and when
+more than 6 threads start running, they have to start sharing FPUs and threads
+start stalling each other. Maybe, I haven't looked into the pipeline of my
+processor to know for sure.
+
+I was also curious to see how the bytecode interpreter fared, since the main
+focus of `ejit` is for the JIT to be efficient, and the bytecode is mainly as a
+backup for more obscure hardware. Here's are some runtime results for when the
+JIT compiler is disabled:
+
+| Params | Runtime for bytecode (s) |
+|--------|--------------------------|
+| -j1    | 35.311                   |
+| -j2    | 18.514                   |
+| -j6    | 6.155                    |
+| -j12   | 3.760                    |
+
+In this case, I'm guessing that there's enough overhead during interpretation
+that adding threads beyond the number of physical cores still improves
+performance. Interpretation is something mainly done with integer ALUs, which I
+guess my CPU has more of than FPUs?
+
+Still, very interesting results. For reference, I ran [Aviva
+Ruben](https://whtwnd.com/aviva.gay/3ll5dbskg3v26)'s Cranelift implementation
+which finished in `0.241` seconds when using all threads (I believe
+`into_par_iter()` uses threads, anyway...). Very impressive! Cranelift is
+particularly cool in that it exposes SIMD instructions, which `ejit` does not
+have.
+
+To roughly compare the compilation speed of `ejit` with JIT enabled vs.
+Cranelift, setting the resolution of the generated image to 1 gives the
+following table:
+
+| Framework | Total runtime (s) |
+|-----------|-------------------|
+| Cranelift | 0.088             |
+| `ejit`    | 0.004             |
+
+This runtime is not quite the same as the compilation time, but the compilation
+should be the dominating factor in this case. There's a fairly obvious tradeoff
+here, Cranelift can produce much faster code (especially if you can take advantage
+of SIMD operations), whereas `ejit` can produce machine code much faster. This
+is what I was expecting, but it's nice to see some (semi)hard numbers.
+
+## Limitations of `ejit` for this particular challenge
+
+As previously stated, not having SIMD instructions hurts performance
+significantly. I've been thinking about how SIMD could be implemented, but
+nothing concrete yet. There's a lot more variability in SIMD implementations than
+base ISAs, and it seems to be rather difficult to be generic over any large-ish
+portion of them. [`sljit`](https://github.com/zherczeg/sljit) takes the approach
+that the user can place custom instructions into the instruction stream and
+implement SIMD for specific platforms, which is cool, but is kind of at
+odds with the 'portability' aspect of `ejit` that I would like to maintain as
+far as possible.
+
+`ejit` also has at least so far had less of a focus on floating point
+instructions, and `max`/`min` were implemented with branches because `ejit`
+simply doesn't have any built-in equivalent instructions. `sqrt` I had implement
+as a function call to `libm`, which seems kind of silly if we're going for top
+performance. Square roots seem to be fairly common in `prospero.vm` as well,
+probably compounding the problem. Then again, these operations are rather
+mathematical and I'm not sure how useful they are for 'typical' scripting
+languages, which, again, is more what `ejit` is aimed towards. I'm not in a huge
+rush to start implementing these operations as built-ins quite yet, but
+definitely something to think about.
+
+I also noticed that in `prospero.vm` a lot of variables are only used once. The
+current register allocator in `ejit` assigns a variable to a register 'forever',
+meaning that the vast majority of all variables in `prospero.vm` get placed on
+the stack. This is unfortunate, but would require something like [Static Single
+Assignment (SSA)](https://en.wikipedia.org/wiki/Static_single-assignment_form)
+to properly tackle, which I suspect would increase compilation times
+dramatically. It might be possible to get by with some kind of simple lifetime
+tracking scheme which would save on compilation time, but I'm not convinced the
+register allocations would be significantly better than the current scheme.
+Something to keep in mind for the future, though.