Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove args sorting from And and Or? #17087

Open
asmeurer opened this issue Jun 24, 2019 · 5 comments

Comments

Projects
None yet
2 participants
@asmeurer
Copy link
Member

commented Jun 24, 2019

As you can see from #17066 (comment), the sorting in the And and Or constructor (from LatticeOp) can take up a significant amount of time when using large logic expressions.

We should see if we can remove it. The _hashable_content, which is used by __eq__, already uses the frozenset _args, so equality checking would work even if the args order is different. However, it will break any code that expects args to be ordered, or expects the current order, so I do not expect this to be an easy fix.

An important warning here, currently LatticeOp.args is cached. We should remove the cache when testing this. Otherwise the cache will make it so that equal objects always have the same args, and potential test failures will be hidden. The cache wouldn't be needed without sorting anyway. We could just set .args in the constructor.

This is related to #5954, but I think removing the ordering from Add/Mul will be much harder, as they are used everywhere. We should try doing it with the logic classes first, to see what are the issues that come up.

@asmeurer

This comment has been minimized.

Copy link
Member Author

commented Jun 24, 2019

Oh and I forgot to mention that I expect this will not be an easy thing to change. Usually changes like this tend to bring up issues that are difficult to fix. I could be wrong, but a heads up that this is most likely not an easy to fix issue.

@smichr

This comment has been minimized.

Copy link
Member

commented Jun 25, 2019

it will break any code that expects args to be ordered

The only major expectation that I am aware of is that if there is an argument that is a Number in an Add, it is in slot 0. (This applies to Mul, too, but you aren't mentioning that here.)

@asmeurer

This comment has been minimized.

Copy link
Member Author

commented Jun 25, 2019

The expectation would be implicit. The issue is that the same object could appear twice with different arg orderings.

Here's a test failure from making the change

______________________________________________________________________________________________________________
______________________ sympy/logic/tests/test_boolalg.py:test_relational_simplification ______________________
Traceback (most recent call last):
  File "/home/aaronmeurer/Documents/python/sympy/sympy/sympy/logic/tests/test_boolalg.py", line 970, in test_relational_simplification
    assert Or(x >= y, w < z, x <= y).simplify() == S.true
AssertionError

(x, y, z, and w are real=True)

I haven't digged into it, but somehow simplify() isn't handling the different arg ordering correctly.

This is the test change (the real change should probably set args in the constructor as I noted)

diff --git a/sympy/core/operations.py b/sympy/core/operations.py
index 4c37663f4..2d10678f5 100644
--- a/sympy/core/operations.py
+++ b/sympy/core/operations.py
@@ -452,9 +452,8 @@ def make_args(cls, expr):
             return frozenset([sympify(expr)])

     @property
-    @cacheit
     def args(self):
-        return tuple(ordered(self._argset))
+        return tuple(self._argset)

     @staticmethod
     def _compare_pretty(a, b):
@smichr

This comment has been minimized.

Copy link
Member

commented Jun 25, 2019

if there is an argument that is a Number in an Add

Uff -- I read as ADD not AND.

@asmeurer

This comment has been minimized.

Copy link
Member Author

commented Jun 25, 2019

Yes, I'd like to try this first with the logic classes. If we can get it working, we can attempt to do it in the core (#5954). But that will be much harder.

In both instances the sorting is the cause of a significant amount of the time SymPy spends doing various things. Removing the sorting should provide a speed boost everywhere. For the logic classes, it should speed up anything using the new assumptions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.