libgap for PermutationGroup

[videlec]

As remarked in this question on ask.sagemath.org a lot of time is spent with pexpect when playing with permutation groups.

In this ticket:

• we interface libgap permutation group so that the following works

sage: p1=libgap.eval("(1,2,3)")
sage: p2=libgap.eval("(3,4,5)")
sage: p1.sage()
(1,2,3)
sage: G=libgap.Group([p1,p2])
sage: G.sage()
Traceback (most recent call last):
...
NotImplementedError: cannot construct equivalent Sage object

• we check that interesting GAP functions such as ClosureGroup, AllBlocks, are available from libgap
• we use them in PermutationGroup inplace of the current gap version

Depends on #27946
Depends on #28354

CC: @nthiery @tscrim

Component: interfaces

Keywords: fpsac2019

Author: Erik Bray

Branch/Commit: 65f8a84

Reviewer: Frédéric Chapoton, Vincent Delecroix, Travis Scrimshaw

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

[embray]

comment:2

The overhead of using pexpect for GAP is especially serious on Cygwin. I believe it to be one of the worst performance hits there, due to the I/O overhead.

It's so slow in fact that I wonder if there isn't a bug/defect in Cygwin related to this. It's normal that there is some additional overhead involved for I/O on Cygwin, but this is especially bad.

[embray]

comment:3

I have a prototype for this in progress that is shaping up pretty well so far. I will likely need help with this part:

we check that interesting GAP functions such as ClosureGroup, AllBlocks, are available from libgap

as I don't know all the math well enough to write interesting tests for this. But I can get most of the skunkworks done and then anyone else who's interested can add on to it.

[embray]

comment:4

The I/O overhead on Cygwin adds up to something on the order of 20x in this test (specially, the _test_cellular test). I tracked this down to being entirely coming from the pexpect communication. On Linux:

sage -t --long src/sage/combinat/symmetric_group_algebra.py
    [422 tests, 30.17 s]

On Cygwin (different machine, but with reasonably good specs):

sage -t --long src/sage/combinat/symmetric_group_algebra.py
    [422 tests, 613.16 s]

More than 10 minutes on this one test! It's by far one of the slowest tests on Cygwin. With my prototype of getting pexpect out of permutation groups I knocked this result down to (again on Cygwin):

sage -t --long src/sage/combinat/symmetric_group_algebra.py
    [422 tests, 25.49 s]

[embray]

comment:5

Unfortunately src/sage/groups/perm_gps/permgroup_named.py still remains by far one of the slowest tests on Cygwin despite my fixes. Unclear as of yet why; maybe several tests using other code that still uses pexpect, or something else...

[embray]

comment:6

Well I found one more pexpect use in permgroup_named; fixing that one knocked it down from ~5 minutes to

sage -t --long src/sage/groups/perm_gps/permgroup_named.py
    [509 tests, 47.12 s]

Which is still about 5 times slower for some reason than that test is on Linux, but progress!

Some of the tests also intentionally use the pexpect interface directly, so nothing to do about that for now.

[embray]

Commit: 75d6b76

[embray]

comment:7

Here is my current prototype for getting pexpect out of permutation groups, and having them use libgap exclusively. For the large part it is quite effective at this. This fixes (among many other examples):

sage: G = SymmetricGroup(3)
sage: %prun G.one()
sage: G.one()
()
sage: gap._expect is None

where previously this was invoking a GAP process through pexpect.

---

Last 10 new commits:

618a0d4	Fix several predicate methods of permutation groups to use libgap.
7a0dd0e	Use libgap for permutation group comparison.
cc5381d	It seems these tests broke again.
d4e81e8	Use libgap in several more methods where it was trivial to make the change, and where it at least didn't break any local tests.
2e60ebe	These tests were marked 'random output' despite the explicit calls to set_random_seed(0), which should have obviated this.
3c8954a	Use libgap for direct_product
220c5e7	Use libgap for character_table
5ab41fb	Some fixes to make ClassFunction work properly with libgap.
db4eeda	Use libgap for PermutationGroup_generic._regular_subgroup_gap
75d6b76	Use libgap for PermutationGroup_generic.molien_series

[embray]

Author: Erik Bray

[embray]

Dependencies: #27946

[embray]

Branch: u/embray/prototype/perm-gps-no-pexpect-gap

[embray]

comment:8

Unfortunately there is still a handful of failing tests with this.

[embray]

comment:9

I think most of the problems are coming from my hacky attempt to make some GapElement objects pickle-able in fcfde85 which can make some surprising results, and is maybe not quite right yet. It should probably be handled in a separate ticket.

[sagetrac-git]

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

