Interpreter is too slow reading a big polynomial
I'm trying to read a large polynomial: about 6Mbytes, about 127000 terms in 100 indets, coefficients in
Make it quicker and less RAM hungry!
#2 Updated by John Abbott about 2 years ago
I have tried doing some profiling. The interpreter takes quadratic time (in the number of terms) to read a polynomial from its printed form, i.e. as a sum of terms.
Somewhat ironically, for polynomials with many terms it is significantly faster to read them as a string and then use
ReadExpr to convert it into a ring element. The point here is that
ReadExpr knows to expect a ring element whereas the interpreter has to be able to cope with expressions of any type.
An ideal situation would be to have the parser generate n-ary nodes for sums. I've no idea how hard this might be; it would certainly involve some "deep" changes to the parse tree structure, and also the interpreter.
An alternative would be to hack the interpreter so that it uses geobuckets when summing values in a polynomial ring. This might be quite messy and fiddly to get right :-/
#3 Updated by John Abbott almost 2 years ago
The solution to use
ReadExpr(P, "poly-as-a-string") works tolerably well from the point of view of the interpreter, but it is insufferably slow inside emacs if the string is a long literal (today's example was 20Mbytes long).
The problem is that emacs gets too slow when there are long lines. Note that changing from
fundamental-mode in emacs did help a bit, but it was still far too slow. Should we revitalize issue #576? (about allowing juxtaposition of string literals to cause the parser to concatenate them)
#4 Updated by John Abbott almost 2 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
I have taken one of Mario's big polys: this one is about 6Mbyte when printed out.I tried to ways of converting the string back to a poly:
- (A) putting the whole string on one very long line;
- (B) splitting the string into a sum of about 81600 short strings (one on each line).
Method (A) took about 7.2s on my MacBook, whereas method (B) took almost 180s.
The point being that computing the sum
str1+str2+...+str81600 has quadratic complexity since the interpreter computes each initial subsum.
I note that editing the file for approach (B) was still a bit slow in
cocoa5-mode; especially "semicolon" and "newline" were quite slow. Editing the file for approach (A) seemed to be far worse (almost every character was slow to appear).