Write a guide "How to write small and fast Miden contracts in Rust"

[greenhat]

@mooori mentioned that this topic came up in discussions.

I'm thinking:

1. Avoid memory allocation.
2. Avoid unaligned memory access (avoid small ints like i8 and i16).
3. Avoid Vec and probably other high-level container types. Use arrays.

Felt arithmetic should have near-zero overhead but we want to discourage it (see #999) so I guess we should not promote it here either.

@bitwalker Thoughts?

/cc @bobbinth @Keinberger

[bitwalker]

I think avoiding memory allocation is actually the opposite of what you want to do - because that means you're using the stack instead, and that's going to be a lot more instruction-heavy (lots of copying stuff around) than passing references to heap allocations around.

Beyond that, code size is going to be a function of monomorphization in Rust, so avoiding generics in favor of trait objects is going to likely pay big dividends. The downside is that will almost certainly require indirect call support which we don't have yet.

Lastly, debug/string formatting code in builds will take up a lot of size if it's ultimately unused - we have to strip that out in those cases.

I don't think unaligned accesses are actually an issue - those are handled via intrinsic procedures that only get counted once. Instead, we probably need to consider identifying common stack manipulation opcode sequences, and factoring them out into procedures (which act like metainstructions basically), so we can drastically reduce the code size of programs which use those common sequences frequently. We could extend this to more than just stack manipulation too, but those would be the most profitable to start with IMO.

[greenhat]

I think avoiding memory allocation is actually the opposite of what you want to do - because that means you're using the stack instead, and that's going to be a lot more instruction-heavy (lots of copying stuff around) than passing references to heap allocations around.

I agree. I have not thought about that.

I don't think unaligned accesses are actually an issue - those are handled via intrinsic procedures that only get counted once.

I was thinking in terms of cycle count. Like in a loop or something where the expensive intrinsics get called over and over again.

Instead, we probably need to consider identifying common stack manipulation opcode sequences, and factoring them out into procedures (which act like metainstructions basically), so we can drastically reduce the code size of programs which use those common sequences frequently. We could extend this to more than just stack manipulation too, but those would be the most profitable to start with IMO.

Yep. We could emit those common stack manipulation sequences as procedures.

[bitwalker]

I was thinking in terms of cycle count.

Ah, gotcha. Yeah while prover time is definitely critical, it seems the biggest pain point right now is simply code size, so there's a delicate balancing act in the advice we give. We probably need to provide guidance tailored towards whether you are more concerned about code size, or about prover time.

I'm definitely interested to see if using build-std with build-std-features=optimize_for_size significantly reduces the size of the code we pull in for types like Vec or not - if it does, then we may be able to focus more on the prover time aspect than code size.

Yep. We could emit those common stack manipulation sequences as procedures.

One thing that just occurred to me is that the reason why we'd benefit from extracting macroinstruction procedures from common opcode sequences is due to source locations we attach to every op - the fingerprint associated with subtrees of MAST differs based on decorators (and of primary relevance here is the AssemblyOp decorator that attaches source locations to each op). This fingerprint prevents sharing subtrees of the MAST when the source locations differ, which effectively means we've got a lot of unnecessary duplication (unnecessary in the sense that it exists solely to preserve decorators).

My suspicion is that when the client is computing the size of a MAST forest, it is doing so on forests which still retain quite a bit of duplication due to MAST node fingerprinting. AFAIK, stripping decorators doesn't actually collapse duplicate subtrees, but I could be mistaken on that (cc @huitseeker as he'd know for sure). If that's the case, we're probably wildly overestimating the actual size of the MAST (since there would be virtually no sharing of subtrees due to fingerprinting). I think we would ultimately fix that by moving away from using decorators for debug info entirely, along the lines discussed at the compiler discussion in Cannes. If, however, stripped MAST does collapse duplicate nodes, then this point is mostly moot.

[Keinberger]

Hey guys, I think this would be really useful, due to the account update size limit we discussed.

I think @bitwalker's point about tailoring the advice to code size vs prover time is important: For most builders right now, code size is the more immediate blocker since it prevents deployment entirely (as mentioned in Cannes)

From a docs perspective, I think this fits well as a dedicated guide under the compiler docs (not in the Quick Start, which covers the basics).

Thanks!