Project

General

Profile

Slug #875

Interpreter is too slow reading a big polynomial

Added by John Abbott about 2 years ago. Updated almost 2 years ago.

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
enhancing/improving
Target version:
Start date:
03 May 2016
Due date:
% Done:

10%

Estimated time:
Spent time:

Description

I'm trying to read a large polynomial: about 6Mbytes, about 127000 terms in 100 indets, coefficients in QQ (but all quite small integers). CoCoA-5 is taking way too long (over 50mins), and too much RAM (over 600Mbytes).

Make it quicker and less RAM hungry!


Related issues

Related to CoCoALib - Slug #874: factor: too slow on largish multivariate polyIn Progress2016-05-03

Related to CoCoA-5 - Design #576: Disallow juxtaposition for string literals?Closed2014-06-25

Related to CoCoA-5 - Feature #781: Option to "fold" long lines?New2015-09-28

Related to CoCoA-5 - Design #473: Multiline string literals - useful or obsolescent?Closed2014-03-13

Related to CoCoA-5 - Slug #434: Emacs UI: very slow when input file is big (with long lines)New2014-02-06

History

#1 Updated by John Abbott about 2 years ago

  • Related to Slug #874: factor: too slow on largish multivariate poly added

#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 cocoa5-mode to 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).

#5 Updated by John Abbott almost 2 years ago

  • Related to Design #576: Disallow juxtaposition for string literals? added

#6 Updated by John Abbott almost 2 years ago

  • Related to Feature #781: Option to "fold" long lines? added

#7 Updated by John Abbott almost 2 years ago

  • Related to Design #473: Multiline string literals - useful or obsolescent? added

#8 Updated by John Abbott almost 2 years ago

  • Related to Slug #434: Emacs UI: very slow when input file is big (with long lines) added

Also available in: Atom PDF