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

Symbolic implementation of update needlessly bit-blasts index argument #579

Closed
brianhuffman opened this issue Mar 4, 2019 · 0 comments
Closed
Assignees
Labels
exponential slowdown Extreme performance problems

Comments

@brianhuffman
Copy link
Contributor

This proof command takes about 5 seconds with Z3 before returning a counterexample. (Much of this time is actually spent in Cryptol preparing to send the proof to z3, not in the prover itself).

:prove \(xs:[1024][8]) (i:[10]) -> update xs i 0 == xs

On the other hand, the same proof command with this alternative definition is about 10 times faster:

update' : {n, a, i} (fin n, fin i, 2^^i >= n) => [n]a -> [i] -> a -> [n]a
update' xs i y = [ if i == j then y else x | x <- xs | j <- [0...] ]

Using :set prover=offline shows that the first version produces a much larger smt output, and makes big mux-trees based on the bits of the index. The second version is much simpler, and only does equality comparisons on the index value.
We should reimplement the update primitive in the symbolic backend so that it avoids bit-blasting the index value.

@brianhuffman brianhuffman self-assigned this Mar 4, 2019
@brianhuffman brianhuffman added the exponential slowdown Extreme performance problems label Mar 4, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
exponential slowdown Extreme performance problems
Projects
None yet
Development

No branches or pull requests

1 participant