Skip to content

Use StringIO to format polynomials #35307

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Apr 1, 2023
Merged

Use StringIO to format polynomials #35307

merged 1 commit into from
Apr 1, 2023

Conversation

remyoudompheng
Copy link
Contributor

This patch modifies the repr()/str() method of polynomials to use a StringIO buffer instead of s += ... to build the result string. It is known that repeatedly calling += has quadratic complexity for large Python strings.

Currently calling str() on a high degree polynomial takes a very long amount of time and it may happen accidentally (a script was stuck during 2 hours trying to format a degree 300000 polynomial for an exception message).

sage: p = random_prime(2**96)
sage: K = GF(p**24, 'a')
sage: pol = K["x"].random_element(30000)
# Before patch
sage: %time _ = str(pol)
CPU times: user 2min 22s, sys: 1min 43s, total: 4min 5s
Wall time: 4min 5s
# After patch
sage: %time _ = str(pol)
CPU times: user 692 ms, sys: 21 ms, total: 713 ms
Wall time: 713 ms

📝 Checklist

  • I have made sure that the title is self-explanatory and the description concisely explains the PR.
  • I have linked an issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation accordingly.

⌛ Dependencies

None.

@remyoudompheng
Use StringIO to format polynomials
5da2277 
Polynomials have variable length and repeated Python built-in +=
operator can behave in a quadratic way for large strings.
@github-actions
Copy link

Documentation preview for this PR is ready! 🎉
Built with commit: 5da2277

@codecov-commenter
Copy link

Codecov Report

Patch coverage has no change and project coverage change: -0.01 ⚠️

Comparison is base (f449b14) 88.62% compared to head (5da2277) 88.61%.

Additional details and impacted files 
@@             Coverage Diff             @@
##           develop   #35307      +/-   ##
===========================================
- Coverage    88.62%   88.61%   -0.01%     
===========================================
  Files         2148     2148              
  Lines       398653   398653              
===========================================
- Hits        353308   353273      -35     
- Misses       45345    45380      +35

see 27 files with indirect coverage changes

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

☔ View full report in Codecov by Sentry.
📢 Do you have feedback about the report comment? Let us know in this issue.

@yyyyx4 yyyyx4 added this to the sage-10.0 milestone Mar 19, 2023
@yyyyx4
Copy link
Member

yyyyx4 commented Mar 23, 2023

Looks great! Just one minor (optional) tweak: I believe sbuf = StringIO(); sbuf.write(" ") can be replaced by sbuf = StringIO(" ").

@yyyyx4 yyyyx4 self-requested a review March 23, 2023 18:43
@remyoudompheng
Copy link
Contributor Author

remyoudompheng commented Mar 24, 2023 •
edited
Loading

It was the original form of the patch StringIO(" ") but I reverted that after seeing some failures.
This is because when creating a StringIO with a value, the cursor is set to offset 0 (mainly for reading) so to append data you would have to seek to the end of the buffer, which gives uglier code.

@yyyyx4
Copy link
Member

yyyyx4 commented Mar 24, 2023

Oh, I see. Looks good to me then, thank you for the fix!

@vbraun vbraun merged commit 85da6cc into sagemath:develop Apr 1, 2023
@remyoudompheng remyoudompheng deleted the polystr branch April 3, 2023 09:05
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
1 more reviewer

@yyyyx4 yyyyx4 yyyyx4 approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees
No one assigned
Labels
c: commutative algebra t: performance
Projects
None yet
Milestone
sage-10.0
Development

Successfully merging this pull request may close these issues.
5 participants
@remyoudompheng @codecov-commenter @yyyyx4 @vbraun @mkoeppe