Why does FiniteLatticePoset sometimes makes copies?

[Jonathan Kliem]

Can anyone help me explain this

sage: o = lattice_polytope.cross_polytope(3)
sage: F = o.face_lattice()
sage: G = F.relabel(F._elements)
sage: G[0].ambient() is o
True
sage: o = lattice_polytope.cross_polytope(3)
sage: F = o.face_lattice()
sage: G = F.relabel(F._elements)
sage: G[0].ambient() is o
False
sage: G[0].ambient() is G[1].ambient()
True

More importantly, I am interested in a work around, such that relabeling does not create copies.

It works once with every lattice polytope and the second time it fails. The only thing that helps is to quit sage and restart it.

Currently, I'm working on using CombinatorialPolyhedron to obtain the face lattice for lattice polytopes. It works nicely, but that the faces do not know the ambient polytope (exactly) anymore, which makes the doctests fail.

Somehow the current setup works, but I'm puzzled on why.

[Nils Bruin]

I haven't dug very deep into this, but the following looks suspicious:

sage: o1 = lattice_polytope.cross_polytope(3)
sage: o2 = lattice_polytope.cross_polytope(3)
sage: o1==o2
True
sage: o1 is o2
False

This in itself isn't a problem, but o1.face_lattice() is a UniqueRepresentation object. That means that if you create two face_lattice() structures with arguments that are *equal* you'll get back *identical* lattices. That means you get:

sage: o1 = lattice_polytope.cross_polytope(3)
sage: F1 = o.face_lattice()
sage: G1 = F1.relabel(F1._elements)
sage: o2 = lattice_polytope.cross_polytope(3)
sage: F2 = o2.face_lattice()
sage: G2 = F2.relabel(F2._elements)
sage: G1 is G2
True

Interestingly:

sage: F1 is F2
False

so something is sufficiently different between the construction parameters of F1 and F2 to return different structures.

Because the unique representation cache will store G1, the construction of G2 will get you back G1. That's as designed. UniqueRepresentation structure have (A == B) iff (A is B).

It's always questionable to derive UniqueRepresentation objects from non-unique ones, although this particular example for F1 and F2 isn't exhibiting problematic behaviour right here (yet? perhaps it's just the order or accidental labelling that happens to introduce sufficient differences?)

Additionally, "o2.face_lattice()" is cached. If any of the construction parameters of F2 reference back to o2 -- which it seems to do via "ambient" there's a memory leak there of the classic "UniqueRepresentation weak-caching-but-with-value-keeping-keys-alive" kind. Never cache a UniqueRepresentation object on one of the objects involved in its construction.

[Jonathan Kliem]

Thanks. I think I have it figured out now.

The current construction passes to the face lattice the ID of self as a key. This is why F1 and F2 are not identical.

Basically, I can just do it like this. Now, if I understand it correctly:

Face lattice as it is, should not be cached. Instead its probably fine to store the version with indices and convert on each call. Or the DiGraph. Just not the FiniteLatticePoset with labels that point to self.

[Nils Bruin]

On Wednesday, October 30, 2019 at 2:31:37 PM UTC-7, Jonathan Kliem wrote:

Basically, I can just do it like this. Now, if I understand it correctly:

Face lattice as it is, should not be cached. Instead its probably fine to store the version with indices and convert on each call. Or the DiGraph. Just not the FiniteLatticePoset with labels that point to self.

As a rule, a function that returns a UniqueRepresentation object should NOT be a cached method. The UniqueRepresentation constructor is already cached: it uses the construction parameters as a key into the cache, and this is a global cache.

What you can do is cache the construction keys themselves (provided they are not UniqueRepresentation objects), so that you can call UniqueRepresentation quickly. If that doesn't meet your performance requirements then you shouldn't be using a UniqueRepresentation object.

The reason why caching UniqueRepresentation objects VERY easily leads to memory leaks is documented in many places, see e.g. https://groups.google.com/forum/#!msg/sage-devel/q5uy_lI11jg/CB15fcRmE4cJ (coincidentally also about FinitePoset).

It is possible to cache a reference to a UniqueRepresentation object A on an object B, but then you must make absolutely sure that there is NO reference path from A to B. Generally, mathematical objects hold references to the objects they are constructed from (possibly indirectly), so generally this is not an option. This is a fundamental design weakness of UniqueRepresentation that people get caught by again and again. Making objects UniqueRepresentation is a very costly thing to do and therefore very undesirable, even if it may seem like a nice property to have superficially. It's just a requirement for participating in some of the more advanced  coercion discovery, because there "is" is used rather than "==" for performance reasons.

[Jonathan Kliem]

Ok, thanks again. Using the construction parameters is definitely an option and I will change it soon.