Singular interface wasting time by waiting for the prompt too often

[simon-king-jena]

There are two fundamental differences between the Singular and the Gap interfaces:

1. The Singular interface uses a synchronisation method in each call to its eval method. Gap doesn't.
2. The Gap interface deletes variables by declaring that their name may be overwritten. This is not possible in Singular, since Singular variables are statically typed. Thus, the Singular interface explicitly kills the underlying variable in Singular, which requires one call to _eval_line for each variable that is to be deleted.

Unfortunately, waiting for the prompt to appear in a pseudo terminal may be very costly on some systems, since select.select() may be very slow - see #10294. So, additional calls to _eval_line should be strictly avoided!

The first point makes me wonder: Why has the synchronisation method become necessary for Singular but not for Gap?

The second point makes me wonder whether it is really necessary to use one _eval_line for each single deletion.

Moreover, I wonder whether the two points are actually related: I could imagine that synchronisation became necessary when garbage collection, accidentally performed inside an _eval_line, and thus sending an _eval_line inside an outer _eval_line, caused a dead lock in the outer _eval_line. Was that the case, historically?

Suggestions:

1. singular.eval(cmd) is currently simply passing cmd to _eval_line, after synchronisation and after killing unused variables. I suggest to add the code for killing unused variables to cmd, thus using _eval_line only once.
2. If my above guess on the role of synchronisation is correct, then one could simply drop synchronisation after implementing my first suggestion.

This is related with #10294 and perhaps with #10295. Cc to William and Willem-Jan, since they wrote the synchronisation code.

Depends on #7377.

For the release manager:

Apply

• attachment: trac10296_singular_overhead_combined.patch

Depends on #11431

CC: @williamstein @wjp @alexanderdreyer @malb @nexttime

Component: interfaces

Keywords: Singular, _eval_line, synchronization, synchronisation

Author: Simon King

Reviewer: Martin Albrecht

Merged: sage-5.0.beta8

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

[simon-king-jena]

comment:1

Committing the kills in singular.eval by prepending stuff to the given command turned out to break a lot of doc tests, since they test against the given command showing up in the output. But I think one could be even closer to the Gap interface.

Recall that in the Gap interface, variables are freed by allowing to re-use their names. So, memory allocated in Gap is only freed when the old variable is actually overwritten.

In Singular, memory is freed by the command kill. I suggest to use this command not inside singular.eval but inside SingularElement.__init__: It is put in front of the command that creates the new variable. Then, the analogy between Gap and Singular interfaces is rather close: Memory in Gap or in Singular is freed only when a new Element is created -- by overwriting the old stuff in the case of Gap, or by killing the old stuff in the case of Singular.

Moreover, I removed the synchronisation code, since it seems to me that synchronisation is not really necessary if the garbage collection is not using an additional _eval_line (which is the case with my suggestion).

So, there remains only one call to select.select when creating a new Singular element, rather than two plus the number of old variables to be killed.

Indeed, my approach reduces the overhead in using the Singular interface by 2/3 in the test above!

But there occur two doctest failures, that I have to deal with now.

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:3

My patch does the following.

Garbage Collection

In the Singular interface, freeing the memory used for old variables in Singular requires to send a "kill" command to Singular, presumably by _eval_line.

A problem would result if garbage collection would create such _eval_line inside an outer _eval_line: The inner _eval_line would cause the outer _eval_line to hang forever. I guess this was the reason why the del method does not actually delete the variables but only marks them for deletion; the actual deletion is postponed to the next use of "eval".

I guess that for the same reason, synchronisation is done at the beginning of "eval". Please correct me, if the reason for synchronising so frequently is different!

I suggest to do the deletions a bit less frequently, namely in the "set" method rather than in the "eval" method. Moreover, I suggest to send the kill command not by a separate _eval_line (one for each old variable), but to prepend the join of all kill commands to the command that creates the new variable.

Since killing does not require an additional _eval_line, nesting can not occur. So, synchronisation is not needed.

Overhead Reduction

As mentioned in the ticket description, calling _eval_line frequently is bad, since waiting for the Singular prompt in the output of a pseudo terminal produces a massive overhead (up to 22ms per call) on some machines.

My patch removes synchronisation (which avoids one call to _eval_line per call to eval), and killing old variables does not require any additional _eval_line. So, in the example proposed in the ticket description, the wall time drops by 2/3!

Miscellaneous

Synchronisation used to fail with an AttributeError for the GAP interface. It is fixed by the patch.

I tried to make everything more stable, by giving more opportunities to detect that the interface crashed, and restarting if necessary.

Of course, I added documentation and tests that (I think) cover all issues mentioned here. Moreover, I added tests covering some optional arguments to _eval_line.

For me, sage -testall passes. Hence, ready for review!

[simon-king-jena]

comment:4

The old patch needed to be rebased.

The new patch version should apply on top of sage-4.6.1.alpha3. I am now running doctests, but I'll keep it "needs review" for now.

[simon-king-jena]

comment:5

Not good. There are several timeouts in the tests. I need to work on it.

[simon-king-jena]

comment:6

Replying to @simon-king-jena:

Not good. There are several timeouts in the tests.

It seems that I forgot sage -b. I repeated the tests that previously had a timeout, and now it is fine.

I put it back to "needs review".

[simon-king-jena]

comment:7

Since the nagbot currently does not seem to send messages: I hope you don't mind that I'm sending a reminder about speeding up the Singular pexpect interface.

[simon-king-jena]

comment:8

