Memory leaks in RootSystem

[tscrim]

RootSystem is currently creating memory leaks in the following way:

Upon creating a root system, say of type B3, this line:

self.dual = RootSystem(self._cartan_type.dual(), as_dual_of=self);

causes the B3 root system to be used as a key in the UniqueRepresentation of the C3 root system (I call it so, but note it is the dual of the B3, which will be different than the honest C3 root system), which is a strong reference that can never be deleted. Moreover, the B3 root system then holds a (strong) reference to the C3 root system, so the C3 root system never gets collected either.

Some data:

sage: from collections import Counter
sage: import gc
sage: gc.collect()
349
sage: pre = {id(a) for a in gc.get_objects()}
sage: get_memory_usage()
8697.9453125
sage: for n in range(5, 3000):
....:     RS = RootSystem(['A', n])
....:
sage: gc.collect()
106
sage: get_memory_usage()
8703.08984375
sage: post = Counter(str(type(a)) for a in gc.get_objects() if id(a) not in pre)
sage: sorted([p for p in post.items() if p[1] > 2000])
[("<class 'dict'>", 6123),
 ("<class 'sage.combinat.root_system.root_system.RootSystem'>", 5985),
 ("<class 'sage.combinat.root_system.type_A.CartanType'>", 2991),
 ("<class 'tuple'>", 30460),
 ("<class 'weakref.KeyedRef'>", 9003)]

CC: @sagetrac-sage-combinat @nthiery @slel

Component: memleak

Author: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/18426

[tscrim]

comment:1

One possible workaround is to not accept a root system as input, but instead a boolean. Then when it creates the dual root system, and then explicitly sets the dual attribute of the dual root system to self.

[tscrim]

Description changed:

--- 
+++ 
@@ -5,7 +5,7 @@
 ```python
 self.dual = RootSystem(self._cartan_type.dual(), as_dual_of=self);

-causes the B3 root system to be used as a key in the UniqueRepresentation of the C3 root system (I call it so, but note it is the dual of the B3, which will be different than the honest C3 root system), which is a strong reference that can never be deleted. Moreover, the B3 root system then holds a (strong) reference to the C3 root system, so the C3 root system never gets collected either. +causes the B3 root system to be used as a key in the UniqueRepresentation of the C3 root system (I call it so, but note it is the dual of the B3, which will be different than the honest C3 root system), which is a strong reference. Moreover, the B3 root system then holds a (strong) reference to the C3 root system (and vice versa), so both root systems can never can get collected.

Some data:

[nthiery]

Description changed:

--- 
+++ 
@@ -5,7 +5,7 @@
 ```python
 self.dual = RootSystem(self._cartan_type.dual(), as_dual_of=self);

-causes the B3 root system to be used as a key in the UniqueRepresentation of the C3 root system (I call it so, but note it is the dual of the B3, which will be different than the honest C3 root system), which is a strong reference. Moreover, the B3 root system then holds a (strong) reference to the C3 root system (and vice versa), so both root systems can never can get collected. +causes the B3 root system to be used as a key in the UniqueRepresentation of the C3 root system (I call it so, but note it is the dual of the B3, which will be different than the honest C3 root system), which is a strong reference that can never be deleted. Moreover, the B3 root system then holds a (strong) reference to the C3 root system, so the C3 root system never gets collected either.

Some data:

[nthiery]

comment:2

Hi Travis!

I am sure there are plenty of other similar situations of cross-referencing parents (e.g. in SymmetricFunctions). How critical do you think this specific situation is? I mean: do you foresee people creating thousands of different root systems in the same Sage session?

Cheers, Nicolas

[tscrim]

comment:3

I'm not so sure about how frequent we get the cross-referencing parents with one of them being a key for a UniqueRepresentation. Although it's hard to tell because there are known memory leaks with the category Algebras that would keep parents alive.

For this particular situation, I doubt anyone will create thousands of root systems. What I'm a little worried about is all the different things a root system might keep alive and could pile up (like root lattices (and say you tested them over a large range of finite fields, but this might not be mathematically reasonable), Cartan types/matrices, etc.).

[nbruin]

comment:4

Questions:

• do you really need RootSystem to be UniqueRepresentation (i.e., do these things really participate in the coercion framework)? I would think the "parent" component of a RootSystem is only there because mathematically it looks like something that has elements, not as something whose elements will be interacting with elements from other parents.
• do you really need RootSystem to hold any references to other root systems? Doesn't the UniqueRepresentation cache provide fast enough access?
• can you key the UniqueRepresentation via lower level information, e.g., a sequence of integers or so? By changing to a UniqueFactory instead, you could still offer the same interface. Especially because these things probably happen all over the place, I think it's really good that you're trying to see what kind of solution strategies work well. I'm sure your experience in this can be used in lots of other places. It's hard to predict what people will be doing with the code, so we should try to not make assumptions and unnecessarily restrict usage scenarios.

[slel]

Description changed:

--- 
+++ 
@@ -2,7 +2,7 @@

 Upon creating a root system, say of type B3, this line:

-```python
+```
 self.dual = RootSystem(self._cartan_type.dual(), as_dual_of=self);

causes the B3 root system to be used as a key in the UniqueRepresentation of the C3 root system (I call it so, but note it is the dual of the B3, which will be different than the honest C3 root system), which is a strong reference that can never be deleted. Moreover, the B3 root system then holds a (strong) reference to the C3 root system, so the C3 root system never gets collected either. @@ -13,22 +13,22 @@ sage: from collections import Counter sage: import gc sage: gc.collect() -91 +349 sage: pre = {id(a) for a in gc.get_objects()} sage: get_memory_usage() -1022.7890625 -sage: for n in range(5,3000):

• RS = RootSystem(['A',n]) -....:
  +8697.9453125 +sage: for n in range(5, 3000): +....: RS = RootSystem(['A', n]) +....: sage: gc.collect() -0 +106 sage: get_memory_usage() -1031.359375 +8703.08984375 sage: post = Counter(str(type(a)) for a in gc.get_objects() if id(a) not in pre) -sage: [p for p in post.iteritems() if p[1] > 2000] -[("<class 'weakref.KeyedRef'>", 8985),
• ("<class 'sage.combinat.root_system.type_A.CartanType'>", 2994),
• ("<class 'sage.combinat.root_system.root_system.RootSystem'>", 5990),
• ("<type 'dict'>", 6012),
• ("<type 'tuple'>", 29952)] -``` +sage: sorted([p for p in post.items() if p[1] > 2000]) +[("<class 'dict'>", 6123),
• ("<class 'sage.combinat.root_system.root_system.RootSystem'>", 5985),
• ("<class 'sage.combinat.root_system.type_A.CartanType'>", 2991),
• ("<class 'tuple'>", 30460),
• ("<class 'weakref.KeyedRef'>", 9003)]