Made ordered() calls faster for large expressions #20635
Conversation
|
✅ Hi, I am the SymPy bot (v161). I'm here to help you write a release notes entry. Please read the guide on how to write release notes. Your release notes are in good order. Here is what the release notes will look like: This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.9. Click here to see the pull request description that was parsed.
Update The release notes on the wiki have been updated. |
|
It seems there are multiple core test failures in modules other than |
|
It looks like most of the failures are for the same thing. There is some use of |
|
A rather crude workaround in the newly added Second issue here is the rather strange behavior of sympy/sympy/core/operations.py Line 499 in eb926a1 It fails some tests in |
There is a deep bug here somehow. I tried the diff: diff --git a/sympy/core/operations.py b/sympy/core/operations.py
index a6c0b92f2b..fa0d3e973d 100644
--- a/sympy/core/operations.py
+++ b/sympy/core/operations.py
@@ -496,7 +496,7 @@ def __new__(cls, *args, **options):
else:
# XXX in almost every other case for __new__, *_args is
# passed along, but the expectation here is for _args
- obj = super(AssocOp, cls).__new__(cls, _args)
+ obj = super(AssocOp, cls).__new__(cls, *_args)
obj._argset = _args
return objWith that running gives different random failures each time I run it. Random failures like this could be due to set ordering. I can reproduce the problem semi-reliably by running this test in particular: $ pytest sympy/logic/tests/test_boolalg.py -k test_to_nnf
====================================================== test session starts =======================================================
platform darwin -- Python 3.8.5, pytest-6.2.0, py-1.10.0, pluggy-0.13.1
architecture: 64-bit
cache: no
ground types: python
rootdir: /Users/enojb/current/sympy/sympy, configfile: pytest.ini
plugins: xdist-2.1.0, cov-2.10.1, doctestplus-0.8.0, forked-1.3.0
collected 71 items / 70 deselected / 1 selected
sympy/logic/tests/test_boolalg.py F [100%]
============================================================ FAILURES ============================================================
__________________________________________________________ test_to_nnf ___________________________________________________________
def test_to_nnf():
assert to_nnf(true) is true
assert to_nnf(false) is false
assert to_nnf(A) == A
assert to_nnf(A | ~A | B) is true
assert to_nnf(A & ~A & B) is false
assert to_nnf(A >> B) == ~A | B
assert to_nnf(Equivalent(A, B, C)) == (~A | B) & (~B | C) & (~C | A)
> assert to_nnf(A ^ B ^ C) == \
(A | B | C) & (~A | ~B | C) & (A | ~B | ~C) & (~A | B | ~C)
E assert (A | B | C) & (A | ~B | ~C) & (B | ~A | ~C) & (C | ~A | ~B) == (((((A | B) | C) & ((~A | ~B) | C)) & ((A | ~B) | ~C)) & ((~A | B) | ~C))
E + where (A | B | C) & (A | ~B | ~C) & (B | ~A | ~C) & (C | ~A | ~B) = to_nnf(((A ^ B) ^ C))
sympy/logic/tests/test_boolalg.py:506: AssertionError
======================================================== warnings summary ========================================================
../38venv/lib/python3.8/site-packages/_pytest/config/__init__.py:1233
/Users/enojb/current/sympy/38venv/lib/python3.8/site-packages/_pytest/config/__init__.py:1233: PytestConfigWarning: Unknown config option: doctestplus
self._warn_or_fail_if_strict(f"Unknown config option: {key}\n")
-- Docs: https://docs.pytest.org/en/stable/warnings.html
DO *NOT* COMMIT!
==================================================== short test summary info =====================================================
FAILED sympy/logic/tests/test_boolalg.py::test_to_nnf - assert (A | B | C) & (A | ~B | ~C) & (B | ~A | ~C) & (C | ~A | ~B) == (...
========================================== 1 failed, 70 deselected, 1 warning in 0.34s =========================================== |
|
Looks like a few more changes are needed to fix it: diff --git a/sympy/core/operations.py b/sympy/core/operations.py
index a6c0b92f2b..7164faa03d 100644
--- a/sympy/core/operations.py
+++ b/sympy/core/operations.py
@@ -494,9 +494,7 @@ def __new__(cls, *args, **options):
elif len(_args) == 1:
return set(_args).pop()
else:
- # XXX in almost every other case for __new__, *_args is
- # passed along, but the expectation here is for _args
- obj = super(AssocOp, cls).__new__(cls, _args)
+ obj = super(AssocOp, cls).__new__(cls, *ordered(_args))
obj._argset = _args
return obj
@@ -524,13 +522,6 @@ def make_args(cls, expr):
else:
return frozenset([sympify(expr)])
- # XXX: This should be cached on the object rather than using cacheit
- # Maybe _argset can just be sorted in the constructor?
- @property # type: ignore
- @cacheit
- def args(self):
- return tuple(ordered(self._argset))
-
@staticmethod
def _compare_pretty(a, b):
return (str(a) > str(b)) - (str(a) < str(b))
diff --git a/sympy/functions/elementary/miscellaneous.py b/sympy/functions/elementary/miscellaneous.py
index 3e958c55f8..8466fe0ab5 100644
--- a/sympy/functions/elementary/miscellaneous.py
+++ b/sympy/functions/elementary/miscellaneous.py
@@ -1,6 +1,7 @@
from sympy.core import Function, S, sympify
from sympy.core.add import Add
from sympy.core.containers import Tuple
+from sympy.core.compatibility import ordered
from sympy.core.operations import LatticeOp, ShortCircuit
from sympy.core.function import (Application, Lambda,
ArgumentIndexError)
@@ -405,7 +406,7 @@ def __new__(cls, *args, **assumptions):
# base creation
_args = frozenset(args)
- obj = Expr.__new__(cls, _args, **assumptions)
+ obj = Expr.__new__(cls, *ordered(_args), **assumptions)
obj._argset = _args
return objI haven't timed that to see how it compares. |
sympy/core/compatibility.py
Outdated
| def _node_count(e): | ||
| if hasattr(e,'args'): | ||
| return 1 + sum(map(_node_count, e.args)) | ||
| elif isinstance(e, int): | ||
| return 0 |
There was a problem hiding this comment.
We only call this _node_count function if e is an instance of Basic. That should mean that it is guaranteed to have .args that are also all Basic. The hasattr above shouldn't be necessary and it shouldn't be possible for e to be an int. I think these are both workarounds covering up bugs.
Can you show examples where the hasattr and the elif etc are needed?
There was a problem hiding this comment.
In the stats module there are many instances of function objects being in the .args list (Formerly these were counted as 0 in the preorder traversal of e.count(Basic) ) . An example is the core test of stats\test\test_stochastic_process.py
sympy/stats/tests/test_stochastic_process.py:515:
assert P(X(t) < 1) == exp(-3*t)
sympy/stats/rv.py:809: in probability
return Probability(condition, given_condition).doit(**kwargs)
sympy/stats/symbolic_probability.py:75: in doit
return pspace(condition).probability(condition, given_condition,
sympy/stats/stochastic_process.py:53: in probability
return self.process.probability(condition, given_condition, evaluate, **kwargs)
sympy/stats/stochastic_process_types.py:2104: in probability
return _SubstituteRV._probability(condition, evaluate=evaluate, **kwargs)
sympy/stats/stochastic_process_types.py:1820: in _probability
new_condition, new_givencondition = self._rvindexed_subs(condition, given_condition)
sympy/stats/stochastic_process_types.py:1755: in _rvindexed_subs
expr = expr.subs(swapdict_expr)
sympy/core/basic.py:921: in subs
k = list(ordered(sequence, default=False, keys=(
sympy/core/compatibility.py:589: in ordered
d[f(a)].append(a)
sympy/core/basic.py:922: in <lambda>
lambda x: -_nodes(x),
sympy/core/compatibility.py:492: in _nodes
assert _node_count(e)==e.count(Basic)
sympy/core/compatibility.py:476: in _node_count
return 1 + sum(map(_node_count, e.args))
sympy/core/compatibility.py:476: in _node_count
return 1 + sum(map(_node_count, e.args))
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
e = <bound method PoissonProcess.distribution of PoissonProcess(X, 3)>
def _node_count(e):
> return 1 + sum(map(_node_count, e.args))
E AttributeError: 'function' object has no attribute 'args'
Also there was an instance of an int object in the core test unify\test\test_sympy.py . This is a singular occurence and probably a bug.
def test_FiniteSet_complex():
from sympy import FiniteSet
a, b, c, x, y, z = symbols('a,b,c,x,y,z')
> expr = FiniteSet(Basic(1, x), y, Basic(x, z))
sympy/unify/tests/test_sympy.py:127:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
sympy/sets/sets.py:1778: in __new__
for i in reversed(list(ordered(args))):
sympy/core/compatibility.py:608: in ordered
yield from d[k]
sympy/core/compatibility.py:589: in ordered
d[f(a)].append(a)
sympy/core/compatibility.py:492: in _nodes
assert _node_count(e)==e.count(Basic)
sympy/core/compatibility.py:476: in _node_count
return 1 + sum(map(_node_count, e.args))
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
e = 1
def _node_count(e):
> return 1 + sum(map(_node_count, e.args))
E AttributeError: 'int' object has no attribute 'args'
Intrestingly I just found out returning 0 or 1 for either of the function orint objects didn't make any difference (all core tests passed in both cases). But the current e.count(Basic) returns them as 0 so probably these might be part of a bug or might be intended logic which e.count(Basic) covers up for by returning 0 for them, given that only instances of Basic are allowed in the .args of Basic
There was a problem hiding this comment.
There are also few instances of NoneType being returned in stats\test\test_stochastic_process.py
> assert P(Eq(Y[3], 2), Eq(Y[1], 1) & TransitionMatrixOf(Y, TO)).round(3) == Float(0.375, 3)
sympy/stats/tests/test_stochastic_process.py:90:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
sympy/core/decorators.py:266: in _func
return func(self, other)
sympy/logic/boolalg.py:70: in __and__
return And(self, other)
sympy/core/operations.py:489: in __new__
_args = frozenset(cls._new_args_filter(args))
sympy/logic/boolalg.py:685: in _new_args_filter
for x in ordered(args):
sympy/core/compatibility.py:607: in ordered
yield from d[k]
sympy/core/compatibility.py:588: in ordered
d[f(a)].append(a)
sympy/core/compatibility.py:491: in _nodes
assert _node_count(e)==e.count(Basic)
sympy/core/compatibility.py:476: in _node_count
return 1 + sum(map(_node_count, e.args))
sympy/core/compatibility.py:476: in _node_count
return 1 + sum(map(_node_count, e.args))
sympy/core/compatibility.py:476: in _node_count
return 1 + sum(map(_node_count, e.args))
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
e = None
def _node_count(e):
> return 1 + sum(map(_node_count, e.args))
E AttributeError: 'NoneType' object has no attribute 'args'
Again returning these cases as 1 or 0 still passed the test but e.count(Basic) returned them as 0.
There was a problem hiding this comment.
Is that something like #20078 (comment)
I think some part of this is being fixed in #20626
There was a problem hiding this comment.
This is why it's good that we don't cover over things like this so that these mistakes are picked up early.
There was a problem hiding this comment.
You're right, I'll remove the check.
#20626 this will fix the bugs in stats but the int instance in unify still persists.
There was a problem hiding this comment.
I think that test can just be changed to Basic(S(1), x).
There was a problem hiding this comment.
Alright I made the necessary changes.
Basic(S(1), x)
I added this for now. Perhaps later we could add the ability to internally convert int instances to sympy's Integer() if passed like in the original test.
There was a problem hiding this comment.
The problem is that most of the time the args are already Basic so sympifying them would be mostly unnecessary and would slow a lot of things down. It would be better if we had a way of testing this without actually having the checks at runtime.
It's considerably faster. Result for this example. Upon running on current codebase : After this Fix : |
|
To be closed and opened again for restarting tests after #20626 is merged and see if the underlying issues in |
|
Restarted all jobs. |
|
One of the failing test in current PR seems to be random ( similar to those which were caused by The test is : The pytest stack trace is as follows : |
|
The failure I see is That seems to fail 50% of the time. |
|
The issue pointed out here #20635 (comment) seems to be arising from typecasting a list of arguments (which are always in same order) into Line 628 in 8f29f03 Which ultimately leads us to here: sympy/sympy/core/operations.py Lines 499 to 501 in 8f29f03 It almost seems like the newly added |
|
Yes, # t.py
from sympy import *
from sympy.abc import x
s = frozenset([Q.real(x), Q.positive(x)])
print(list(ordered(s)))That gives: $ python t.py
[Q.real(x), Q.positive(x)]
$ python t.py
[Q.positive(x), Q.real(x)]The result is different in different processes because it depends on set ordering. I guess that the problem is this: In [1]: p1 = Q.positive(x)
In [2]: p2 = Q.real(x)
In [3]: type(p1)
Out[3]: sympy.assumptions.assume.AppliedPredicate
In [4]: type(p1) == type(p2)
Out[4]: True
In [5]: p1.args == p2.args
Out[5]: TrueIn general two I think that the "new" design for Predicate should fix this although |
|
If the problem comes from that |
|
Yes, it is because of the args. |
|
After every old predicates are migrated, I will remove |
|
I'm afraid that fixing |
It shouldn't be necessary to change |
|
Some tests are failing on this. |
|
@oscarbenjamin Does this look OK? |
|
It looks good to me although it shouldn't be listed as fixing the issue because |
|
Then I'll edit the OP and merge this. |
References to other Issues or PRs
Related to #20359
Brief description of what is fixed or changed
Added changes suggested by @oscarbenjamin in the issue page.
Release Notes