Implement optimizations
- Dominant language
- Rust
- Stars
- 6
- Forks
- 1
- PR merge metrics
- No merged PRs in 30d
Description
Currently, the compiler emits entirely unoptimized bytecode. There are tons of optimizations that could be applied.
> [!TIP]
> If you're reading this and want to contribute, I think good ones to start out with below would be "_useless addition,_" "_reuse buffers_," and "_compile-time evaluation of constant expressions_". Or maybe just set up some way to run a profiler to gain some insight on what the worst offender is. :)
Off the top of my head:
- [ ] Useless addition: `[n, 0, add]` should just be `[n]`
- This happens often in cases like `[get_bp, 0, add, load/store]`.
- I _have_ (unintentionally) optimised global variables since their address is constant at the beginning of the stack, meaning no additions have to be performed at all.
- [ ] Loop cleanup instructions. For example `[swap, pop, swap, pop]`, which could be done much more efficiently in Rust-land rather than having to decode and execute 4 separate instructions.
- [ ] Reuse buffers
- I doubt this is a bottleneck at the moment, but it would be beneficial to reuse buffers in the VM rather than constantly allocate new `Vec`s. One example is when multiple arguments are loaded from the stack, they're collected into a vector. But this vector is a one-off that will be discarded after the instruction is done executing. Instead, have a buffer in the VM that is reused every time (meaning only allocated once).
- [ ] Specialised type instructions. Currently, all types on the stack are arbitrary "runtime values". But it's possible (quite often) to analyse the input program statically and determine the type of most values, variables, and functions.
- There could be
- [ ] Statements versus expressions
- Currently _everything_ is an expression, meaning everything leaves a value on the stack. For a sequence of expressions, that causes each expression to leave a value on the stack that is immediately popped again. An optimisation could be to analyse the program statically to see which expressions act as statements, and provide instructions for those that do _not_ leave values on the stack. But I'm assuming this will lead to pretty extreme bloat of instructions.
- [ ] Compile-time evaluation of constant expressions.
- Something like a hardcoded list `[1, 2, 3]` takes O(n) instructions on runtime to evaluate. Instead, we could make a static analyzer that just constructs the value at compile-time. There are two levels to this approach:
1) Just evaluate literals. Easy peasy, just check if everything within the expression is a `Value`
2) For each expression in the AST (bottom-up), attempt to evaluate any constant subtree expression. This would require implementing an interpreter (easy), allowing code execution at compile-time.
- [ ] The extremely spicy one: add an LLVM-based JIT compiler. This probably requires stupendous effort.
- [ ] And many more...
But of course, please use profiling to discover the worst bottlenecks. I saw there's something called _Callgrind_ from Valgrind, which seems super cool - and there's [a Rust crate for it](https://docs.rs/iai-callgrind/latest/iai_callgrind/).
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by profiling the compiler and VM to identify the worst bottleneck, as the issue suggests using Callgrind or the Rust iai-callgrind crate. Then choose and scope one optimization, such as removing useless additions, reusing VM buffers, or evaluating constant expressions at compile time. Done means the selected optimization is implemented and its effect is measured.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 15/100