如何分析z3性能问题？

Question

我有 37 个类似的 SMT2 问题，每个问题都有两个可满足的版本，我称之为 compact 和 unrolled。这些问题正在使用增量 SMT 求解和每个 (check-sat) returns unsat。压缩版本使用 QF_AUFBV 逻辑，展开版本使用 QF_ABV。我在 z3、yices 和 boolector 中做了运行它们（但 boolector 只支持展开的版本）。可以在此处找到此性能评估的结果：

http://scratch.clifford.at/compact_smt2_enc_r1102.html

可从此处下载此示例的 SMT2 文件 (~10 MB)：

http://scratch.clifford.at/compact_smt2_enc_r1102.zip

I 运行每个求解器 5 次，:random-seed 选项具有不同的值。（不支持 :random-seed 的 boolector 除外。所以我在同一输入上简单地运行 boolector 5 次。）当运行使用不同的 :random-seed 求解器时，我得到的变化相对较小（请参阅 table 中的 +/- 值以了解最大离群值）。

求解器之间存在广泛的差异。 Boolector 和 Yices 始终比 z3 快，在某些情况下高达两个数量级。

但是，我的问题是关于 "z3 vs z3" 性能。例如考虑以下数据点：

| Test Case         | Z3 Median Runtime | Max Outlier |
|-------------------|-------------------|-------------|
| insn_add unrolled |    873.35 seconds |     +/-  0% |
| insn_add compact  |   1837.59 seconds |     +/-  1% |
| insn_sub unrolled |   4395.67 seconds |     +/- 16% |
| insn_sub compact  |   2199.21 seconds |     +/-  5% |

问题insn_add和insn_sub几乎相同。两者都是使用 Yosys 从 Verilog 生成的，唯一的区别是 insn_add 使用 this Verilog module and insn_sub is using this one 代替。这是这两个源文件之间的差异：

--- insn_add.v  2017-01-31 15:20:47.395354732 +0100
+++ insn_sub.v  2017-01-31 15:20:47.395354732 +0100
@@ -1,6 +1,6 @@
 // DO NOT EDIT -- auto-generated from generate.py

-module rvfi_insn_add (
+module rvfi_insn_sub (
   input                                rvfi_valid,
   input [                32   - 1 : 0] rvfi_insn,
   input [`RISCV_FORMAL_XLEN   - 1 : 0] rvfi_pc_rdata,
@@ -29,9 +29,9 @@
   wire [4:0] insn_rd     = rvfi_insn[11: 7];
   wire [6:0] insn_opcode = rvfi_insn[ 6: 0];

-  // ADD instruction
-  wire [`RISCV_FORMAL_XLEN-1:0] result = rvfi_rs1_rdata + rvfi_rs2_rdata;
-  assign spec_valid = rvfi_valid && insn_funct7 == 7'b 0000000 && insn_funct3 == 3'b 000 && insn_opcode == 7'b 0110011;
+  // SUB instruction
+  wire [`RISCV_FORMAL_XLEN-1:0] result = rvfi_rs1_rdata - rvfi_rs2_rdata;
+  assign spec_valid = rvfi_valid && insn_funct7 == 7'b 0100000 && insn_funct3 == 3'b 000 && insn_opcode == 7'b 0110011;
   assign spec_rs1_addr = insn_rs1;
   assign spec_rs2_addr = insn_rs2;
   assign spec_rd_addr = insn_rd;

但他们在这个基准测试中的行为非常不同：总体而言，insn_sub 的性能比 insn_add 的性能差得多。此外，在 insn_add 的情况下，展开版本运行s 大约是压缩版本的两倍，但在 insn_sub 的情况下，压缩版本运行s 大约两倍与展开版本一样快。

这是创建中位数之前的时间。 :random-seed 设置显然似乎没有太大区别：

insn_add unrolled:  868.15  873.34  873.35  873.36  874.88
insn_add compact:  1828.70 1829.32 1837.59 1843.74 1867.13
insn_sub unrolled: 3204.06 4195.10 4395.67 4539.30 4596.05
insn_sub compact:  2003.26 2187.52 2199.21 2206.04 2209.87

由于 :random-seed 的值似乎没有太大影响，我认为这些 .smt2 文件有一些固有的东西使它们在 z3 上变快或变慢。 我该如何调查？我如何找出是什么让快的情况变快而慢的情况变慢，这样我就可以避免让慢的情况变慢的原因？（是的，我知道这是一个非常广泛的问题。抱歉。:)

<编辑>

根据我的主要问题，这里有一些更具体的问题。这个问题直接受到我在（紧凑）insn_add 和 insn_sub 基准测试之间看到的明显差异的启发。

我的 SMT 输入中 (declare-..) 和 (define-..) 语句的顺序会影响性能吗？
更改声明或定义函数的名称会影响性能吗？
如果我将一个 BV 拆分成更小的 BV，然后再将它们连接起来，这会影响性能吗？
如果我比较两个 BV 是否相等，或者将 BV 拆分为单个位变量并单独比较每个位，这会影响性能吗？
此外：当我为 :random-seed 选择不同的值时，z3 中的哪些操作实际上发生了变化？

在不改变语义的情况下对 .smt2 文件进行微小的更改对于复杂工具生成的大型测试用例来说可能非常困难。我希望我可以先尝试其他事情，或者可能有一些关于可能值得研究的变化的现有专家知识。或者：什么样的更改实际上等同于更改 :random-seed，因此不值得研究。

（使用 git rev c67cf16 执行的测试，即 AWS EC2 c4.8xlarge 实例上 z3 的当前 git 头 make -j40。运行次是CPU 秒，不是挂钟秒。）

编辑 2：

我现在有三个测试用例（test1.smt2、test2.smt2 和 test3.smt2），它们 相同，只是我重命名了一些函数declare/define。可以在 http://svn.clifford.at/handicraft/2017/z3perf/.

找到测试用例

这是原始问题的变体，需要大约 2 分钟而不是大约 1 小时来解决。和以前一样，更改 :random-seed 的值只会产生边际效应。但是在不改变任何其他东西的情况下重命名一些函数会使运行time 改变超过 2x:

我现在 opened an issue on github 认为，当我在 SMT2 代码中重命名函数时，:random-seed 应该绑定到我在 z3 中随机更改的任何内容。

Answer 1

正如您所说，可能有很多因素会造成添加与子之间的性能差异。一个好的开始是检查预处理后的公式是否等于模 add/sub（顺便说一句，Z3 将 'a - b' 转换为 'a + (-1) * b'）。如果不是，则追查哪个预处理步骤有问题。然后追查问题并向我们发送补丁 :)

或者，问题可能出在生产线上，例如，在 bitblaster 中。您还可以转储两个文件的位爆破公式，并检查变量 and/or 子句的数量是否存在显着差异。

无论如何，您需要准备好花一两天（也许更多）时间来追踪这些问题。如果您发现了什么，请告诉我们 and/or 给我们发送补丁！ :)

如何分析z3性能问题？

How to analyse z3 performance issues?

smt

z3