MemoryError when individually doctesting sage/combinat/tableau.py

96 views
Skip to first unread message

Steven Trogdon

unread,
Feb 11, 2019, 4:19:12 PM2/11/19
to sage-devel
When individually doctesting tableau.py with vanilla 8.7.beta3 I see:

sage -t --long src/sage/combinat/tableau.py  # Bad exit: 1

The source is

Trying (line 7735):    StandardTableaux(50).cardinality()  # long time
Expecting:
    27886995605342342839104615869259776
**********************************************************************
File "src/sage/combinat/tableau.py", line 7735, in sage.combinat.tableau.StandardTableaux_size.cardinality
Failed example:
    StandardTableaux(50).cardinality()  # long time
Exception raised:
    Traceback (most recent call last):
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1095, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.tableau.StandardTableaux_size.cardinality[4]>", line 1, in <module>
        StandardTableaux(Integer(50)).cardinality()  # long time
      File "sage/misc/lazy_import.pyx", line 354, in sage.misc.lazy_import.LazyImport.__call__ (build/cythonized/sage/misc/lazy_import.c:3683)
        return self.get_object()(*args, **kwds)
      File "sage/misc/classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1700)
        return cls.classcall(cls, *args, **kwds)
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/combinat/tableau.py", line 7568, in __classcall_private__
        return StandardTableaux_size(n)
      File "sage/misc/classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1700)
        return cls.classcall(cls, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 1005, in sage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6067)
        w = self.f(*args, **kwds)
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 1027, in __classcall__
        instance = typecall(cls, *args, **options)
      File "sage/misc/classcall_metaclass.pyx", line 497, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:2150)
        return (<PyTypeObject*>type).tp_call(cls, args, kwds)
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/combinat/tableau.py", line 7677, in __init__
        facade=True, keepkey=False)
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/sets/disjoint_union_enumerated_sets.py", line 288, in __init__
        self._facade_for = tuple(family)
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/sets/family.py", line 1061, in __iter__
        for i in self.set:
      File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/combinat/partition.py", line 6698, in __iter__
        yield self.element_class(self, p)
      File "sage/misc/classcall_metaclass.pyx", line 333, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1725)
        return (<PyTypeObject*>type).tp_call(cls, args, kwds)
    MemoryError
Trying (line 7740):    def cardinality_using_hook_formula(n):
        c = 0
        for p in Partitions(n):
            c += StandardTableaux(p).cardinality()
        return c
Expecting nothing
ok [0.00 s]
Trying (line 7745):    all(cardinality_using_hook_formula(i) == StandardTableaux(i).cardinality() for i in range(10))
Expecting:
    True
Process DocTestWorker-1:
Traceback (most recent call last):
  File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/multiprocessing/process.py", line 267, in _bootstrap
    self.run()
  File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 2139, in run
    task(self.options, self.outtmpfile, msgpipe, self.result_queue)
  File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 2498, in __call__
    result_queue.put(result, False)
  File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/multiprocessing/queues.py", line 107, in put
    self._start_thread()
  File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/multiprocessing/queues.py", line 195, in _start_thread
    self._thread.start()
  File "/64bitdev/storage/sage-git_develop/sage/local/lib/python2.7/threading.py", line 736, in start
    _start_new_thread(self.__bootstrap, ())
error: can't start new thread
    Bad exit: 1
**********************************************************************

Usually there is no failure if the doctest is run again. I've been able to replicate this by rebuilding sagelib and re-running the individual doctest. I first noticed this on a Sage-on-Gentoo install in Prefix where the host is Debian (see https://github.com/cschwan/sage-on-gentoo/commit/f62108870dbc9c69adbb5e1dcb772c405519f569#commitcomment-32252815). In the Prefix the tableau.py doctest always fails with a MemoryError. In the Prefix there are 3 MemoryError failures, all associated with '--long' doctests. Perhaps others have seen this failure.


Dima Pasechnik

unread,
Feb 11, 2019, 4:52:09 PM2/11/19
to sage-devel
I see similar errors on Fedora 26
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

Travis Scrimshaw

