Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimization of sys::truncate_stack procedure in stdlib #1334

Open
bobbinth opened this issue May 11, 2024 · 0 comments
Open

Optimization of sys::truncate_stack procedure in stdlib #1334

bobbinth opened this issue May 11, 2024 · 0 comments
Labels
stdlib Related to Miden standard library

Comments

@bobbinth
Copy link
Contributor

bobbinth commented May 11, 2024

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.

@bobbinth bobbinth added the stdlib Related to Miden standard library label May 11, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
stdlib Related to Miden standard library
Projects
None yet
Development

No branches or pull requests

1 participant