I am sorry to nag you again - could someone take a look at the patch? The patchbot has no complaints at that point.

[simon-king-jena]

comment:9

Too late...

Meanwhile the patchbot finds some errors. I try to find the reason.

[simon-king-jena]

Work Issues: fix tests

[simon-king-jena]

comment:10

Apparently, a StdOutContext was recently introduced, and the expected output for one doctest has changed by my patch. I changed the test slightly, so that now it should work.

[simon-king-jena]

Changed work issues from fix tests to none

[simon-king-jena]

comment:11

I think reducing the overhead in the Singular pexpect interface by 2/3 is a good thing. But the ticket is starting to become old.

Review, anyone?

[malb]

comment:12

• the patch applies cleanly against 4.7.alpha3
  • long doctests pass
  • the patch is well documented
  • the patch does look okay

So all good. The only caveat: I cannot claim I thought long and hard about the possible implications of changing this stuff. But unless someone comes up with a good example why Simon's approach is wrong, I'd say positive review.

[malb]

Reviewer: Martin Albrecht

[malb]

comment:57

Hi,

• attachment: trac_10296-restart_if_needed.patch has no commit message
• I get lots of errors when applying attachment: trac10296_expect_on_nonlinux.patch to 5.0-beta6?

[simon-king-jena]

comment:58

Bad. Needs work, then...

Concerning the missing commit message: I think I'll produce a combined patch with a commit message.

[simon-king-jena]

Work Issues: rebase

[simon-king-jena]

comment:59

The first patch only applies with fuzz 2, because of #11431 (-> new dependency). The conflict is in the author list, easy to fix.

[simon-king-jena]

Dependencies: #11431

[simon-king-jena]

comment:60

I produced a combined patch and verified that it cleanly applies on sage-5.0.beta6.

I started doctests without the patch, and later I will repeat with the patch. But for now it needs review...

Apply trac10296_singular_overhead_combined.patch

[simon-king-jena]

Changed work issues from rebase to none

[simon-king-jena]

comment:61

FWIW: The doc tests of sage-5.0.beta6 with the combined patch applied pass.

[malb]

comment:62

I only have some very minor comments:

• Could you escape EOFError with "``" backquotes so it's printed as code
• You wrote: "Since nesting of _eval_line can not occur during garbage collection" can you explain that, I am not sure I understand.
• why did you indent REMARK etc. further in pid()?

[simon-king-jena]

comment:63

Replying to @malb:

I only have some very minor comments:

• Could you escape EOFError with "``" backquotes so it's printed as code

Done

• You wrote: "Since nesting of _eval_line can not occur during garbage collection" can you explain that, I am not sure I understand.

I elaborated the comment.

Without my patch, garbage collection would result in a call to _eval_line. So, if garbage collection occurs while being in _eval_line, we would have two nested calls to _eval_line. The inner _eval_line would receive the Singular prompt and return. The outer _eval_line would also wait for a Singular prompt -- but Singular would not provide a second prompt. Result: A deadlock.

To my understanding, this is why synchronisation of the Singular interface was necessary. But with my patch, garbage collection does not involve an additional call to _eval_line, and thus the deadlock is prevented without synchronisation.

• why did you indent REMARK etc. further in pid()?

To the contrary, the first line of the doc string of pid() needed to be indented more! Fixed with the new patch version.

Apply trac10296_singular_overhead_combined.patch

[simon-king-jena]

Modify garbage collection in Singular interface, which reduces the overhead. Synchronization of Gap interface. Cope with non-linux pexpect errors

[simon-king-jena]

comment:64

Attachment: trac10296_singular_overhead_combined.patch.gz

Oops, I only had a single backtick around EOFError -- hence, it would be typeset as LaTeX. So, I have updated my patch, with double backticks around EOFError.

[malb]

comment:65

I am satisfied.

But out of curiosity, do you have a simple before/after benchmark you could add to this ticket?

[jdemeyer]

Merged: sage-5.0.beta8

[jdemeyer]

comment:67

There is a doctest error on OpenSolaris, please have a look at #12687.

[jdemeyer]

comment:68

I have also seen the following error:

sage -t  --long -force_lib devel/sage/sage/interfaces/expect.py
**********************************************************************
File "/home/buildbot/build/sage/cleo-1/cleo_full/build/sage-5.0.beta9/devel/sage-main/sage/interfaces/expect.py", line 829:
    sage: singular.interrupt(timeout=1)
Expected:
    False
Got:
    True
**********************************************************************

What does that mean? It is really a failure or should we just increase the timeout?

[simon-king-jena]

comment:69

Replying to @jdemeyer:

What does that mean? It is really a failure or should we just increase the timeout?

That error has always been mysterious to me.

Frankly, I need a break, in the sense of I need to focus on my main project (cohomology and ext algebras) and on my family. Martin, would you be able to take over?

[nexttime]

comment:70

Replying to @simon-king-jena:

Replying to @jdemeyer:

What does that mean? It is really a failure or should we just increase the timeout?

That error has always been mysterious to me.

Frankly, I need a break, in the sense of I need to focus on my main project (cohomology and ext algebras) and on my family.

Yes, have a "break". :-)

Since cleo is not the fastest machine, and I assume the above occurred when doctesting in parallel, I would either ignore it (if it doesn't happen too often), or try with increasing the timeout (to a few seconds) and if that helps, change the doctest permanently.

For the test I don't think it matters whether we wait 1 or 5 seconds, probably even more; it's only important that Singular finally does get interrupted (within perhaps at most half a minute, say).