[LFSC] Fix performance issues, more determinism
authorAndres Notzli <andres.noetzli@gmail.com>
Tue, 10 Jan 2017 22:23:22 +0000 (01:23 +0300)
committerAndres Notzli <andres.noetzli@gmail.com>
Mon, 16 Jan 2017 10:22:08 +0000 (02:22 -0800)
commitc2be2448c618bbc21ecaa35a681b684c2c802c88
tree445cad2d0df45eda45c3a2f3aeca394079eb15df
parentff498bb43b3d3785bdb894974678e65926de62ab
[LFSC] Fix performance issues, more determinism

For certain proofs, the performance was drastically different on
different OSes. The cause for this difference was a pointer comparison
in the deduplication in `Expr::defeq()`. Depending on how the OS
allocated the memory, an expression `a` would get replaced with an
equivalent expression `b` or vice versa, which in turn affected
performance of `Expr::free_in()` dramatically (sub-second vs. >5 min
running times). This commit makes the process more deterministic by
using a heuristic that favors symbolic expressions and greedily tries to
make small refcounts smaller when replacing, and changes
`Expr::free_in()` to not repeatedly explore the same subexpressions.
proofs/lfsc_checker/expr.cpp
proofs/lfsc_checker/expr.h