Run doctests with limited memory

[jdemeyer]

There are various reasons to limit the maximal amount of memory that doctests can use:

1. Bugs which cause large memory usage and which can cause trouble for the OS when running doctests.
2. It is good to check that doctests do not use a large amount of memory.
3. It allows to doctest graceful recovery when memory cannot be allocated by intentionally allocating more memory than available.

I suggest to limit the virtual memory for doctests. The following two files contain the tests which need the most memory:

src/sage/game_theory/matching_game.py
src/sage/schemes/elliptic_curves/heegner.py

This branch also reduces the memory needed for matching_game.py, such that heegner.py is now the doctest which requires the most memory.

Component: doctest framework

Author: Jeroen Demeyer

Branch: 06d4307

Reviewer: Travis Scrimshaw

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

[jdemeyer]

Branch: u/jdemeyer/run_doctests_with_limited_memory

[jdemeyer]

New commits:

6b2589e

Run doctests with limited memory

[jdemeyer]

Commit: 6b2589e

[tscrim]

comment:3

Maybe this should be discussed on sage-devel, but my vote would be for 1Gb as IMO, doctests should in general not use a large amount of memory similar to the paradigm that they should be fast.

[jdemeyer]

comment:4

Replying to @tscrim:

Maybe this should be discussed on sage-devel, but my vote would be for 1Gb as IMO, doctests should in general not use a large amount of memory similar to the paradigm that they should be fast.

With 1GB, you cannot even start Sage.

And some doctests in src/sage/schemes/elliptic_curves/heegner.py do not pass with a limit of only 3GB.

[jdemeyer]

comment:5

Replying to @tscrim:

doctests should in general not use a large amount of memory similar to the paradigm that they should be fast.

That's precisely the reason for this patch.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
-Sometimes, due to bugs, it can happen that doctests take a very large amount of memory, causing trouble for the OS. I suggest to find a reasonable value of `ulimit -v` and use that to limit the virtual memory taken by doctests. This is also a check that doctests do not use too large amounts of memory.
+Sometimes, due to bugs, it can happen that doctests take a very large amount of memory, causing trouble for the OS. Also, it is good to check that doctests do not use a large amount of memory.
+
+I suggest to limit the virtual memory for doctests to 4GiB. This may seem like a lot, but note that some doctests in `src/sage/schemes/elliptic_curves/heegner.py` do not pass with 3GiB.

[tscrim]

comment:7

Replying to @jdemeyer:

Replying to @tscrim:

Maybe this should be discussed on sage-devel, but my vote would be for 1Gb as IMO, doctests should in general not use a large amount of memory similar to the paradigm that they should be fast.

With 1GB, you cannot even start Sage.

Oh, I was thinking this was the amount of memory specifically used by any particular doctest, not Sage + doctests. What about when doctests are run in parallel? Since it is using threads, we still have the same limit of 4Gb, so I am worried we will hit this limit on systems with larger amounts of cores.

And some doctests in src/sage/schemes/elliptic_curves/heegner.py do not pass with a limit of only 3GB.

Maybe we also want to consider a # high memory marker (another ticket?) or have # long time also allow higher memory?

[jdemeyer]

comment:8

Replying to @tscrim:

Oh, I was thinking this was the amount of memory specifically used by any particular doctest, not Sage + doctests.

No, it is the virtual memory limit for the whole process. This includes code (Python + Python modules + libraries) and data, also unused but allocated memory (like the PARI stack).

What about when doctests are run in parallel? Since it is using threads

No! It uses processes, not threads. The limit is per process, so we do not need to worry about that.

And some doctests in src/sage/schemes/elliptic_curves/heegner.py do not pass with a limit of only 3GB.

Maybe we also want to consider a # high memory marker (another ticket?) or have # long time also allow higher memory?

Perhaps, but this is just a very simple limit, comparable to the absolute doctest time limit of 360s (short tests) or 1800s (long tests).