unread,
Feb 13, 2019, 11:33:38 AM2/13/19
to sage-devel
My (complete) guess is that there are so many partitions of 50 (204226 to be precise) and in such a tight for loop that the garbage collector does not have enough time to actually collect the parents being created and discarded. Maybe also other stuff in tableau.py built up is causing a memory problem? Could you try inserting a `gc.collect()` in the for loop and seeing if the file passes after that?

Best,
Travis

Steven Trogdon

unread,
Feb 13, 2019, 1:27:03 PM2/13/19
to sage-devel
Assuming this is the correct thing to do, starting at line 7740, the following

           sage: def cardinality_using_hook_formula(n):
            ....:     import gc
            ....:     c = 0
            ....:     for p in Partitions(n):
            ....:         gc.collect()
            ....:         c += StandardTableaux(p).cardinality()
            ....:     return c

gets rid of the MemoryError. This is on my gentoo prefix where the test also fails. I have to rebuild sagelib to get results on vanilla. However, I still see

Process DocTestWorker-1:
Traceback (most recent call last):
  File "/storage/strogdon/gentoo-rap/usr/lib64/python2.7/multiprocessing/process.py", line 267, in _bootstrap
    self.run()
  File "/storage/strogdon/gentoo-rap/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 2139, in run
    task(self.options, self.outtmpfile, msgpipe, self.result_queue)
  File "/storage/strogdon/gentoo-rap/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 2498, in __call__
    result_queue.put(result, False)
  File "/storage/strogdon/gentoo-rap/usr/lib64/python2.7/multiprocessing/queues.py", line 107, in put
    self._start_thread()
  File "/storage/strogdon/gentoo-rap/usr/lib64/python2.7/multiprocessing/queues.py", line 195, in _start_thread
    self._thread.start()
  File "/storage/strogdon/gentoo-rap/usr/lib64/python2.7/threading.py", line 736, in start
    _start_new_thread(self.__bootstrap, ())
error: can't start new thread
    Bad exit: 1

It's not clear the origin of this since it appears all tests passed?

1650 tests in 281 items.
1650 passed and 0 failed.
Test passed.

Steven Trogdon

unread,
Feb 13, 2019, 3:00:19 PM2/13/19
to sage-devel
One more thing. If I remove

            sage: StandardTableaux(50).cardinality()  # long time

then doctesting `tableary.py` with --long passes.

Volker Braun

unread,
Feb 13, 2019, 4:02:37 PM2/13/19
to sage-devel
On Wednesday, February 13, 2019 at 5:33:38 PM UTC+1, Travis Scrimshaw wrote:
My (complete) guess is that there are so many partitions of 50 (204226 to be precise) and in such a tight for loop that the garbage collector does not have enough time to actually collect the parents being created and discarded. 

The Python GC also starts collection if there are many new objects, so I don't think this is it.

 Running the example takes > 1 gb of ram; Surely a smaller example could be used with the same code coverage.  

Martin R

unread,
Feb 14, 2019, 6:38:20 AM2/14/19
to sage-devel
Can we exclude the possibility that this is a regression?

As far as I can see, the expensive part is in creating the parent 'StandardTableaux(50)', which is a bit strange, isn't it?

Martin

Martin R

unread,
Feb 14, 2019, 6:49:06 AM2/14/19
to sage-devel
Further digging reveals that the problem is in `DisjointUnionEnumeratedSets.__init__, which expands the lazy `Family(Partitions_n(n), StandardTableaux_shape)` into a tuple.  I have (currently) no idea whether this is necessary.

Martin

Travis Scrimshaw

unread,
Feb 14, 2019, 11:54:49 AM2/14/19
to sage-devel
Maybe...Because the façade parent framework needs the tuple to say it is a façade for that set of parents. Currently Family is a parent, so there would be no way to distinguish between the family should represent the set of parents or a parent to be the façade for.

Most of what that test is for is to show that we are not actually creating all of those elements and enumerating them (i.e., it is using the hook-length formula). So we could maybe make it StandardTableaux(40) instead of 50, but it will still likely use a large chunk of memory.

Best,
Travis

Martin R

unread,
Feb 14, 2019, 2:41:10 PM2/14/19
to sage-devel
Thanks for the explanation!

might it work to replace the call to `tuple` with a call to `lazy_list`?

Martin
Reply all
Reply to author
Forward
0 new messages