075a48a	It seems these tests broke again.
dcc0b11	Use libgap in several more methods where it was trivial to make the change, and where it at least didn't break any local tests.
96c55c3	These tests were marked 'random output' despite the explicit calls to set_random_seed(0), which should have obviated this.
13b0e3c	Use libgap for direct_product
6928f69	Use libgap for character_table
77513fe	Some fixes to make ClassFunction work properly with libgap.
edf2a5d	Use libgap for PermutationGroup_generic._regular_subgroup_gap
6fbdbd1	Use libgap for PermutationGroup_generic.molien_series
42318a9	Fix minor test failure: This will now fail at trying to find a `_libgap_init_` rather than a _gap_init_
c02c2f1	If the values passed to the ClassFunction constructor are already a libgap

[sagetrac-git]

Changed commit from 75d6b76 to c02c2f1

[embray]

comment:11

Fixed the problems that I knew about, though there are likely still others. Although this is set to "needs_work" it would probably be interesting-enough to start playing around with if anyone wants to review.

[embray]

comment:12

With the current version of this branch almost everything works except for a few trivial doctest failures due to new pseudo-random results in some tests.

However, I am also getting a bizarre memory error when running the tests for sage.combinat.tableau that's similar to what I reported in #27681 (but later couldn't reproduce).

[tscrim]

comment:13

+1 for doing this.

[embray]

comment:14

If anyone would like to help test this that would be great for moving forward on this work. In particular, it would be helpful to know if anyone can reproduce the test failure in sage.combinat.tableau, since from my end that is the only major blocker to completing this work.

[embray]

comment:25

I think I'll just remove the dependency. It's not actually a dependency for this ticket, especially since my solution proposed there still doesn't seem to work. The relation between that issue and this ticket is much more indirect than I previously thought.

[vbraun]

comment:26

This breaks the gap interfaces when building with SAGE_DEBUG=yes:

**********************************************************************
File "src/sage/interfaces/gap.py", line 732, in sage.interfaces.gap.Gap_generic._eval_line
Failed example:
    a = gap(3)
Exception raised:
    Traceback (most recent call last):
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1105, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.interfaces.gap.Gap_generic._eval_line[8]>", line 1, in <module>
        a = gap(Integer(3))
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 295, in __call__
        result = self._coerce_from_special_method(x)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 323, in _coerce_from_special_method
        return (x.__getattribute__(s))(self)
      File "sage/structure/sage_object.pyx", line 693, in sage.structure.sage_object.SageObject._gap_ (build/cythonized/sage/structure/sage_object.c:5929)
        return self._interface_(G)
      File "sage/structure/sage_object.pyx", line 669, in sage.structure.sage_object.SageObject._interface_ (build/cythonized/sage/structure/sage_object.c:5475)
        X = I(s)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 288, in __call__
        return cls(self, x, name=name)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/expect.py", line 1438, in __init__
        self._name = parent._create(value, name=name)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 491, in _create
        self.set(name, value)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 1411, in set
        self._eval_line(cmd, allow_use_file=True)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 746, in _eval_line
        expect_eof= (self._quit_string() in line))
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 609, in _execute_line
        x = E.expect_list(self._compiled_full_pattern)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/spawnbase.py", line 369, in expect_list
        return exp.expect_loop(timeout)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/expect.py", line 111, in expect_loop
        incoming = spawn.read_nonblocking(spawn.maxread, timeout)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/pty_spawn.py", line 469, in read_nonblocking
        self.isalive()
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/pty_spawn.py", line 704, in isalive
        alive = ptyproc.isalive()
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/contextlib.py", line 35, in __exit__
        self.gen.throw(type, value, traceback)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/pty_spawn.py", line 25, in _wrap_ptyprocess_err
        raise ExceptionPexpect(*e.args)
    ExceptionPexpect: isalive() encountered condition where "terminated" is 0, but there was no child process. Did someone else call waitpid() on our process?
**********************************************************************
[...]
    [227 tests, 92 failures, 42.83 s]
----------------------------------------------------------------------
sage -t --long src/sage/interfaces/gap.py  # 92 doctests failed
----------------------------------------------------------------------

[embray]

comment:27

I'm not really sure what makes you think that has anything to do with this ticket. That looks like the gap interpreter itself is crashing unexpectedly when running a debug build. But this ticket doesn't change anything about gap itself or the pexpect interface.

[vbraun]

comment:28

I only ran the tests with and without this ticket, I haven't looked at the code. If it is as you say then presumably its some sort of resource exhaustion while running the tests.

[embray]

comment:29

I'll still check if I can reproduce. It could be something like #28106

[embray]

comment:30

I can reproduce it, even with --memlimit=0. Truly baffling, but I guess there must be something...

[embray]

comment:31

