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.