[jdemeyer]

comment:9

I'll try to lower the limit of 4GiB somewhat, but it certainly must be higher than 3GiB.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1,3 +1,6 @@
-Sometimes, due to bugs, it can happen that doctests take a very large amount of memory, causing trouble for the OS. Also, it is good to check that doctests do not use a large amount of memory.
+There are various reasons to limit the maximal amount of memory that doctests can use:
+1. Bugs which cause large memory usage and which can cause trouble for the OS when running doctests.
+2. It is good to check that doctests do not use a large amount of memory.
+3. It allows to doctest graceful recovery when memory cannot be allocated by intentionally allocating more memory than available.

-I suggest to limit the virtual memory for doctests to 4GiB. This may seem like a lot, but note that some doctests in `src/sage/schemes/elliptic_curves/heegner.py` do not pass with 3GiB.
+I suggest to limit the virtual memory for doctests to 3400MiB. This may seem like a lot, but note that some doctests in `src/sage/schemes/elliptic_curves/heegner.py` need this.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -3,4 +3,4 @@
 2. It is good to check that doctests do not use a large amount of memory.
 3. It allows to doctest graceful recovery when memory cannot be allocated by intentionally allocating more memory than available.

-I suggest to limit the virtual memory for doctests to 3400MiB. This may seem like a lot, but note that some doctests in `src/sage/schemes/elliptic_curves/heegner.py` need this.
+I suggest to limit the virtual memory for doctests to 3500MiB. This may seem like a lot, but note that some doctests need this.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f8fcb51

Run doctests with limited memory

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6b2589e to f8fcb51

[jdemeyer]

Description changed:

--- 
+++ 
@@ -3,4 +3,4 @@
 2. It is good to check that doctests do not use a large amount of memory.
 3. It allows to doctest graceful recovery when memory cannot be allocated by intentionally allocating more memory than available.

-I suggest to limit the virtual memory for doctests to 3500MiB. This may seem like a lot, but note that some doctests need this.
+I suggest to limit the virtual memory for doctests to 3600MiB. This may seem like a lot, but some doctests need this much.

[tscrim]

comment:14

Replying to @jdemeyer:

Replying to @tscrim:

What about when doctests are run in parallel? Since it is using threads

No! It uses processes, not threads. The limit is per process, so we do not need to worry about that.

We should probably change this then:

travis@apricot:~/sage/src/sage/categories$ sage -tp category.py category_types.py 
[snip]
Doctesting 2 files using 8 threads.

Although I am somewhat surprised my memory usage is not higher when I am running parallel tests since each copy of Sage should take a minimum of 1Gb. shrugs, oh well, not important.

And some doctests in src/sage/schemes/elliptic_curves/heegner.py do not pass with a limit of only 3GB.

Maybe we also want to consider a # high memory marker (another ticket?) or have # long time also allow higher memory?

Perhaps, but this is just a very simple limit, comparable to the absolute doctest time limit of 360s (short tests) or 1800s (long tests).

I don't mind 4Gb, I probably prefer it over the 3.x for simplicity.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -3,4 +3,12 @@
 2. It is good to check that doctests do not use a large amount of memory.
 3. It allows to doctest graceful recovery when memory cannot be allocated by intentionally allocating more memory than available.

-I suggest to limit the virtual memory for doctests to 3600MiB. This may seem like a lot, but some doctests need this much.
+I suggest to limit the virtual memory for doctests to 4500MiB. This may seem like a lot, but these doctests do not pass with a limit of 4000MiB:
+
+```
+src/sage/matrix/matrix_integer_dense.pyx
+src/sage/rings/polynomial/pbori.pyx
+src/sage/game_theory/matching_game.py
+src/sage/rings/integer.pyx
+```
+The one requiring the most memory is `src/sage/game_theory/matching_game.py`

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b4001c6

Run doctests with limited memory

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f8fcb51 to b4001c6

[jdemeyer]

