I have added case study for the performance issue i am working on. https://github.com/sympy/sympy/wiki/GSoC-2019-Application-SHIKSHA-RAWAT-:-Benchmarks-and-performance
Please review the proposal and suggest changes. I have not completed the implementation plans. But i will add that part too by tonight. On Mon, Apr 1, 2019 at 7:55 PM Shiksha Rawat <[email protected]> wrote: > I am currently trying to improve the performance in the PR > https://github.com/sympy/sympy/pull/16509 > To complete my gsoc proposal should i write the way i am trying to improve > the performance and how i have planned to proceed ? > > Because the idea of benchmarking and performance mainly involves trying to > find suitable substitute for a bottleneck. > > On Sat, Mar 30, 2019 at 1:29 AM Shiksha Rawat <[email protected]> > wrote: > >> Okay, i have continued the discussion on the issue itself. >> >> On Sat, Mar 30, 2019 at 12:06 AM Aaron Meurer <[email protected]> wrote: >> >>> On Fri, Mar 29, 2019 at 12:07 PM Shiksha Rawat <[email protected]> >>> wrote: >>> > >>> > Thank you for the replies. >>> > >>> > As suggested by Aaron , I figured out ways to fix the performance of >>> https://github.com/sympy/sympy/issues/16249. >>> > One of the easy way is to disable _find_localzeros >>> > The function is creating a set of non-minimal(non-maximal) numbers and >>> to identify these it is making comparison between every two possible >>> combination of numbers. >>> > But these non-minimal values can be computed by sorting the values in >>> ascending or descending order. >>> > This sorting can be done by using algorithms like merge-sort with >>> complexity (nlogn) which is much better than currently used n**2. >>> > So second option is to use better algorithms. >>> > >>> > Which would be better or which one should i use to fix this issue? >>> > Please suggest. >>> >>> It depends on what the performance is like, and what the tradeoffs >>> are. Often when trying to make something faster you may think that >>> something will improve performance, but after implementing it you'll >>> find that it doesn't change it at all, or it even makes it worse. So >>> you always have to try it out and profile it. >>> >>> It would be better to move the discussion of this specific issue to >>> the issue itself. >>> >>> Aaron Meurer >>> >>> > >>> > I am also trying to find regressions on which i could work in >>> https://github.com/sympy/sympy_benchmarks. >>> > >>> > On Thu, Mar 28, 2019 at 9:38 PM Jason Moore <[email protected]> >>> wrote: >>> >> >>> >> We have a benchmark repository that is run periodically: >>> https://github.com/sympy/sympy_benchmarks >>> >> >>> >> I recommend starting there. You can find a number of regressions that >>> can be investigated. >>> >> >>> >> Jason >>> >> moorepants.info >>> >> +01 530-601-9791 >>> >> >>> >> >>> >> On Wed, Mar 27, 2019 at 5:17 PM Aaron Meurer <[email protected]> >>> wrote: >>> >>> >>> >>> I agree with Oscar. I would also add that it's usually not trivial to >>> >>> determine where the bottlenecks are in SymPy. So I would write more >>> >>> about how you intend to profile the code. >>> >>> >>> >>> Perhaps it would be useful to take an existing thing that is slow in >>> >>> SymPy (you can use the performance issue label as a guide, or find >>> >>> something yourself, >>> >>> >>> https://github.com/sympy/sympy/issues?q=is%3Aopen+is%3Aissue+label%3APerformance >>> ), >>> >>> and try to fix the performance, documenting how you went about >>> finding >>> >>> the bottleneck and fixing it. This can be used as a case study in >>> your >>> >>> application. >>> >>> >>> >>> Also I would note that currently the benchmarking infrastructure for >>> >>> SymPy is quite bad (basically nonexistent). See >>> >>> >>> https://github.com/sympy/sympy/wiki/GSoC-2019-Ideas#benchmarks-and-performance >>> . >>> >>> It's fine if you do not want to work on that specifically, but you >>> >>> should note that you will be running the benchmarks on your own >>> >>> computer to find performance regressions. Not all performance issues >>> >>> are regressions either (some things have always been slow), so you >>> >>> should consider absolute numbers as well as relative numbers. >>> >>> >>> >>> Aaron Meurer >>> >>> >>> >>> On Wed, Mar 27, 2019 at 5:11 PM Oscar Benjamin >>> >>> <[email protected]> wrote: >>> >>> > >>> >>> > This looks like good work to do. I don't know how these >>> applications >>> >>> > are evaluated but my thought if I was reviewing this would be that >>> it >>> >>> > seems quite vague. This would probably be a more enticing proposal >>> if >>> >>> > it had some specific suggestions of changes that would speed things >>> >>> > up. >>> >>> > >>> >>> > I can tell you now what is slow in the ODE module: currently even >>> for >>> >>> > the simplest ODEs all matching code is run for all the possible >>> >>> > methods even after a suitable method has been found. It would be >>> much >>> >>> > better to identify the most immediately usable solver and then use >>> >>> > that without matching all the others. This needs a refactor of the >>> >>> > module though and a redesign of the basic approach used by dsolve. >>> I >>> >>> > want that to happen as an ultimate goal but I would like to see >>> better >>> >>> > test coverage first. >>> >>> > >>> >>> > On Wed, 27 Mar 2019 at 09:56, Shiksha Rawat < >>> [email protected]> wrote: >>> >>> > > >>> >>> > > >>> https://github.com/sympy/sympy/wiki/GSoC-2019-Application-SHIKSHA-RAWAT-:-Benchmarks-and-performance >>> >>> > > >>> >>> > > I have designed a proposal for Benchmarks and Perfromance idea, >>> though it is not complete yet. >>> >>> > > >>> >>> > > Can Jason Moore, Aaron and Oscar please review that and suggest >>> changes? >>> >>> > > >>> >>> > > >>> >>> > > On Tue, Mar 19, 2019 at 11:53 PM Shiksha Rawat < >>> [email protected]> wrote: >>> >>> > >> >>> >>> > >> I did further digging on the idea mentioned by Jason Moore. >>> >>> > >> >>> >>> > >> Figuring out the main bottlenecks for sympy : The best way to >>> figure out these bottlenecks would be to designing a typical problem for >>> each module for example mass spring damper for physics and computing time >>> taken by sympy to give the output.If it is greater then expected than or a >>> predefined threshold than analyzing the codebase of that module for >>> possible changes to decrease computation time. And the results of >>> predefined benchmarks could also be used. >>> >>> > >> >>> >>> > >> Creating benchmarks : >>> https://media.readthedocs.org/pdf/asv/v0.1.1/asv.pdf >>> >>> > >> I think this documentation could come in handy for creating the >>> benchmarks. The requirement of a particular benchmark could be made on the >>> basis of the bottlenecks which we will figure out. >>> >>> > >> >>> >>> > >> Improving performance: I think the best way to improve >>> performance would be cleaning up the codebase first and then making changes >>> in the algorithms used according to the requirements. >>> >>> > >> >>> >>> > >> Future Scope: Figuring out a method by which each PR also has >>> to give information about the time the modules related to that PR will take >>> to give output of problems associated with that module. (those mentioned in >>> figuring out the bottlenecks point). >>> >>> > >> >>> >>> > >> I might be wrong about the ideas mentioned above. So I want >>> suggestions from the mentors. >>> >>> > >> >>> >>> > >> Thanks. >>> >>> > >> >>> >>> > >> On Fri, Mar 15, 2019 at 9:48 PM Shiksha Rawat < >>> [email protected]> wrote: >>> >>> > >>> >>> >>> > >>> I am really interested in taking up that idea. Can you suggest >>> where or how should I start from because up till now I was just focusing on >>> the physics module and benchmarks related to it? >>> >>> > >>> I am still trying to find how could we optimize matrix >>> operations. >>> >>> > >>> >>> >>> > >>> >>> >>> > >>> On Fri, Mar 15, 2019 at 8:46 PM Jason Moore < >>> [email protected]> wrote: >>> >>> > >>>> >>> >>> > >>>> The mechanics speedup idea is really just a narrow version of >>> the profiling and benchmarking idea (focuses on just a couple of packages). >>> Maybe a proposal that focuses on figuring out the main bottlenecks for >>> sympy, creating benchmarks for them, and then improving performance is a >>> good proposal idea that will ultimately help all the packages. I'm happy to >>> support and mentor on that idea if someone wants to submit. >>> >>> > >>>> >>> >>> > >>>> Jason >>> >>> > >>>> moorepants.info >>> >>> > >>>> +01 530-601-9791 >>> >>> > >>>> >>> >>> > >>>> >>> >>> > >>>> On Thu, Mar 14, 2019 at 2:19 PM Aaron Meurer < >>> [email protected]> wrote: >>> >>> > >>>>> >>> >>> > >>>>> I agree. The biggest challenge with symbolic matrices is >>> expression >>> >>> > >>>>> blow up. In some cases it is unavoidable, for instance, >>> symbolic >>> >>> > >>>>> eigenvalues/eigenvectors use the symbolic solutions to >>> polynomials, >>> >>> > >>>>> which are complicated in the general case for n > 2. >>> >>> > >>>>> >>> >>> > >>>>> One thing I meant by "overhead" is that if the type of a >>> matrix's >>> >>> > >>>>> entries is known to all be rational numbers, for instance, >>> we can >>> >>> > >>>>> operate directly on those numbers, ideally using fast number >>> types >>> >>> > >>>>> like gmpy.mpq. If they are all rational functions, we can use >>> >>> > >>>>> polynomial algorithms that operate on rational functions. >>> These always >>> >>> > >>>>> keep rational functions in canonical form, and the zero >>> equivalence >>> >>> > >>>>> testing becomes literally "expr == 0" (no simplification >>> required). >>> >>> > >>>>> These can be more efficient than general symbolic >>> manipulation. >>> >>> > >>>>> >>> >>> > >>>>> This is how the polys module is structured. See >>> >>> > >>>>> https://docs.sympy.org/latest/modules/polys/internals.html. >>> It would >>> >>> > >>>>> be nice to have a similar structure in the matrices, where a >>> matrix >>> >>> > >>>>> can have a ground domain (or type) associated with its >>> underlying >>> >>> > >>>>> data. >>> >>> > >>>>> >>> >>> > >>>>> Aaron Meurer >>> >>> > >>>>> >>> >>> > >>>>> On Thu, Mar 14, 2019 at 2:52 PM Oscar Benjamin >>> >>> > >>>>> <[email protected]> wrote: >>> >>> > >>>>> > >>> >>> > >>>>> > (Replying on-list) >>> >>> > >>>>> > >>> >>> > >>>>> > On Thu, 14 Mar 2019 at 20:37, Alan Bromborsky < >>> [email protected]> wrote: >>> >>> > >>>>> > > >>> >>> > >>>>> > > Since most pc these days have multiple cores and threads >>> what not use >>> >>> > >>>>> > > parallel algorithyms. For honesty I must state I have a >>> vested interest >>> >>> > >>>>> > > since I have a pc with a threadripper cpu with 16 cores >>> and 32 threads. >>> >>> > >>>>> > >>> >>> > >>>>> > Parallel algorithms can offer improvement. Your 16 cores >>> might amount >>> >>> > >>>>> > to a 10x speed up if used well for this kind of thing. The >>> >>> > >>>>> > double-threading probably can't be exploited in CPython. >>> >>> > >>>>> > >>> >>> > >>>>> > However I think that many of the things that SymPy is slow >>> for have >>> >>> > >>>>> > *really* bad asymptotic performance: think O(N!) rather >>> than O(N^2). >>> >>> > >>>>> > Many orders of magnitude improvements can be made by >>> spotting these >>> >>> > >>>>> > where more efficient methods are possible. It's not hard >>> in a CAS to >>> >>> > >>>>> > accidentally generate enormous expressions and end up >>> simplifying them >>> >>> > >>>>> > down again. This leads to many situations where it would >>> be vastly >>> >>> > >>>>> > more efficient to somehow take a more direct route. >>> >>> > >>>>> > >>> >>> > >>>>> > -- >>> >>> > >>>>> > You received this message because you are subscribed to >>> the Google Groups "sympy" group. >>> >>> > >>>>> > To unsubscribe from this group and stop receiving emails >>> from it, send an email to [email protected]. >>> >>> > >>>>> > To post to this group, send email to >>> [email protected]. >>> >>> > >>>>> > Visit this group at https://groups.google.com/group/sympy. >>> >>> > >>>>> > To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAHVvXxTeAGZUv1kdtKCvBRodMZPyX5jHh76G0M49VshwMziJZA%40mail.gmail.com >>> . >>> >>> > >>>>> > For more options, visit https://groups.google.com/d/optout >>> . >>> >>> > >>>>> >>> >>> > >>>>> -- >>> >>> > >>>>> You received this message because you are subscribed to the >>> Google Groups "sympy" group. >>> >>> > >>>>> To unsubscribe from this group and stop receiving emails >>> from it, send an email to [email protected]. >>> >>> > >>>>> To post to this group, send email to [email protected]. >>> >>> > >>>>> Visit this group at https://groups.google.com/group/sympy. >>> >>> > >>>>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAKgW%3D6JGfKjgHP3EaoX%3DXW_SMfnbGOZgi9LLJoUT3Ty7%3Dutd%2BA%40mail.gmail.com >>> . >>> >>> > >>>>> For more options, visit https://groups.google.com/d/optout. >>> >>> > >>>> >>> >>> > >>>> -- >>> >>> > >>>> You received this message because you are subscribed to the >>> Google Groups "sympy" group. >>> >>> > >>>> To unsubscribe from this group and stop receiving emails from >>> it, send an email to [email protected]. >>> >>> > >>>> To post to this group, send email to [email protected]. >>> >>> > >>>> Visit this group at https://groups.google.com/group/sympy. >>> >>> > >>>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAP7f1AiMm_i%2BJBLBnv3_xzG_8Czag10DWvAUfiAhe-QUzUANiw%40mail.gmail.com >>> . >>> >>> > >>>> For more options, visit https://groups.google.com/d/optout. >>> >>> > > >>> >>> > > -- >>> >>> > > You received this message because you are subscribed to the >>> Google Groups "sympy" group. >>> >>> > > To unsubscribe from this group and stop receiving emails from >>> it, send an email to [email protected]. >>> >>> > > To post to this group, send email to [email protected]. >>> >>> > > Visit this group at https://groups.google.com/group/sympy. >>> >>> > > To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAKVsmS7P3w9nL%2BA9UJOnpZ4oBmc7UjGUdVjpmcFyog%2B5QwuP5g%40mail.gmail.com >>> . >>> >>> > > For more options, visit https://groups.google.com/d/optout. >>> >>> > >>> >>> > -- >>> >>> > You received this message because you are subscribed to the Google >>> Groups "sympy" group. >>> >>> > To unsubscribe from this group and stop receiving emails from it, >>> send an email to [email protected]. >>> >>> > To post to this group, send email to [email protected]. >>> >>> > Visit this group at https://groups.google.com/group/sympy. >>> >>> > To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAHVvXxRXE%2BF%2BWVk2pY%2Bsbzem6ZTG6QrDZXh24qPtYnjdojoDmA%40mail.gmail.com >>> . >>> >>> > For more options, visit https://groups.google.com/d/optout. >>> >>> >>> >>> -- >>> >>> You received this message because you are subscribed to the Google >>> Groups "sympy" group. >>> >>> To unsubscribe from this group and stop receiving emails from it, >>> send an email to [email protected]. >>> >>> To post to this group, send email to [email protected]. >>> >>> Visit this group at https://groups.google.com/group/sympy. >>> >>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAKgW%3D6LZLd0kEcLGurCvmAZihW2E4dEiXx_LXQc3nKhXpFA3gA%40mail.gmail.com >>> . >>> >>> For more options, visit https://groups.google.com/d/optout. >>> >> >>> >> -- >>> >> You received this message because you are subscribed to the Google >>> Groups "sympy" group. >>> >> To unsubscribe from this group and stop receiving emails from it, >>> send an email to [email protected]. >>> >> To post to this group, send email to [email protected]. >>> >> Visit this group at https://groups.google.com/group/sympy. >>> >> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAP7f1Aj2yffQDWJH47ox3UvQUSfj_VPKgef-2b1P0FVGZqi-Mg%40mail.gmail.com >>> . >>> >> For more options, visit https://groups.google.com/d/optout. >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups "sympy" group. >>> > To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> > To post to this group, send email to [email protected]. >>> > Visit this group at https://groups.google.com/group/sympy. >>> > To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAKVsmS6W9PQQi4coLzj%2Bw6AQBJewPxZUHYa4TP5%2B8snpSKZPhg%40mail.gmail.com >>> . >>> > For more options, visit https://groups.google.com/d/optout. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "sympy" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> To post to this group, send email to [email protected]. >>> Visit this group at https://groups.google.com/group/sympy. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/sympy/CAKgW%3D6JnJLZVLiw%3DmtiPaVVRfYZCj%2BGTjtdbnapDmBfE4A9dcA%40mail.gmail.com >>> . >>> For more options, visit https://groups.google.com/d/optout. >>> >> -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKVsmS7a1eJWkQTh3qVV29-xOw5WrMYYJrhygKPDqF2Zh1DQjg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
