search

0xPolygonMiden / miden-vm

STARK-based virtual machine
MIT License
611 stars 148 forks source link

Implement table-based MAST #1349

Closed plafer closed 2 weeks ago

plafer commented 1 month ago

Closes #1217

plafer commented 3 weeks ago

Note: we're probably going to want to rename Operation::{Span, Respan}, but I'm not sure what these should be.

bobbinth commented 3 weeks ago

Oh - and let's also update the changelog.

plafer commented 2 weeks ago

Oh - and let's also update the changelog.

Done.

Given some info you listed in one of the previous comments, I'm expecting cycle count and execution time to double (because we are no longer merging basic blocks) - but would be good to confirm this.

It can get much worse than 2x. I think the worst case scenario is with repeat, where all iterations used to get combined into a single basic block, but not instead each iteration is a separate basic block (joined by a tree of JOINs).

Our generate_fibonacci_program() is exactly this. For a repeat.16 instantiation of the program,

A ~5x increase in pre-padding trace length.

plafer commented 2 weeks ago

@bitwalker was the purpose of this line (#[cfg(feature = "nope")]) to disable the tests? Currently, the code in there no longer compiles, as it is not tracked neither by the compiler nor rust-analyzer. Should I remove it?

bobbinth commented 2 weeks ago

I think all looks good here. There are a couple of small questions for @bitwalker (i.e., this one and this one) - but other than that, we should be good to merge.

bitwalker commented 2 weeks ago

@bitwalker was the purpose of this line (#[cfg(feature = "nope")]) to disable the tests? Currently, the code in there no longer compiles, as it is not tracked neither by the compiler nor rust-analyzer. Should I remove it?

@plafer I'm actually not 100% sure why that is still in there, I use that fake feature trick to disable a section of code temporarily, but never as a permanent thing. That said, I'm pretty sure the end goal was to remove that code entirely, because the serialization referred to there is basically DOA - we're switching to MAST, so serializing the Miden Assembly syntax tree isn't important. In fact, we probably should just remove all of the serialization-related code from the assembly crate once the MAST refactoring is complete, for now it is still used by the code that emits .masl files (which itself is going away, once the new package format is finalized).

plafer commented 2 weeks ago

I'm actually not 100% sure why that is still in there, I use that fake feature trick to disable a section of code temporarily, but never as a permanent thing.

Removed the disabled tests; we can remove any other test that still needs to be removed in the next PR