search

bastikr / boolean.py

Implements boolean algebra in one module.
BSD 2-Clause "Simplified" License
76 stars 34 forks source link

Performance: prevent blowup in normalization #105

Closed olliemath closed 2 years ago

olliemath commented 3 years ago

This addresses the case where we have an expression which is small when normalized, but in its current form contains large dual expressions. The blowup happens at the _rdistributive step, so the idea is to normalize subexpressions as much as possible before that. Closes https://github.com/bastikr/boolean.py/issues/106

The current test case takes 0.4s with the new code, but took 500s with the old code. We have many of these cases in our codebase and the blow-up is exponential in the size of the original expression. We have tested and this now has reasonable performance with all formulas from our codebase.

The original expression which drew our attention to this issue (below) now takes 30s (~3s under pypy) with the new code and never returns (in fact I run out of memory) with the old code:

        a & (
            (b & c & d & e & f & g)
            | (c & d & f & g & i & j)
            | (c & f & g & h & i & j)
            | (c & f & g & i & j & k)
            | (c & d & f & g & i & n & p)
            | (c & e & f & g & i & m & x)
            | (c & e & f & g & l & o & w)
            | (c & e & f & g & q & s & t)
            | (c & f & g & i & m & n & r)
            | (c & f & g & l & n & o & r)
            | (c & d & f & g & i & l & o & u)
            | (c & e & f & g & i & p & y & ~v)
            | (c & f & g & i & j & z & ~(c & f & g & i & j & k))
            | (
                c & f & g & t
                & ~(b & c & d & e & f & g)
                & ~(c & d & f & g & i & j)
                & ~(c & f & g & h & i & j)
                & ~(c & f & g & i & j & k)
                & ~(c & d & f & g & i & n & p)
                & ~(c & e & f & g & i & m & x)
                & ~(c & e & f & g & l & o & w)
                & ~(c & e & f & g & q & s & t)
                & ~(c & f & g & i & m & n & r)
                & ~(c & f & g & l & n & o & r)
                & ~(c & d & f & g & i & l & o & u)
                & ~(c & e & f & g & i & p & y & ~v)
                & ~(c & f & g & i & j & z & ~(c & f & g & i & j & k))
            )
            | (
                c & f & g & ~t
                & ~(b & c & d & e & f & g)
                & ~(c & d & f & g & i & j)
                & ~(c & f & g & h & i & j)
                & ~(c & f & g & i & j & k)
                & ~(c & d & f & g & i & n & p)
                & ~(c & e & f & g & i & m & x)
                & ~(c & e & f & g & l & o & w)
                & ~(c & e & f & g & q & s & t)
                & ~(c & f & g & i & m & n & r)
                & ~(c & f & g & l & n & o & r)
                & ~(c & d & f & g & i & l & o & u)
                & ~(c & e & f & g & i & p & y & ~v)
                & ~(c & f & g & i & j & z & ~(c & f & g & i & j & k))
            )
        )
pombredanne commented 2 years ago

I am merging this in https://github.com/bastikr/boolean.py/pull/107 ... so I am closing this here

pombredanne commented 2 years ago

Thanks!