comment:17

Replying to @tscrim:

each copy of Sage should take a minimum of 1Gb.

Well, remember that this is virtual memory. Most of that 1GB is shared between processes. If you run 10 copies of Sage, the executable code of Sage needs to be in physical memory only once: the OS maps the same physical memory inside the 10 processes.

Then there is also memory which is reserved but typically not used: Sage might allocate a large PARI stack and GAP memory pool for example which counts against virtual memory. However, as long as this memory is not actually used, you don't need that much physical memory.

[jdemeyer]

comment:18

It turns out that even 4GiB is not enough... This new version uses 4500MiB which passes make ptestlong on my machine.

[tscrim]

comment:19

Replying to @jdemeyer:

Replying to @tscrim:

each copy of Sage should take a minimum of 1Gb.

Well, remember that this is virtual memory. Most of that 1GB is shared between processes. If you run 10 copies of Sage, the executable code of Sage needs to be in physical memory only once: the OS maps the same physical memory inside the 10 processes.

Then there is also memory which is reserved but typically not used: Sage might allocate a large PARI stack and GAP memory pool for example which counts against virtual memory. However, as long as this memory is not actually used, you don't need that much physical memory.

Ah, right. Thank you for the explanation.

[tscrim]

comment:20

Replying to @jdemeyer:

It turns out that even 4GiB is not enough... This new version uses 4500MiB which passes make ptestlong on my machine.

I am pretty sure it is this block of tests that takes the large amount of memory (with n = 10):

        sage: from itertools import permutations
        sage: suitr_preferences = list(permutations([-i-1 for i in range(n)]))
        sage: revr_preferences = list(permutations([i+1 for i in range(n)]))
        sage: for player in range(n):
        ....:     big_game.suitors()[player].pref = suitr_preferences[player]
        ....:     big_game.reviewers()[player].pref = revr_preferences[-player]
        sage: big_game.solve()
        {1: -1, 2: -8, 3: -9, 4: -10, 5: -7, 6: -6, 7: -5, 8: -4, 9: -3, 10: -2}

That is 2 * 10! * 10 == 72576000 integers plus other stuff. Might consider dropping n = 8 instead for this example.

[jdemeyer]

comment:21

Maybe, but I consider lowering the actual memory requirements of doctests outside the scope of this ticket.

[jdemeyer]

comment:22

This is failing badly on the patchbot

[jdemeyer]

comment:23

The problem seems to be that setrlimit() is done way too late. We need to limit the memory before starting Sage.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b4001c6 to 38f9823

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

38f9823

Run doctests with limited memory

[jdemeyer]

Description changed:

--- 
+++ 
@@ -3,12 +3,9 @@
 2. It is good to check that doctests do not use a large amount of memory.
 3. It allows to doctest graceful recovery when memory cannot be allocated by intentionally allocating more memory than available.

-I suggest to limit the virtual memory for doctests to 4500MiB. This may seem like a lot, but these doctests do not pass with a limit of 4000MiB:
+I suggest to limit the virtual memory for doctests. The following two files contain the tests which need the most memory:

-src/sage/matrix/matrix_integer_dense.pyx -src/sage/rings/polynomial/pbori.pyx src/sage/game_theory/matching_game.py -src/sage/rings/integer.pyx +src/sage/schemes/elliptic_curves/heegner.py

-The one requiring the most memory is `src/sage/game_theory/matching_game.py`

[jdemeyer]

comment:25

New attempt, this time limiting the memory in the sage-runtests script. Let's see what the patchbot says...

[jdemeyer]

comment:26

Hmm, patchbots won't test this because it's "unsafe".

[jdemeyer]

comment:27

In case it helps, I did test this on sardonis (ppc64le with lots of RAM) and on my laptop (x86_64 with 6GB of RAM) and it passed tests. 32-bit should also pass for the simple reason that the condition memlimit <= sys.maxsize() will be false.

