#11740: reading integers from a file takes quadratic time
--------------------------------+-------------------------------------------
Reporter: zimmerma | Owner: AlexGhitza
Type: defect | Status: new
Priority: major | Milestone: sage-4.7.2
Component: basic arithmetic | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
--------------------------------+-------------------------------------------
Comment(by nbruin):
Replying to [comment:10 zimmerma]:
> I guess you are joking? No serious computer algebra package would
*require* users to write inputs
> in hexadecimal.
I didn't mean the documentation addition as a joke and I didn't mean it as
a requirement. Just a tip to get better performance, and that tip will
apply even if we can get reading decimal integer representations faster.
It's the Python routine that is less-than-optimal here. If we can fix that
and get it accepted upstream: Great! However, CPython is meant to be
general purpose, so doesn't want good MPint performance at all cost
(otherwise they would have moved to GMP already), so our patch would have
to be clean and concise as well.
Patching Python with something that won't be accepted upstream is probably
worse than the disease. Projects like sage-on-gentoo etc. are definitely
not going to be happy with it.
I realized we cannot change the preparser to do "100":->"Integer('100')"
in general. Currently, the "100" in "Integer(100)" gets converted to an
integer constant *at compile time*. Quoting it would trigger a string-to-
int conversion *at run time*. {{{preparse_file}}} alleviates this somewhat
by pushing constant definitions outside of loops, but the principle
remains.
The workaround for the example in the report at the moment is:
{{{
sigma=Integer(file('b.sage').read()[7:])
}}}
In the presence of Python's suboptimal behaviour, "load" simply optimizes
for a different use-case (by preferring to translate via Python's "int").
Actually, that is a wrong optimization! "load <file>.sage" never leads to
a ".pyc" file, so "compile" and "run" time are never separate.
So perhaps
{{{sage.misc.preparser.preparse_file}}} needs a third state for
"numeric_literals" which makes integer constants convert via strings? This
option would be safe if preparse/compile/run are guaranteed to only occur
together. Some experiments would quickly show if this should be done to
all integer literals or just those of certain minimum length. I wouldn't
dare to touch the preparser but someone else might.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11740#comment:11>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
