massive memory usage generating posets...

[Andrew Juell]

Running sage locally under Ubuntu to avoid any esoteric problems in the cloud, I discovered another issue...while I could iterate over Posets(7) and (8) and count their linear extensions with little trouble, attempting to do so with the 9-element posets overnight resulted in python eating up 4+GB of memory before giving up and nearly freezing my machine outright. Watching it run a second time even after inserting regular calls to gc.collect() I see the memory usage steadily climb even though each poset is only referenced once and then discarded...I recognize that there's a lot of calculation to do, but I don't understand why the intermediate results would accumulate in this fashion. Is there any way to circumvent this? Thanks in advance...

[Andrew Juell]

v=9
f = open('posetstats', 'w')
P=Posets(v)
Bean=0
for p in P:
      Bean+=1
      if Bean%1000==0: print Bean
      f.write(str(Bean)+ " "+ str(len(p.cover_relations()))+" "+str(p.linear_extensions().cardinality())+"\n")
print "done"
f.close()

[Nils Bruin]

On Saturday, April 5, 2014 7:41:47 PM UTC-7, Andrew Juell wrote:

Running sage locally under Ubuntu to avoid any esoteric problems in the cloud, I discovered another issue...while I could iterate over Posets(7) and (8) and count their linear extensions with little trouble, attempting to do so with the 9-element posets overnight resulted in python eating up 4+GB of memory before giving up and nearly freezing my machine outright.

It's a memory leak:

sage: import gc
sage: from collections import Counter
sage: P=Posets(6)
sage: gc.collect()
1
sage: pre={id(c) for c in gc.get_objects()}
sage: for p in P: dummy=p.linear_extensions()
sage: gc.collect()
0
sage: post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
sage: sorted(post.iteritems(),key=lambda t: t[1])
[(_ctypes.PyCFuncPtrType, 1),
 (_ast.Attribute, 1),
 (frame, 1),
 (sage.categories.category.JoinCategory_with_category, 1),
 (StgDict, 1),
 (sage.categories.facade_sets.FacadeSets_with_category, 1),
 (sage.structure.coerce_maps.DefaultConvertMap_unique, 1),
 (thread._local, 1),
 (listiterator, 1),
 (sage.categories.homset.Homset_with_category, 1),
 (sage.misc.cachefunc.CachedFunction, 1),
 (sage.misc.function_mangling.ArgumentFixer, 1),
 (collections.defaultdict, 1),
 (ctypes.CDLL, 1),
 (_ast.Module, 1),
 (_ast.Interactive, 1),
 (decimal._Log10Memoize, 1),
 (_ast.Compare, 1),
 (sage.categories.posets.Posets_with_category, 1),
 (_ast.Assign, 1),
 (sage.misc.cachefunc.CachedMethod, 1),
 (sage.categories.finite_posets.FinitePosets_with_category, 1),
 (sage.misc.constant_function.ConstantFunction, 2),
 (ctypes._FuncPtr, 2),
 (operator.itemgetter, 3),
 (decimal.Context, 3),
 (_ast.Call, 3),
 (instance, 3),
 (frozenset, 4),
 (abc.abstractproperty, 4),
 (uuid.UUID, 4),
 (_ast.Name, 4),
 (sage.misc.classcall_metaclass.ClasscallMetaclass, 4),
 (wrapper_descriptor, 5),
 (classmethod, 5),
 (abc.ABCMeta, 6),
 (classobj, 6),
 (sage.structure.dynamic_class.DynamicClasscallMetaclass, 6),
 (decimal.Decimal, 6),
 (sage.structure.dynamic_class.DynamicMetaclass, 8),
 (member_descriptor, 9),
 (method_descriptor, 9),
 (_weakrefset.WeakSet, 18),
 (cython_function_or_method, 20),
 (property, 27),
 (set, 38),
 (getset_descriptor, 55),
 (type, 67),
 (cell, 112),
 (staticmethod, 170),
 (module, 181),
 (sage.combinat.posets.hasse_diagram.HasseDiagram, 318),
 (sage.combinat.posets.linear_extensions.LinearExtensionsOfPoset_with_category, 318),
 (sage.graphs.linearextensions.LinearExtensions, 318),
 (sage.misc.cachefunc.CachedMethodCaller, 318),
 (sage.graphs.base.static_sparse_backend.StaticSparseBackend, 318),
 (sage.combinat.posets.posets.FinitePoset_with_category, 318),
 (sage.misc.cachefunc.CachedMethodCallerNoArgs, 321),
 (builtin_function_or_method, 377),
 (sage.structure.coerce_dict.TripleDictEraser, 637),
 (sage.structure.coerce_dict.TripleDict, 637),
 (instancemethod, 638),
 (weakref.KeyedRef, 656),
 (sage.structure.coerce_dict.MonoDictEraser, 1274),
 (sage.structure.coerce_dict.MonoDict, 1274),
 (function, 1687),
 (weakref, 2054),
 (dict, 2684),
 (tuple, 3773),
 (list, 5675)]