I just got hit again by the issue of doctests taking infinite memory, apparently this creates an infinite list:

sage: L = [1, 2, 3]
sage: L.extend(-x for x in L)

I'm just saying that this ticket protects against stupid mistakes like this, which might otherwise cause the system to start to swap and become unresponsive.

[tscrim]

comment:28

Replying to @jdemeyer:

In case it helps, I did test this on sardonis (ppc64le with lots of RAM) and on my laptop (x86_64 with 6GB of RAM) and it passed tests. 32-bit should also pass for the simple reason that the condition memlimit <= sys.maxsize() will be false.

Everything seems to be okay on my laptop as well (x86_64 with 8Gb of RAM).

I just got hit again by the issue of doctests taking infinite memory, apparently this creates an infinite list:

sage: L = [1, 2, 3]
sage: L.extend(-x for x in L)

I'm actually slightly surprised Python doesn't catch that as it does so well (sometimes too well) with mutating dicts.

I'm just saying that this ticket protects against stupid mistakes like this, which might otherwise cause the system to start to swap and become unresponsive.

Indeed. Let's kick this to the buildbots and into a beta to see if this causes any trouble.

[tscrim]

Reviewer: Travis Scrimshaw

[vbraun]

comment:29

I'm getting

sage -t --warn-long 69.8 src/sage/game_theory/matching_game.py
**********************************************************************
File "src/sage/game_theory/matching_game.py", line 161, in sage.game_theory.matching_game.MatchingGame
Failed example:
    revr_preferences = list(permutations([i+1 for i in range(n)]))
Exception raised:
    Traceback (most recent call last):
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 515, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 885, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.game_theory.matching_game.MatchingGame[17]>", line 1, in <module>
        revr_preferences = list(permutations([i+Integer(1) for i in range(n)]))
    MemoryError

Here n=10, so 10! permutations...

PS: This is x86_64 with 32GB ram

[kiwifb]

comment:30

Same as Volker. Also x86_64 with 32GB (although free says 12GB are free and 25GB available).

[jdemeyer]

comment:31

Replying to @vbraun:

I'm getting

sage -t --warn-long 69.8 src/sage/game_theory/matching_game.py
**********************************************************************
File "src/sage/game_theory/matching_game.py", line 161, in sage.game_theory.matching_game.MatchingGame
Failed example:
    revr_preferences = list(permutations([i+1 for i in range(n)]))
Exception raised:
    Traceback (most recent call last):
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 515, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 885, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.game_theory.matching_game.MatchingGame[17]>", line 1, in <module>
        revr_preferences = list(permutations([i+Integer(1) for i in range(n)]))
    MemoryError

Did you run all doctests? Is this the only file which fails?

[kiwifb]

comment:32

Full failure

sage -t --long /usr/lib64/python2.7/site-packages/sage/game_theory/matching_game.py
**********************************************************************
File "/usr/lib64/python2.7/site-packages/sage/game_theory/matching_game.py", line 161, in sage.game_theory.matching_game.MatchingGame
Failed example:
    revr_preferences = list(permutations([i+1 for i in range(n)]))
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 518, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 888, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.game_theory.matching_game.MatchingGame[17]>", line 1, in <module>
        revr_preferences = list(permutations([i+Integer(1) for i in range(n)]))
    MemoryError
**********************************************************************
File "/usr/lib64/python2.7/site-packages/sage/game_theory/matching_game.py", line 162, in sage.game_theory.matching_game.MatchingGame
Failed example:
    for player in range(n):
        big_game.suitors()[player].pref = suitr_preferences[player]
        big_game.reviewers()[player].pref = revr_preferences[-player]
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 518, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 888, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.game_theory.matching_game.MatchingGame[18]>", line 3, in <module>
        big_game.reviewers()[player].pref = revr_preferences[-player]
    NameError: name 'revr_preferences' is not defined