Somehow it seems this has caused a regression of something that was supposed to be fixed by #10296. The problems start here:

        The following tests against a bug fixed at :trac:`10296`::

            sage: gap(3)
            3
            sage: gap.eval('quit;')
            ''
            sage: a = gap(3)
            ** Gap crashed or quit executing '\$sage...:=3;;' **
            Restarting Gap and trying again
            sage: a
            3

Instead of gap crashing normally and restarting, we get this error instead:

Exception raised:
    Traceback (most recent call last):
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1105, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.interfaces.gap.Gap_generic._eval_line[8]>", line 1, in <module>
        a = gap(Integer(3))
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 295, in __call__
        result = self._coerce_from_special_method(x)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 323, in _coerce_from_special_method
        return (x.__getattribute__(s))(self)
      File "sage/structure/sage_object.pyx", line 693, in sage.structure.sage_object.SageObject._gap_ (build/cythonized/sage/structure/sage_object.c:5929)
        return self._interface_(G)
      File "sage/structure/sage_object.pyx", line 669, in sage.structure.sage_object.SageObject._interface_ (build/cythonized/sage/structure/sage_object.c:5475)
        X = I(s)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 288, in __call__
        return cls(self, x, name=name)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/expect.py", line 1438, in __init__
        self._name = parent._create(value, name=name)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 491, in _create
        self.set(name, value)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 1411, in set
        self._eval_line(cmd, allow_use_file=True)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 746, in _eval_line
        expect_eof= (self._quit_string() in line))
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 609, in _execute_line
        x = E.expect_list(self._compiled_full_pattern)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/spawnbase.py", line 369, in expect_list
        return exp.expect_loop(timeout)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/expect.py", line 111, in expect_loop
        incoming = spawn.read_nonblocking(spawn.maxread, timeout)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/pty_spawn.py", line 469, in read_nonblocking
        self.isalive()
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/pty_spawn.py", line 704, in isalive
        alive = ptyproc.isalive()
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/contextlib.py", line 35, in __exit__
        self.gen.throw(type, value, traceback)
      File "/home/buildbot-sage/slave/sage_git/build/local/lib/python2.7/site-packages/pexpect/pty_spawn.py", line 25, in _wrap_ptyprocess_err
        raise ExceptionPexpect(*e.args)
    ExceptionPexpect: isalive() encountered condition where "terminated" is 0, but there was no child process. Did someone else call waitpid() on our process?

after which point the gap interface never recovers. It's only happening in the tests though. I can't reproduce interactively. Running the tests with --serial makes no difference.

[sagetrac-git]

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

2fc1096	These tests were marked 'random output' despite the explicit calls to set_random_seed(0), which should have obviated this.
b123422	Use libgap for direct_product
f35a967	Use libgap for character_table
4aacf0f	Some fixes to make ClassFunction work properly with libgap.
4fe1132	Use libgap for PermutationGroup_generic._regular_subgroup_gap
3ef4b4b	Use libgap for PermutationGroup_generic.molien_series
9205aa6	Fix minor test failure: This will now fail at trying to find a `_libgap_init_` rather than a _gap_init_
0d0e1bb	If the values passed to the ClassFunction constructor are already a libgap
c8c5ecf	Fixed slightly different output on a few tests due to PRNG differences related
65f8a84	Update this test to still use the gap pexpect interface.

[sagetrac-git]

Changed commit from cc64910 to 65f8a84

[embray]

comment:33

Rebased on current develop, and the latest commit fixes the immediate problem in the test suite.

I believe there is still an underlying problem with libgap/gap interaction which is not yet addressed though (and is probably not new as of this ticket, but just more likely to occur with libgap being used more extensively).

[embray]

comment:34

This might be related to gap-system/gap#3380 , with libgap wait()-ing on random child processes inappropriatly.

[embray]

comment:35

It seems that, at least theoretically, we already do disable GAP's default SIGCHLD handler.

[embray]

comment:36

Bizarrely, even after backing out that last test update, and rebuilding, I can't reproduce the issue anymore either. I think it might have actually had something to do with sage-cleaner.

Please send this to the buildbots again. I really don't think the issue is caused by this ticket, but is something more ephemeral that it happens to provoke somehow.

[embray]

comment:37

Yes, this has got to have something to do with sage-cleaner. If I just start a sage-cleaner process on its own, then run ./sage -t src/sage/interfaces/gap.py I can reproduce the issue reliably.

[embray]

comment:38

Soft dependency on #28354: Although I don't think the issues are particularly related, if those pexpect exceptions about isalive() keep happening, merging #28354 first should alleviate them.

[vbraun]

Changed dependencies from #27946 to #27946, #28354

[vbraun]

Changed branch from u/embray/prototype/perm-gps-no-pexpect-gap to 65f8a84