As you can see for n=6, all the 318 sage.graphs.linearextensions.LinearExtensions instances are still in memory.  I suspect it's something like this:
 - The "linear_extension" method is cached. This means that the poset will keep the linear_extension alive
 - The unique_parent of linear_extension property means that its construction arguments (which includes the poset!) are used as a strong key in a weak_value_dictionary. This means that as long as the linear_extension is alive, the key will remain and hence the category of linear_extension will keep the poset alive.

Voila, a classic memory leak. "cached_methods" and "unique_parent" combined are basically designed to invite memory leaks like this. Don't use them together unless you're prepared to think very hard about basically all the objects that might have a glancing interaction with the objects you're implementing.

[Nathann Cohen]

> As you can see for n=6, all the 318 sage.graphs.linearextensions.LinearExtensions instances are still in memory.  I suspect it's something like this:
>  - The "linear_extension" method is cached. This means that the poset will keep the linear_extension alive
>  - The unique_parent of linear_extension property means that its construction arguments (which includes the poset!) are used as a strong key in a weak_value_dictionary. This means that as long as the linear_extension is alive, the key will remain and hence the category of linear_extension will keep the poset alive.
>
> Voila, a classic memory leak. "cached_methods" and "unique_parent" combined are basically designed to invite memory leaks like this. Don't use them together unless you're prepared to think very hard about basically all the objects that might have a glancing interaction with the objects you're implementing.

Are you serious ? I'm ready to bet that a LOT of classes use those two things at the same time. But there is a way to identify them automatically, isn't it ?

Nathann

[Nils Bruin]

If you mean by "automatic": write a script to create a lot of them and throw them away and see if it leaks then, yes. Otherwise: this really is a non-local program logic problem, so detecting it is hard.

Yep. The problem is:  UniqueRepresentation implements necessarily a GLOBAL cache and hence will hold strong references to the creation parameters. It's very unfortunate and I think if we had thought about the consequences of that a little more, we wouldn't have gone with this design choice at all. It's just too hard to work with. But now we're stuck with it.

UniqueRepresentation does try to alleviate the problems a little bit by using a WeakValueDictionary for its cache, but as you see: Construction parameter passed to a UniqueRepresentation constructor should NEVER hold a strong reference to the resulting object, because that creates a memory leak. Ideally, construction parameters should just not hold references at all, but that's unfortunately infeasible.

Caching a routine that's simply a wrapper around a UniqueRepresentation constructor is nearly useless anyway: UniqueRepresentation is supposed to be fast and cached anyway! (it does have to do some argument processing, though, so it is a little slower that a straight cached routine). However, I can imagine that similar scenarios occur in less obvious ways and yes, they all leak.

We can clean things up a little bit in this example by clearing the cache ourselves, i.e., run

for p in P:
    dummy=p.linear_extensions()

    p.linear_extensions.clear_cache()