**********************************************************************
File "/usr/lib64/python2.7/site-packages/sage/game_theory/matching_game.py", line 165, in sage.game_theory.matching_game.MatchingGame
Failed example:
    big_game.solve()
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 518, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 888, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.game_theory.matching_game.MatchingGame[19]>", line 1, in <module>
        big_game.solve()
      File "/usr/lib64/python2.7/site-packages/sage/game_theory/matching_game.py", line 901, in solve
        self._is_complete()
      File "/usr/lib64/python2.7/site-packages/sage/game_theory/matching_game.py", line 668, in _is_complete
        raise ValueError("suitor preferences are not complete")
    ValueError: suitor preferences are not complete
**********************************************************************

I cannot talk for Volker but this is the only file for which I have a failure related to this ticket. The other failure I got was #23497 comment:39

[vbraun]

comment:33

Thats the only file that failed for me, too

[jdemeyer]

comment:34

If you both have only that file failing, it's a good reason to revisit those doctests after all and make them use less memory.

[kiwifb]

comment:35

But it didn't fail before this ticket and this ticket doesn't touch this particular file.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 38f9823 to 06d4307

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

06d4307

Simplify doctest in matching_game.py

[jdemeyer]

comment:37

Replying to @kiwifb:

But it didn't fail before this ticket and this ticket doesn't touch this particular file.

The point of this ticket is to limit the amount of memory that doctests are allowed to use. Apparently matching_game.py is the file which uses the most memory of all doctests. There is no reason why the testcase in the matching_game.py doctests must be so large. I just simplified that.

[jdemeyer]

comment:38

Replying to @kiwifb:

But it didn't fail before this ticket and this ticket doesn't touch this particular file.

So what would you suggest instead? Simply increasing the limit from 3300 MiB to some higher number?

[kiwifb]

comment:39

Replying to @jdemeyer:

Replying to @kiwifb:

But it didn't fail before this ticket and this ticket doesn't touch this particular file.

So what would you suggest instead? Simply increasing the limit from 3300 MiB to some higher number?

No, after reading the description again properly, the fact that it passed before for me is irrelevant to what you try to achieve. I'll put it back to positive review to send it back to the bots.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -9,3 +9,5 @@
 src/sage/game_theory/matching_game.py
 src/sage/schemes/elliptic_curves/heegner.py

+ +This branch also reduces the memory needed for matching_game.py, such that heegner.py is now the doctest which requires the most memory.

[jdemeyer]

comment:41

Thanks!

[kiwifb]

comment:42

Now I get this on Volker's develop branch

sage -t --long /usr/lib64/python2.7/site-packages/sage/rings/integer.pyx
**********************************************************************
File "/usr/lib64/python2.7/site-packages/sage/rings/integer.pyx", line 2828, in sage.rings.integer.Integer.divisors
Failed example:
    for i in range(20):  # long time
        try:
            alarm(RDF.random_element(1e-3, 0.5))
            _ = n.divisors()
            cancel_alarm()  # we never get here
        except AlarmInterrupt:
            pass
Exception raised:
    Traceback (most recent call last):
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 518, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/lib64/python2.7/site-packages/sage/doctest/forker.py", line 888, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.rings.integer.Integer.divisors[19]>", line 4, in <module>
        _ = n.divisors()
      File "sage/rings/integer.pyx", line 2897, in sage.rings.integer.Integer.divisors (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/cythonized/sage/rings/integer.c:19409)
        ptr = <unsigned long*>check_allocarray(divisor_count, 3 * sizeof(unsigned long))
      File "memory.pxd", line 87, in cysignals.memory.check_allocarray (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/build/cythonized/sage/rings/integer.c:45630)
    MemoryError: failed to allocate 33554432 * 24 bytes
**********************************************************************

I have another failure in that file that is not related to memory, so there is probably problems with other tickets touching that file. I'll see if I can find out which one(s).

[vbraun]

Changed branch from u/jdemeyer/run_doctests_with_limited_memory to 06d4307