MemoryError when individually doctesting sage/combinat/tableau.py

[Steven Trogdon]

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]

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]

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]

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]

One more thing. If I remove

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

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

[Volker Braun]

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]

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]

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]

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]

Thanks for the explanation!

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

Martin