but you'll find that you need to do multiple gc.collect() afterwards to get rid of all the crud: the garbage is so complicated that the collector can't clean it up in one go (the objects that get released from being WeakValueDictionary keys due to weakref callbacks are still part of reference cycles, and it takes a fresh gc run to recognize them as such)

[Nathann Cohen]

Helloooooo !!!

> If you mean by "automatic": write a script to create a lot of them and throw
> them away and see if it leaks then, yes. Otherwise: this really is a
> non-local program logic problem, so detecting it is hard.

No, I meant... Can't we add some parameter to cached_method, so that
it could not be applied to an object which inherits from
UniqueRepresentation (if this is the problem) ?

something like

def cached_method(self, function,
check_that_self_if_not_unique_representation=True):
if check_that_self_if_not_unique_representation and
isinstance(self,UniqueRepresentation):
raise RuntimeError("This will cause memory leaks ! If you know
what you are doing, disable this test")
...

This way it could only be used when developers DID think hard of what
they did, and not by mistake, which produces leaks like this one.

> Yep. The problem is: UniqueRepresentation implements necessarily a GLOBAL
> cache and hence will hold strong references to the creation parameters. It's
> very unfortunate and I think if we had thought about the consequences of
> that a little more, we wouldn't have gone with this design choice at all.
> It's just too hard to work with. But now we're stuck with it.

I hated UniqueRepresentation for years already. I would be glad to see
it replaced by anything that makes sense. Please don't "stick with it"
if we encounter leaks like that as a result. We can change things and
improve them.

> UniqueRepresentation does try to alleviate the problems a little bit by
> using a WeakValueDictionary for its cache, but as you see: Construction
> parameter passed to a UniqueRepresentation constructor should NEVER hold a
> strong reference to the resulting object, because that creates a memory
> leak. Ideally, construction parameters should just not hold references at
> all, but that's unfortunately infeasible.
>
> Caching a routine that's simply a wrapper around a UniqueRepresentation
> constructor is nearly useless anyway: UniqueRepresentation is supposed to be
> fast and cached anyway! (it does have to do some argument processing,
> though, so it is a little slower that a straight cached routine). However, I
> can imagine that similar scenarios occur in less obvious ways and yes, they
> all leak.
>
> We can clean things up a little bit in this example by clearing the cache
> ourselves, i.e., run
>
> for p in P:
> dummy=p.linear_extensions()
> p.linear_extensions.clear_cache()
>
> but you'll find that you need to do multiple gc.collect() afterwards to get
> rid of all the crud: the garbage is so complicated that the collector can't
> clean it up in one go (the objects that get released from being
> WeakValueDictionary keys due to weakref callbacks are still part of
> reference cycles, and it takes a fresh gc run to recognize them as such)

Oh. That's what I advised Andrew to do... I hope it will work somehow :-/

Nathann

[Nils Bruin]

On Sunday, April 6, 2014 1:35:17 PM UTC-7, Nathann Cohen wrote:

No, I meant... Can't we add some parameter to cached_method, so that
it could not be applied to an object which inherits from
UniqueRepresentation (if this is the problem) ?

something like

def cached_method(self, function,
check_that_self_if_not_unique_representation=True):
    if check_that_self_if_not_unique_representation and
isinstance(self,UniqueRepresentation):
        raise RuntimeError("This will cause memory leaks ! If you know
what you are doing, disable this test")

It's not "self" that matters, it's the result returned by the cached method that shouldn't contain any UniqueRepresentation object that was constructed using self. That's expensive to check.

As a debugging tool, one could rig cached_method to do a check like that, though. It would involve a reverse lookup of construction parameters for all UniqueRepresentation objects found in the return value.
 

[Nathann Cohen]

Yooooooooo !

> It's not "self" that matters, it's the result returned by the cached method
> that shouldn't contain any UniqueRepresentation object that was constructed
> using self. That's expensive to check.

Oh. I see :-/

Nathann