Speedups for symbolic assumptions

[mkoeppe]

As a follow-up from #30065, we cache GenericDeclaration, maintain the current assumptions as a dictionary instead of a list, and rework GenericDeclaration.assume so it reuses maxima contexts.

The examples from #30065 become near-instantaneous.

The example from #30061, previously 32.8 s, becomes much faster:

sage: %time EuclideanSpace(80)
CPU times: user 1.76 s, sys: 194 ms, total: 1.95 s
Wall time: 1.63 s
80-dimensional Euclidean space E^80

Also ./sage -btp src/sage/symbolic/ src/sage/manifolds/ src/sage/calculus/ shows modest improvements.

[tscrim]

I wonder a little bit if OrderedDict is really the best data structure. It feels like it really should be a set, but I guess OrderedDict has more guaranteed consistency across different sessions. Note that iterating over a set is actually faster:

sage: from collections import OrderedDict
sage: d = OrderedDict()
sage: for i in range(10):
....:     d[i] = None
sage: x = set(range(10))

sage: def test_iter(X):
....:     for i in X:
....:         pass
....: def test_access(X):
....:     for i in range(20):
....:         if i in X:
....:             pass

sage: %timeit test_iter(d)
1000000 loops, best of 5: 293 ns per loop
sage: %timeit test_iter(x)
10000000 loops, best of 5: 173 ns per loop

sage: %timeit test_access(d)
1000000 loops, best of 5: 786 ns per loop
sage: %timeit test_access(x)
1000000 loops, best of 5: 761 ns per loop

Although this micro-optimization probably doesn't matter too much.

---

New commits:

​134da39	sage.symbolic.assumptions.GenericDeclaration.assume: Validate against cached valid features first
​8b31261	sage.symbolic.assumptions.GenericDeclaration: Make it a UniqueRepresentation
​51ea23d	sage.symbolic.assumptions.GenericDeclaration.assume: Check first if already in _assumptions
​9119e82	sage.symbolic.assumptions._assumptions: Change from list to OrderDict
​cda81ff	sage.symbolic.assumptions.GenericDeclaration: Make it hashable by inheriting comparisons from UniqueRepresentation

[mkoeppe]

Replying to tscrim:

I wonder a little bit if OrderedDict is really the best data structure. It feels like it really should be a set, but I guess OrderedDict has more guaranteed consistency across different sessions. Note that iterating over a set is actually faster:

Right, I actually would have wanted an OrderedSet here except that there is no such thing in the standard library.

Ordered because I wanted to preserve the behavior of the previous code using lists to reduce the potential for changes from the order of operations. In this untyped symbolics business, it's best to tread very carefully.

The small constant factor between set and OrderDict does not matter much, I would think.

[tscrim]

Then let it be so.

[mkoeppe]

Thank you!

[nbruin]

Perhaps this point can be cleared quickly, but I think it deserves addressing. It seems here that "UniqueRepresentation?" is used just for caching behaviour here. That's not what UniqueRepresentation? is for!! It imposes very specific semantics! If it's just the caching, perhaps you're looking for "CachedRepresentation?".

In either case, the caching comes with a heavy price to pay: the construction parameters used for CachedRepresentation? and UniqueRepresentation? get global references to them for the lifetime of the created object. This can create very non-obvious memory leaks. For instance, you have to make absolutely sure that the construction parameters never support a reference chain pointing to the created object. Furthermore, you have to make absolutely sure that the created object is immutable, because unrelated pieces of code can end up sharing a reference to the object.

[gh-mwageringel]

Replying to mkoeppe:

Replying to tscrim:

I wonder a little bit if OrderedDict is really the best data structure. It feels like it really should be a set, but I guess OrderedDict has more guaranteed consistency across different sessions. Note that iterating over a set is actually faster:

Right, I actually would have wanted an OrderedSet here except that there is no such thing in the standard library.

As of Python 3.6.x, regular dicts preserve the insertion order, so in most cases OrderedDict is not needed anymore.

[tscrim]

Considering that the inputs are a symbolic variable and a string, I would be very surprised if any memory leaks were ever created.

However, one benefit is the equality checks and hashing becomes really quick for the UniqueRepresentation.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​642836d

sage.symbolic.assumptions: Use dict instead of OrderedDict for _assumptions

[mkoeppe]

Replying to gh-mwageringel:

As of Python 3.6.x, regular dicts preserve the insertion order, so in most cases OrderedDict is not needed anymore.

Thanks, done.

[mkoeppe]

Replying to nbruin:

Perhaps this point can be cleared quickly, but I think it deserves addressing. It seems here that UniqueRepresentation is used just for caching behaviour here. That's not what UniqueRepresentation is for!! It imposes very specific semantics! If it's just the caching, perhaps you're looking for CachedRepresentation.

In either case, the caching comes with a heavy price to pay: the construction parameters used for CachedRepresentation and UniqueRepresentation get global references to them for the lifetime of the created object. This can create very non-obvious memory leaks. For instance, you have to make absolutely sure that the construction parameters never support a reference chain pointing to the created object. Furthermore, you have to make absolutely sure that the created object is immutable, because unrelated pieces of code can end up sharing a reference to the object.

Thanks for the discussion. This is an important point.

I am using UniqueRepresentation here in the same way as I would use INTERN in Lisp.

Note that SR variable names already have indefinite lifetime: SR.var adds them to the dictionary SR.symbols; even reset() does not remove them.

Before this ticket, a GenericDeclaration is associated with a Maxima context after calling .assume() for the first time. The context is never killed or collected. Repeated assumptions as illustrated in the examples in #30065 lead to unbounded growth and slowdown.

In this ticket, by using UniqueRepresentation for GenericDeclaration, I manage the resource "Maxima context" explicitly; it's not just caching. Effectively I give indefinite lifetime to pairs of an SR variable and a declaration - this matches the indefinite lifetime of Maxima contexts that was already present. But now repeated assumptions no longer lead to growth.

[mkoeppe]

Any more thoughts on this one?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9e0cbed

src/sage/symbolic/assumptions.py: Fix style warning

[tscrim]

Nils, are you okay with the current version and justifications? If so, then I would set a positive review.

[gh-mjungmath]

It's me again, complaining about pyflakes warnings, again. Due to the new use of UniqueRepresentation, the import of SageObject is not necessary anymore.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4adcb20

src/sage/symbolic/assumptions.py: Remove unused import

[tscrim]

Green bot, so I am setting a positive review.

[mkoeppe]

Thank you!

[slelievre]

Modifying ticket description which still mentioned OrderedDict.