Why is Z3 slow for tiny search space?

Question

I'm trying to make a Z3 program (in Python) that generates boolean circuits that do certain tasks (e.g. adding two n-bit numbers) but the performance is terrible to the point where a brute-force search of the entire solution space would be faster. This is my first time using Z3 so I could be doing something that impacts my performance, but my code seems fine.

The following is copied from my code here:

from z3 import *

BITLEN = 1 # Number of bits in input
STEPS = 1 # How many steps to take (e.g. time)
WIDTH = 2 # How many operations/values can be stored in parallel, has to be at least BITLEN * #inputs

# Input variables
x = BitVec('x', BITLEN)
y = BitVec('y', BITLEN)

# Define operations used
op_list = [BitVecRef.__and__, BitVecRef.__or__, BitVecRef.__xor__, BitVecRef.__xor__]
unary_op_list = [BitVecRef.__invert__]
for uop in unary_op_list:
    op_list.append(lambda x, y : uop(x))

# Chooses a function to use by setting all others to 0
def chooseFunc(i, x, y):
    res = 0
    for ind, op in enumerate(op_list):
        res = res + (ind == i) * op(x, y)
    return res

s = Solver()
steps = []

# First step is just the bits of the input padded with constants
firststep = Array("firststep", IntSort(), BitVecSort(1))
for i in range(BITLEN):
    firststep = Store(firststep, i * 2, Extract(i, i, x))
    firststep = Store(firststep, i * 2 + 1, Extract(i, i, y))
for i in range(BITLEN * 2, WIDTH):
    firststep = Store(firststep, i, BitVec("const_0_%d" % i, 1))
steps.append(firststep)

# Generate remaining steps
for i in range(1, STEPS + 1):
    this_step = Array("step_%d" % i, IntSort(), BitVecSort(1))
    last_step = steps[-1]

    for j in range(WIDTH):
        func_ind = Int("func_%d_%d" % (i,j))
        s.add(func_ind >= 0, func_ind < len(op_list))

        x_ind = Int("x_%d_%d" % (i,j))
        s.add(x_ind >= 0, x_ind < WIDTH)

        y_ind = Int("y_%d_%d" % (i,j))
        s.add(y_ind >= 0, y_ind < WIDTH)

        node = chooseFunc(func_ind, Select(last_step, x_ind), Select(last_step, y_ind))
        this_step = Store(this_step, j, node)

    steps.append(this_step)

# Set the result to the first BITLEN bits of the last step
if BITLEN == 1:
    result = Select(steps[-1], 0)
else:
    result = Concat(*[Select(steps[-1], i) for i in range(BITLEN)])

# Set goal
goal = x | y
s.add(ForAll([x, y], goal == result))

print(s)
print(s.check())
print(s.model())

The code basically lays out the inputs as individual bits, then at each "step" one of 5 boolean functions can operate on the values from the previous step, where the final step represents the end result.

In this example, I generate a circuit to calculate the boolean OR of two 1-bit inputs, and an OR function is available in the circuit, so the solution is trivial.

I have a solution space of only 5*5*2*2*2*2=400:

• 5 Possible functions (two function nodes)
• 2 Inputs for each function, each of which has two possible values

This code takes a few seconds to run and provides a correct answer, but I feel like it should run instantaneously as there are only 400 possible solutions, of which quite a few are valid. If I increase the inputs to be two bits long, the solution space has a size of (5^4)*(4^8)=40,960,000 and never finishes on my computer, though I feel this should be easily doable with Z3.

I also tried effectively the same code but substituted Arrays/Store/Select for Python lists and "selected" the variables by using the same trick I used in chooseFunc(). The code is here and it runs in around the same time the original code does, so no speedup.

Am I doing something that would drastically slow down the solver? Thanks!

Answer 1

You have a duplicated __xor__ in your op_list; but that's not really the major problem. The slowdown is inevitable as you increase bit-size, but on a first look you can (and should) avoid mixing integer reasoning with booleans here. I'd code your chooseFunc as follows:

def chooseFunc(i, x, y):
    res = False;
    for ind, op in enumerate(op_list):
        res = If(ind == i, op (x, y), res)
    return res

See if that improves run-times in any meaningful way. If not, the next thing to do would be to get rid of arrays as much as possible.