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/CAKVsmS7TmBFOmFxuUr_wdDtYuUacgMOD%3Dd4gCvgvWMZ83SyDXQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
