[sage-devel] Re: Blog post on parallel multivariate arithmetic : comparing all the things!
I found a way to get better timings by caching the index of the insertion chain of the previous monomial. But now multi-threaded execution is slower than 1 thread execution most certainly because of locks during insertion... I will probably force 1 thread sparse multiplication. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Blog post on parallel multivariate arithmetic : comparing all the things!
Roman Pearce said he would put up some code to explain this. (The
conditions Daniel uses are quite complex in comparison.) I therefore think
that it's ok to quote the following from correspondence with Roman (since I
put up my blog):
[The idea is based on ] "Ellis Horowitz, A Sorting Algorithm for Polynomial
Multiplication
Journal of the ACM, Volume 22 Issue 4, Oct. 1975, Pages 450-462
http://dl.acm.org/citation.cfm?doid=321906.321908
Before inserting f_i * g_j into the heap, check if there exists
f_k * g_j in the heap where k < i, and if so, do not insert the
product. We simply check if f_{i-1} * g_j is the next unmerged
product for f_{i-1} whether it is in the heap or not. Then you
have to put the dropped products back in the heap later. After
extracting f_i * g_j from the heap, check if f_{i+1} has a term
in the heap, and if not, insert f_{i+1} * g_j."
This is what I had remembered from what Roman explained at ISSAC. But
Daniel wasn't able to figure out something along those lines that improved
timings. Clearly it does though, since Roman uses it to great effect. And
thanks very much to Roman for suggesting this very important improvement!
I haven't yet looked in detail at Daniel's conditions. It will be
interesting to compare. You can see then in fmpz_mpoly/mul_heap_threaded.c
in the Flint repository [1]. To my eye, they don't look that complicated. I
think it is the lines 187 and following. Perhaps they will end up being
equivalent.
[1] https://github.com/wbhart/flint2/blob/trunk/fmpz_mpoly/mul_heap_threaded.c
On Tuesday, 26 September 2017 07:52:27 UTC+2, parisse wrote:
>
>
>
> Le lundi 25 septembre 2017 18:56:26 UTC+2, Bill Hart a écrit :
>>
>> Do you use anything special for memory management? Mickael Gastineau
>> recommended jemalloc, which we haven't tried yet. I assume you expected to
>> see better times for the threaded benchmarks with giac?
>>
>
> I'm not using anything specific for memory management. Thread-efficient
> memory management would certainly help improve performances, because more
> than half of the time is done in conversions inside giac, and conversions
> to mpz types are not parallelized because it would be slower to wait for
> locks. I was asking about the compiler because I looked at my code and saw
> that some optimizations are disabled for clang.
> Can you give some precisions about what you call delayed insertion in the
> heap? I can delay insertion of the initial product monomials f[i]*g[0] but
> that does not improve much the timings, at least with 1 thread.
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Blog post on parallel multivariate arithmetic : comparing all the things!
We used to do this, and Daniel noticed that it wasn't really threadsafe. I don't know the current status of this. At some point he said it didn't make any difference after he got the delayed insertion working. I didn't check carefully, but maybe he stores it in the final heap location now. But I'm not sure. I'll ask him when I get a chance. [2] [2] https://github.com/wbhart/flint2/blob/trunk/mpoly.h (lines 582 ff.) On Tuesday, 26 September 2017 10:12:23 UTC+2, parisse wrote: > > I found a way to get better timings by caching the index of the insertion > chain of the previous monomial. But now multi-threaded execution is slower > than 1 thread execution most certainly because of locks during insertion... > I will probably force 1 thread sparse multiplication. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: changelogs missing in http://www.sagemath.org/changelogs/index.html
Yes it's a pity. A big project like Sage should have a changelog at each new release. My understanding is that 1/ the automated script generating the raw changelog from the git logs was lost somehow (during some migration of server?) 2/ it requires some volunteer to maintain such a file Probably someone else can provide a better answer, especially regarding 1/. Best wishes, Eric. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Is trac down?
I can't seem to reach trac.sagemath.org , the page seems to take forever to load. Do other people have this problem as wel? Thanks, Maarten -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Is trac down?
On 2017-09-26 12:10, Maarten Derickx wrote: I can't seem to reach trac.sagemath.org , the page seems to take forever to load. Do other people have this problem as wel? Me too. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Is trac down?
Seems to be back up again. On Tuesday, 26 September 2017 12:13:38 UTC+2, Jeroen Demeyer wrote: > > On 2017-09-26 12:10, Maarten Derickx wrote: > > I can't seem to reach trac.sagemath.org , the page seems to take > forever > > to load. Do other people have this problem as wel? > > Me too. > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Blog post on parallel multivariate arithmetic : comparing all the things!
Le mardi 26 septembre 2017 10:43:10 UTC+2, Bill Hart a écrit : > > We used to do this, and Daniel noticed that it wasn't really threadsafe. > It would be in my implementation, but inserting requires sometimes memory allocation and it seems to slow down too much. Anyway, as explained earlier, conversions from packed exponent-int128 coefficients to polynomials with unpacked exponents and generic coefficients takes too much time in the sparse case, I think is not worth rewriting a thread-efficient sparse multivariate polynomial multiplication algorithms in giac. For example in the n=12 case, the effective multiplication takes 1.3s on my Mac and conversion takes twice more, in the n=16 case, effective multiplication takes 11.5s and conversion 19s (run export GIAC_DEBUG=6 in a shell or debug_infolevel:=6; in a script to see some details while running giac). It's probably the same problem for Maple with their "native" vs sdmp polynomial representation. This is something that the reader of your benchmarks should keep in mind. Thinks are completely different for dense polynomials, because the conversion is dominated by the multiplication time (but fortunately thread-efficient multiplication code is available for giac for these kind of polynomials). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: changelogs missing in http://www.sagemath.org/changelogs/index.html
On Tue, Sep 26, 2017 at 2:15 AM Eric Gourgoulhon wrote: > Yes it's a pity. A big project like Sage should have a changelog at each > new release. My understanding is that > > 1/ the automated script generating the raw changelog from the git logs was > lost somehow (during some migration of server?) > No files were lost. It's just that every time I make the files available to Jereon, I'm too busy and he tends to ignore me, and every time he asks for them from me, I tend to be too busy and ignore him... > 2/ it requires some volunteer to maintain such a file > > Probably someone else can provide a better answer, especially regarding > 1/. > > Best wishes, > > Eric. > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. > -- -- William Stein -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] let's make FriCAS optional
Dear all, I would like to propose to make the package FriCAS optional. FriCAS provides some functionality which is otherwise either mostly missing (e.g., guessing formulas, lazy powerseries), or not as complete as might be desirable (e.g., symbolic integration, solving differential equations). The FriCAS interface was completely rewritten after FriCAS was demoted to experimental in #18563 and is now quite mature, containing lots of doctests. I opened trac ticket #23847 for the process. Martin -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Blog post on parallel multivariate arithmetic : comparing all the things!
Now that you have given the precise conditions, I will check if they are
equivalent to whats in the smp code. They do look like what I was aiming
for.
As for caching the last entry, that code is still in there in a thread-safe
way. This optimisation had no effect on the timings when the exponent
vectors fit into one word, but it was +5% on multi-word exponents, so I
left it in.
On Tuesday, September 26, 2017 at 10:37:33 AM UTC+2, Bill Hart wrote:
>
> Roman Pearce said he would put up some code to explain this. (The
> conditions Daniel uses are quite complex in comparison.) I therefore think
> that it's ok to quote the following from correspondence with Roman (since I
> put up my blog):
>
> [The idea is based on ] "Ellis Horowitz, A Sorting Algorithm for
> Polynomial Multiplication
> Journal of the ACM, Volume 22 Issue 4, Oct. 1975, Pages 450-462
> http://dl.acm.org/citation.cfm?doid=321906.321908
>
> Before inserting f_i * g_j into the heap, check if there exists
> f_k * g_j in the heap where k < i, and if so, do not insert the
> product. We simply check if f_{i-1} * g_j is the next unmerged
> product for f_{i-1} whether it is in the heap or not. Then you
> have to put the dropped products back in the heap later. After
> extracting f_i * g_j from the heap, check if f_{i+1} has a term
> in the heap, and if not, insert f_{i+1} * g_j."
>
> This is what I had remembered from what Roman explained at ISSAC. But
> Daniel wasn't able to figure out something along those lines that improved
> timings. Clearly it does though, since Roman uses it to great effect. And
> thanks very much to Roman for suggesting this very important improvement!
>
> I haven't yet looked in detail at Daniel's conditions. It will be
> interesting to compare. You can see then in fmpz_mpoly/mul_heap_threaded.c
> in the Flint repository [1]. To my eye, they don't look that complicated. I
> think it is the lines 187 and following. Perhaps they will end up being
> equivalent.
>
> [1]
> https://github.com/wbhart/flint2/blob/trunk/fmpz_mpoly/mul_heap_threaded.c
>
> On Tuesday, 26 September 2017 07:52:27 UTC+2, parisse wrote:
>>
>>
>>
>> Le lundi 25 septembre 2017 18:56:26 UTC+2, Bill Hart a écrit :
>>>
>>> Do you use anything special for memory management? Mickael Gastineau
>>> recommended jemalloc, which we haven't tried yet. I assume you expected to
>>> see better times for the threaded benchmarks with giac?
>>>
>>
>> I'm not using anything specific for memory management. Thread-efficient
>> memory management would certainly help improve performances, because more
>> than half of the time is done in conversions inside giac, and conversions
>> to mpz types are not parallelized because it would be slower to wait for
>> locks. I was asking about the compiler because I looked at my code and saw
>> that some optimizations are disabled for clang.
>> Can you give some precisions about what you call delayed insertion in the
>> heap? I can delay insertion of the initial product monomials f[i]*g[0] but
>> that does not improve much the timings, at least with 1 thread.
>>
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Blog post on parallel multivariate arithmetic : comparing all the things!
The dense multicore examples will take months to run in Flint, since we haven't written the code yet! :-) But your explanation about the cost of conversion in the sparse case certainly more than accounts for overall difference in performance. Giac also has a symbolic front end, too, which Flint and Nemo do not. That is certainly important for people to realise. On Tuesday, 26 September 2017 13:13:06 UTC+2, parisse wrote: > > > > Le mardi 26 septembre 2017 10:43:10 UTC+2, Bill Hart a écrit : >> >> We used to do this, and Daniel noticed that it wasn't really threadsafe. >> > > It would be in my implementation, but inserting requires sometimes memory > allocation and it seems to slow down too much. Anyway, as explained > earlier, conversions from packed exponent-int128 coefficients to > polynomials with unpacked exponents and generic coefficients takes too much > time in the sparse case, I think is not worth rewriting a thread-efficient > sparse multivariate polynomial multiplication algorithms in giac. For > example in the n=12 case, the effective multiplication takes 1.3s on my Mac > and conversion takes twice more, in the n=16 case, effective multiplication > takes 11.5s and conversion 19s (run export GIAC_DEBUG=6 in a shell or > debug_infolevel:=6; in a script to see some details while running giac). > It's probably the same problem for Maple with their "native" vs sdmp > polynomial representation. This is something that the reader of your > benchmarks should keep in mind. > Thinks are completely different for dense polynomials, because the > conversion is dominated by the multiplication time (but fortunately > thread-efficient multiplication code is available for giac for these kind > of polynomials). > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: let's make FriCAS optional
Tue 2017-09-26 14:06:36 UTC, Martin R: > I would like to propose to make the package FriCAS optional. +1 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] let's make FriCAS optional
On Tue, Sep 26, 2017 at 10:06 AM, 'Martin R' via sage-devel wrote: > Dear all, > > I would like to propose to make the package FriCAS optional. FriCAS > provides some functionality which is otherwise either mostly missing (e.g., > guessing formulas, lazy powerseries), or not as complete as might be > desirable (e.g., symbolic integration, solving differential equations). +1 If it helps to improve Sage's DE solving capability, I'm all for it. > > The FriCAS interface was completely rewritten after FriCAS was demoted to > experimental in #18563 and is now quite mature, containing lots of doctests. > > I opened trac ticket #23847 for the process. > > Martin > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Is trac down?
Tue2017-09-26 10:29:17 UTC, Maarten Derickx: > Seems to be back up again. Not sure if it's related but when I click on the branch at https://trac.sagemath.org/ticket/21944 I get the following error: Internal Server Error The server encountered an internal error or misconfiguration and was unable to complete your request. Please contact the server administrator at [no address given] to inform them of the time this error occurred, and the actions you performed just before this error. More information about this error may be available in the server error log. Apache/2.4.7 (Ubuntu) Server at git.sagemath.org Port 443 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Is trac down?
On Tuesday, September 26, 2017 at 1:56:39 PM UTC-7, mforets wrote: > > > > El martes, 26 de septiembre de 2017, 22:38:23 (UTC+2), Samuel Lelievre > escribió: >> >> Tue2017-09-26 10:29:17 UTC, Maarten Derickx: >> > Seems to be back up again. >> >> Not sure if it's related but when I click on the branch at >> https://trac.sagemath.org/ticket/21944 >> I get the following error: >> >> Internal Server Error >> >> The server encountered an internal error or misconfiguration >> and was unable to complete your request. >> >> Please contact the server administrator at [no address given] >> to inform them of the time this error occurred, and the actions >> you performed just before this error. >> >> More information about this error may be available in the server error >> log. >> >> Apache/2.4.7 (Ubuntu) Server at git.sagemath.org Port 443 >> > > same error here. i pulled this branch some days ago, and it was working. > > > That seems to be specific to that ticket: branches on other tickets seem to be working. John -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: let's make FriCAS optional
+1 -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: let's make FriCAS optional
+1, with some wishes : - doctests -documentation -- Emmanuel Charpentier Le mardi 26 septembre 2017 16:06:36 UTC+2, Martin R a écrit : > > Dear all, > > I would like to propose to make the package FriCAS optional. FriCAS > provides some functionality which is otherwise either mostly missing (e.g., > guessing formulas, lazy powerseries), or not as complete as might be > desirable (e.g., symbolic integration, solving differential equations). > > The FriCAS interface was completely rewritten after FriCAS was demoted to > experimental in #18563 and is now quite mature, containing lots of doctests. > > I opened trac ticket #23847 for the process. > > Martin > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
