Opened 7 years ago

Last modified 6 years ago

#14356 needs_info defect

memleak in UniqueRepresentation / Poset

Reported by: vbraun Owned by: rlm
Priority: major Milestone: sage-6.4
Component: memleak Keywords:
Cc: SimonKing, tscrim, jkeitel, novoselt Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Its easy to construct posets whose element labels refer back to the poset, for example in toric varieties the face lattice is labelled by cones of the fan. The result is that everything is unconditionally alive because the UniqueRepresentation WeakValueDictionary has a key referring back to the poset:

sage: class Foo:
....:         pass
....: 
sage: foo = Foo()
sage: foo.dag = random_DAG(10)
sage: foo.poset = Poset(foo.dag, element_labels=[(i,foo) for i in range(10)], key=id(foo))
sage: del foo
sage: 
sage: import gc
sage: gc.collect()
591
sage: print [ x for x in gc.get_objects() if isinstance(x,sage.combinat.posets.posets.FinitePoset) ]
[Finite poset containing 10 elements]

Change History (10)

comment:1 follow-up: Changed 7 years ago by vbraun

  • Cc SimonKing tscrim added
  • Status changed from new to needs_info

It seems that this is a rather common use of posets: You have some objects that refer back to their common container. Now label the poset elements with. This then keeps everything alive.

Questions:

  • Poset has an optional key= argument, but it is seems to be not used by UniqueRepresentation. Whats up with that?
  • Maybe Poset should support for weakly referenced labels?
  • UniqueRepresentations could check that the key does not have a reference to the value for debugging purposes

comment:2 in reply to: ↑ 1 Changed 7 years ago by SimonKing

Replying to vbraun:

It seems that this is a rather common use of posets: You have some objects that refer back to their common container.

It is indeed normal that, e.g., an element refers to its parent. Hence, the element keeps the parent alive. But:

Now label the poset elements with. This then keeps everything alive.

If the element is gone, the parent can be garbage collected. Or "should be" garbage collected.

Hence, what is the difference to the element vs. parent situation?

Here, we have foo, which points to a poset (let's call it P) as an attribute foo.poset. Part of the construction of P are the element_labels, which refer to foo. Since the construction data of P are stored as keys of a weak value dictionary, they are kept alive.

Hence, foo is alive, and thus P=foo.poset, too.

I'd say this is impossible to prevent automatically (see below).

Questions:

  • Maybe Poset should support for weakly referenced labels?

That should solve this problem.

  • UniqueRepresentations could check that the key does not have a reference to the value for debugging purposes

How could this be checked?

Note that the reference does not exist when UniqueRepresentation.__classcall__ is called! Namely, first the poset is constructed, and only in the second step the poset is assigned to foo.poset. But during construction, there is no reason for Sage to guess that the user will later create a strong reference from the key to the resulting poset.

So, I'd say it is a misuse.

comment:3 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 7 years ago by jkeitel

  • Cc jkeitel added

comment:5 Changed 7 years ago by jkeitel

  • Cc novoselt added

comment:6 follow-up: Changed 7 years ago by nbruin

I think I agree with Simon's assessment that the code behaves as designed and hence that strictly speaking, the memory leak is created by misuse. However, I think we have a problematic design if it's that easy to "misuse" it.

I think this issue indicates that perhaps parents like Poset should NOT be unique. If we go back to why "unique" parent were introduced we see:

  • it means that polynomials in QQ['x'] created in two separate places will actually lie in the same parent
  • it makes some things easier/faster in the coercion framework

Keeping strong references globally to the construction parameters of a parent for the lifetime of the parent is OK if the parameters are fundamentally "simpler" than the constructed object. However, that's not the case with constructing a Poset: the entire complexity of the object is part of the construction call.

That makes it rather unlikely that the uniquerepresentation feature will ever make a useful contribution. It also means that constructing an n-element Poset is at least O(n), because UniqueRepresentation will walk the call argument (i.e., all the labels!) to hash them, converting lists to something hashable. Note that constructing a Poset from a set should normally be O(1), because the only thing required is saving a reference to the set and the comparison method.

So, I think parents that require more than O(1) [in some reasonable sense] construction parameter complexity should probably usually not be UniqueRepresentation.

Poset seems to have explicitly designed to be UniqueRepresentation, so I assume someone really needed that. It does mean, though, that if someone needs a Poset but doesn't particularly need it to be UniqueRepresentation, they should probably not use Poset, because it's an expensive feature for parents like this.

Last edited 7 years ago by nbruin (previous) (diff)

comment:7 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 in reply to: ↑ 6 Changed 6 years ago by ncohen

Poset seems to have explicitly designed to be UniqueRepresentation, so I assume someone really needed that.

Someone also needed those UniqueRepresentation objects to be mutable (#14019).

Nathann

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.