0xPolygonMiden / miden-vm

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

Optimization of `sys::truncate_stack` procedure in `stdlib` #1334

Open bobbinth opened 1 month ago

bobbinth commented 1 month ago

Our current sys::truncate_stack procedure does quite a bit of unnecessary work. I'm thinking we can improve it as follows:

export.truncate_stack.1
    # save the first word to memory and bring elements to be dropped to the top of the stack
    loc_storew.0 dropw movupw.3
    # => [X, B, C, D, ...]

    # until stack depth greater than 16, keep dropping extra elements
    sdepth neq.16
    while.true
        dropw movupw.3
        # => [X, B, C, D, ...]

        sdepth neq.16
    end
    # => [X, B, C, D, ...]

    # bring the previously saved word back onto the stack
    loc_loadw.0
    # => [A, B, C, D, ...]
end

In cases when stack depth is 20 or smaller, this procedure would take ~20 cycles to execute. For any extra word to be dropped, another ~12 cycles would be required. Compare with the current procedure which would require ~50 cycles to execute in the best case.